XOR Linked List • Hacker News Board

Re: XOR Linked List

#41

Post by joeld42 » Fri, May 04, 2012, 5:53 AM UTC

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.

Re: XOR Linked List

#42

Post by benwr » Fri, May 04, 2012, 6:14 AM UTC

alecbenzer wrote: post #23

sukuriant wrote: post #4

Earlier quoted context omitted.

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

If you're on a 64bit machine storing 32bit ints, this will decrease the node size from 32 + 64 + 64 = 160 to 32 + 64 = 96, so you should be able to store 66% more data. edit: In fact, when do you ever really need to store particularly large objects in something like a linked-list? It seems like you can always get some relatively small reference value to the data (eg, a pointer) and store that in your list instead of…

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.

Re: XOR Linked List

#43

Post by exDM69 » Fri, May 04, 2012, 6:33 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. :)

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.

Re: XOR Linked List

#44

Post by exDM69 » Fri, May 04, 2012, 6:44 AM UTC

jacquesm wrote: post #22

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

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

Re: XOR Linked List

#45

Post by exDM69 » Fri, May 04, 2012, 6:47 AM UTC

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

Note: the CPU knows your virtual address spaces and a whole lot more. So "looking like a pointer" is not just a 64 bit hexadecimal value, but the CPU has the possibility of checking whether it's a sane virtual address and other heuristics.

Also, if you make an incorrect prefetch decision, it's not a big deal. Just one wasted cache line.

Re: XOR Linked List

#46

Post by ithkuil » Fri, May 04, 2012, 7:05 AM UTC

tresta wrote: post #11

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.

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)

Re: XOR Linked List

#47

Post by zanny » Fri, May 04, 2012, 7:05 AM UTC

benwr wrote: post #42

alecbenzer wrote: post #23

Earlier quoted context omitted.

If you're on a 64bit machine storing 32bit ints, this will decrease the node size from 32 + 64 + 64 = 160 to 32 + 64 = 96, so you should be able to store 66% more data. edit: In fact, when do you ever really need to store particularly large objects in something like a linked-list? It seems like you can always get some relatively small reference value to the data (eg, a pointer) and store that in your list instead of…

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.

Re: XOR Linked List

#48

Post by malkia » Fri, May 04, 2012, 7:28 AM UTC

exDM69 wrote: post #44

jacquesm wrote: post #22

Earlier quoted context omitted.

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

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

Any refs, docs about this behavior? First time hearing it. How does it work with MMU, protected memory, or external memory mapped as normal one?

I know a bit about prefetch, and it's variants, but haven't directly used in 10 years (I was on a software project that had one of the first Katmai's, back in 1999 to do some bilinear/bicubic texture filtering for a media/drawing application, and had to code extensively in mmx assembly back then).

Re: XOR Linked List

#49

Post by exDM69 » Fri, May 04, 2012, 7:35 AM UTC

malkia wrote: post #48

exDM69 wrote: post #44

Earlier quoted context omitted.

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

Any refs, docs about this behavior? First time hearing it. How does it work with MMU, protected memory, or external memory mapped as normal one? I know a bit about prefetch, and it's variants, but haven't directly used in 10 years (I was on a software project that had one of the first Katmai's, back in 1999 to do some bilinear/bicubic texture filtering for a media/drawing application, and had to code extensively in m…

> Any refs, docs about this behavior? First time hearing it. How does it work with MMU, protected memory, or external memory mapped as normal one?

edit: try to look for performance tuning guides for your CPU architecture, there might be some details about systems like this.

Nope. Some might exist but this stuff is generally considered trade secrets. A patent search might yield something. You can find some material about speculative execution, branch prediction, prefetching, etc but the real beef is hidden somewhere in Intel's (and their competitors') vaults.

It's all supposed to be transparent to the programmer so there's no need to write and release detailed public documentation about it.

As I said earlier, I have no idea how they work (or do they even exist), but I'll give a handwaving example of how they _could_ work.

Re: XOR Linked List

#50

Post by Someone » Fri, May 04, 2012, 8:51 AM UTC

exDM69 wrote: post #44

jacquesm wrote: post #22

Earlier quoted context omitted.

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

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

"If it hits, it might yield big performance boost in real world apps. If it misses, it's just a little wasted electricity."

Caches have limited size. If it misses, it also evicts something else from the cache. If that is what is actually needed, this costs performance.

"and are pretty close to the original cache line's (virtual) address"

Why does it have to be 'pretty close'?

"Now if these values happen to be sane virtual addresses in the current process"

That sanity check would involve visiting the paging tables, so it would require at least two indirections (http://lwn.net/Articles/253361/). If a cache line is 16 bytes, you would have at least 4 positions where a 32-bit pointer could be present. So, at least four times two memory lookups would be needed. I think all of them would go through the same cache, but even assuming that the CPU has ways of signalling that it should not recurse, I do not think it is practical to do what you describe (disclaimer: I am not an expert on CPU design)

What is possible is to guess at where data is to be found. That allows CPUs to read and speculatively execute instructions from the physical memory that they think backs the virtual address of the PC while they, in parallel, do the lookup to verify that. See http://dl.acm.org/citation.cfm?id=2000101&dl=ACM&col.... I do not know whether this has made it into actual CPUs, though.