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

31–40 of 86 posts

Re: XOR Linked List

#31

Post by zaptheimpaler »

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.

Pre-fetchers rely on two metrics to determine what to cache - temporal locality, meaning it will cache things that it judges to be frequently accessed, and spatial locality, meaning that when you access something at memory address X, the cache will fill one cache line with the contents of consecutive memory locations i.e X,X+1,X+2,..,X+s.

Hence, they have no capability to understand a structure like a linked list and will not cache it intelligently. All you can rely on is that they will cache arrays and traverse them in a way that efficiently uses the cache.

Re: XOR Linked List

#32

Post by kevingadd »

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

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

Re: XOR Linked List

#33

Post by ComputerGuru »

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!

Don't be silly, the principle is sound.

    #ifdef _DEBUG
    typedef BasicLinkedList LinkedList
    #else
    typedef XorLinkedList LinkedList
    #endif

Re: XOR Linked List

#34

Post by agravier »

bodski wrote: post #30
DennisP wrote: post #3

Earlier quoted context omitted.

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

P2P simulation, just what I am getting into right now. Interested to know if you... have made/intend to make, any code available.

Would that be for a university assignment, to design your own protocol or for something else?

Re: XOR Linked List

#35

Post by derleth »

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

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.

Re: XOR Linked List

#37

Post by shirro »

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

Re: XOR Linked List

#38

Post by excuse-me »

shirro wrote: post #37

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

Saving 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

Re: XOR Linked List

#39

Post by shirro »

excuse-me wrote: post #38
shirro wrote: post #37

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

Saving 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

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

Re: XOR Linked List

#40

Post by aggftw »

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!

Except this is not about performance, but memory.
Post reply on HN