Strategy

Strategy: Stop Using Linked-Lists

High Scalability

High Scalability

— 2 min read

What data structure is more sacred than the link list? If we get rid of it what silly interview questions would we use instead? But not using linked-lists is exactly what Aater Suleman recommends in Should you ever use Linked-Lists?

In The Secret To 10 Million Concurrent Connections one of the important strategies is not scribbling data all over memory via pointers because following pointers increases cache misses which reduces performance. And there’s nothing more iconic of pointers than the link list.

Here are Aeter's reasons to be anti-linked-list:

  1. They reduce the benefit of out-of-order execution.
  2. They throw off hardware prefetching.
  3. They reduce DRAM and TLB locality.
  4. They cannot leverage SIMD.
  5. They are harder to send to GPUs.

He also demolishes the pros of linked-lists, finding arrays a better option in almost every case. Good discussion in the comment section as not everyone agrees.

Patrick Wyatt details how a linked-list threading bug repeatedly crashed Starcraft. Also a good comment discussion with a lot of disagreement.

KjellKod is also against linked-lists: Number crunching: Why you should never, ever, EVER use linked-list in your code again. The idea is mathematical complexity does not reflect real-life performance in situ on actual hardware:

Big-O notations tells nothing about how one (data structure with algorithm) fare against another. Big-O will only tell you how performance will degrade as n increases. So comparing one a data structure that is RAM intensive to another data structure that is cache friendly from an abstract Big-O point-of-view is just pointless.

The key as we've seen before is locality of reference. When memory is local and you can avoid cache misses and avoid paging then operations like copying are dirt cheap, when in the mind of the programmer they are expensive. When you don't have locality of reference the thing that programmers think is dirt cheap, following pointers, is extremely expensive. While the first part of the article is frustratingly vague, the last half is full of excellent explanatory detail. Well worth reading. And there are even more good comments in the comment section.

But people really like their link lists. Probably as much as people used to love goto statements. So if performance really matters to you then this is something to think about rather than immediately dismiss as heresy.

Read more