3 ms·
Thats right. Though in reality, programs behave in a complex way. You rarely have to insert something in the middle of a list in practice. You rarely do random
by quadcore 4y ago
Thats right. Though in reality, programs behave in a complex way. You rarely have to insert something in the middle of a list in practice. You rarely do random behaviors, at least in my field. Let me explain.
In the game industry, we use contiguous-allocated intrusive free list memory pools. For enemies or projectiles as an example. Those things live and die (they are removed from the free list and inserted in the "live" list or put back in the free list when they die) in such a way the locality is kept good.
Admitedly I dont have sources nor benchmarks and never did. But its obvious it at least invalidates author's point in the sense that benchmarks gota be done in real life programs.
- devit 4y agoLinked lists only perform poorly if you iterate them, or otherwise access multiple items at once. If you use them as a single-linked free list they are faster than a vector since you only need to fetch a cache line for the object rather than a cacheline for the object and one for the vector storing free objects.
- pornel 4y agoEven this doesn't give you optimal locality. Objects in the same pool are closer than if they were randomly fragmented from a global allocator, but if you're accessing them in the list order, you're not accessing adjacent addresses to take advantage of memory prefetch. If the pool is large, it may not even fit in the cache. When performance needs to be maximized, games switch to entity component systems and switch from arrays-of-structs to structs-of-arrays. This enables processing all objects as a vector, linearly from start to end, and often without needing to fetch any irrelevant bytes that aren't processed in a given pass. This sometimes also helps utilize SIMD for data spanning more than one entity, which you can't do when using linked lists.