A 64-bit pointer can address over 18 exabytes (18 billion gigabytes) of memory, which far exceeds the needs of even the most top-end supercomputers. For this reason, most modern desktop CPUs only use 48 bits for virtual addresses, leaving the upper 16 bits unused.
The bottom bits are typically underutilized, too. Most malloc implementations align allocations to 16-byte boundaries, so the bottom four bits are always set to zero. These bottom four bits can be repurposed to store extra data, as long as those bits are cleared back to zero when dereferencing the pointer.
Taken together, a 16-byte aligned pointer on a CPU with 48 bits of virtual address space has a total of 20 bits available for packing extra data. This concept may sound abstract — after all, who cares about some measly 20 bits? — but tagging pointers with extra data is a very common technique, so much so that x64 and ARM have included features to support it at the ISA-level.
Any data structure that uses a significant number of pointers can benefit immensely from these techniques. Some examples include:
Dynamic type information in high-level, untyped languages Chrome’s V8 engine uses pointer tagging to distinguish whether a value represents a raw integer or a reference to a heap-allocated object. Objective-C uses a similar approach: if an object is small enough to fit within a pointer’s worth of memory, the runtime stores its data directly in the pointer (along with a tag) instead of allocating it on the heap. Tree-like data structures where each node can be interpreted multiple ways In the Linux kernel’s implementation of a red–black tree, one bit of each node’s parent pointer is used to determine whether a node is red or black. Dynamic Polymorphism PBRT uses tagged pointers in place of a per-object v-table, reducing the overhead of dynamic dispatch.
The benefits go beyond just space savings alone. Rather than traversing a pointer every single time, packed data in a pointer is already likely to be local in the CPU cache. It can be used to very quickly determine if a pointer should even be traversed in the first place.
An implementation in C++
Pointer Bit Manipulation In Practice
To make the details of tagged pointers more concrete, we can look at an implementation in C++. For this article, we’ll assume a 48-bit canonical address space (though keep in mind that this detail is platform-dependent), giving us 16 high bits to work with.
0x0000 0048 1030 8C90 0200 └───┬───┘ └─────┬──────┘ Data Bits 48-bit Address
... continue reading