You Can't Always Hash Pointers in C (2016)
nullprogram.com
nullprogram.com
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 ;)
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.
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.
Reminds me of memory mirroring on the NES (https://wiki.nesdev.com/w/index.php/Mirroring#Memory_Mirrori...). Except that, in this case, the mirrored memory has different access semantics :)
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);
}
}
size_t hash(char* c);
Then you just link your C program to my_hash.o and include my_hash.h
This allows a pointer to be larger than size_t, which might be the case on some system with tagged pointers.
"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.
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).
I thought it was a stylistic choice: size_t for lengths and sizes, and intptr_t for, well, an integer holding a pointer value.
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.
I seem to recall some late 90s Unix where size_t was 32 bits and pointers were 64 bits. I think it was Tru64? Seems to be backed up here: http://www.cecalc.ula.ve/documentacion/tutoriales/COMPAQC/DO... In Compaq C, size_t is unsigned int .
On 16 bit x86 it certainly is most natural to have size_t be 16 bits but full addressable memory is 1mb.
Again, if there were no ambiguity here there would be no need to introduce a new typedef, but they did, in 1999.
But the DOS one is wrong. "Addressible" memory with segmentation may be 20 bits, but the maximum size of an object that can be referenced through any pointer is 65536 bytes. It was possible to compile in a "huge mode" where all pointers were expressed as base/offset, but in fact there the size_t was a compiler-generated 32 bit type.
Unless, you have a particular love for debugging non-reproducible behavior that is.
No that's false. See my clarification above.
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.
`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.
Generally speaking, 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.
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).
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.
[1] https://www.microsoft.com/en-us/research/project/checked-c/
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.
[1] MS-DOS with its FAR pointers.
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.
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc....
ARM Cortex M4 supports adressing individual bits (often registers of hardware peripherals) of memory locations as one additional memory location writing to, or reading from a single bit.
e.g., from the examples of said infocenter url:
*(uint32_t*)0x20000000 |= (1<<7)
*(uint32_t*)0x20000000 &= ~(1<<7)
*(uint32_t*)0x2200001C = 1;
*(uint32_t*)0x2200001C = 0;
I would say treating pointers as integers is a more common approach. Heck the STD library has some support for that as well. So any sane compiler for even a wacky environment is going to try to make the transparent.
The article lays out its motivation pretty explicitly, and it runs entirely contrary to your point:
> My purpose is not to discourage you from casting pointers to integers and using the result. The vast majority of the time this works fine and as you would expect. I just think it’s an interesting part of the language, and C/C++ programmers should be aware of potential the trade-offs.
"Details of C implementations are sometimes interesting to think about" is very different from the strawman of "never do this thing because it's not universally portable".
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.