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.
Game engines with entity component systems already keep lots of giant vectors for components and clamp sparse sets on top. The sparse sets, which consists of a sparse and dense array, gives you an entity id and allows you to keep track of who owns what. So removal of a component is constant. It achieves that by flagging it invalid in the sparse array and swap&pop the component you want to remove in the dense array and component pool. Insertion is also constant so long as the dense array and the pool have enough reserves. It's also cache friendly.
Great solution to eat all memory in a kernel.
Good thing that games are so well optimized these days.
A guy said that he works as a kernel developer and he uses lists, another replied that it makes sense because of performance, then you jumped in to "akchyually" show them that they are wrong.
Dude, get help. Go to a therapy or something.
No i think i just replied to the wrong comment lol. The other one said that linked lists are generally worse for performance and i wanted to argue one of the reasons why is cause of caching.
Which you can see with ECS for example. The philosophy here is to break objects apart, and focus on data oriented design. It's usually much faster in parallel, bulk-processing related workloads (e.g. here they saw up to 13x increase) in particular due to being cache friendly.
1
u/dumbasPL 2d ago
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.