I was going to implement an object pool for my particle system in Java, then I found this on Wikipedia. To rephrase, it says that object pools aren't worth using in managed languages like Java and C#, because allocations take just tens of operations as compared to hundreds in unmanaged languages like C++.

But as we all know, every instruction may hurt game performance. For example, a pool of clients in an MMO: the clients won't enter and exit the pool too fast. But particles may get renewed tens of times in a second.

The question is: is it worth it to use an object pool for particles (specifically, those that die and get recreated fast) in a managed language?

up vote 14 down vote accepted

Yes, it is.

Allocation time isn't the only factor. Allocation can have side-effects, such as inducing a garbage collection pass, which can not only impact performance negatively it can also impact performance unpredictably. The specifics of this will depend on your language and platform choices.

Pooling also generally improves locality of reference for the objects in the pool, for example by keeping them all in contiguous arrays. This can improve performance while iterating the contents of the pool (or at least the live portion thereof) because the next object in the iteration will tend to already be in the data cache.

The conventional wisdom of trying to avoid any allocations whatsoever in your innermost game loops still applies even in managed languages (especially on, for example, the 360 when using XNA). The reasons for it just differ slightly.

  • +1 But, you didn't touch on whether it's worthwhile when using structs: basically it's not (pooling value types achieves nothing) - instead you should have a single (or possible a set of) array to manage them instead. – Jonathan Dickinson Mar 7 '12 at 17:04
  • 2
    I didn't touch on the struct thing since the OP mentioned using Java and I am not as familiar with how value types/structures operate in that language. – Josh Mar 7 '12 at 17:08
  • There are no structs in Java, only classes (always on the heap). – Brendan Long Mar 7 '12 at 23:57

For Java it's not so helpful to pool objects* since the first GC cycle for objects still around will reshuffle them in memory, moving them out of "Eden" space and potentially losing spatial locality in the process.

  • It is always useful in any language to pool complex resources which are very expensive to destroy and create like threads. Those can be worth pooling because the expense of creating and destroying them has almost nothing to do with the memory associated with the object handle to the resource. However, particles do not fit this category.

Java offers fast burst allocation using a sequential allocator when you rapidly allocate objects into Eden space. That sequential allocation strategy is super fast, faster than malloc in C since it's just pooling memory already allocated in a straight sequential fashion, but it comes with the downside that you can't free individual chunks of memory. It's also a useful trick in C if you just want to allocate things super fast for, say, a data structure where you don't need to remove anything from it, just add everything and then use it and toss the whole thing away later.

Because of this downside of not being able to free individual objects, the Java GC, after a first cycle, will copy all the memory allocated from Eden space to new memory regions using a slower, more general-purpose memory allocator that does allow memory to be freed in individual chunks in a different thread. Then it can toss away the memory allocated in Eden space as a whole without bothering with individual objects which have now been copied and live elsewhere in memory. After that first GC cycle, your objects can end up being fragmented in memory.

Since the objects can end up being fragmented after that first GC cycle, the benefits of object pooling when it's primarily for the sake of improving memory access patterns (locality of reference) and reducing allocation/deallocation overhead are largely lost... so much so that you'll get better locality of reference typically by just allocating new particles all the time and use them while they're still fresh in Eden space and before they become "old" and potentially scattered in memory. However, what can be extremely helpful (like getting performance rivaling C in Java) is to avoid using objects for your particles and pool plain old primitive data. For a simple example, instead of:

class Particle
{
    public float x;
    public float y;
    public boolean alive;
}

Do something like:

class Particles
{
    // X positions of all particles. Resize on demand using
    // 'java.util.Arrays.copyOf'. We do not use an ArrayList
    // since we want to work directly with contiguously arranged
    // primitive types for optimal memory access patterns instead 
    // of objects managed by GC.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];
}

Now to reuse memory for existing particles, you can do this:

class Particles
{
    // X positions of all particles.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];

    // Next free position of all particles.
    public int next_free[];

    // Index to first free particle available to reclaim
    // for insertion. A value of -1 means the list is empty.
    public int first_free;
}

Now when the nth particle dies, to allow it to be reused, push it to the free list like so:

alive[n] = false;
next_free[n] = first_free;
first_free = n;

When adding a new particle, see if you can pop an index from the free list:

if (first_free != -1)
{
     int index = first_free;

     // Pop the particle from the free list.
     first_free = next_free[first_free];

     // Overwrite the particle data:
     x[index] = px;
     y[index] = py;
     alive[index] = true;
     next_free[index] = -1;
}
else
{
     // If there are no particles in the free list
     // to overwrite, add new particle data to the arrays,
     // resizing them if needed.
}

It's not the most pleasant code to work with, but with this you should be able to get some very fast particle simulations with sequential particle processing being very cache-friendly always since all the particle data will always be stored contiguously. This type of SoA rep also reduces memory usage since we don't have to worry about padding, the object metadata for reflection/dynamic dispatch, and it splits hot fields away from cold fields (for example, we're not necessarily concerned with data fields like a particle's color during the physics pass so it'd be wasteful to load it into a cache line only to not use it and evict it).

To make the code easier to work with, it might be worth writing your own basic resizable containers that store arrays of floats, arrays of integers, and arrays of booleans. Again you can't use generics and ArrayList here (at least since the last time I checked) since that requires GC-managed objects, not contiguous primitive data. We want to use contiguous array of int, e.g., not GC-managed arrays of Integer which won't necessarily be contiguous after leaving Eden space.

With arrays of primitive types, they're always guaranteed to be contiguous, and so you get the extremely desirable locality of reference (for sequential particle processing it makes a world of difference) and all the benefits that object pooling is intended to provide. With an array of objects, it is instead somewhat analogous to an array of pointers which start out pointing to the objects in a contiguous fashion assuming you allocated them all at once into Eden space, but after a GC cycle, can be pointing all over the place in memory.

  • 1
    This is a nice write-up on the matter, and after 5 years of java coding I can see it clearly; Java GC certainly isn't dumb, neither was it made for game programming (since it doesnt really care for data locality and stuff), so we better play as it pleases :P – Gustavo Maciel Jan 2 at 16:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.