Best data structure for a particle system?

[qznc]

On Friday, 15 November 2013 at 14:01:36 UTC, Chris Cain wrote:
> 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.

This swapping might even speed up the normal particle processing, 
because with a mix of dead and alive particles the flag checking 
could confuse the branch predictor.

http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

Ultimately, if flag or swap is faster must be measured. Profiling 
and bencharking are your friends, if you want to optimize your 
particle system. For a start use an array and either method.