🔒 Locked

Allocating particles in memory at run-time not slow?

Started by deadlydog Apr 23, 2009 at 10:43 AM 22 replies 6.6k views

Original Post

Apr 23, 2009 at 10:43 AM

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?

Anonymous P

Apr 23, 2009 at 11:05 AM

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.

nhatkthanh

Apr 23, 2009 at 11:28 AM

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.

Antheus

Apr 23, 2009 at 3:56 PM

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.

deadlydog

Apr 23, 2009 at 4:08 PM

Quote:
Original post by Antheus
The reason for your results sounds like you're using classes, in which case there would be no difference

Yes, my Particle objects are classes, not structs

Antheus

Apr 23, 2009 at 4:19 PM

Quote:
Original post by deadlydog
Quote:
Original post by Antheus
The reason for your results sounds like you're using classes, in which case there would be no difference

Yes, my Particle objects are classes, not structs

Write 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.

iMalc

Apr 24, 2009 at 4:01 AM

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.

Antheus

Apr 24, 2009 at 9:01 AM

Quote:
Original post by iMalc
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.

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 elements

Depending 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.

EJH

Apr 24, 2009 at 11:03 AM

Thanks for sharing these test results. Thats some good info.

Quote:
Original post by deadlydog
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%).

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 deadlydog
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?

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) ...".

KulSeran

Apr 24, 2009 at 11:09 AM

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.

raigan

Apr 24, 2009 at 11:28 AM

Quote:
Original post by Antheus
Write 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).

I might be really confused, but in C# don't structs become read-only when you store them in an array/list?

For instance the following code doesn't actually do anything to the ith particle:

particles.x = 20;

The value of particles.x will remain unchanged, because indexing into a list of structs returns the value and not a reference to the object that's in the list.

Which makes structs sort of useless as far as I can tell.. though I suspect I'm missing something since this seems crazy.

deadlydog

Apr 24, 2009 at 11:55 AM

Quote:
Original post by KulSeran
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.

Yup, I actually just implemented this method last night and it seems to give the best performance all around on average, for both static and random lifetimes. In total I implemented 8 different methods.

1 - Active Linked List with no pre-allocated memory. Just add particles to the linked list when they are needed, and delete them when they die.
2 - Array with linear search for inactive particles. Process entire array.
3 - Array with circular search for inactive particles. Process entire array.
4 - Array with swapping dead particles to the end of the active particles (method mentioned by KulSeran). Process only active particles.
5 - Array with an inactive queue to hold the inactive particle indexes. Process entire array.
6 - Array with an inactive queue and active list. Process only active particles.
7 - active LinkedList and inactive LinkedList holding the particle instances (no array, but memory is still pre-allocated since the linked list nodes are never "deleted", they are just moved back and forth between the linked lists). Process only active particles.
8 - Array with an active LinkedList and inactive LinkedList, where the linked lists hold pointers to the particles in the array. Process only active particles.

Before implementing method 4 last night, method 8 performed best with static lifetimes (but not very well with random lifetimes), method 1 with random lifetimes, and method 5 for both static and random lifetimes (but only when the number of active particles = the number of particles allocated in memory). Approach 1 was the best happy medium, however, like it was mentioned since my program isn't allocating / deallocating memory for other application resources at run-time, as would happen in a real application, this methods memory was staying sequential, where in a real application it would likely become fragmented and not perform as well.

But now that I've implemented method 4 it seems to be the all around winner, winning with both static and random lifetimes for all active particle amounts almost every time.

Quote:
Original post by raigan
I might be really confused, but in C# don't structs become read-only when you store them in an array/list?

For instance the following code doesn't actually do anything to the ith particle:

particles.x = 20;

The value of particles.x will remain unchanged, because indexing into a list of structs returns the value and not a reference to the object that's in the list.

Yup, you're right; which is why I use a Particle class, not a struct.

If you used a struct you would need to do something like:

Particle sTempParticleStruct = particles;  // Copy values into a new structsTempParticleStruct.x = 20;  // Update valuesparticles = sTempParticleStruct;  // Replace old particle with updated one

EJH

Apr 24, 2009 at 11:59 AM

Quote:
Original post by raigan
I might be really confused, but in C# don't structs become read-only when you store them in an array/list?

Hmm yeah I just tried and it doesn't allow them to be changed. I get the following errors:

"Cannot modify members of 's' because it is a 'foreach iteration variable'"

"Cannot modify the return value of System.Collections.Generic.List.this[int]' because it is not a variable"

On this code when trying to modify a struct by a For or Foreach loop:

using System;using System.Collections.Generic;using System.Linq;using System.Text;struct S{ public int x; public S(int x) { this.x = x; }}class Program{ static void Main(string[] args) { List<S> sList = new List<S>(); for(int i=0; i<5; i++) sList.Add(new S(1)); foreach (S s in sList) Console.WriteLine(s.x.ToString()); foreach (S s in sList) s.x = 0; for (int i = 0; i < 5; i++) sList.x = 0; foreach (S s in sList) Console.WriteLine(s.x.ToString()); }}

Antheus

Apr 24, 2009 at 12:58 PM

Quote:
Original post by raigan
Quote:
Original post by Antheus
Write 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).

I might be really confused, but in C# don't structs become read-only when you store them in an array/list?

        struct Foo        {            public int x, y;        }...            Foo[] foos = new Foo[10];            Console.WriteLine("{0}==0 {1}==0", foos[0].x, foos[0].y);            foos[0].x = 10;            Console.WriteLine("{0}==10 {1}==0", foos[0].x, foos[0].y);            foos[0].x = 12;            foos[0].y = 33;            Console.WriteLine("{0}==12 {1}==33", foos[0].x, foos[0].y);            Foo ff;            ff.x = 20;            ff.y = 11;            foos[0] = ff;            Console.WriteLine("{0}==20 {1}==11", foos[0].x, foos[0].y);

raigan

Apr 24, 2009 at 3:05 PM

I see -- so you can copy the value out, modify it, then copy it back into the list.

Given that you'll be modifying every particle every frame, isn't all this copying going to add up? Or does the dense array of structs make up for this (i.e by improving locality since all the particles are contiguous in memory rather than scattered around)?

Antheus

Apr 24, 2009 at 3:18 PM

Quote:
Original post by raigan
I see -- so you can copy the value out, modify it, then copy it back into the list.

Well, that's what one needs to do anyway. x += dx. Read the value, increment it, write it back. This is the same, regardless of how particles are represented, and they're just floats.

Quote:
Given that you'll be modifying every particle every frame, isn't all this copying going to add up? Or does the dense array of structs make up for this (i.e by improving locality since all the particles are contiguous in memory rather than scattered around)?

My quick and very dirty benchmarks say no. Copying only happens on particle removal.

The original implementation posted above is, as said, 2-4 times faster than LL equivalent. Some extra performance can be squeezed out by inlining add/remove calls. All these optimizations are fairly trivial since particle systems are frequently just trivial physics systems.

Another observation is, that on each iteration, only a small number of particles will be added or removed. If more than 50% of original particles survive on single pass, then struct array is usually better.

I update/assign in two places, rather than particles.x += particles.dx; This allows me to do real work with stack variables, which brings considerable performance improvement as well (about 2x compared to +=).

Lastly, and perhaps the most important in managed languages - this algorithm does not use GC at all. And this is always good for real-time applications.

But in general, never underestimate benefits of sequential access, regardless of language.

raigan

Apr 24, 2009 at 5:18 PM

Quote:
Original post by Antheus

Well, that's what one needs to do anyway. x += dx. Read the value, increment it, write it back. This is the same, regardless of how particles are represented, and they're just floats.

I see, that makes total sense. Unless the particle class is less lightweight, right? i.e if each particle has mass, gravity vector, damping, array of previous positions, etc.

But I don't know what the tipping point would be, possibly the struct would have to be quite huge to make a difference. And I guess at that point you could just split it into two parallel arrays, one full of frequently-written data and one with everything else..

Quote:
Original post by Antheus
The original implementation posted above is, as said, 2-4 times faster than LL equivalent.

Wouldn't an array of class instances (used similarly to the array of structs) be a more fair comparison? I'm unclear why you'd want to use LL at all anyway rather than a nice simple array. Unless, since the references might point all over, a LL isn't any less coherent.

Sorry for the stupid questions, I'm still a noob :(

Antheus

Apr 24, 2009 at 7:28 PM

Quote:
Original post by raigan

I see, that makes total sense. Unless the particle class is less lightweight, right? i.e if each particle has mass, gravity vector, damping, array of previous positions, etc.

This is why profiling is mandatory. Splitting into two arrays (read-only and read write may perhaps make some sense), but in case of removal, one still needs to copy both.

Quote:
I'm unclear why you'd want to use LL at all anyway rather than a nice simple array. Unless, since the references might point all over, a LL isn't any less coherent.

Because OP compared to LL. I only cared about fast(er) way to get the job done, and I haven't really done any such profiling in C# before, so it was a nice experiment.

For memory optimization see here (ppt). It covers all techniques mentioned including hot/cold splitting, and much more.

deadlydog

May 6, 2009 at 5:38 PM

Quote:
Original post by deadlydog
But now that I've implemented method 4 it seems to be the all around winner, winning with both static and random lifetimes for all active particle amounts almost every time.

Number 4 is definitely wins when it comes to performance, but after actually implementing it in a real particle system I've realized one thing that I overlooked with this approach. When a particle dies it gets moved to the end of the list and the position in the array where that particle was gets replaced with the last active particle in the list, and the total number of Active particles is decremented.

When the particles are copied into the vertex buffer, I loop over all of the active particles, starting from the end of the Active Particles section of the array to the start of the array (newest particles are drawn first so that older particles are drawn over top of them). Also, most particle systems have the RenderState.DepthWriteEnabled set to false to avoid sorting thousands of particles by depth, saving on execution time and increasing performance.

The problem is that since depth sorting is not enabled, the particles are drawn in the order that they appear in the vertex buffer. So when a particle dies it's position in the array is replaced by the newest particle added to the particle system (since new particles are added to the end of the Active particles list). When this happens that new particle which used to be behind most of the other particles is suddenly drawn on top of all of the particles, since its position in the array moved from the end to (possibly) near the start of the array.

So as the particle system simulation runs you can notice that particles suddenly jump to the front of the array and are drawn on top of other particles.

Can anyone think of a simple solution to this problem? One approach would be to resort the active particles based on age after each update. However this would kill performance and I would be better off just using approach number 8, which gave the 2nd best average performance.

Any ideas on how to solve this problem easily would be appreciated. If I can't find any I will likely end up sticking with approach number 8. Thanks.

Zahlman

May 6, 2009 at 7:32 PM

Quote:
Original post by raigan
I see -- so you can copy the value out, modify it, then copy it back into the list.

Given that you'll be modifying every particle every frame, isn't all this copying going to add up? Or does the dense array of structs make up for this (i.e by improving locality since all the particles are contiguous in memory rather than scattered around)?

Just FWIW: if you're iteratively making changes to the entire list, you can iteratively make modified copies and put them in a new list, then rebind to the new list and let the old one get GCd.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.