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 ;)
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.
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.
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
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.
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?
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).
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.
I'll grant the Alpha point, which seems like a clear and unfortunate bug.
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.
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).
> 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).
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"
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.
>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.
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.
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.
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.
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.
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.
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.
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.
> 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.
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".
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).
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.
Also Analog Sharc DSPs (which, I think, still are being sold with this architecture, and still used, even though I've used them only 10 years ago) alias their memory four times, depending if you want to access it as 16bit, 32bit, 48 or 64bit data.
Probably so the compiler doesn't just optimize out the statements, seeing as they don't seem to have a visible effect on the program execution because they're never read again.
because writing to one location causes the data to change in another (a system register) you don't want the compiler to assume that data in an IO register can be cached in a CPU register
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.
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.
The zero-ness of NULL is a good example of the phenomenon I'm talking about. How much time have people wasted over the years tweaking and worsening code afer somebody pointed out that some platform at one point might not have used the all-zero bit pattern for NULL? In how many cases did the program that was changed get anywhere close to such a strange, special-purpose, and likely obsolete computer? I'm guessing the answer is "vanishingly close to zero." Being exactly ANSI C correct (as opposed to relying on POSIX's stronger guarantees) comes with an engineering cost, and there's no sense paying that cost unnecessarily.
It's one thing to do something because you found that it works. It's another if you know what the rules are, and why breaking them will work in this case, and if you (or someone else) needs to port the code, you know the potential problem spots that need attention.
I agree, but I would not consider hashing pointers a common tool or technique.
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.
No, the bad practice is on the side of standardisation commitees and all users suffer from it. Recently, I got burned by the removal of the symbol CLK_TCK from a header (https://github.com/Orc/pdksh/issues/1). If you have access to a RedHat 5, you can observe it with the command /bin/pdksh -c "time sleep 5". I think we should work to replace the C language because all its weaknesses have been worsen by standardisation commitees.
This change breaks working applications, is difficult to notice and has no clear benefits. The same occurs when compilers use standard's undefined behaviour for micro optimizations.
This breaks the HN guidelines, which ask: "Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize."
Ouch. Thanks for the reminder; I've edited the response into something I hope better contributes to the discussion.
Though, I'm not quite sure I was using a straw man there, since my argument really hasn't changed. I think the issue was just that I was being overly snarky.
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.
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.
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 ;)