That's true, but in modern game engines, objects of the same type share an allocation pool. So a bunch of Projectiles should still be in contiguous memory, since they're using the same pool allocator.
At that point, vector is still a better choice because it prevents the CPU from accessing a bunch of intermediate list nodes which will pollute the CPU cache. If you use a vector, there are no intermediate objects, so less stuff winds up in the cache. There's also less memory fragmentation overall.
As long as you're using a vector implementation that grows by a factor of 2 every time it expands, then there shouldn't be any significant cost of enlarging the vector. If it's just storing pointers, it won't invoke any copy constructors. It can even be optimized to a straight-line memcpy, which is blazingly fast on a modern CPU.
> That's true, but in modern game engines, objects of the same type share an allocation pool.
I don't think pool allocation guarantees memory contiguity: what if we have a pool with two elements free, those elements being the first and last ones, and we allocate two elements and stick pointers to them in our vector?
> a vector implementation that grows by a factor of 2....shouldn't be any significant cost
It depends on what you mean by "cost". I agree that the enlargement cost is acceptable from an overall CPU budget sense, but each enlargement can still cause a latency spike, since the cost for enlargement is still large (especially considering the cost of taking the heap lock) for _that_ insertion. Sometimes consistency is more important than throughput.
> vector is still a better choice because it prevents the CPU from accessing a bunch of intermediate list nodes which will pollute the CPU cache
Who said anything about intermediate list nodes? The nice thing about an intrusive linked list is that once you pay for accessing an element's cache line, the rest of the accesses are nice and local. There are no intermediate nodes, and all costs are smooth and consistent. Besides: you can issue a memory prefetch instruction for node B while you process node A, further hiding latency.
While a vector is value types might be best in most situations, if you can't use that, an intrusive linked list may or may not be better than a vector of pointers.
Good points! I love tech chats like this. There are a few caveats:
A pool should be trying to make new allocations as contiguous as possible. That's accomplished by wrapping the allocations. For example, let's say we have a pool with slots A, B, C, D, E. We allocate A through D, then C is later freed. The pool shouldn't put the next allocation at C. It should be placed at E. That way, the objects are still roughly sorted by creation time: A is younger than B, which is younger than D, and so on.
(The next allocation should go in C after that, because there are no more slots. But by that time D and E might have been freed, so it's still in sorted order.)
That way, if you access any given element, it will cache the next element in memory. Due to the sorted nature of the allocations, that means even if you're iterating over them using some other container like a list or vector of pointers, accessing an element will still likely cache the next iterator's element. Not guaranteed, but likely.
About the vector enlargement: Usually the cost is nil, because as long as the vector stays under 1MB, you can simply preallocate large blocks of memory at startup for each type of vector. Therefore the cost of expansion is just a few arithmetic instructions for bookkeeping purposes, not anything expensive like a heap lock.
Good point about the intrusive list. I personally wouldn't like it because it makes the code more complicated, but as long as you're using a pool allocator, the memory characteristics of an intrusive list shouldn't be too different from the scheme I described above.
At that point, vector is still a better choice because it prevents the CPU from accessing a bunch of intermediate list nodes which will pollute the CPU cache. If you use a vector, there are no intermediate objects, so less stuff winds up in the cache. There's also less memory fragmentation overall.
As long as you're using a vector implementation that grows by a factor of 2 every time it expands, then there shouldn't be any significant cost of enlarging the vector. If it's just storing pointers, it won't invoke any copy constructors. It can even be optimized to a straight-line memcpy, which is blazingly fast on a modern CPU.