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

61–70 of 86 posts

Re: XOR Linked List

#61

Post by zurn »

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.

Some compilers/runtimes support pointer compression (eg. https://wikis.oracle.com/display/HotSpotInternals/Compressed...)

Re: XOR Linked List

#62

Post by zurn »

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.

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.

Re: XOR Linked List

#63

Post by mkup »

Some implementations of heap memory allocators manage free memory chunks as doubly-linked lists. There are multiple lists for chunks of equal size, i.e. 4, 8, 16, 32 ... 2^n.

This XOR linked list hack makes sense for smallest chunk size. On 32-bit system, two pointers will take 8 bytes, so minimum size of allocated memory block is 8 bytes without this hack and 4 bytes with this hack. On 64-bit system, this hack makes possible allocation of 8-byte block from heap without rounding up to 16 bytes.

For other practical purposes, I think that trading speed and code maintainability for memory size isn't good idea.

Re: XOR Linked List

#64

Post by wladimir »

zurn wrote: post #58
duskwuff wrote: post #2

It's a cute trick, but please don't use it. It will confound debuggers, garbage collectors, memory leak detectors, and future readers. :)

A supercompiler could do this transparently. edit: reference: http://c2.com/cgi/wiki?SuperCompiler

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

#65

Post by nuje »

wladimir wrote: post #64
zurn wrote: post #58

Earlier quoted context omitted.

A supercompiler could do this transparently. edit: reference: http://c2.com/cgi/wiki?SuperCompiler

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

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

#66

Post by wladimir »

nuje wrote: post #65
wladimir wrote: post #64

Earlier quoted context omitted.

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

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.

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.

Re: XOR Linked List

#67

Post by DennisP »

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.

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

#68

Post by DennisP »

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.

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

#69

Post by adsr »

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.

In theory yes, but how many references do you need to claim random access.

Re: XOR Linked List

#70

Post by nuje »

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.

What about destructors? I guess only using the GC on destructorless objects could work.
Post reply on HN