[ncmncm]

Halves the cost provided that touching that many cache lines is free. Even after you rewrite them back to how they were, the cache doesn't know, so has to write back every line.

If it's a balanced tree, you need only log(n) stack entries you can statically provision, and then other threads can traverse the tree at the same time.

Most of the traditional optimizations turned into pessimizations decades back. That has been a good thing.

[jhgb]

> Even after you rewrite them back to how they were

Why would you do that? I was under the impression that the trick with the "XOR-ly linked list" is to keep these in RAM strictly in the XOR'd form. What exactly did you mean by "has to write back every line"?

[ncmncm]

I misremembered the trick. Yes, it does save on storage without appreciable overhead.