4 ms·

Clarification: I though this was well know, but apparently it isn't, so I'll explain it. `malloc` doesn't have to give you the same pointer the next time the p

Clarification: I though this was well know, but apparently it isn't, so I'll explain it. `malloc` doesn't have to give you the same pointer the next time the program is run - and sometimes it doesn't. In that case, the ordering of the hash table on iteration can change. Particularly, release build `malloc` and debug `malloc` are likely to differ, leading to bugs in production that don't reproduce when debugging.

quotemstr 8y ago
Who said you need or want run-to-run hash stability? One common technique for defeating hash collision attacks is maxing a secret random tweak, newly computed on each program run, into to hash function. (Python is one environment that uses this trick.) Under this scheme, hash values are unstable, but the world keeps working. Hash stability turns out not to be particularly important most of the time. Generally speaking, if your program depends on the stability of hash-table enumeration order, you're doing something wrong in the first place.
- delhanty 8y ago
  >if your program depends on the stability of hash-table enumeration order, you're doing something wrong in the first place The point is not all programs are correct. If you're trying to reproduce a bug that occurs in the release version, but goes away in the debug version (because hash-table enumeration order changes) that makes life more difficult.
wutbrodo 8y ago
> In that case, the ordering of the hash table on iteration can change. Order-dependent iteration of a hash table's items isn't exactly a central use case of the data structure and often isn't even guaranteed. I don't think that this example is really sufficient to suggest that hashing pointers is a bad idea (though it may be for other reasons).
- TrinaryWorksToo 8y ago
  In golang it is purposefully randomized on every execution to prevent you from relying on iteration order
  - delhanty 8y ago
    That's actually better than the situation in C. In C, debug `malloc` may very well behave the same run after run. Then you move into production, and release `malloc` behaves differently to debug `malloc`. Suddenly a latent bug that was there all along shows itself in release, but fails to reproduce in debug. With the randomized behavior you describe in golang, the bug probably will show in debug and be caught.
  - wutbrodo 8y ago
    Yea I wasn't sure enough to make a stronger claim, but I don't believe I've ever used ordered iteration of a hashtable. I feel like if I was tempted to do so, it would prompt me to rethink my design. Call it an "algorithm smell"

quotemstr 8y ago

Who said you need or want run-to-run hash stability? One common technique for defeating hash collision attacks is maxing a secret random tweak, newly computed on each program run, into to hash function. (Python is one environment that uses this trick.) Under this scheme, hash values are unstable, but the world keeps working. Hash stability turns out not to be particularly important most of the time. Generally speaking, if your program depends on the stability of hash-table enumeration order, you're doing something wrong in the first place.

delhanty 8y ago
>if your program depends on the stability of hash-table enumeration order, you're doing something wrong in the first place The point is not all programs are correct. If you're trying to reproduce a bug that occurs in the release version, but goes away in the debug version (because hash-table enumeration order changes) that makes life more difficult.

wutbrodo 8y ago

> In that case, the ordering of the hash table on iteration can change. Order-dependent iteration of a hash table's items isn't exactly a central use case of the data structure and often isn't even guaranteed. I don't think that this example is really sufficient to suggest that hashing pointers is a bad idea (though it may be for other reasons).

TrinaryWorksToo 8y ago
In golang it is purposefully randomized on every execution to prevent you from relying on iteration order
- delhanty 8y ago
  That's actually better than the situation in C. In C, debug `malloc` may very well behave the same run after run. Then you move into production, and release `malloc` behaves differently to debug `malloc`. Suddenly a latent bug that was there all along shows itself in release, but fails to reproduce in debug. With the randomized behavior you describe in golang, the bug probably will show in debug and be caught.
- wutbrodo 8y ago
  Yea I wasn't sure enough to make a stronger claim, but I don't believe I've ever used ordered iteration of a hashtable. I feel like if I was tempted to do so, it would prompt me to rethink my design. Call it an "algorithm smell"