Re:Four Years of Rust
by davemp on Wednesday May 15, 2019 @01:34PM
(#19921778)
Doubly linked lists are used all over for low level programming. For low access, large dynamic data they're a pretty good solution AFAIK.
[ Parent
| on HN ]
Re:Four Years of Rust
by DblPlusUngood on Wednesday May 15, 2019 @04:55PM
(#19923681)
You are absolutely right. They are used everywhere in the Linux, OpenBSD, and FreeBSD kernels, and likely many other kernels.
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.
Re:Four Years of Rust
by sriram_malhar on Thursday May 16, 2019 @01:11PM
(#19930814)
I wasn't speaking of low-level programming. I was referring to very low-latency code.
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.