News for hackers. Stuff that matters.
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...)