3 ms·
Doubly linked lists are used all over for low level programming. For low access, large dynamic data they're a pretty good solution AFAIK.
by davemp 7y ago
Doubly linked lists are used all over for low level programming. For low access, large dynamic data they're a pretty good solution AFAIK.
- DblPlusUngood 7y agoYou 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.
- sriram_malhar 7y agoI 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.