Drop millions of allocations by using a linked list (2015)

Re:Drop millions of allocations by using a linked list (2015) by kazinator on Friday March 12, 2021 @11:46AM (#26437713)

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.

[ Parent | on HN ]

Re:Drop millions of allocations by using a linked list (2015) by simiones on Friday March 12, 2021 @12:20PM (#26438161)

Absolutely, 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.

[ Parent | on HN ]

Re:Drop millions of allocations by using a linked list (2015) by galangalalgol on Friday March 12, 2021 @12:00PM (#26437892)

And if your data is truly contiguous and its struct of arrays instead of the other way around, SIMD becomes much more usable.

[ Parent | on HN ]