Hacker News new | past | comments | ask | show | jobs | submit login

I’m mightily curious to know how you decide which double linked list to get from crates, isn’t there a clear best implementation? Are the differences/trade offs described somewhere? And if you can get one from crates, why would you implement your own with unsafe at all? Wouldn’t using an existing C linked list be more convenient?



So the first question: Why are you using a doubly-linked list? :-)

Due to the way modern processors work, following long chains of pointers is massively expensive (unless can you carefully control where all of the memory was allocated). There's a whole section discussing this in the "Too Many Lists" book. Basically, following pointers to unpredictable places will eventually defeat your processor's caches. You could easily wind up running a thousand times slower than if you used the cache well.

So you first want to look at data structures which store many elements in a single block, so that they're adjacent in memory and you won't have to chase nearly as many pointers.

- If you just want an ordered group of elements, use a "Vec", which is similar to a C array.

- If you're going to add elements at the back, and remove them from the front, look for a queue. These can be implemented with ring buffers or slabs of memory containing multiple elements at a time. There's a couple in the standard library.

- If you need to keep elements in order and search for them, you might actually want a B-tree, which again uses slabs of memory. There's a nice BTreeMap in the standard library.

Basically, by the time you've analyzed your problem, there's a 95% chance that a doubly-linked list was just the wrong data structure. Cache locality just has too big an effect on performance.

But if you really need a linked list, go to https://crates.io/ and search for "linked list" or "doubly linked list." Flip through the first page or two, and look for something with lots of downloads and nice docs. Check if it supports the APIs you want for your use case.

Also take a look at petgraph, which is an awesome Rust graph library: https://crates.io/crates/petgraph This has a zillion downloads (by Rust data structure standards), plenty of reference docs, and good support. It knows about cache locality. And a linked list is really just a special case of a graph.

But basically, you shouldn't be using doubly-linked lists unless you know exactly why you need one. They're a nice teaching exercise (except in Rust or functional languages) but they're actually pretty specialized.


>So the first question: Why are you using a doubly-linked list? :-)

Honestly there is only one legitimate usecase for a linked list that can only be solved suboptimally with a continguous array. Removing elements in the middle of a list assuming you already know the pointer to the linked list node.

In a linked list you can just overwrite the previous node to link to the next node.

However what I do is I just swap the element with the last one in a vector and delete the last element. This doesn't preserve the order of the list but for me this has never been a significant issue.


”there is only one legitimate usecase for a linked list that can only be solved suboptimally with a continguous array. Removing elements in the middle of a list assuming you already know the pointer to the linked list node.”

You will be surprised to see how large a memmove you can do on modern hardware in the time it would chase those pointers.

For an extreme example (moving array data gets slower if your elements grow larger), see https://youthdev.net/en/performance-of-array-vs-linked-list-...


The usecase imtringued was talking about:

> assuming you already know the pointer to the linked list node

For example a LinkedHashMap where a hash provides the primary means of looking up elements and the nodes contain an intrusive linked list. Removing an element from that list doesn't involve chasing pointers from the start of it.

The linked benchmark is for a different scenario.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: