I'm trying to draw a few thousand particles using instancing. It's working and it's fast, but I have one bottleneck that slows the whole program down.
My Particle class is similar to this:
public class Particle
{
public Vector2 Position;
//More data not used for drawing
//....
}
Now in my DrawLoop() I got something like this:
Vector2[] instanceData = new Vector2[numParticles];
public void Draw()
{
for(int i = 0; i < numParticles; ++i)
instanceData[i] = Particles[i].Position; //THAT'S the slow part
instanceBuffer.SetData(instanceData);
//Now draw VertexBuffer using instancing
//...
}
I have tried using Parallel.For, but it doesn't speed things up enough, since I'm having like 8000 particles. Also I looked in the particlesystem example from MSDN. But their Particle struct just contains the data for drawing the particles, and the positions are calculated in the shader. However, I need additional data for several algorithms.
I can't think of a class design, so I don't need to assign the particle positions to the array every frame.
Since this problem ultimately arose from the data structures being used, let me present you with a common alternative to the linked list for scenarios such as this one.
Linked lists are generally not a good idea for storing particles for two reasons: one, you can't randomly access them efficiently, as you discovered here; and two, linked lists have poor locality of reference. Given the performance requirements of particle systems, the latter point can be killer.
A standard list has much better locality of reference, but as you've discovered, adding and removing items can be slow, and this is something you do commonly in particle engines.
Can we improve on that?
Let's start with something even more basic than a list, a simple array. For simplicity's sake, let's hard-cap the number of particles in your engine (we'll redress this later).
private const Int32 ParticleCount = 8000;
private readonly Particle[] particles = new Particle[ParticleCount];
private Int32 activeParticles = 0;
Assuming you have room, you can always add a particle to the end of the array in constant time:
particles[activeParticles++] = newParticleData;
But removing a particle is O(n), because all of the particles after it need to be shifted down:
var indexOfRemovedParticle = 12;
particles.RemoveAt(indexOfRemovedParticle);
activeParticles--;
What else can we do in constant time? Well, we can move particles around:
particles[n] = particles[m];
Can we use this to improve our performance?
Yes! Change the remove operation to a move operation, and what was O(n) becomes O(1):
var indexOfRemovedParticle = 12;
var temp = particles[indexOfRemovedParticle];
particles[indexOfRemovedParticles] = particles[activeParticles - 1];
particles[activeParticles - 1] = temp;
activeParticles--;
We partition our array: all of the particles at the beginning are active, and all of the particles at the end are inactive. So to remove a particle, all we have to do is swap it with the last active particle, then decrement the number of active particles.
(Note that you need the index within the array of the particle to remove. If you have to go searching for this, you end up reverting to O(n) time; however, since the usual workflow for particles is "loop through the whole list, update each particle, and if it's dead, remove it from the list," you often get the index of dead particles for "free" anyway.)
Now, this all assumes a fixed number of particles, but if you need more flexibility you can solve this problem the same way the List<T> class does: whenever you run out of room, just allocate a bigger array and copy everything into it.
This data structure provides quick inserts and removals, quick random access, and good locality of reference. The latter can be improved further by making your Particle class into a structure, so that all of your particle data will be stored contiguously in memory.