Hacker News Reader

mik1998

> linked lists invariably result in terrible cache locality

With a compacting GC (ie most of the relevant ones) lists often provide better memory locality than arrays. They only lose at a large scale due to having +8 bytes of memory, which makes arrays occasionally cheaper for large sequences.

View on HN

Even with perfect cache locality, a linked list will be significantly slower to traverse than an array because of worse pipelining and parallelization. Partially unrolled lists can help, but at the cost of additional complexity.

Of course not all container accesses require traversal.

Why do lists provide better memory locality than arrays? The array already stores its elements next to each other in memory. The compacting GC helps arrange the elements of the list close to each other too, right? Then wouldn’t the compacting GC at best even out the performance difference for sequential traversal?

Reply on news.ycombinator.com