   Allocating particles in memory at run-time not slow?
  I'm doing some performance tests on different particle system memory management techniques in C#.  I've created a particle simulation (no rendering though) to see how many times each different approach is able to update all of the particles.  Three of the approaches I'm using are:1 - Use a linked list to hold the active particles. When a new particle is required I create a new instance of the Particle class (allocates memory at run-time) and add it to the linked list. When a particle dies remove the particle from the linked list (de-allocated from memory). To update the active particles just update all of the particles in the linked list.2 - Create a pool of particles in memory using an array of Particle instances and store the inactive particle indexes in an inactive queue. When a new particle is needed grab the next index from the inactive queue, and when it dies return it to the inactive queue. When updating particles loop through the entire particle pool array and update the active particles.3 - Create a pool of particles in memory using an array of Particle instances and use both an inactive queue and active particle list. When a new particle is needed grab the next index from the inactive queue and add it to the active list, and when it dies remove it from the active list and return it to the inactive queue. To update the active particles just update all of the particles in the active particle list.I test the approaches both with static particle lifetimes (all particles have the same lifetime) and with random lifetimes. I do two tests, the first where 10,000 particles are allocated in memory (for approach 2 and 3) and I test with 10, 100, 1000, 5000, and 10000 active particles. For the second test I allocate 100,000 particles in memory, and test with 10, 100, 1000, 5000, 10000, 50000, and 100000 active particles. Also, I run these tests 5 times and then take the average of the results.I implemented approach #1 just as a simple baseline for comparison (100%). I thought it would be the slowest since it allocates and de-allocates memory at run-time, which I've always heard is expensive and a no-no in particle systems.  However, it turns out that this approach gives the best results in the average case (static and random lifetimes, and when some particles are active, and many particles are active).Approach #2, which seems to be the most popular from the particle systems I've downloaded, gives the best performance (~150%) when all of the allocated particles are active, but gives the worst performance when less than half of the particles are active (10% - 50%).Approach #3, which I thought would be the fastest, gives about 90% - 100% performance on average using static particle lifetimes, but around 60% - 70% using random particle lifetimes.So if you know how many particles your effect will require (and allocate only that much memory), and that number remains constant through out the entire effect (which is not always the case), then approach #2 is the best. However, approach #1 seems to give the best performance in the average case. I tested this with a small Particle class (6 floats and 5 ints) and with a large particle class (36 floats and 5 ints), but it did not make much of a difference.So is there something I am missing here? How come approach #1 isn't horribly slow like most people say it should be? My only guess is that it's because I'm using C# and it must be handling the memory management like a champ hehe. Any thoughts?   
Quote:So is there something I am missing here? How come approach #1 isn't horribly slow like most people say it should be? My only guess is that it's because I'm using C# and it must be handling the memory management like a champ hehe. Any thoughts? Garbage-collected languages with generational compacting GC.Allocation is incrementing a pointer, about as fast as a stack allocation in C or C++.Collection defragments and the cost of a minor collection is proportional to the number of live objects, so allocating many objects is fine as long as their lifetime is short.After collection, objects are nicely packed into contiguous memory, which is cache-optimal.Pre-allocating an object pool in a generational-gc language is a bad idea, as it confuses the collector and allocation is virtually free anyway; instead of working with the gc and getting nicely cache-friendly access patterns after compaction, you incur major collection costs for unused objects in the pool and nonlocal access patterns for no gain, as objects in the pool aren't collected but put in the old generation.Work with the collector, not against it. The awesome thing is that working with the collector generally means doing the most straightforward thing.   ;Quote:So is there something I am missing here? How come approach #1 isn't horribly slow like most people say it should be? My only guess is that it's because I'm using C# and it must be handling the memory management like a champ hehe. Any thoughts?The reason is when you're testing, you're only allocate and deallocate particles only.  In a bigger app where there are other things that gets allocate, and destroy, then you run in to fragmentation.  It typically happens when you have limited memory to allocate.  When your memory are fragment then you might not able to allocate memory or your memory manager spend time to coalescing memory together to find a big enough block to allocate for you.  It's depends on how the memory manager is implemented.Also when you testing performance, you typically look at worse case, average case and best case, then depends on your which is suitable for you then use that.  Look into Big O, little o, and Big Theta for measurement of performance of algorithms.   ;  While it depends on how many particles are added, removed, such close results seem somewhat unusual.What if particles are implemented like this:    class Particles2    {   struct Particle {  public float x, y, z;  public float dx, dy, dz;   }   public Particles2(int maxParticles) {  max = maxParticles;  count = 0;  particles = new Particle[maxParticles];   }   public void update()   {  int i = 0;  while (i < count)  { float x = particles.x + particles.dx; float y = particles.y + particles.dy; float z = particles.z + particles.dz; if (x < 0 || y < 0 || z < 0) {remove(i);add(r.Next(1000), r.Next(1000), r.Next(1000), r.Next(100) - 50, r.Next(100 - 50), r.Next(100) - 50); } else {particles.x = x;particles.y = y;particles.z = z;i++; }  }   }   public void remove(int index)   {  count--;  if (count > 0)  { particles[index] = particles[count];  }   }   public void add(float x, float y, float z, float dx, float dy, float dz)   {  if (count < max)  { particles[count].x = x; particles[count].y = y; particles[count].z = z; particles[count].dx = dx; particles[count].dy = dy; particles[count].dz = dz; count++;  }   }   public int max;   int count;   Particle[] particles;   readonly Random r = new Random();    }Basically, a fixed-size struct array, elements are removed by replacing them with last element.I just ran a few quick tests comparing to LinkedList version. If no elements are removed, then struct array version is 4 times faster. If 90% of elements are removed on each pass, then array version is around 2 times faster.For very small number of particles (<100), both versions are approximately the same.The reason for your results sounds like you're using classes, in which case there would be no difference - biggest performance difference comes from memory access, and struct allows you to avoid an extra dereference. This is however achieved by having a single array, and only updating active elements, rather than moving the particles between two queues/arrays.   ;Quote:Original post by AntheusThe reason for your results sounds like you're using classes, in which case there would be no differenceYes, my Particle objects are classes, not structs;Quote:Original post by deadlydogQuote:Original post by AntheusThe reason for your results sounds like you're using classes, in which case there would be no differenceYes, my Particle objects are classes, not structsWrite a particle system that uses single array of structs. There are no fundamental limitations using that approach, the array can even be resized if needed (at one time cost of copying and allocation).However, using fixed array in this way performs no run-time allocations (no GC), the maximum number of particles is not really a limitation (it's only viable to have at most N particles per frame) and it maximizes cache utilization. These days, memory is where performance lies, CPUs have peaked several years ago.If Particle is large, then it may be feasible to add an "alive" flag. When iterating, update only alive particles, but ignore dead ones. Depending on usage, this may still be faster than actually moving data around.   ;  As long as your algorithms are pretty optimal in terms of their big-Oh notations then it should be fine either way.However you might find it even faster to just use a large array where each item includes an index of the next item, and "virtual lists" of used and unused particles are "embedded" within the array. That bypasses .NET's list class altogether.   ;Quote:Original post by iMalcAs long as your algorithms are pretty optimal in terms of their big-Oh notations then it should be fine either way.However you might find it even faster to just use a large array where each item includes an index of the next item, and "virtual lists" of used and unused particles are "embedded" within the array. That bypasses .NET's list class altogether.Cursors can be useful, but there are two reasons why they might not be needed for particle system:- order of iteration doesn't matter- primary purpose is fast iteration over all (or sequential part) of elementsDepending on how large particles are (affects the cost of copying), single array where elements are removed by replacing them with the last one is probably optimal. If elements get removed rarely (<10% on each pass), then optimizing for iteration is probably best, since it maximizes cache utilization.Cursor version might be slightly less efficient than LinkedList (gc can actually make LL better), but it has the benefit of performing no allocations, which is always good, and it's also where considerably benefits are to be had in real cases.Either way, while allocations are far from expensive, they are not free, and in many cases, they can be completely avoided without any considerable downside.   ;  Thanks for sharing these test results. Thats some good info.Quote:Original post by deadlydogApproach #2, which seems to be the most popular from the particle systems I've downloaded, gives the best performance (~150%) when all of the allocated particles are active, but gives the worst performance when less than half of the particles are active (10% - 50%).When there are only a few particles on the screen though, optimization doesn't really matter. It is performance with lots of particles that we really care about.Quote:Original post by deadlydogSo is there something I am missing here? How come approach #1 isn't horribly slow like most people say it should be? My only guess is that it's because I'm using C# and it must be handling the memory management like a champ hehe. Any thoughts?I suppose that approach #2 running at 150% doesn't make approach #1 "horribly slow", but it is a lot slower. With approach 2 you could put 50% more particles on the screen at the same performance. BTW, I'd be interested in seeing results on a 4th method:Approach 4: Create pool of particles in memory using an array of particle instances (just like #2 and #3). However, do not use queues for active/inactive. Simply use an active flag on each particle in the particle list itself. Precede Updates()/Draw() calls with "if(particle.active) ...".;  Have an array of MAX particles.When you need a particle grab par_array[count]. Increment count.When a particle dies decrement count, swap the particle with par_array[count].Update only count particles.If you use a linked list to allocated blocks of these arrays you can insure that par_array[count] can never overlap the cacheline of par_array thus insuring maximum performance.