Hello,
I've been wondering what the "best" way to implement a doubly linked list would be (best is a combination of high performance, memory efficiency and "elegance"). The 3 main approaches so far are raw pointers (probably the fastest and most efficient, but should I really be touching raw pointers with "only" 5 months experience? I did a lot of C so it shouldn't be too hard tho), RefCell (seems kind of like a cheat) and a "slab" model (https://www.reddit.com/r/rust/comments/7zsy72/writing_a_doubly_linked_list_in_rust_is_easy/). Which of these is the "best"?
Thanks,
ndrewxie
1 Like
Presumably you've already read Learn Rust with Entirely Too Many Linked Lists. As you point out, it's straightforward to write source code that appears to implement a doubly-linked list. However, it's very difficult to avoid UB, and thus difficult to ensure that the compiler actually implements what you intend (since the presence of UB enables aggressive machine-level instruction "optimizations" that can totally destroy the integrity of your code).
4 Likes
As Vec<(next_index, previous_index, T)>, or better simplified to Vec<T> 
From performance perspective, linked lists are self-defeating:
- the "linked" part makes vectorization impossible, so operations on the elemens are slower,
- the "list" part goes against caching and prefetching, so getting to the next element may stall CPU pipeline for a relatively very very long time.
So if you want a fast linked list, the first thing you have to do is to choose another data structure.
11 Likes
That's the best argument I've seen for avoiding linked lists. Linked lists were a great innovation for simple computer architectures similar to the 1970-era PDP-11, but they defeat most of the hardware acceleration features of modern architectures with their parallel and pipelined execution resources. Multi-level memory caches, single- and multi-issue instruction pipelines, look-aside address translation and branch prediction caches, parallel arithmetic and logical execution units, etc. all end up stalling or being massively under-utilized when chasing linked lists.
2 Likes
None of those stated properties apply to linked lists in Rust 
What operations on a linked list were you interested in? Splices, O(1) inserts, etc?
What I wanted wasn't a doubly linked list, I just used this question as a way to gain insight to a similar problem (sorry about not putting the "actual" problem there).
Actually what I want isn't really a "doubly linked list", more like a tree where the children have pointers to their parents. Each node has a Vec of children (it owns its' children) and a pointer to the parent (basically doubly linked list but each node can own multiple subnodes). I need to keep a "parent" pointer so that each child knows it's parent, hence the doubly linked list. The graph will be rearranged very often, so I didn't use a vec approach (actually what I want isn't a simple list, so a Vec won't work). It's also very sparse, with about 2000 nodes, but each node only being connected to 4-6 other nodes, so the adjacency matrix approach was also out. I really don't care about any properties except:
- You can easily and quickly move nodes around the graph
- Doesn't waste too much space (adjacency matrix doesn't work then, sadly)
This is more focusing on "do it correctly and idiomatically" as opposed to "get the job done", I have already "hacked up" a solution that uses a buffer of Vec, and each Node uses indexes to that vec instead of pointers. Seems unidiomatic, though, and kind of like "cheating the borrow checker".
Like a tree, or actually only 0-or-1 parent? You could plausibly have fn parent(&self) -> Option<&Self> on a node if it's really a tree and you're not trying to get ownership of the parent from ownership of a child. (Probably needs unsafe internally, but shouldn't be too bad.)
Not at all, actually, especially if you actually need full graph behaviour: Modeling graphs in Rust using vector indices · baby steps
(And even for trees I've seen it done for the better locality of Vec elements compared to separate heap-allocations)
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.