Hacker News Reader

This is very similar to an old approach to LISP garbage collection. All of memory is a tree of small cells. You need to walk the the tree and don't have space for a stack of the links that got you to where you are. So you store the backlinks in the forward links by XORing the forward link with the backlink. As the tree-walker backs down the tree, the links are XORed again, restoring the forward link.

View on HN

That's brilliant

Wikipedia has a note on XOR linked lists.[1] That's a more general form of this concept. This technique is decades older than the references there indicate. I'm trying to find a reference to this in early garbage collection papers, and not, so far, succeeding. It's the sort of thing that mattered around when LISP was being invented in the 1950s and 1960s, and memory cost millions of dollars per megabyte.

[1] https://en.wikipedia.org/wiki/XOR_linked_list

This was brought up in another thread here yesterday titled "XOR", as well!

Reply on news.ycombinator.com