3 ms·

> xor the “next” and “prev” pointers of their linked list into a single DWORD to save 32 bits I suppose that it's true that if you were coming from the item po

> xor the “next” and “prev” pointers of their linked list into a single DWORD to save 32 bits 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?

silvestrov 6y ago
Yes, the Z88 used this for memory: https://www.cl.cam.ac.uk/~jrh13/devnotes/all.html#sec218 https://www.cl.cam.ac.uk/~jrh13/devnotes/all.html#sec218 Another crazy thing in Z88 is that the maximum amount you could allocate in one 'malloc' call was 256 bytes!
benibela 6y ago
It can be done even better. I read an article about that recently. 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.
- glangdale 6y ago
  These are neat tricks, but they are now completely different data structures to the original one (and, IMO, maybe not all that great a data structure, in that it seems to be a festival of special cases and clever hacks). Once you're willing to allocate large blocks of objects, all sorts of things are possible, but you have to be ready for radically different performance properties (not always bad, just... different). 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.

silvestrov 6y ago

Yes, the Z88 used this for memory: https://www.cl.cam.ac.uk/~jrh13/devnotes/all.html#sec218 https://www.cl.cam.ac.uk/~jrh13/devnotes/all.html#sec218 Another crazy thing in Z88 is that the maximum amount you could allocate in one 'malloc' call was 256 bytes!

benibela 6y ago

It can be done even better. I read an article about that recently. 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.

glangdale 6y ago
These are neat tricks, but they are now completely different data structures to the original one (and, IMO, maybe not all that great a data structure, in that it seems to be a festival of special cases and clever hacks). Once you're willing to allocate large blocks of objects, all sorts of things are possible, but you have to be ready for radically different performance properties (not always bad, just... different). 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.