[Animats]

The classic use of XOR-swap was to traverse a tree without needing a stack. As you traverse the tree, the forward links are swapped with backward links, so you can find your way back. Used in the mark phase of some early garbage collectors.

[StillBored]

Yah, or just store both the forward and backwards links in a single variable by xoring the forward and backward links together and storing it. Then the list traversal direction is picked by selecting either the head or tail and starting the operation. Halves the cost of a doubly linked list, while allowing the same function to be used for forward and backwards traversal.

[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.

[throwaway81523]

That's pointer reversing but as I've seen it, it usually doesn't involve xor swap. It is still used in some gc's.

[Jerrrry]

can you explain this please (your comments are lovely btw)

[KMag]

If you're interested in this sort of thing "The Art of Garbage Collection" is the standard go-to text these days.

It's been a little while, but as I remember, the main reason for pointer reversing is to be able to not use any extra space to keep track of the list of grey (currently being processed) objects in a standard three-color collector. As you'll recall, a basic tracing collector marks each object as one of 3 colors: black, white, and grey. It must maintain the invariant that black objects never have pointers to white objects. A (full) GC cycle begins with all objects marked white, then the GC roots are marked grey. Then the collector repeatedly removes an object from the grey set, marks all of the white objects it points to as grey, and then marks the just removed grey object black. The GC cycle ends when there are no more grey objects, at which point all white objects are garbage and can be reclaimed.

This is often implemented by using a single bit in the object header to keep track of white/black, and a stack to keep track of the set of grey objects. In this setup, a white object is marked grey by setting the color bit in the object header to whichever color indicates black, and putting it in the grey set. That is, grey objects are really marked black, but in the grey set. In other words, the color bit in the object header is really a "white"/"not white" bit. This is the easiest way to ensure a white object never gets added twice to the grey set without having to explicitly mark the object as grey. (Some systems actually invert the sense of the color bit in the object header between major GC collections. In one major collection 0 means white, and the next major collection 0 means black. This avoids having to scan the heap marking all objects white at the beginning of the GC cycle.)

One way to implement the logical stack of grey objects is to use a singly-linked list. If you want to implement a linked list of objects without adding an extra pointer to every object's header, and you don't want to allocate any extra space in the middle of a garbage collection, then you need to figure out some kind of clever hack to re-purpose some existing space. I forget the exact details, but (1) if an object doesn't have any pointers in it, you can immediately mark it black without first adding it to the grey set ... and that's where I lose track of the details about how you keep track of which object pointer you've borrowed to reverse in order to use a linked list to implement your grey object stack.

So, I'm missing the key detail that makes the whole trick work, but at a high level, you have extra storage space of one pointer to point at the top of the grey stack. The object at the bottom of the grey stack has its pointer nulled out, and off to the side you keep track of that last final pointer to restore when you empty the grey stack (which ends the GC cycle). When you pop an object off of the grey stack, you point its pointer to the previous object popped off of the grey stack (thus restoring (re-reversing) its reversed pointer).

However, I can't for the life of me remember how you keep track of which pointer you've reversed in each object without using any extra space. I don't think you can always just use the first pointer in an object, because that could trap you in a cyclic sub-graph.

EDIT: I've found a few different sets of very vague lecture notes online that are super vague... just saying you reverse pointers in order to make a linked list of grey objects. However, if you reverse all of the pointers, you don't get a linked list, but a general graph. You need to have exactly one pointer per object in order to have a singly linked list. If you have some rule of always using the first (or last) non-null pointer in an object, you might still wind up in a situation where you're reversing a cycle of pointers. I found a nice slide deck showing the steps, but the example was acyclic, and there was no explanatory text.

I thought maybe there's a trick with using two bits for color in the object header, and using that to mark which pointer has been reversed by also marking the target object, but that breaks if there are multiple pointers to the specially marked object.

Maybe the unmentioned trick is to use tagged pointers to keep track of the one pointer in each grey object that has been reversed. I really hope that's not it. That just feels... less brilliant.

[KMag]

Aha... it seems I've been lied to! It seems the proof of correctness is for a binary graph (each node has an out-degree of at most 2, but cycles are allowed in the graph) and needs 2 extra bits of state per node. [0][1]

Now, one can represent any higher-degree graph as a binary graph by simply replacing any higher-degree nodes with a binary tree with the required number of out-nodes, but then that increases the number of extra bits required.

Gries's 2006 less formal writeup [1] is simple to extend to higher-degree nodes. Instead of his 2-bit counter, one can use a counter that goes from 0 to the number of out-links. My guess is that real implementations use tagged pointers to indicate which pointer has been reversed instead of using a counter in Gries's write-up.

I feel so lied to! No wonder I couldn't figure out how to do it without tagged pointers! Though, please correct me if you find a pointer reversal algorithm that doesn't use tagged pointers and is guaranteed to terminate in the case of arbitrary graph cycles.

[0] https://xlinux.nist.gov/dads//HTML/SchorrWaiteGraphMarking.h...

[1] https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec...

[rurban]

yes, you keep the 3 colors in each object. conveniently 2 bits of a pointer.

[KMag]

That's not quite what I'm talking about. If you look at Gries's 2006 paper (the less formal one, not his formal proof of the algorithm), each node has 2 bits for state and two child pointers.

  State 0: Node is white

  State 1: Node is grey and child[0] points to parent

  State 2: Node is grey and child[1] points to parent

  State 3: Node is black and both child pointers are restored

To generalize this algorithm to nodes with k children, you need to either pack ceil(log2(k+1)) bits into object header and tag bits in the first few fields of the object, or else have a white/not-white bit in the object header and have one tag bit in each object field, indicating which pointer has been reversed to point to the parent node. The latter is less complex, but results in O(k^2) time complexity in the repeated scanning of the object to find the currently reversed pointer each time you recurse back up to the node while traversing the graph. To really maximize speed, I suspect the O(k^2) algorithm is used in practice for small k, and the more complex counter spread across tag bits of multiple pointers is used for nodes with larger k.

[mangamadaiyan]

> The Art of Garbage Collection

By any chance, were you referring instead to Richard Jones' "The Garbage Collection Handbook: The Art of Automatic Memory Management"?

Garbage Collection interests me greatly, and I was looking forward to exploring a new reference - as it turned out, I couldn't find anything titled "The Art of Garbage Collection", so I thought I'd ask.

[KMag]

Oops. You're right. "The Garbage Collection Handbook: The Art of Automatic Memory Management" by Richard Jones, et al., CRC Press, 2012.