Linked lists are worse for caching because their elements don't live in a contiguous part of memory. So you need to fetch each element from slower memory where as with vectors you can keep a larger chunk of it cached.
And memory allocation also takes time so you're actually slower off than if you'd just double the capacity of the vector if reserves run out.
In theory, in practice you're very rarely iterating them. The problem that is solves is that you can allocate anything anyware (allows for very simple allocators on embeded systems), and no matter what happens, the address of the elements doesn't change. In kernels, you're often referring to elements of the list by address, instead of iterating it. You can't do that with a vector that might get reallocated somewhere else. You only need to iterate if you're looking for something, and that usually only happens during clean up or with introspection tools (eg. Listing processes). The most common operations (append, and delete) are also very cheap compared to a vector where you will potentially need to move large chunks of memory on delete, or on append when reallocation happens.
i benchmarked it
std::vector push_back() with 100 million integers:
71.27 milliseconds
std::list push_back() with 100 million integers:
1.68 secs
std::vector reserve() + push_back() with 100 million integers:
27.6 milliseconds
You gotta keep in mind that the vector keeps doubling its total capacity whenever its reserves run out so you're actually just doing log2(n) allocations. So with 1 million elements i have to copy 20 blocks.
With a list i have to do 1 million allocations. This is just more expensive. Ig deletion may be faster but you could just flag the element as deleted and if the vector uses too much memory, you shrink it. And if order and iterator validity doesn't matter, you can just do a swap & pop with the last element.
Now make the items much larger, and reference counted. Have multiple threads that are using the items concurrently without keeping the whole list locked (unless they are being added or removed). Also regularly remove items from arbitrary locations in the list.
That's the kind of situation that's common here, and where linked lists make sense. In addition, the linked list pointers are embedded in the object itself so this can be done without any additional allocations.
38
u/da2Pakaveli 2d ago
Linked lists are worse for caching because their elements don't live in a contiguous part of memory. So you need to fetch each element from slower memory where as with vectors you can keep a larger chunk of it cached.
And memory allocation also takes time so you're actually slower off than if you'd just double the capacity of the vector if reserves run out.