XOR Linked List
en.wikipedia.org
XOR Linked List
1–10 of 86 posts
Re: XOR Linked List
#2It's a cute trick, but please don't use it. It will confound debuggers, garbage collectors, memory leak detectors, and future readers. :)
Re: XOR Linked List
#3It's a cute trick, but please don't use it. It will confound debuggers, garbage collectors, memory leak detectors, and future readers. :)
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.
Re: XOR Linked List
#4It's a cute trick, but please don't use it. It will confound debuggers, garbage collectors, memory leak detectors, and future readers. :)
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.
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
Re: XOR Linked List
#5Anyone actually using this is almost certainly committing a heinous premature optimization.
Re: XOR Linked List
#6Please 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.
Re: XOR Linked List
#7Earlier 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.
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
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.
Re: XOR Linked List
#8Please 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?
Re: XOR Linked List
#9Earlier 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
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.
Re: XOR Linked List
#10Just curious, this wouldn't work for a circularly linked list in the case where there is only one element, right?