Best data structure for a particle system?

[bearophile]

On Friday, 15 November 2013 at 11:52:44 UTC, Mikko Ronkainen 
wrote:
> What would be the best data structure for handling particles in 
> a particle system in D2?
>
> Here's some thoughts:
>
> Particles are simple structs.
> Two lists, one for alive particles, one for dead ones.
> Memory allocations should be avoided, preallocate everything, 
> no allocations when moving between lists.
> Keep alive list as short as possible for fast iteration -> move 
> dead particles off  during iteration.
> Removal and addition of single items only, and it should be 
> fast.
>
> Maybe a single-linked list, std.container.SList? Is there any 
> gotchas? Or some better container for this scenario?

Linked lists are very cache unfriendly, so they should be 
avoided. Generally try to use arrays first, then try again using 
arrays, and if you fail then try to use something different.

I suggest to use a dynamic array of particle structs, that 
contain a boolean that represents if a particle is alive or dead. 
This is very simple to implement and use.

Once you have implemented and benchmarked that, if the code is 
*not fast enough* then you could try adding a pointer field (or 
uint/ushort index) to each struct that contains the pointer to 
the next active cell. But you have to start using and updating 
such pointers only when the _estimate_ percentage of active cells 
is very low.

An alternative strategy to try is to compact the array of 
particle structs (copying only the active particles as you scan 
it to use it). This is especially good if you don't need to keep 
their order stable and if the structs are small (like a size_t).

Bye,
bearophile