Best data structure for a particle system?

[Marco Leise]

Am Fri, 15 Nov 2013 21:56:15 +0900
schrieb Mike Parker <aldacron at gmail.com>:

> 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.

It is true, that these days you optimize for cache locality
more than for anything else.
How about this:
- use an array
- keep alive particles at the front and dead particles at the
  back
- when an alive particle dies, you swap it with the last alive
  particle in the array and mark it as dead
This way you always have a compact array from 0..aliveCount
and don't need if-else to check for dead ones. (Which is
otherwise another slowdown factor).

-- 
Marco