News for hackers. Stuff that matters.
Re:XOR Linked List by duskwuff on Thursday May 03, 2012 @06:00PM (#3926025)
It'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 by exDM69 on Friday May 04, 2012 @02:33AM (#3927341)
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 by ajray on Friday May 04, 2012 @05:37AM (#3927688)
Yeah, there's going to be these trade-offs (complexity/efficiency), but I've seen this end up in fellow student's personal projects after learning it in class.

Aside from that though, I think if you're clever enough to come to this and implement it well, I hope you're clever enough to understand whether or not it's the RightWay(TM).

Re:XOR Linked List by DennisP on Thursday May 03, 2012 @06:04PM (#3926039)
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 by sukuriant on Thursday May 03, 2012 @06:13PM (#3926076)
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 by alecbenzer on Thursday May 03, 2012 @07:47PM (#3926351)
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 storing your large objects themselves.

Re:XOR Linked List by benwr on Friday May 04, 2012 @02:14AM (#3927293)
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 by zanny on Friday May 04, 2012 @03:05AM (#3927418)
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 by DiabloD3 on Friday May 04, 2012 @06:03AM (#3927746)
I think Bulldozer and Ivy Bridge are both 48, but I'm not going to dive into 500 page PDFs to find out.
Re:XOR Linked List by zanny on Friday May 04, 2012 @12:32PM (#3929150)
Maybe, I just remember that number from powerPC / ARM back in my assembly class in 2010.
Re:XOR Linked List by alecbenzer on Friday May 04, 2012 @07:34PM (#3930800)
> 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.

Re:XOR Linked List by DennisP on Friday May 04, 2012 @08:01AM (#3927999)
Not if you're storing lots of references to the same object, which is what I'm often doing. And my objects are really small anyway.
Re:XOR Linked List by zurn on Friday May 04, 2012 @06:27AM (#3927800)
Some compilers/runtimes support pointer compression (eg. https://wikis.oracle.com/display/HotSpotInternals/Compressed...)
Re:XOR Linked List by benwr on Thursday May 03, 2012 @06:18PM (#3926085)
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 by lmkg on Thursday May 03, 2012 @06:25PM (#3926107)
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

Re:XOR Linked List by CJefferson on Thursday May 03, 2012 @06:35PM (#3926144)
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 by dpark on Thursday May 03, 2012 @08:24PM (#3926446)
This is similar to the problem with deletion in a standard linked list. Destructive actions can invalidate existing pointers.

One fix for this issue would be to extract the node where you split and "freeze" it. i.e. If you split at element 10, that element gets shoved into a new node which holds only one element and pointers are adjusted as necessary. The node it's extracted from may also be split into two pieces if necessary. From this point on, the single-element node is never merged into another node. It always exists independently.

Merging in this world works basically like it does in a normal linked list. You rearrange pointers but don't combine nodes. Insertion works like it does for a typical unrolled linked list, but with the frozen nodes special cased.

The tricky bit is if you're saving a lot of pointers that aren't part of a split operation. Then you might need to explicitly expose the freeze operation. And if you use it on every node, you're back to a standard linked list (with a bigger constant factor). You could also expose unfreeze, but that could get buggy really quickly. You could do a ref-counted freeze/unfreeze, but you should probably quit before you get to that point.

Re:XOR Linked List by derleth on Thursday May 03, 2012 @10:37PM (#3926762)
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 by dpark on Friday May 04, 2012 @09:47AM (#3928313)
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 by bodski on Thursday May 03, 2012 @09:25PM (#3926595)
P2P simulation, just what I am getting into right now. Interested to know if you... have made/intend to make, any code available.
Re:XOR Linked List by DennisP on Friday May 04, 2012 @07:58AM (#3927990)
What I've got isn't general-purpose at all. I'm working on distributed learning algorithms, and right now I'm more concerned with having lots of nodes in the learning algorithms than I am in simulating real-world p2p...so I'm not modeling things like network delays, nodes dropping out and returning with different IPs, etc.

How about you?

If I get something that might possibly be useful for someone else, sure, I'll put it on github or something. (If I get a good design, the real network will be opensource too.)

Re:XOR Linked List by agravier on Thursday May 03, 2012 @10:25PM (#3926727)
Would that be for a university assignment, to design your own protocol or for something else?
Re:XOR Linked List by zurn on Friday May 04, 2012 @06:18AM (#3927780)
A supercompiler could do this transparently.

edit: reference: http://c2.com/cgi/wiki?SuperCompiler

Re:XOR Linked List by wladimir on Friday May 04, 2012 @07:26AM (#3927919)
Isn't that what we're all waiting for, the mythical "smart enough" compiler. Imagine constructing programs from abstract and composable high-level concepts, and the compiler does all the dirty hacks behind the screen. Producing fully parallelized, secure, efficient machine code on-the-fly. Could it? One can dream :)
Re:XOR Linked List by nuje on Friday May 04, 2012 @07:35AM (#3927936)
There's been some invisible barriers for compilers to start reorganising data and not just code. It would seem to me that side has even more potential than semantics preserving code optimization that takes data layout as a given.
Re:XOR Linked List by wladimir on Friday May 04, 2012 @07:48AM (#3927965)
Agreed. It would already make a lot of difference if the compiler could make decisions between (for example) structure of arrays or array of structures representations. The programmer could always organize the data in a human-sensible way, and the compiler would transparently convert it to an efficient internal representation, with only the fields that are necessary for certain computations.

Of course there are some cases in which the binary layout matters (for example, serialization, or buffer handling in network code), but those can be regarded as glorified (un)parsers instead of fixed data layout. Would also make the langsec people happy.