Best data structure for a particle system?

[Mike Parker]

On 11/15/2013 9:19 PM, Mikko Ronkainen wrote:
>
> If relevant, doubly-linked might work better? dcollections LinkList, or
> maybe DList? I'm asking mostly because I'd like the container to avoid
> memory allocations while in use.

For a particle system, I would avoid lists. A list of particles needs to 
be iterated every frame. A linked list is going to kill you as the 
particle count increases. Since the particles will most like not be 
contiguous in memory, you'll be thrashing your cache to hell and back.

"Caches love linear access" is a quote to remember. When you need to do 
frequent iteration of a list, your cache will love you if all of the 
items are in a block of contiguous memory. So it's almost always better 
to use an array for this sort of thing. Make your particle object a 
struct and use a dynamic array of particles that you can grow as needed 
or, if it makes sense, a fixed size static array. The point is that 
arrays of structs will be lined up one next to the other in memory so 
that you can make good use of the cache. Of course, the size of your 
particle object also has a role to play here.

Google for "linked list cache thrashing" or "cache-friendly data 
structures" or some such for ideas.