XOR Linked List • Hacker News Board

Re: XOR Linked List

#71

Post by jacquesm » Fri, May 04, 2012, 1:28 PM 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…

> I'm not familiar with the internals of the prefetcher of any CPU at this level

So better not speculate, what you think could be done when you are not familiar with the details typically tends to be a lot harder when you are familiar with the details and are tasked with the implementation. The devil is in the details and there is a very appreciable gap between theory and practice.

Further reading: http://www.futurechips.org/chip-design-for-all/prefetching.h...

Note the caution against using lists and trees and an advice to stick to arrays, which are typically accessed sequentially.

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

And that is exactly the point, if you don't supply the knowledge neither the processor nor the compiler can do this for you. If the processor or the compiler could do this then those __builtin_prefetch calls would not be required.

Re: XOR Linked List

#72

Post by dpark » Fri, May 04, 2012, 1:47 PM UTC

derleth wrote: post #35

lmkg wrote: post #9

Earlier quoted context omitted.

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

This is esssentially CDR coding. Here's what a Lisp FAQ has to say about that: http://www.faqs.org/faqs/lisp-faq/part2/section-9.html Essentially, it says that it isn't as good an idea as you might imagine, because lists aren't often created all at once and they get chopped up and inserted into often enough the advantages of the scheme disappear.

These seem like like related but distinct ideas. From what I understand, CDR coding is basically an optimization that replaces the entire list with an array. This has the effect that inserting elements involves an ugly and expensive indirection hack.

Unrolled linked list don't exhibit this behavior (though they have other drawbacks). Their behavior is closer to that of B-trees, where size-bounded multi-element nodes can be split and joined cheaply, which allows for cheap element insertion.

Re: XOR Linked List

#73

Post by dpark » Fri, May 04, 2012, 2:04 PM UTC

pheon wrote: post #60

adsr wrote: post #55

Earlier quoted context omitted.

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.

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

Re: XOR Linked List

#74

Post by mason55 » Fri, May 04, 2012, 2:16 PM UTC

glimcat wrote: post #28

Tossrock wrote: post #5

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

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

    LinkedList 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(); //???

Re: XOR Linked List

#75

Post by nknight » Fri, May 04, 2012, 3:26 PM UTC

mzl wrote: post #59

nknight wrote: post #21

Earlier quoted context omitted.

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.

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

Re: XOR Linked List

#76

Post by nknight » Fri, May 04, 2012, 3:42 PM UTC

zurn wrote: post #62

mzl wrote: post #59

Earlier quoted context omitted.

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

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

C++ 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

Re: XOR Linked List

#77

Post by zanny » Fri, May 04, 2012, 4:32 PM UTC

DiabloD3 wrote: post #57

zanny wrote: post #47

Earlier quoted context omitted.

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.

Maybe, I just remember that number from powerPC / ARM back in my assembly class in 2010.

Re: XOR Linked List

#78

Post by noselasd » Fri, May 04, 2012, 5:39 PM UTC

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.

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

Re: XOR Linked List

#79

Post by orky7 » Fri, May 04, 2012, 7:10 PM UTC

jacquesm wrote: post #71

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…

> I'm not familiar with the internals of the prefetcher of any CPU at this level So better not speculate, what you think could be done when you are not familiar with the details typically tends to be a lot harder when you are familiar with the details and are tasked with the implementation. The devil is in the details and there is a very appreciable gap between theory and practice. Further reading: http://www.futurec…

hardware prefetching mechanism is in core i7 that i know for sure, it automatically identify memory referencing pattern and attempts to fetch those blocks into cache before they are accessed, the detailed algorithm of prefetching are not documented...

Re: XOR Linked List

#80

Post by alecbenzer » Fri, May 04, 2012, 11:34 PM 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.

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

Right, of course...

> I really don't know all that much about architecture (yet), so that's totally possible, and I might be wrong about the 66% thing I guess.

edit: Actually, about the whole more objects thing, there might be some strange use case where you only have a few objects but are storing multiple references to them in a list. But yeah, in general, the benefit goes down with larger objects.