8 ms·

You Can't Always Hash Pointers in C (2016)

deleted 8y ago
[deleted]
RcouF1uZ4gsC 8y ago
One thing interesting to note is that C++ has a specialization for template<class T> struct hash<T> which is required to have the correct semantics. Given that the in practice the underlying machine models of C and C++ are very similar, and that the most widely used C compilers (gcc, clang, msvc) are also C++ compilers, in practice hashing C pointers is likely not an issue. However, if you want to hash pointers in a way that is blessed by the standard, you can probably do this my_hash.cc #include <functional> extern "C"{ size_t hash(char* c){ std::hash<char*> hasher; return hasher(c); } } my_hash.h size_t hash(char* c); EDIT: Added code if you wanted to be pedantic about it. Then you just link your C program to my_hash.o and include my_hash.h
- tlb 8y ago
  C++11 only requires that "A Hash is a function object for which the output depends only on the input and has a very low probability of yielding the same output given different input values" and that "the probability of h(a)==h(b) for a!=b should approach 1.0/std::numeric_limits<std::size_t>::max()." This allows a pointer to be larger than size_t, which might be the case on some system with tagged pointers.
  - RcouF1uZ4gsC 8y ago
    This is the case with hashing algorithms in general. The important part is "For two parameters k1 and k2 that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2)." This is what allows hash maps to work.
  - saagarjha 8y ago
    Wait, so std::hash::operator() doesn't have to return a size_t, or are you just saying that pointers can have values "greater" than size_t and need to be "trimmed" down to size?
    - gumby 8y ago
      std::hash::operator() is indeed required by the standard to return a size_t, but the standard puts few constraints on a size_t. It's certainly reasonable for an architecture with boxed numbers to make a size_t too small to hold a bona fide pointer. BTW the boxed environment could be a hardware platform (e.g. some of the Risc-V variants these days) or a software architecture -- imagine a C++ variant that generated code to run inside such an environment even if the hardware it's hosted on has a flat address space).
    - asveikau 8y ago
      There are lots of places where size_t can't fit a full address. That is kind of the point of adding intptr_t (if it were covered by another typedef, why add it?) By the way, intptr_t is relatively recent (C99).
      - saagarjha 8y ago
        > That is kind of the point of adding intptr_t (if it were covered by another typedef, why add it?) I thought it was a stylistic choice: size_t for lengths and sizes, and intptr_t for, well, an integer holding a pointer value.
        int_19h 8y ago
        size_t only has to be large enough to accommodate the size of the largest object possible in a given implementation. It has no relation to pointers at all. Similarly, ptrdiff_t only has to be large enough to accommodate the difference between two pointers where such difference is legal ("when two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object"). Hence the need for intptr_t and uintptr_t, and why they're optional unlike size_t and ptrdiff_t.
- taejo 8y ago
  I think you meant template<class T> struct hash< T* >
delhanty 8y ago
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.
Animats 8y ago
With Microsoft going to "fat pointers" in their systems, some pointer conversions are not going to work.
- fulafel 8y ago
  I assume this is something else than the "far" pointers from the 16-bit days - what is the new application of fat C pointers at MS?
  - cbHXBY1D 8y ago
    I think Animats is referring to checkedc [1] which I can assure you Microsoft/MSVC is not moving towards. [1] https://www.microsoft.com/en-us/research/project/checked-c/ https://www.microsoft.com/en-us/research/project/checked-c/
anfilt 8y ago
Why would one need to hash pointers? Seems like a bad idea and data strutures made of pointers like trees are pretty well behaved.
- xamuel 8y ago
  Say you have an array of pointers and you want to take its distinct members. For each pointer, you could look up its hash in a table. If it's not there, you can be sure the pointer hasn't been seen before: append it to your result and put its hash in the table. If the hash is there, you learn nothing since it could be a collision, and you'll need to do something else (like iterate through your whole result so far). But if the original input has few distinct members, this shouldn't happen often.
  - anfilt 8y ago
    Yea a list of pointers can be handy. However, if the code managing this list is receiving duplicate pointers this sounds like an other problem. If it's newly allocated memory it should probably be submitted to this list on creation. If we have some sort sub-allocater that sounds like a problem with sub-allotments. I think is probably more common ways to avoid the need for hashing, and not needing to do a linear search of your list.
- rurban 8y ago
  cloning trees, garbage collection, serialization on structures with references. graphs.
quotemstr 8y ago
I don't like this genre of programming blog post. These things always amount to premature optimization for portability. They point out that some technique that's been used by millions of programs for decades might not work on every single architecture that's technically compatible with the C standard. So what? The techniques work, and because so many programs use these techniques, they'll keep working. In practice, almost nobody targets esoteric environments. Avoiding useful and well-known tools just for the sake of an environment that will never see your program is just a needless self-imposed tax that's going to suck time from other aspects of development. In my programs, I'll keep hashing uintprt_t values.
- spc476 8y ago
  While an architecture where two distinct pointers could point to the same location is esoteric today (minus `mmap()` tricks), go back 30 years and it was not only esoteric, but downright the most popular system in existence! [1]. Who's to say something just as esoteric becomes the mainstream? (although I hope not---it was horrible). [1] MS-DOS with its FAR pointers.
  - anfilt 8y ago
    Harvard architectures might be an other example that's not really strange. You can have two different pointers with the same value. However, why are we trying to compare data and instruction pointers? They are pointers for different types of data. One being instructions and the other data.
    - spc476 8y ago
      True. But C is pretty restrictive in what you can assume. POSIX is more lax (for the programmer, not for the compiler) because it mandates certain behavior---like an all-0 bit pattern for NULL pointers, and the ability to case `void *` to a function pointer (and back again). That "`NULL` need not be physical 0s" [1] is a real pain in ANSI C because `memset(astruct,0,sizeof(astruct))` won't NULL out pointers---you have to explicitly assign NULL to each pointer. It's one of the reasons I tend to stick to POSIX if I can. [1] In source, a 0 in a pointer context is a NULL pointer, but the architecture could mandate "all 1s" as a NULL pointer.
dang 8y ago
Discussed at the time: https://news.ycombinator.com/item?id=11805030 https://news.ycombinator.com/item?id=11805030
scraft 8y ago
Slightly related (but only slightly), on the PS2 (games console, from Sony) you could access main memory with three different pointers, cacheable, uncached accelerated and uncached (which was the same base address with different high bits set accordingly). Each mode had reasons to be used (for example, when you read/write to memory which is cacheable and then fire off a DMA transfer, the data being transferred may, and often won't, match, what has been set in the program, until a cache flush has been requested). As you can imagine, this regularly resulted in hard to track down bugs. Anyway, the bottom line of this is: I have seen various pieces of code on platforms which when comparing a memory pointer you need to mask out several bits (unless of course you actually want to differentiate between the different access methods of the same piece of memory). It isn't quite what this article is talking about, but I thought it was a related piece of interesting trivia to those that don't already know ;)
- karmakaze 8y ago
  Great example to add to the discussion. The post does mention that pointers may have some meta bits which I fully accept but without concrete examples wouldn't give much consideration for. Reminds me of the recent underspec that was closed with signed/unsigned some operation or other. Better for the spec but can't imagine practically mattered. If some unbelievable situation occurs on some unique platform/compiler remember this post. In the meantime do as we have been with using pointer values. Back before the System7 32bit clean code people put all sorts of stuff in pointers because we could. We know the costs but also remember that it had value too.
- mrslave 8y ago
  Smells like a MIPS processor? I really enjoyed this stuff at university. I work with very high level tools these days, informing business decision makers, and I don't regret the move up the value stack. In fact I have found that being a competent developer at low levels (embedded systems, operating systems) has helped solve some incredibly subtle issues with high-level tools in my career.
- derefr 8y ago
  > which was the same base address with different high bits set accordingly Reminds me of memory mirroring on the NES (https://wiki.nesdev.com/w/index.php/Mirroring#Memory_Mirroring https://wiki.nesdev.com/w/index.php/Mirroring#Memory_Mirrori...). Except that, in this case, the mirrored memory has different access semantics :)

deleted 8y ago

[deleted]

One thing interesting to note is that C++ has a specialization for template<class T> struct hash<T> which is required to have the correct semantics. Given that the in practice the underlying machine models of C and C++ are very similar, and that the most widely used C compilers (gcc, clang, msvc) are also C++ compilers, in practice hashing C pointers is likely not an issue. However, if you want to hash pointers in a way that is blessed by the standard, you can probably do this my_hash.cc #include <functional> extern "C"{ size_t hash(char* c){ std::hash<char*> hasher; return hasher(c); } } my_hash.h size_t hash(char* c); EDIT: Added code if you wanted to be pedantic about it. Then you just link your C program to my_hash.o and include my_hash.h

tlb 8y ago
C++11 only requires that "A Hash is a function object for which the output depends only on the input and has a very low probability of yielding the same output given different input values" and that "the probability of h(a)==h(b) for a!=b should approach 1.0/std::numeric_limits<std::size_t>::max()." This allows a pointer to be larger than size_t, which might be the case on some system with tagged pointers.
- RcouF1uZ4gsC 8y ago
  This is the case with hashing algorithms in general. The important part is "For two parameters k1 and k2 that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2)." This is what allows hash maps to work.
- saagarjha 8y ago
  Wait, so std::hash::operator() doesn't have to return a size_t, or are you just saying that pointers can have values "greater" than size_t and need to be "trimmed" down to size?
  - gumby 8y ago
    std::hash::operator() is indeed required by the standard to return a size_t, but the standard puts few constraints on a size_t. It's certainly reasonable for an architecture with boxed numbers to make a size_t too small to hold a bona fide pointer. BTW the boxed environment could be a hardware platform (e.g. some of the Risc-V variants these days) or a software architecture -- imagine a C++ variant that generated code to run inside such an environment even if the hardware it's hosted on has a flat address space).
  - asveikau 8y ago
    There are lots of places where size_t can't fit a full address. That is kind of the point of adding intptr_t (if it were covered by another typedef, why add it?) By the way, intptr_t is relatively recent (C99).
    - saagarjha 8y ago
      > That is kind of the point of adding intptr_t (if it were covered by another typedef, why add it?) I thought it was a stylistic choice: size_t for lengths and sizes, and intptr_t for, well, an integer holding a pointer value.
      - int_19h 8y ago
        size_t only has to be large enough to accommodate the size of the largest object possible in a given implementation. It has no relation to pointers at all. Similarly, ptrdiff_t only has to be large enough to accommodate the difference between two pointers where such difference is legal ("when two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object"). Hence the need for intptr_t and uintptr_t, and why they're optional unlike size_t and ptrdiff_t.
taejo 8y ago
I think you meant template<class T> struct hash< T* >

delhanty 8y ago

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.

Animats 8y ago

With Microsoft going to "fat pointers" in their systems, some pointer conversions are not going to work.

fulafel 8y ago
I assume this is something else than the "far" pointers from the 16-bit days - what is the new application of fat C pointers at MS?
- cbHXBY1D 8y ago
  I think Animats is referring to checkedc [1] which I can assure you Microsoft/MSVC is not moving towards. [1] https://www.microsoft.com/en-us/research/project/checked-c/ https://www.microsoft.com/en-us/research/project/checked-c/

anfilt 8y ago

Why would one need to hash pointers? Seems like a bad idea and data strutures made of pointers like trees are pretty well behaved.

xamuel 8y ago
Say you have an array of pointers and you want to take its distinct members. For each pointer, you could look up its hash in a table. If it's not there, you can be sure the pointer hasn't been seen before: append it to your result and put its hash in the table. If the hash is there, you learn nothing since it could be a collision, and you'll need to do something else (like iterate through your whole result so far). But if the original input has few distinct members, this shouldn't happen often.
- anfilt 8y ago
  Yea a list of pointers can be handy. However, if the code managing this list is receiving duplicate pointers this sounds like an other problem. If it's newly allocated memory it should probably be submitted to this list on creation. If we have some sort sub-allocater that sounds like a problem with sub-allotments. I think is probably more common ways to avoid the need for hashing, and not needing to do a linear search of your list.
rurban 8y ago
cloning trees, garbage collection, serialization on structures with references. graphs.

quotemstr 8y ago

I don't like this genre of programming blog post. These things always amount to premature optimization for portability. They point out that some technique that's been used by millions of programs for decades might not work on every single architecture that's technically compatible with the C standard. So what? The techniques work, and because so many programs use these techniques, they'll keep working. In practice, almost nobody targets esoteric environments. Avoiding useful and well-known tools just for the sake of an environment that will never see your program is just a needless self-imposed tax that's going to suck time from other aspects of development. In my programs, I'll keep hashing uintprt_t values.

spc476 8y ago
While an architecture where two distinct pointers could point to the same location is esoteric today (minus `mmap()` tricks), go back 30 years and it was not only esoteric, but downright the most popular system in existence! [1]. Who's to say something just as esoteric becomes the mainstream? (although I hope not---it was horrible). [1] MS-DOS with its FAR pointers.
- anfilt 8y ago
  Harvard architectures might be an other example that's not really strange. You can have two different pointers with the same value. However, why are we trying to compare data and instruction pointers? They are pointers for different types of data. One being instructions and the other data.
  - spc476 8y ago
    True. But C is pretty restrictive in what you can assume. POSIX is more lax (for the programmer, not for the compiler) because it mandates certain behavior---like an all-0 bit pattern for NULL pointers, and the ability to case `void *` to a function pointer (and back again). That "`NULL` need not be physical 0s" [1] is a real pain in ANSI C because `memset(astruct,0,sizeof(astruct))` won't NULL out pointers---you have to explicitly assign NULL to each pointer. It's one of the reasons I tend to stick to POSIX if I can. [1] In source, a 0 in a pointer context is a NULL pointer, but the architecture could mandate "all 1s" as a NULL pointer.

dang 8y ago

Discussed at the time: https://news.ycombinator.com/item?id=11805030 https://news.ycombinator.com/item?id=11805030

scraft 8y ago

Slightly related (but only slightly), on the PS2 (games console, from Sony) you could access main memory with three different pointers, cacheable, uncached accelerated and uncached (which was the same base address with different high bits set accordingly). Each mode had reasons to be used (for example, when you read/write to memory which is cacheable and then fire off a DMA transfer, the data being transferred may, and often won't, match, what has been set in the program, until a cache flush has been requested). As you can imagine, this regularly resulted in hard to track down bugs. Anyway, the bottom line of this is: I have seen various pieces of code on platforms which when comparing a memory pointer you need to mask out several bits (unless of course you actually want to differentiate between the different access methods of the same piece of memory). It isn't quite what this article is talking about, but I thought it was a related piece of interesting trivia to those that don't already know ;)

karmakaze 8y ago
Great example to add to the discussion. The post does mention that pointers may have some meta bits which I fully accept but without concrete examples wouldn't give much consideration for. Reminds me of the recent underspec that was closed with signed/unsigned some operation or other. Better for the spec but can't imagine practically mattered. If some unbelievable situation occurs on some unique platform/compiler remember this post. In the meantime do as we have been with using pointer values. Back before the System7 32bit clean code people put all sorts of stuff in pointers because we could. We know the costs but also remember that it had value too.
mrslave 8y ago
Smells like a MIPS processor? I really enjoyed this stuff at university. I work with very high level tools these days, informing business decision makers, and I don't regret the move up the value stack. In fact I have found that being a competent developer at low levels (embedded systems, operating systems) has helped solve some incredibly subtle issues with high-level tools in my career.
derefr 8y ago
> which was the same base address with different high bits set accordingly Reminds me of memory mirroring on the NES (https://wiki.nesdev.com/w/index.php/Mirroring#Memory_Mirroring https://wiki.nesdev.com/w/index.php/Mirroring#Memory_Mirrori...). Except that, in this case, the mirrored memory has different access semantics :)