Object Pool

Game Programming PatternsOptimization Patterns

Intent

Improve performance and memory use by reusing objects from a fixed pool insteadof allocating and freeing them individually.

Motivation

We’re working on the visual effects for our game. When the hero casts a spell,we want a shimmer of sparkles to burst across the screen. This calls for aparticle system, an engine that spawns little sparkly graphics and animatesthem until they wink out of existence.

Since a single wave of the wand could cause hundreds of particles to be spawned,our system needs to be able to create them very quickly. More importantly, weneed to make sure that creating and destroying these particles doesn’t causememory fragmentation.

The curse of fragmentation

Programming for a game console or mobile device is closer to embeddedprogramming than conventional PC programming in many ways. Memory is scarce,users expect games to be rock solid, and efficient compacting memory managersare rarely available. In this environment, memory fragmentation is deadly.

Fragmentation means the free space in our heap isbroken into smaller pieces of memory instead of one largeopen block. Thetotal memory available may be large, but the largestcontiguous region might be painfully small. Say we’ve got fourteen bytes free,but it’s fragmented into two seven-byte pieces with a chunk of in-use memorybetween them. If we try to allocate a twelve-byte object, we’ll fail. No moresparklies on screen.

The best of both worlds

Because of fragmentation and because allocation may be slow, games are verycareful about when and how they manage memory. A simple solution is often best —grab a big chunk of memory when the game starts, and don’t free it until the gameends. But this is a pain for systems where we need to create and destroy thingswhile the game is running.

An object pool gives us the best of both worlds. To the memory manager, we’rejust allocating one big hunk of memory up front and not freeing it while thegame is playing. To the users of the pool, we can freely allocate and deallocateobjects to our heart’s content.

The Pattern

Define apool class that maintains a collection ofreusable objects.Each object supports an“in use” query to tell if it is currently “alive”.When the pool is initialized, it creates the entire collection of objects upfront (usually in a single contiguous allocation) and initializes them all tothe “not in use” state.

When you want a new object, ask the pool for one. It finds an available object,initializes it to “in use”, and returns it. When the object is no longer needed,it is set back to the “not in use” state. This way, objects can be freelycreated and destroyed without needing to allocate memory or other resources.

When to Use It

This pattern is used widely in games for obvious things like game entities andvisual effects, but it is also used for less visible data structures such as currentlyplaying sounds. Use Object Pool when:

• You need to frequently create and destroy objects.

• Objects are similar in size.

• Allocating objects on the heap is slow or could lead to memory fragmentation.

• Each object encapsulates a resource such as a database or network connection that is expensive to acquire and could be reused.

Keep in Mind

You normally rely on a garbage collector ornew anddelete to handlememory management for you. By using an object pool, you’re saying, “I knowbetter how these bytes should be handled.” That means the onus is on you to dealwith this pattern’s limitations.

The pool may waste memory on unneeded objects

The size of an object pool needs to be tuned for the game’s needs. When tuning,it’s usually obvious when the pool is toosmall (there’s nothing like a crashto get your attention). But also take care that the pool isn’t toobig. Asmaller pool frees up memory that could be used for other fun stuff.

Only a fixed number of objects can be active at any one time

In some ways, this is a good thing. Partitioning memory into separate pools fordifferent types of objects ensures that, for example, a huge sequence ofexplosions won’t cause your particle system to eatall of the availablememory, preventing something more critical like a new enemy from being created.

Nonetheless, this also means being prepared for the possibility that yourattempt to reuse an object from the pool will fail because they are all in use.There are a few common strategies to handle this:

• Prevent it outright. This is the most common “fix”: tune the pool sizes so that they never overflow regardless of what the user does. For pools of important objects like enemies or gameplay items, this is often the right answer. There may be no “right” way to handle the lack of a free slot to create the big boss when the player reaches the end of the level, so the smart thing to do is make sure that never happens.

  The downside is that this can force you to sit on a lot of memory for objectslots that are needed only for a couple of rare edge cases. Because of this,a single fixed pool size may not be the best fit for all game states. Forinstance, some levels may feature effects prominently while others focus onsound. In such cases, consider having pool sizes tuned differently for eachscenario.

• Just don’t create the object. This sounds harsh, but it makes sense for cases like our particle system. If all particles are in use, the screen is probably full of flashing graphics. The user won’t notice if the next explosion isn’t quite as impressive as the ones currently going off.

• Forcibly kill an existing object. Consider a pool for currently playing sounds, and assume you want to start a new sound but the pool is full. You donot want to simply ignore the new sound — the user will notice if their magical wand swishes dramaticallysometimes and stays stubbornly silent other times. A better solution is to find the quietest sound already playing and replace that with our new sound. The new sound will mask the audible cutoff of the previous sound.

  In general, if thedisappearance of an existing object would be lessnoticeable than theabsence of a new one, this may be the right choice.

• Increase the size of the pool. If your game lets you be a bit more flexible with memory, you may be able to increase the size of the pool at runtime or create a second overflow pool. If you do grab more memory in either of these ways, consider whether or not the pool should contract to its previous size when the additional capacity is no longer needed.

Memory size for each object is fixed

Most pool implementations store the objects in an array of in-place objects. Ifall of your objects are of the same type, this is fine. However, if you want tostore objects of different types in the pool, or instances of subclasses thatmay add fields, you need to ensure that each slot in the pool has enough memoryfor thelargest possible object. Otherwise, an unexpectedly large object willstomp over the next one and trash memory.

At the same time, when your objects vary in size, you waste memory. Each slotneeds to be big enough to accommodate the largest object. If objects are rarelythat big, you’re throwing away memory every time you put a smaller one in thatslot. It’s like going through airport security and using a huge carry-on-sizedluggage tray just for your keys and wallet.

When you find yourself burning a lot of memory this way, consider splitting thepool intoseparate pools for different sizes ofobject — big trays for luggage, little trays for pocket stuff.

Reused objects aren’t automatically cleared

Most memory managers have a debug feature that will clear freshly allocated orfreed memory to some obvious magic value like0xdeadbeef. This helps you findpainful bugs caused by uninitialized variables or using memory after it’s freed.

Since our object pool isn’t going through the memory manager any more when itreuses an object, we lose that safety net. Worse, the memory used for a “new”object previously held an object of the exact same type. This makes it nearlyimpossible to tell if you forgot to initialize something when you created thenew object: the memory where the object is stored may already containalmostcorrect data from its past life.

Because of this, pay special care that the code that initializes new objects inthe poolfully initializes the object. It may even be worth spending a bit oftime adding a debug feature thatclears the memory foran object slot when the object is reclaimed.

Unused objects will remain in memory

Object pools are less common in systems that support garbage collection becausethe memory manager will usually deal with fragmentation for you. But pools arestill useful there to avoid the cost of allocation and deallocation, especiallyon mobile devices with slower CPUs and simpler garbage collectors.

If you do use an object pool in concert with a garbage collector, beware of a potential conflict. Since thepool doesn’t actually deallocate objects when they’re no longer in use, theyremain in memory. If they contain references toother objects, it will preventthe collector from reclaiming those too. To avoid this, when a pooled object isno longer in use, clear any references it has to other objects.

Sample Code

Real-world particle systems will often apply gravity, wind, friction, and otherphysical effects. Our much simpler sample will only move particles in a straightline for a certain number of frames and then kill the particle. Not exactly filmcaliber, but it should illustrate how to use an object pool.

We’ll start with the simplest possible implementation. First up is the littleparticle class:

classParticle{public:Particle():framesLeft_(0){}voidinit(doublex,doubley,doublexVel,doubleyVel,intlifetime){x_=x;y_=y;xVel_=xVel;yVel_=yVel;framesLeft_=lifetime;}voidanimate(){if(!inUse())return;framesLeft_--;x_+=xVel_;y_+=yVel_;}boolinUse()const{returnframesLeft_>0;}private:intframesLeft_;doublex_,y_;doublexVel_,yVel_;};

The default constructor initializes the particle to “not in use”. A later calltoinit() initializes the particle to a live state. Particles are animatedover time using the unsurprisingly namedanimate() function, which should becalled once per frame.

The pool needs to know which particles are available for reuse. It gets thisfrom the particle’sinUse() function. This function takes advantage of the fact thatparticles have a limited lifetime and uses theframesLeft_ variable todiscover which particles are in use without having to store a separate flag.

The pool class is also simple:

classParticlePool{public:voidcreate(doublex,doubley,doublexVel,doubleyVel,intlifetime);voidanimate(){for(inti=0;i<POOL_SIZE;i++){particles_[i].animate();}}private:staticconstintPOOL_SIZE=100;Particleparticles_[POOL_SIZE];};

Thecreate() function lets external code create new particles. The game callsanimate() once per frame, which in turn animateseach particle in the pool.

Thisanimate() method is an example of theUpdate Method pattern.

The particles themselves are simply stored in a fixed-size array in the class.In this sample implementation, the pool size is hardcoded in the classdeclaration, but this could be defined externally by using a dynamic array of agiven size or by using a value template parameter.

Creating a new particle is straightforward:

voidParticlePool::create(doublex,doubley,doublexVel,doubleyVel,intlifetime){// Find an available particle.for(inti=0;i<POOL_SIZE;i++){if(!particles_[i].inUse()){particles_[i].init(x,y,xVel,yVel,lifetime);return;}}}

We iterate through the pool looking for the first available particle. When wefind it, we initialize it and we’re done. Note that in this implementation, ifthere aren’t any available particles, we simply don’t create a new one.

That’s all there is to a simple particle system, aside from rendering theparticles, of course. We can now create a pool and create some particles usingit. The particles will automatically deactivate themselves when their lifetimehas expired.

This is good enough to ship a game, but keen eyes may have noticed that creatinga new particle requiresiterating through(potentially) the entire collection until we find an open slot. If the pool isvery large and mostly full, that can get slow. Let’s see how we can improvethat.

A free list

If we don’t want to waste timefinding free particles, the obvious answer isto not lose track of them. We could store a separate list of pointers to eachunused particle. Then, when we need to create a particle, we remove thefirst pointer from the list and reuse the particle it points to.

Unfortunately, this would require us to maintain an entire separate array withas many pointers as there are objects in the pool. After all, when we firstcreate the pool,all particles are unused, so the list would initially have apointer to every object in the pool.

It would be nice to fix our performance problemswithout sacrificing anymemory. Conveniently, there is some memory already lying around that we can borrow —the data for the unused particles themselves.

When a particle isn’t in use, most of its state is irrelevant. Its position andvelocity aren’t being used. The only state it needs is the stuff required totell if it’s dead. In our example, that’s theframesLeft_ member. All thoseother bits can be reused. Here’s a revised particle:

classParticle{public:// ...Particle*getNext()const{returnstate_.next;}voidsetNext(Particle*next){state_.next=next;}private:intframesLeft_;union{// State when it's in use.struct{doublex,y;doublexVel,yVel;}live;// State when it's available.Particle*next;}state_;};

We’ve moved all of the member variables except forframesLeft_into alive struct inside astate_union. Thisstruct holds the particle’s state when it’s being animated. When the particle isunused, the other case of the union, thenext member, is used. It holds apointer to the next available particle after this one.

This clever technique is called afreelist. For it to work, we need to makesure the pointers are initialized correctly and are maintained when particlesare created and destroyed. And, of course, we need to keep track of the list’shead:

classParticlePool{// ...private:Particle*firstAvailable_;};

When a pool is first created,all of the particles are available, so our freelist should thread through the entire pool. The pool constructor sets that up:

ParticlePool::ParticlePool(){// The first one is available.firstAvailable_=&particles_[0];// Each particle points to the next.for(inti=0;i<POOL_SIZE-1;i++){particles_[i].setNext(&particles_[i+1]);}// The last one terminates the list.particles_[POOL_SIZE-1].setNext(NULL);}

Now to create a new particle, we jump directly to thefirst available one:

voidParticlePool::create(doublex,doubley,doublexVel,doubleyVel,intlifetime){// Make sure the pool isn't full.assert(firstAvailable_!=NULL);// Remove it from the available list.Particle*newParticle=firstAvailable_;firstAvailable_=newParticle->getNext();newParticle->init(x,y,xVel,yVel,lifetime);}

boolParticle::animate(){if(!inUse())returnfalse;framesLeft_--;x_+=xVel_;y_+=yVel_;returnframesLeft_==0;}

voidParticlePool::animate(){for(inti=0;i<POOL_SIZE;i++){if(particles_[i].animate()){// Add this particle to the front of the list.particles_[i].setNext(firstAvailable_);firstAvailable_=&particles_[i];}}}

Design Decisions

As you’ve seen, the simplest object pool implementation is almost trivial:create an array of objects and reinitialize them as needed. Production code israrely that minimal. There are several ways to expand on that to make the poolmore generic, safer to use, or easier to maintain. As you implement pools inyour games, you’ll need to answer these questions:

Are objects coupled to the pool?

The first question you’ll run into when writing an object pool is whether theobjects themselves know they are in a pool. Most of the time they will, but youwon’t have that luxury when writing a generic pool class that can hold arbitraryobjects.

• If objects are coupled to the pool:

  • The implementation is simpler. You can simply put an “in use” flag or function in your pooled object and be done with it.

  • You can ensure that the objects can only be created by the pool. In C++, a simple way to do this is to make the pool class a friend of the object class and then make the object’s constructor private.

    classParticle{friendclassParticlePool;private:Particle():inUse_(false){}boolinUse_;};classParticlePool{Particlepool_[100];};

    This relationship documents the intended way to use the class andensures your users don’t create objects that aren’t tracked by the pool.

  • You may be able to avoid storing an explicit “in use” flag. Many objects already retain some state that could be used to tell whether it is alive or not. For example, a particle may be available for reuse if its current position is offscreen. If the object class knows it may be used in a pool, it can provide aninUse() method to query that state. This saves the pool from having to burn some extra memory storing a bunch of “in use” flags.

• If objects are not coupled to the pool:

  • Objects of any type can be pooled. This is the big advantage. By decoupling objects from the pool, you may be able to implement a generic reusable pool class.

  • The “in use” state must be tracked outside the objects. The simplest way to do this is by creating a separate bit field:

    template<classTObject>classGenericPool{private:staticconstintPOOL_SIZE=100;TObjectpool_[POOL_SIZE];boolinUse_[POOL_SIZE];};

What is responsible for initializing the reused objects?

In order to reuse an existing object, it must be reinitialized with new state. Akey question here is whether to reinitialize the object inside the pool class oroutside.

• If the pool reinitializes internally:

  • The pool can completely encapsulate its objects. Depending on the other capabilities your objects need, you may be able to keep them completely internal to the pool. This makes sure that other code doesn’t maintain references to objects that could be unexpectedly reused.

  • The pool is tied to how objects are initialized. A pooled object may offer multiple functions that initialize it. If the pool manages initialization, its interface needs to support all of those and forward them to the object.

    classParticle{// Multiple ways to initialize.voidinit(doublex,doubley);voidinit(doublex,doubley,doubleangle);voidinit(doublex,doubley,doublexVel,doubleyVel);};classParticlePool{public:voidcreate(doublex,doubley){// Forward to Particle...}voidcreate(doublex,doubley,doubleangle){// Forward to Particle...}voidcreate(doublex,doubley,doublexVel,doubleyVel){// Forward to Particle...}};

• If outside code initializes the object:

  • The pool’s interface can be simpler. Instead of offering multiple functions to cover each way an object can be initialized, the pool can simply return a reference to the new object:

    classParticle{public:// Multiple ways to initialize.voidinit(doublex,doubley);voidinit(doublex,doubley,doubleangle);voidinit(doublex,doubley,doublexVel,doubleyVel);};classParticlePool{public:Particle*create(){// Return reference to available particle...}private:Particlepool_[100];};

    The caller can then initialize the object by calling any method theobject exposes:

    ParticlePoolpool;pool.create()->init(1,2);pool.create()->init(1,2,0.3);pool.create()->init(1,2,3.3,4.4);

  • Outside code may need to handle the failure to create a new object. The previous example assumes thatcreate() will always successfully return a pointer to an object. If the pool is full, though, it may returnNULL instead. To be safe, you’ll need to check for that before you try to initialize the object:

    Particle*particle=pool.create();if(particle!=NULL)particle->init(1,2);

See Also

• This looks a lot like the Flyweight pattern. Both maintain a collection of reusable objects. The difference is what “reuse” means. Flyweight objects are reused by sharing the same instance between multiple ownerssimultaneously. The Flyweight pattern avoidsduplicate memory usage by using the same object in multiple contexts.

  The objects in a pool get reused too, but only over time. “Reuse” in thecontext of an object pool means reclaiming the memory for an objectafterthe original owner is done with it. With an object pool, there isn’t anyexpectation that an object will be shared within its lifetime.

• Packing a bunch of objects of the same type together in memory helps keep your CPU cache full as the game iterates over those objects. TheData Locality pattern is all about that.