Alternatively you can follow what java did with compressed ops and use 4bytes per pointer on 64bit archs (instead of 8) and shift the pointers prior to dereference - effectively enabling 32GB heaps with 4bytes pointers.
Consider a typical binary-tree with a 64-bit integer as its value. You use 24-bytes per node (value, left child, right child) if you use 64-bit pointers, but only use 16-bytes per node if you use 32-bit pointers (or array indexes).
Now, a 32-bit pointer can have at most 4billion nodes across the whole tree. But 4billion is more than usable for many programs.
EDIT: Consider that 4billion nodes of size 16 bytes (where each node is the value + left child + right child struct discussed earlier) will take up 64GB of RAM.
EDIT2: And half the time, my brain gets short-circuited and I end up recreating some terrible form of segmented memory before having to slap myself for thinking up such a horrible idea. In any case, a surprising amount of memory is used up as pointers in almost all the code I write. If you care about fitting as much data into L1 cache (64kB on modern machines), you will absolutely want to minimize your data usage.
Im wondering though, this isnt totally free, is it ? I guess there’s an extra addition/subtraction calculation everytime you go from one cell to the next since instead of reading the next/prev pointer you now need to read a value and calculate the pointer from it, am i understanding this correctly ? (Not a computer scientist, so ive never had a formal algorithm class).
Very very very neat nonetheless, thank you very much ;)
Yep, the lower 1-3 bits in many pointers will always be zero due to how C run-time allocators and structure alignment works out of the box.
Sadly the original Mozilla link is broken. https://wingolog.org/archives/2011/05/18/value-representatio...
http://www.folklore.org/StoryView.py?project=Macintosh&story...
―
¹ I think, but to be honest it's been some time since I really knew the arcane C rules and I'm not confident anymore
Anyways, I did some digging into TAOCP. In section 2.3.1 Knuth mentions threaded binary trees[1]. They are trees that you can traverse without a stack and do not use more memory than a regular binary tree. This is compared to the method used in the post which requires you to store the parent pointers. The trick is that in a binary tree, lots of pointers are going to be null. Instead of storing null there, you can store a special value that provides information on how to traverse the tree. Indicating the difference between a regular pointer and one of these special values requires only a single bit. You can often store that bit within the pointer itself, requiring no additional space over a regular binary tree.
For a threaded binary tree, if the left child is null, you instead store the predecessor node. If the right child is null, you store the successor node. Finding the successor now becomes:
One small advantage of threaded binary trees is you traverse the tree slightly less. If the right child is null, instead of traversing back up the tree as in the post, you can jump straight to the successor node.[0] https://en.wikipedia.org/wiki/XOR_linked_list
[1] https://en.wikipedia.org/wiki/Threaded_binary_tree