4 ms·

Generally, hashing pointers in C or C++ is a bad idea anyway. Unless, you have a particular love for debugging non-reproducible behavior that is.

dingo_bat 8y ago
Agreed. Even in the author's use-case, just hashing the string itself would be much better.
- quotemstr 8y ago
  What? No. Hashing a string involves extra pointer chasing and looping over a variable-length data structure, and that's on top of the collision-chain resolution the hash table itself has to do. In performance-sensitive code (like a dynamic language interpreter), it's far better to intern your strings and look them up by ID (i.e., pointer value) directly.
saagarjha 8y ago
I don’t see anything wrong with using pointers as keys in a lookup table. There’s nothing non-reproducible about this.
- delhanty 8y ago
  >There’s nothing non-reproducible about this. No that's false. See my clarification above.
  - xamuel 8y ago
    There's nothing non-reproducible about it within a particular run. Of course it would be silly to write a pointer hash table to disk!
  - saagarjha 8y ago
    I really don't care what the actual value of the pointers are, since I'm not going to use them for anything other than key lookup. The thing that breaks in your case is hash table iteration, but if I'm not doing that I still don't see any non-reproducible behavior other than slight timing differences.
    - Zanni 8y ago
      If you read the article, there's an explicit mention of the possibility of tagged pointers for some implementations, where the low-order bits represent the address and the high-order bits are used for housekeeping and might change dynamically. Thus the pointer to the same object might naively cast to different integers at different times in program execution. That will lead to non-reproducible behavior.
      - wruza 8y ago
        Given the factual amount of times it will happen, even this small thread is not worth it except for few pedants. And on architectures where it will, and on compilers that dare to make it happen — it will break much more than just your clever code anyway. All these ancient standard details are there only for history. In reality, you cannot even change the direction of memcpy(3) without turning the world upside down.
      - rurban 8y ago
        sure, but in practice everybody knows the actually used bits of every pointers per platform. on amd64 e.g. it's the 2 lowest and 16 highest which need to be masked off for comparison. it's simply platform and vm dependent. I know very well where and how I'm able to compare ptrs in a hash table, and I'm doing it all the time. just complaining out loud is no solution.
- maljx 8y ago
  Compiler/runtime can create two pointers with different integer values that point to same memory address. The article explains a few reasons why that might happen. It's very uncommon, but it's valid in the standard.
delhanty 8y ago
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

dingo_bat 8y ago

Agreed. Even in the author's use-case, just hashing the string itself would be much better.

quotemstr 8y ago
What? No. Hashing a string involves extra pointer chasing and looping over a variable-length data structure, and that's on top of the collision-chain resolution the hash table itself has to do. In performance-sensitive code (like a dynamic language interpreter), it's far better to intern your strings and look them up by ID (i.e., pointer value) directly.

saagarjha 8y ago

I don’t see anything wrong with using pointers as keys in a lookup table. There’s nothing non-reproducible about this.

delhanty 8y ago
>There’s nothing non-reproducible about this. No that's false. See my clarification above.
- xamuel 8y ago
  There's nothing non-reproducible about it within a particular run. Of course it would be silly to write a pointer hash table to disk!
- saagarjha 8y ago
  I really don't care what the actual value of the pointers are, since I'm not going to use them for anything other than key lookup. The thing that breaks in your case is hash table iteration, but if I'm not doing that I still don't see any non-reproducible behavior other than slight timing differences.
  - Zanni 8y ago
    If you read the article, there's an explicit mention of the possibility of tagged pointers for some implementations, where the low-order bits represent the address and the high-order bits are used for housekeeping and might change dynamically. Thus the pointer to the same object might naively cast to different integers at different times in program execution. That will lead to non-reproducible behavior.
    - wruza 8y ago
      Given the factual amount of times it will happen, even this small thread is not worth it except for few pedants. And on architectures where it will, and on compilers that dare to make it happen — it will break much more than just your clever code anyway. All these ancient standard details are there only for history. In reality, you cannot even change the direction of memcpy(3) without turning the world upside down.
    - rurban 8y ago
      sure, but in practice everybody knows the actually used bits of every pointers per platform. on amd64 e.g. it's the 2 lowest and 16 highest which need to be masked off for comparison. it's simply platform and vm dependent. I know very well where and how I'm able to compare ptrs in a hash table, and I'm doing it all the time. just complaining out loud is no solution.
maljx 8y ago
Compiler/runtime can create two pointers with different integer values that point to same memory address. The article explains a few reasons why that might happen. It's very uncommon, but it's valid in the standard.

delhanty 8y ago

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