2 ms·
You can use this same property of xor to make a double-linked list using just one pointer per item, which is xor of the previous and next item addresses!
by stinkbeetle 6mo ago
You can use this same property of xor to make a double-linked list using just one pointer per item, which is xor of the previous and next item addresses!
- Panzerschrek 6mo agoExcept such "optimization" may affect performance on CPUs with speculative execution/prediction. But it should be measured.
- gblargg 6mo agoPresumably the reason is to reduce memory overhead for nodes.
- stinkbeetle 6mo agoWell it is a memory optimization where the interest would be to reduce cache misses or memory consumption. I have never felt the need to use such a thing seriously but I find it a neat trick. It can only be used when walking the list of course, which is quite likely why it is not more widely used -- it does not provide the benefit that a regular double linked list is mostly used for.