4 ms·
Even if you have a bump allocator, the fact is that a linked list requires storage for the pointers, which are not needed in an array. That makes the list bigg
by kazinator 6y ago
Even if you have a bump allocator, the fact is that a linked list requires storage for the pointers, which are not needed in an array. That makes the list bigger, and bigger means worse from a caching point of view. Fewer parts of a linked list fit into a cache line and so on.
Plus the pointer traversals are dependent loads. Until we load node->next, we don't know what address that is, so we cannot pre-fetch node->next->anything.
But when we access array[i], it's possible to pre-fetch array[i+1].
I'm still using linked lists because of the flexibility, functional substructure sharing and allocations you can avoid, but let's not kid ourselves.
- galangalalgol 6y agoAnd if your data is truly contiguous and its struct of arrays instead of the other way around, SIMD becomes much more usable.
- simiones 6y agoAbsolutely, I'm not claiming linked lists are "better" than arrays. The GP was mentioning memory fragmentation and cache behavior, and I was pointing out that GCs can, at least in some conditions, make linked lists more efficient then they are in C (comparing naive implementations). But yes, linked lists are almost always worse than arrays, unless you're doing huge amounts of add/remove on large amounts of data.