21–30 of 86 posts
It looks fun and all, but I really wonder about the implementation and practicality of it in C. But once again, it does look really cool.
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.
That's some pretty advanced magic.
Even the compiler has very limited insight into what your code is actually doing without simulating it, the prefetcher might be able to look a bit ahead in the execution stream and do branch prediction but absolutely no way does that extend to knowing stuff about your data structures.
Unless I have just been transported by a time warp I really think this is fiction.
If you're thinking of cache pre-fetching that actually has a really hard time dealing with stuff like linked lists because it has absolutely no idea at all about the data structure it is looking at. The 'next' and 'previous' pointers in the linked list might actually simply be values without any significance at all. And if they are dereferenced as pointers then that memory could be just about anywhere within the valid address range.
For arrays on the other hand such pre-fetching can be useful.
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.
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
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.
Earlier quoted context omitted.
The prefetcher knows what a linked list looks like That seems unlikely to me. Which processors do this?
Prefetching when a register contains what looks like a memory address at least seem possible
There has been some research on this subject with respect to compiler optimizations but as far as I know this is not at all done at the hardware level.
Just curious, this wouldn't work for a circularly linked list in the case where there is only one element, right?
Why wouldn't it? A xor A = 0. A xor 0 = A. That should work like a regular circularly linked list or am I missing something? edit Doh, now I understand. If this was allowed it wouldn't be possible to have a one-node non-circular list.
Earlier 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
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…
Earlier quoted context omitted.
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
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).
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.
Anyone actually using this is almost certainly committing a heinous premature optimization.
interface LinkedList
class BasicLinkedList implements LinkedList
class XORLinkedList implements LinkedList
It'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.