I suppose that it's true that if you were coming from the item pointed to by 'prev' you could xor your previous address with the linked list pointer to get the value of 'next'. Is that from an actual implementation? Was anyone crazy enough to actually do that?
Nowadays pointers are 64-bit. So the simple xoring already saves 64 bits.
But, in most cases allocated memory blocks are close together, so that xoring of those 64-bit values gives a 32-bit value. So if you ignore the upper half and store the result in 32-bit, you basically save 96 bits. For the cases where the upper half matters, you can store it in an additional hashmap.
But it goes even better, if you allocate blocks and store indices. Like if you allocate blocks of 512 objects each. Then it is likely that the next/prev index is also in that block. Then you can store those indices in 2*8 bits (or just 8 bits if xored again?). In case it is in another block, you use the hashmap again. Then you save up to 120 bits.
The question remains, how do you find that hashmap? The article had a really clever solution. You allocate the blocks as 4K-aligned pages, e.g. by using mmap rather than malloc. Then you put a pointer to the hashmap at the beginning of the page, and when you have a pointer inside the block, you can find the hashmap by rounding the pointer down to the previous aligned position.
The XOR-trick is curious (if weird) because it preserves most* of the properties of the list structure. Traversal is almost identical to that of the original list in machine terms. Maybe an additional cycle on the critical path; probably not the worst thing in pointer chasing code.
* you do need to double the size of your iterator, so if you were needing to stash large numbers of iterators relative to the number of linked list elements, this wouldn't be a particularly nice trick.
Another crazy thing in Z88 is that the maximum amount you could allocate in one 'malloc' call was 256 bytes!