Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

XOR Linked List

en.wikipedia.org

Post reply on HN
Print view View original

11–20 of 86 posts

Re: XOR Linked List

#11

Post by tresta »

codezero wrote: post #10

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

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.

Re: XOR Linked List

#12

Post by CJefferson »

lmkg wrote: post #9
benwr wrote: post #7

Earlier quoted context omitted.

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

You 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

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

Re: XOR Linked List

#13

Post by idunno246 »

ssp wrote: post #8
seanmcq wrote: post #6

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.

The prefetcher knows what a linked list looks like That seems unlikely to me. Which processors do this?

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

Re: XOR Linked List

#14

Post by Vlaix »

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.

Re: XOR Linked List

#15

Post by pmjordan »

idunno246 wrote: post #13
ssp wrote: post #8

Earlier quoted context omitted.

The prefetcher knows what a linked list looks like That seems unlikely to me. Which processors do this?

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

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

Re: XOR Linked List

#16

Post by ajross »

idunno246 wrote: post #13
ssp wrote: post #8

Earlier quoted context omitted.

The prefetcher knows what a linked list looks like That seems unlikely to me. Which processors do this?

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

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

Re: XOR Linked List

#17

Post by pmjordan »

codezero wrote: post #10

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

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.

Re: XOR Linked List

#19

Post by no_more_death »

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.

Re: XOR Linked List

#20

Post by forgotusername »

seanmcq wrote: post #6

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.

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.

Post reply on HN