Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast linked lists

dygalo.dev

Post reply on HN
Print view View original

1–10 of 131 posts

Re: Fast linked lists

#3

Post by boxed »

ertucetin wrote: post #2

7-8 years ago I created GlueList ( https://github.com/ertugrulcetin/GlueList ) in order to build faster version of LinkedList + ArrayList. It was a fun effort.

I believe that's called a "rope"

Re: Fast linked lists

#4

Post by vbezhenar »

boxed wrote: post #3
ertucetin wrote: post #2

7-8 years ago I created GlueList ( https://github.com/ertugrulcetin/GlueList ) in order to build faster version of LinkedList + ArrayList. It was a fun effort.

I believe that's called a "rope"

Rope is binary tree of arrays, for O(logN) index operation.

Re: Fast linked lists

#5

Post by kevingadd »

I was hoping to see optimization of the actual linked list manipulation and traversal (pipelining? i'm not sure what you'd do), but this is still a neat post. It's cool to see thought put into various parts of the problem, like reallocation/preallocation, stack allocation, etc.

Re: Fast linked lists

#6

Post by vlovich123 »

Intrusive linked lists might bring down the allocations further, reduce the memory footprint, & more importantly improve locality when doing pointer chasing (single predictable indirection vs double hard-to-predict indirection).

Re: Fast linked lists

#7

Post by kolbe »

Linked list benchmarks are amazing.... if you don't thrash your cache on inserts so all its elements are contiguous. You get all the benefits of a vector and a linked list, without the reality that linked lists mostly don't get populated 100% consecutively, and thus can be anywhere in memory.

Re: Fast linked lists

#9

Post by duped »

ertucetin wrote: post #2

7-8 years ago I created GlueList ( https://github.com/ertugrulcetin/GlueList ) in order to build faster version of LinkedList + ArrayList. It was a fun effort.

If I have this right, what you've built is this, storing M items in M / N nodes where N is the radix of the array?

    0                 1                        M / Nth node
    [ N elem ] [.] -> [N elem] [.] -> .... -> [M - (M / N) elem] [null]
And so if you want to index the `i`th element you chase the pointers

    index (node i) :
        acc = 0
        while acc + N
Or something like that? You can do better using a B tree and exploit the fact that you don't need keys to just store pointers in the branch nodes. This reduces the number of pointer dereferences in large arrays.

For example say you have N = 8 and there are 1024 elements in the list, you would need 127 pointer dereferences to reach the end of the array. In a B-tree you only have 3. (double check my math, I might be off by one).

This is the typical implementation for immutable/persistent vector types. If you keep the links between leave nodes at the bottom of the tree, you've got a B+ tree and have fast iteration through it as well.

Re: Fast linked lists

#10

Post by bjoli »

kolbe wrote: post #7

Linked list benchmarks are amazing.... if you don't thrash your cache on inserts so all its elements are contiguous. You get all the benefits of a vector and a linked list, without the reality that linked lists mostly don't get populated 100% consecutively, and thus can be anywhere in memory.

Most languages with linked lists as an important part (lisps mostly) all have well optimized linked lists that end up with a lot better memory locality.
Post reply on HN