4 ms·
> 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
by mik1998 2y ago
> 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.
- nequo 2y agoWhy 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?
- gpderetta 2y agoEven 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.