Best data structure for a particle system?

[Chris Cain]

On Friday, 15 November 2013 at 13:32:38 UTC, Mikko Ronkainen 
wrote:
> Ok, thanks! That linked list cache thrashing was just the thing 
> I knew that I don't know :)
>
> Let's say I just use dynamic array and grow it when adding new 
> particles to the system, and when particles die, just set their 
> dead flag on. This means that, when adding a new particle, I 
> need to scan the array first for possible dead particles that 
> can be reused. Is there some trick that could be used here to 
> reduce excessive searching/iteration?

Instead of having a "dead flag", you could swap ( 
http://dlang.org/phobos/std_algorithm.html#swap ) the dying 
particle with the last particle in the list and then decrement 
the list's length.

Two assumptions: 1, you don't have pointers to particles 
anywhere. 2, when a particle "dies" it knows about the list and 
its position in the list.

By default (using the default GC and everything), D does not 
reallocate a dynamic array every time you change the length (even 
increasing it), so this will still be okay with allocations.