8 ms·
XOR Linked List
- codezero 14y agoJust curious, this wouldn't work for a circularly linked list in the case where there is only one element, right?
- tresta 14y agoWhy 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.
- pmjordan 14y agoGenerally, 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.
- duskwuff 14y agoIt's a cute trick, but please don't use it. It will confound debuggers, garbage collectors, memory leak detectors, and future readers. :)
- DennisP 14y agoOh, 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 14y agoSo 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
- benwr 14y agoIt would depend on the data you're storing. If you have a really long list of a really small data type (one machine word? I guess it's possible), this could cut your memory usage by up to a third.
- lmkg 14y agoYou could cut your memory usage by arbitrarily close to 1/2 by using an unrolled linked list instead. Plus then you get the benefits of having pointers look like pointers, and getting your nodes to fit neatly in cache lines. http://en.wikipedia.org/wiki/Unrolled_linked_list http://en.wikipedia.org/wiki/Unrolled_linked_list
- CJefferson 14y agoI find unrolled linked lists less useful than I hoped in the past. I tend to use linked lists when I want to do a lot of splicing, and be able to keep pointers to particular nodes. Requiring being able to keep a pointer to nodes stops unrolled linked lists being useful, as you can't merge/split unrolled nodes as required (or at least, I couldn't come up with a clever way to do it).
- dpark 14y agoThis is similar to the problem with deletion in a standard linked list. Destructive actions can invalidate existing pointers. One fix for this issue would be to extract the node where you split and "freeze" it. i.e. If you split at element 10, that element gets shoved into a new node which holds only one element and pointers are adjusted as necessary. The node it's extracted from may also be split into two pieces if necessary. From this point on, the single-element node is never merged into another node. It always exists independently. Merging in this world works basically like it does in a normal linked list. You rearrange pointers but don't combine nodes. Insertion works like it does for a typical unrolled linked list, but with the frozen nodes special cased. The tricky bit is if you're saving a lot of pointers that aren't part of a split operation. Then you might need to explicitly expose the freeze operation. And if you use it on every node, you're back to a standard linked list (with a bigger constant factor). You could also expose unfreeze, but that could get buggy really quickly. You could do a ref-counted freeze/unfreeze, but you should probably quit before you get to that point.
- Tossrock 14y agoAnyone actually using this is almost certainly committing a heinous premature optimization.
- glimcat 14y agoWhy would you not just do the following? interface LinkedList class BasicLinkedList implements LinkedList class XORLinkedList implements LinkedList
- kevingadd 14y agoHm, I'm super concerned about performance! I know, I'll turn every function call into a virtual function call!
- ComputerGuru 14y agoDon't be silly, the principle is sound. #ifdef _DEBUG typedef BasicLinkedList LinkedList #else typedef XorLinkedList LinkedList #endif
- aggftw 14y agoExcept this is not about performance, but memory.
- hythloday 14y agoYou'd implement it either with a policy-based class[0] or a CRTP compile-time virtual dispatch[1]. There's zero need to involve vtables in this. [0] http://en.wikipedia.org/wiki/Policy-based_design [1] http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern#Static_polymorphism
- mason55 14y agoLinkedList<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(); //???
- seanmcq 14y agoPlease 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 14y agoThe prefetcher knows what a linked list looks like That seems unlikely to me. Which processors do this?
- idunno246 14y agoPrefetching when a register contains what looks like a memory address at least seem possible
- pmjordan 14y agoPretty much everything looks like a memory address. There is currently a memory address "hole" on x86_64 which doesn't, but any number between -140737488355328 and 140737488355327 can represent a virtual memory address. Prefetching any occurrance of any of those would be insane. The prefetcher detects patterns. If you start accessing memory at N byte intervals, it will start prefetching N, 2N, 3N etc. ahead. So if you allocate your linked list elements from contiguous (virtual) memory, it will be able to prefetch elements. But once you start jumbling the list up, that will fall apart.
- ajross 14y agoYes, but imagine the bus traffic if you tried that: every commited instruction would require a TLB read to see if it "looked like" an address. The poor TLB is overcommited as it is (Intel CPUs can do three memory operations in a clock). All prefetch implementation I'm aware of simply do sequential access (positive or negative) prediction, sometimes with stride detection, and that's it.
- jacquesm 14y agoYou can't tell whether a register contains a memory address or not after it has just been fetched right up until the moment that it is used. If the instruction stream contains instructions that reference that register that are within the look-ahead window of the instruction pipeline then maybe this might work, but if there is any conditional code in there or something else that causes the value to be used in a way that is not 'as a pointer' and to access the memory (and not for for instance pointer arithmetic prior to utilization) then such a pre-fetch would likely cause more harm than good by blowing good data out of the cache and replacing it with useless data (at a significant penalty). There has been some research on this subject with respect to compiler optimizations but as far as I know this is not at all done at the hardware level.
- Vlaix 14y agoIt 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.
- nknight 14y agoIt'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 14y agoJust curious, what part of an XOR-linked list is undefined? AFAIK, casting to and from sufficiently wide integers is ok.
- zurn 14y agoI remember hearing claims that a C++ implementation would be allowed to use conservative GC (and nop out free/delete). I wonder what the language lawyers make of this.
- nuje 14y agoWhat about destructors? I guess only using the GC on destructorless objects could work.
- nknight 14y agoC++ is a lot stricter about a lot of things, and C++11 added some explicit GC-related language, but I have little desire to parse that particular 10MB document. Bjarne covers it in his FAQ, at least: http://www2.research.att.com/~bs/C++0xFAQ.html#gc-abi http://www2.research.att.com/~bs/C++0xFAQ.html#gc-abi
- nknight 14y agoActually, the behavior is a combination of undefined and implementation defined. To the extent that it's implementation defined, it may still result in nasal demons, but they have to be documented nasal demons. Point is, it's strictly non-portable according to the standard, but when done carefully is unlikely to break on a general-purpose architecture. This is from C99, I don't have a copy of C11: 6.3.2.3 Pointers [...] 5) An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation.[56]) 6) Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type. [...] And footnote [56]: The mapping functions for converting a pointer to an integer or an integer to a pointer are intended to be consistent with the addressing structure of the execution environment.
- TheBoff 14y agoBelieve 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.pdf http://www.cl.cam.ac.uk/teaching/exams/pastpapers/y2010p3q6.... With classic mildly amusing exam humour introduction!
- goldeneye 14y agoThis question still haunts me.
- no_more_death 14y agoI 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 14y agoAs 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 14y agoThis is an exercise in Knuth, TAOCP v.1.
- shirro 14y agoI 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 14y agoSaving 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
- shirro 14y agoMost 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 14y agoCool! 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.
- pheon 14y agoit 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.
- adsr 14y agoA regular linked list doesn't have random access to elements, typically a head node is inserted into a function that iterates the list.
- pheon 14y 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.
- adsr 14y agoIn theory yes, but how many references do you need to claim random access.
- pheon 14y agoits how I use them. theres the list + some other structure/object that points/references the node, usually multiple time and the node is contained in multiple lists - big data + performance optimization
- dpark 14y agoSo your function needs to be passed current and next (or prev, depending on which direction you want to iterate). XOR-lists have lots of issues. This isn't one of them.
- peterderivaz 14y agoThe 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
- pheon 14y agooooh very cool.
- mkup 14y agoSome 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.