Fat, Slim Pointers

64 bits address space lets us access tons more memory than 32 bits, but with a catch: the pointers themselves are … well, yes, 64 bits. 8 bytes. Which eventually pile up to make a whole lot of memory devoted to pointers if you use pointer-rich data structures. Can we do something about this?

Well, in ye goode olde dayes of 16 bits/32 bits computing, we had some compilers that could deal with near and far pointers; the near, 16-bit pointers being relative to one of the segments, possibly the stack segment, and the far, 32-bits pointers being absolute or relative to a segment. This, of course, made programming pointlessly complicated as each pointer was to be used in its correct context to point to the right thing.

In 64 bits computing, and in the current implementation of x86_64/AMD64 CPUs using the LP64 model (where longs and pointers are 64 bits but ints 32), we find ourselves using 64 bits pointers that are either absolute or relative to a segment. But they are always 64 bits.

That is, fat.

But (fortunately), not all bits are used. In the current max-level implementation, only 48 bits are used out of 64, leaving 16 bits of the pointer redundant. Maybe we can exploit this to save a bit of memory?

The virtual memory appears to be split into two large regions, the “upper” part, with addresses above 0x0000 8000 0000 0000 and the “lower” region with addresses 0x0000 7fff ffff ffff and under. The rule is that bit 47 is sign-extended to fill the last 16 bits, which are, therefore, redundant with bit 47. What about we used only 48 bits to store the pointers?

A naïve and direct implementation of such a pointer class would look something like:

template <typename T>
class _48bit_ptr
  uint32_t lo;
  uint16_t hi;


  operator T * () const 
     uint32_t lo,hi;
    } parts;
    T * ptr;
   } promoted;

   promoted.parts.hi=(int16_t)hi; // sign-extends!

   return promoted.ptr;

  _48bit_ptr(T * ptr)

   : lo(0),hi(0) // c++0x

The class demotes a 64 bits pointer to 48 bits, and promotes it again to 64 when used (by the operator T *()). Such a class would have to implement pointer arithmetic to be truly useful, but this yields a 25% storage gain relative to the native 64 bits pointers.

* *

A more aggressive technique would use stretch codes, a technique I discussed quite a while ago. The idea is to use, say 32 bits, to points to regions of varying granularity. So rather than having a pointer that makes accessible every byte in the first 2^{32} bytes of memory, the idea is to use, say, a quarter of the pointer values to address 2^{30} (1 GB) bytes to the byte. But after that, you can use a quarter of the pointer values to address only, says, chunks of 4 bytes (for 4GB), then another quarter to address chunks of 8 bytes (for 8GB), and the last one to address chunks of 16 bytes (for 16GB), for a total of (16+8+4+1)=29GB, substantially more than the 4GB a naïve 32 bits pointer would allow to address.

Of course, you can vary the chunk sizes and how the pointer values are used to address almost 64 bits’ worth, but at the cost of not being able to point to arbitrary locations in memory. That’s an interesting trade-off, especially if you build this in the memory allocator (which, as of now, does not support the idea, but it wouldn’t be stupid, I guess, to write an allocator class that does that).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: