XOR Linked List • Hacker News Board

Re: XOR Linked List

#51

Post by hythloday » Fri, May 04, 2012, 9:09 AM UTC

kevingadd wrote: post #32

glimcat wrote: post #28

Earlier quoted context omitted.

Why would you not just do the following? interface LinkedList class BasicLinkedList implements LinkedList class XORLinkedList implements LinkedList

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

You'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

Re: XOR Linked List

#52

Post by pheon » Fri, May 04, 2012, 9:27 AM UTC

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.

Re: XOR Linked List

#53

Post by peterderivaz » Fri, May 04, 2012, 9:36 AM UTC

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

Re: XOR Linked List

#54

Post by ajray » Fri, May 04, 2012, 9:37 AM UTC

exDM69 wrote: post #43

duskwuff wrote: post #2

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

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 thi…

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

Re: XOR Linked List

#55

Post by adsr » Fri, May 04, 2012, 9:42 AM UTC

pheon wrote: post #52

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…

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

Re: XOR Linked List

#56

Post by pheon » Fri, May 04, 2012, 9:57 AM UTC

peterderivaz wrote: post #53

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 t…

oooh very cool.

Re: XOR Linked List

#57

Post by DiabloD3 » Fri, May 04, 2012, 10:03 AM UTC

zanny wrote: post #47

benwr wrote: post #42

Earlier quoted context omitted.

If you're storing references to larger objects, your larger objects are what's taking up the space, which I think was the point (66% more pointers are useless if you can't also store 66% more of the objects they point to). Also, I think on a 64-bit machine with common DDR SDRAM, a memory location is 64 bits wide, no matter the size of the integer contained there. Not sure about this, however.

Most modern architectures like AMD64 use 40 bit memory references in the CPU, but write them as 64 bit to memory. That is why they have much lower addressable memory than the logical limit.

I think Bulldozer and Ivy Bridge are both 48, but I'm not going to dive into 500 page PDFs to find out.

Re: XOR Linked List

#58

Post by zurn » Fri, May 04, 2012, 10:18 AM UTC

duskwuff wrote: post #2

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

A supercompiler could do this transparently.

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

Re: XOR Linked List

#59

Post by mzl » Fri, May 04, 2012, 10:18 AM UTC

nknight wrote: post #21

Vlaix wrote: post #14

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.

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.

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

Re: XOR Linked List

#60

Post by pheon » Fri, May 04, 2012, 10:19 AM UTC

adsr wrote: post #55

pheon wrote: post #52

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…

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

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