XOR Linked List

http://en.wikipedia.org/wiki/Xor_linked_list

by no_more_death • 14 years ago

153 84 14 years ago

en.wikipedia.org

duskwuff• 14 years ago

It's a cute trick, but please don't use it. It will confound debuggers, garbage collectors, memory leak detectors, and future readers. :)

DennisP3• 14 years ago

Oh, I dunno. Every now and then I write a massive simulation of some p2p idea or other and max out my RAM. This might just come in handy.

sukuriant• 14 years ago

So that you can get 30 more nodes? Surely the L/R pointers of the linked lists aren't taking up all the memory in your program

bodski• 14 years ago

P2P simulation, just what I am getting into right now. Interested to know if you... have made/intend to make, any code available.

exDM694• 14 years ago

Never say never. There's a time and place for dirty pointer tricks like the XOR linked list or tagged pointers (low 2-3 bits used for "tags"). Emphasis on words "dirty tricks" so you know that it's the rabbit you pull out of a hat, not something you do every day.

I almost needed XOR linked lists somewhere once, but I ended up doing the same thing with tagged pointers. I wish I remembered the occasion.

But imagine this situation: you're doing some high-perf code on x86's and doing a data structure (with next/prev links somewhere) and your node size is 136 bytes because of arbitrary reason X. You're running a few percent behind your worst competitor in performance figures. Now if you shave 8 bytes you'll fit one node per cache line and probably squeeze out a little pref just by having a cache-friendly alignment. Should you do it? Hell yeah.

Okay, I know many people don't write code with tight performance budgets, but some of us do.

ajray• 14 years ago

Yeah, there's going to be these trade-offs (complexity/efficiency), but I've seen this end up in fellow student's personal projects after learning it in class.

Aside from that though, I think if you're clever enough to come to this and implement it well, I hope you're clever enough to understand whether or not it's the RightWay(TM).

zurn3• 14 years ago

A supercompiler could do this transparently.

edit: reference: http://c2.com/cgi/wiki?SuperCompiler

wladimir2• 14 years ago

Isn't that what we're all waiting for, the mythical "smart enough" compiler. Imagine constructing programs from abstract and composable high-level concepts, and the compiler does all the dirty hacks behind the screen. Producing fully parallelized, secure, efficient machine code on-the-fly. Could it? One can dream :)

Tossrock• 14 years ago

Anyone actually using this is almost certainly committing a heinous premature optimization.

glimcat• 14 years ago

Why would you not just do the following?

interface LinkedList

class BasicLinkedList implements LinkedList

class XORLinkedList implements LinkedList

kevingadd• 14 years ago

Hm, I'm super concerned about performance! I know, I'll turn every function call into a virtual function call!

mason55• 14 years ago

    LinkedList<Element> list = new XORLinkedList(Collections.fromArray(arrayList));
    Element ele = list.get(4); //Ok, when we construct the list we can store the first and second pointers and traverse to the fourth
    Element next = ele.next(); //???

xsmasher2• 14 years ago

XORLinkedList is most assuredly harder to debug then BasicLinkedList. Don't do it unless you hafta. In fact don't implement your own linked list at all, unless you have a specialized scenario that needs it (as proven by profiling).

seanmcq• 14 years ago

Please profile tricks like this, as they may actually be significantly slower than their naive counterparts on modern hardware. The prefetcher knows what a linked list looks like, and it knows how to get it somewhere closer than main memory before the nodes are needed.

ssp• 14 years ago

The prefetcher knows what a linked list looks like

That seems unlikely to me. Which processors do this?

idunno246• 14 years ago

Prefetching when a register contains what looks like a memory address at least seem possible

forgotusername• 14 years ago

As best I understand it, while instruction prefetch is a complex affair, data prefetch is limited to detecting incrementing sequential address access, unless directed through a PREFETCH op. I can't a find a good reference, but I believe at best the CPU can only optimize by detecting stride.

In no circumstance will the CPU magically understand the semantics of some data structure.

jacquesm3• 14 years ago

> The prefetcher knows what a linked list looks like

That's some pretty advanced magic.

Even the compiler has very limited insight into what your code is actually doing without simulating it, the prefetcher might be able to look a bit ahead in the execution stream and do branch prediction but absolutely no way does that extend to knowing stuff about your data structures.

Unless I have just been transported by a time warp I really think this is fiction.

If you're thinking of cache pre-fetching that actually has a really hard time dealing with stuff like linked lists because it has absolutely no idea at all about the data structure it is looking at. The 'next' and 'previous' pointers in the linked list might actually simply be values without any significance at all. And if they are dereferenced as pointers then that memory could be just about anywhere within the valid address range.

For arrays on the other hand such pre-fetching can be useful.

exDM694• 14 years ago

> Unless I have just been transported by a time warp I really think this is fiction.

Nope, the Intel guys and gals do this kinda magic day in, day out. Or at least the chips they manufacture do. I'm not familiar with the internals of the prefetcher of any CPU at this level, but let me wave hands here. This is what the prefetcher could do:

All it takes is for the prefetcher to get a cache line when requested, and then observe what is inside and look at pointer-sized and aligned values that look like pointers and are pretty close to the original cache line's (virtual) address. Now if these values happen to be sane virtual addresses in the current process, the prefetcher might as well fetch them one cache closer to the CPU. If it hits, it might yield big performance boost in real world apps. If it misses, it's just a little wasted electricity.

All modern CPUs do dirty little tricks like this if it helps them outshine their competitors.

Btw. you can add prefetch instructions in your code manually if you do linked list traversals or similar. In GCC you can use __builtin_prefetch() compiler intrinsic.

zaptheimpaler• 14 years ago

Pre-fetchers rely on two metrics to determine what to cache - temporal locality, meaning it will cache things that it judges to be frequently accessed, and spatial locality, meaning that when you access something at memory address X, the cache will fill one cache line with the contents of consecutive memory locations i.e X,X+1,X+2,..,X+s.

Hence, they have no capability to understand a structure like a linked list and will not cache it intelligently. All you can rely on is that they will cache arrays and traverse them in a way that efficiently uses the cache.

noselasd• 14 years ago

Note though that speed isn't all that matter, memory usage does too, especially in constrained environments.

codezero• 14 years ago

Just curious, this wouldn't work for a circularly linked list in the case where there is only one element, right?

tresta• 14 years ago

Why wouldn't it?

A xor A = 0.

A xor 0 = A.

That should work like a regular circularly linked list or am I missing something?

edit

Doh, now I understand. If this was allowed it wouldn't be possible to have a one-node non-circular list.

bbrtyth• 14 years ago

It would be the reverse case if it were non-circular, returning 0.

ithkuil• 14 years ago

You can encode "end of list" with another value like -1 which is usually safe since you can assume that addresses are at word aligned (so odd numbers cannot be addresses)

pmjordan2• 14 years ago

Generally, it doesn't allow you to walk the list given the pointer to an entry. You always need to know the addresses of two adjacent list entries. And yes, this limits its usefulness in practice. I tend to only need doubly linked lists where I want to be able to remove or insert an arbitrary element without walking the list, and you can't do that with an xor list.

Vlaix• 14 years ago

It looks fun and all, but I really wonder about the implementation and practicality of it in C. But once again, it does look really cool.

nknight3• 14 years ago

It's technically undefined behavior, but in practice it will work perfectly well on almost all C implementations, and in the infinitesimal number of cases where this structure is actually useful, portability isn't a major concern.

mzl• 14 years ago

Just curious, what part of an XOR-linked list is undefined? AFAIK, casting to and from sufficiently wide integers is ok.

TheBoff• 14 years ago

Believe it or not, we actually had a C exam question where we were asked to sketch out an implementation of this.

http://www.cl.cam.ac.uk/teaching/exams/pastpapers/y2010p3q6.... With classic mildly amusing exam humour introduction!

goldeneye• 14 years ago

This question still haunts me.

no_more_death• 14 years ago

I know, maybe it's not very useful.

But isn't it fascinating? Some information moved from the link node into the state of the program processing it. This halves the link redundancy of a doubly linked list. Suddenly a doubly linked list has the footprint of a singly linked list. How did that happen? :-)

It taught me. Tricks like this make me a better programmer. Even if I won't use the principle involved in this exact way.

drallison• 14 years ago

As I remember this was used the operating system in the XDS Sigma 7. Decoding core dumps when things went awry was a challenge, but it did save memory.

dubya• 14 years ago

This is an exercise in Knuth, TAOCP v.1.

shirro2• 14 years ago

I haven't used an XOR linked list since my Amstrad 6128. I think probably independently discovered but not sure. It is a pretty obvious thing to do on a memory limited machine. Nice to know people still know about this stuff post the 8 bit micro era but outside of embedded systems why would anyone use this today?

excuse-me• 14 years ago

Saving memory still matters if you are trying to fit something into cache - although the items you are storing in the list would have to be pretty small if the extra pointer mattered

shirro2• 14 years ago

Most people don't need more than 4G per process so I wish stuff like the linux x32 abi became standard. All the extra registers without the huge pointers. Would be handy for squeezing more into a cheap VPS. Not to mention the cpu cache.

joeld42• 14 years ago

Cool! Hadn't seen that before, neat trick.

Seems to me like (as other commenters have pointed out) this wouldn't be a great idea for something that is stored as a straightforward linked list.

Where it seems really useful to me is a cheap way to store an alternate ordering on top of an existing data structure, without having to keep a separate list around. I've done this before, using next pointers to preserve an alternate ordering, but this is a nice way to allow it to be bidirectional. neat.

pheon5• 14 years ago

it only works if you are linearly iterating from the start/end of a list.

IMHO one of the (few) primary benefits of linked lists is random access to insert/delete/iterate an element without having to traverse the entire list. Something that breaks with xor lists.

Secondly if you have so many nodes that the memory saving of one pointer is significant. Its likely traversing that list will take forever and force you to use a different algo anyway.

... an improvement on basic linked lists would be 16B/32B/128B/512B etc alignment of the nodes memory address and bit packing the Left/Right offset in units of the alignment unit. Hell you could probably beat xor lists for space for a range of workloads.

adsr2• 14 years ago

A regular linked list doesn't have random access to elements, typically a head node is inserted into a function that iterates the list.

pheon5• 14 years ago

.. or you pass any node to a function that operates on the list. iterate up/down insert/delete etc.

point being you dont have to iterate from the start of the list.

peterderivaz• 14 years ago

The nicest use of a similar XOR trick I have seen is to eliminate dead cycles in hardware bus arbiters.

Suppose you need to multiplex between inputs A,B,C to make output D (e.g. you have a 3d block, a display engine, and a CPU all trying to access DRAM). The idea is to xor all valid inputs together.

When there is only one input this results in output=input. If all 3 are active then the output is A^B^C. The trick is that the next cycle only the granted input (say A) is removed so the output is B^C

Receivers are required to XOR two sequential values to extract the actual data. In this case (A^B^C)^(B^C)=A.

See the "NoX Router" for details and explanation of how this compares to alternative arbitration approaches: pharm.ece.wisc.edu/papers/micro2011_nox.pdf

pheon5• 14 years ago

oooh very cool.

mkup• 14 years ago

Some implementations of heap memory allocators manage free memory chunks as doubly-linked lists. There are multiple lists for chunks of equal size, i.e. 4, 8, 16, 32 ... 2^n.

This XOR linked list hack makes sense for smallest chunk size. On 32-bit system, two pointers will take 8 bytes, so minimum size of allocated memory block is 8 bytes without this hack and 4 bytes with this hack. On 64-bit system, this hack makes possible allocation of 8-byte block from heap without rounding up to 16 bytes.

For other practical purposes, I think that trading speed and code maintainability for memory size isn't good idea.

XOR Linked List

Related Stories