As someone that uses pointer tagging, I must point out that this article is insufficiently defensive.
I've done my own exploration of what I can get away with across 64-bit x86 and ARM in this regard. It has been a while but the maximum number of bits that are reliably taggable across all environments and use cases that I have been able to determine is six. Can you get away with more? Probably yes, but there are identifiable environments where it will explode if you do so. That may not apply to your use case.
In the 70's when memory was always small and expensive, I had to keep things as packed and tight as possible. But now memory is so huge and cheap that it's been a long time since I had to worry about things like packing bits, which is incredibly bug-prone anyway.
What's old is new again. The original 68000 processor only had a 24-bit physical address bus, so the MacOS used the upper 8 bits for tag information, and didn't even need to clear it when accessing. Once they started using CPUs and more RAM that needed these upper bits, they had to make "32-bit clean" versions of programs.
I wonder whether you could use the MMU to ignore these upper bits, by mapping each combination of bits to the same address as with them clear.
Brings back memories. I cut my teeth in C++ working on a system that used pointer tagging and transactional memory. Good times. That mind mending experience perhaps made my career.
I find it rather concerning that an article of this nature has not a single mention of the words "undefined behavior", even though that is something one has to be very much aware of when doing such shenanigans.
Sadly on 32-bit platforms there is not so many unused bits in pointers - typically only 3 least significant bits. But for some cases even 3 bits may be useful.
One cool technique is to use the packed bits to check if a raw pointer is still valid.
Say you have a pool of objects, when you allocate one you give out a pointer, but in the packed bits you add a 'generation' counter. Every time you free that object from the pool you increment the counter. When you dereference a pointer you can check the generation in the packed pointer and the one in the pool. If they don't match you're using a pointer to an invalid object.
It's a cool technique, but only useful in very limited scenarios. In particular, it is unsuitable when the number of reallocations is unbounded, because the generation counter can easily overflow.
Even if you can squeeze in 32 tag bits (you would need to leverage the virtual memory system in some platform-specific way), counting to 4-billion-and-change takes no time on modern CPUs, so you would realistically overflow the tag in milliseconds.
But if your system is aware of virtual memory, you can still do interesting things, like remapping a whole arena with a different "tag" and use the information in GC write barriers.
I wonder if the language could support a tagged pointer type, where you ask the compiler for n extra bits along with the pointer. If the pointer's internal structure has space for those bits, it uses them, otherwise the compiler allocates space for the pointer and the tag as a larger structure.
This uses the Most Significant Bits to pack some bits into pointers..
Another technique is to use the Least Significant Bits: indeed since pointers are 64 bit aligned, the lowest 3 bits are always zero, therefore it is possible to pack 3 bits of information there.
And there's a third technique in C++, which is to use placement new to morph an object in-place. This can be use to toggle between 2 classes with a boolean method, where one has this method return true and the other class has this method return false. This creates per-object state that really uses bits in the vptr to store this boolean state. Obviously this can be used with a whole set of classes to stores more bits. I have used this successfully to store values of refcount (each AddRef/Release using placement new to morph from RefCounted1/RefCounted2/../RefCountedN classes) to implement reference counting without a counter.
11 comments
[ 3.7 ms ] story [ 33.7 ms ] threadI've done my own exploration of what I can get away with across 64-bit x86 and ARM in this regard. It has been a while but the maximum number of bits that are reliably taggable across all environments and use cases that I have been able to determine is six. Can you get away with more? Probably yes, but there are identifiable environments where it will explode if you do so. That may not apply to your use case.
Reliable pointer tagging is not trivial.
I wonder whether you could use the MMU to ignore these upper bits, by mapping each combination of bits to the same address as with them clear.
Enabled on most iphones even!
Say you have a pool of objects, when you allocate one you give out a pointer, but in the packed bits you add a 'generation' counter. Every time you free that object from the pool you increment the counter. When you dereference a pointer you can check the generation in the packed pointer and the one in the pool. If they don't match you're using a pointer to an invalid object.
Even if you can squeeze in 32 tag bits (you would need to leverage the virtual memory system in some platform-specific way), counting to 4-billion-and-change takes no time on modern CPUs, so you would realistically overflow the tag in milliseconds.
But if your system is aware of virtual memory, you can still do interesting things, like remapping a whole arena with a different "tag" and use the information in GC write barriers.
Another technique is to use the Least Significant Bits: indeed since pointers are 64 bit aligned, the lowest 3 bits are always zero, therefore it is possible to pack 3 bits of information there.
And there's a third technique in C++, which is to use placement new to morph an object in-place. This can be use to toggle between 2 classes with a boolean method, where one has this method return true and the other class has this method return false. This creates per-object state that really uses bits in the vptr to store this boolean state. Obviously this can be used with a whole set of classes to stores more bits. I have used this successfully to store values of refcount (each AddRef/Release using placement new to morph from RefCounted1/RefCounted2/../RefCountedN classes) to implement reference counting without a counter.