Hacker News Reader

Comment by hyperman1 | Hacker News Reader

A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next}

The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;}

While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also works: Node * previous=(Node * )current.xored XOR (Node * ) next.

The first and last node can use 0 as previous or next node, or you make a circular list. You do have to store a pointer to the first and last node, as usual.

I've never seen this used in the real world, which is probably a good thing. It also plays hell with garbage collectors like Boehm, as they can't derive the 2 used adresses.

UPDATE: And of course wikipedia knows everything: https://en.wikipedia.org/wiki/XOR_linked_list

View on HN

I looked up TAOCP (The Art of Computer Programming by Knuth), and (unsurprisingly) this trick is mentioned there, and already by the time of the first edition this trick was folklore, with its origins lost to antiquity: the last exercise in section 2.2.4:

> 18. [25] Devise a way to represent circular lists inside a computer in such a way that the list can be traversed efficiently in both directions, yet only one link field is used per node. [Hint: If we are given two pointers, to two successive nodes x_{i-1} and x_i, it should be possible to locate both x_{i+1} and x_{i-2}.]

Answer (in 1st edition [1968], second printing [1969]):

> 18. Let the link field of node x_i contain LOC{x_{i+1}) ⊕ LOC{x_{i-1}), where "⊕" denotes either subtraction or "exclusive or." Two adjacent list heads are included in the circular list, to help get things started properly. (The origin of this ingenious technique is unknown.)

The "either" is modified to "e.g." in the 2nd edition [1973], and further slightly modified in 3rd edition ([1997], first digital release [December 2013]):

> 18. Let the link field of node x_i contain LOC(x_{i+1}) ⊕ LOC(x_{i−1}), where “⊕” denotes “exclusive or.” Other invertible operations, such as addition or subtraction modulo the pointer field size, could also be used. It is convenient to include two adjacent list heads in the circular list, to help get things started properly. (The origin of this ingenious technique is unknown.)

With modern languages and compilers, even if doing these operations on your language's pointer type is implementation-defined/undefined behaviour as mentioned in some of the other comments, you can still use this trick with your own "pointers" (indexes in an array, as Knuth does in many of his programs: https://en.wikipedia.org/w/index.php?title=Pointer_(computer...), I guess.

Anyway, this gives me another point of appreciation about why the TAOCP series of books were so highly regarded: they were (are) encyclopedic and gathered/organized much of what was known at the time, in a highly compressed way (packed into exercises etc).

The bigger problem with this approach is that you can't remove/erase something from the list just by knowing it's address. This is a key mechanism for most use cases. However, if you're fine with limiting yourself to erasing only during iteration, it's pretty nifty.

I've also done some benchmarks in the past and found it interior iteration performance due to what I'm assuming to be inability to prefetch the next address. However, linked list iteration is already relatively slow so I suppose it's not a big downside.

Also, I think this may be the only data structure I have heard of that has an O(1) reverse ordering operation?

Wouldn’t this be achieved by an array and a Boolean flag just as well?

Technically, but I'm not quite sure that's in the spirit of things.

Ha, very nice!

To clarify: to reverse the list, one would only have to swap the HEAD and TAIL pointers of the base structure.

It's not obvious how prefetching the next address would make things run that much faster - you don't know a given address until you execute the load. That said, there is definitely an extra cycle in your dependency chain to do the XOR, which you might well notice if your linked list is in cache (that extra cycle will show up).

We had a discussion on Twitter about some sort of superfast magic prefetcher that may well have been on the M1 which arguably could shave some cycles off list traversal, and there was a theory that an XOR-list would have been a good negative benchmark to prove/disprove this, but nothing came of it.

The limitation is worse than you say; you can't even navigate from an item just by knowing its address (not just remove/erase something). So any given iterator into this list has to have 2 pointers (say, the item and its predecessor).

It's a weird structure. There's probably almost certainly some peculiar use case for it somewhere, but I've never encountered such a case.

It's been used in the real world, on the Cambridge Z88, ca. 1987:

https://www.cl.cam.ac.uk/~jrh13/devnotes/all.html#sec218

This XOR-list trick was mentioned by Joel Spolsky in "The Duct Tape Programmer" (2009), discussed recently here.

> They have to be good enough programmers to ship code, and we’ll forgive them if they never write a unit test, or if they xor the “next” and “prev” pointers of their linked list into a single DWORD to save 32 bits, because they’re pretty enough, and smart enough, to pull it off.

https://news.ycombinator.com/item?id=25715414

and this comment pointed out the real world usage:

https://news.ycombinator.com/item?id=25718147

Single pointer lists using the XOR trick were used, I believe, to implement the XDS Sigma 7 operating system block free list back in the day when memory was not free and core dumps were the primary debug tool. I remember writing a column on the algorithm for Dr. Dobbs Journal back in the 1980s. There are lots of bit twiddling techniques that use XOR. Henry Warren's Hackers Delight is a good reference there. And, of course, Don Knuth's AOCP has lots of information. Volume 4A, available as a fascicle, has a number of XOR algorithms.

To quote my old OS professor: "people who xor pointers deserve what happens to them."

I used this trick in a sorting pancakes contest. Flipping a list of pancakes required only one XOR, whatever the size. Very nice trick.

That’s undefined behavior in C though: https://news.ycombinator.com/item?id=3928788

Your linked comment only quotes excerpts saying it's implementation-defined, rather than undefined. Can you point to the part that is undefined?

(You would use a uintptr_t for the xor'd prev-next pointers instead of void*.)

To be precise, it's implementation-defined whether it's undefined behavior, prior to C11. You are right that in C11, if uintptr_t is used to store the xored value, behavior is defined.

Implementation-defined whether it's UB or not is still implementation-defined, I think.

Which change are you thinking of in C11? (I'm just curious.) Thanks!

That is amazing and disgusting.

I think there is something like this in linux kernel.

Reply on news.ycombinator.com