You speak of low latency code and doubly linked lists in the same breath.
Personally, I have moved from linked data structures to more cache friendly data structures, which means contiguous spaces. No jumping around. It's very liberating.
Personally, I have moved from linked data structures to more cache friendly data structures, which means contiguous spaces. No jumping around. It's very liberating.
Replacing large linked lists with arrays is rarely an actual win. With an array, insertion and deletion become far more expensive, virtual memory is more likely to become fragmented or grow monotonically, and the cache misses avoided are almost certainly irrelevant to total performance.
Highly performant code tends to get complex. One way to ensure high performance and reduce complexity is to deal with values, not pointers; it is good for concurrency (no aliasing), excellent for cache locality, and the value is right there. Multi-versioned stable values work excellently, like RCU-locks in the Linux kernel.
Then there is the fact that mutation makes things even harder. So for example, you can easily implement a tree using Box to hold pointers to child nodes, but you'll then need a little bit of unsafe code to write a mutable iterator over the tree. (Even mutable iterators for slices require unsafe code under the hood.)
>I decided this time I should just ignore all the dislike of `unsafe` and just use it as much as I need to. I think I was making life more difficult on myself by trying to avoid it so much, but when you have a lot of pointers that have multiple refereces between then, you kind of have to. Doulble linked and mutually linked structures - where any pointer chance can lead to a mutation - are Rust's achillies heel.
Sriram_malhar pointed out that doubly linked lists are usually not a good data structure to use anyway. I was pointing out that there are lots of more useful data structures that raise similar issues in Rust.
I don't think that using unsafe is "fine", necessarily. It is much better to implement a data structure on top of safe Rust if at all possible.