Motivation

Often in games there will be many objects, which need to be created when the gameplay progresses. For example if there are enemies the player needs to combat, those enemies will need to be created at some point. The gameplay may require more enemies to be created once the first set of them has been defeated. This will cause a number of memory allocations and deallocations, as the enemies are created and destroyed. Of course the actual memory usage will depend on the number of enemies and how much memory is required for one enemy. When one enemy requires a lot of memory or there is a considerable number of them, you program may take a performance hit: the game freezes for a second, when a new wave of enemies is created.

This allocation and deallocation of memory can also lead to memory fragmentation. Meaning that if you ask and release chunks of memory with different size, there will be gaps of free memory, which can not be used, because nothing fits there. Furthermore your objects will get spread out in the memory (you lose data locality) and accessing all of them will take longer. For example if you have a list of enemies and want to access them all at some point.

This is one of the reasons games have a loading screen. During that a (hopefully) sufficient amount of memory is pre-allocated and filled with objects that the game uses. Those objects will be marked as dead or inactive, so that they do not cost performance. When it comes a time to create new objects (like new Enemy() or new A()), then instead the pre-created objects will have their variables reset and marked as alive or active. The pattern used to handle such functionality is called the object pool. It pools together a number of created objects and allows you to take one object for use without allocating new memory in the process.

Of course the pool needs to be able to track the alive and dead objects correctly and optimally.

Structure

Depending on your actual implementation the classes may be different. The diagram above can describe an implementation, where the ObjectPool will update and check each alive Object if they are still alive. If they happen to be dead at some point, the pool needs to know not to check that object again. When a GetObject() is called on the pool, the pool needs to take one of the dead objects, mark it alive and know that this objects needs to be checked.

It may happen that the more optimal way for you is to have a method ReleaseObject(Object) in the pool and when an object dies, it calls that method. Upon which the pool will know to release that object from all the alive objects.

Actual structure may vary, but the important things are that:

• Objects have a state dead / alive
• Pool knows about all the dead and all the alive objects at all times
• Pool can serve a dead object to be used (making it alive in the process)
• Objects can reset all their variables to some initial values if need be

Implementation

There are several ways to implement an object pool. The textbook also describes some additional implementations.

The most simple implementation would include two lists in the ObjectPool class, which hold the dead and alive objects. When an object changes its state, it is searched from the corresponding list and moved to another one.

Although this implementation is quite easy to understand, the problem is that searching the list can be quite slow. Furthermore the two lists will always change their size and data locality could be compromised.

A better way to implement an object pool is by using only one list and partitioning it such that alive objects are on one side of it and dead objects on the other side. In that case we need to keep track of the index of the first dead object. When a new object is requested, we make the object under the index alive and increase the index. When an alive object dies, we swap it with the last alive object in the list and decrease the index.

On the right there is a live example with a particle system. Particle systems often include a large number of objects (particles), which have some lifetime. So the particles are constantly created and destroyed. This is one of the prime cases, where to use object pooling. The current example includes:

• Naive implementation – No pooling is implemented. Particles are constantly created and destroyed (allocating and deallocating memory)
• Pool implementation – The simple implementation with two lists described above.
• Fast Pool implementation – The optimized implementation with one list described above.

You can probably see that using the simple implementation of an object pool increases the performance by at least half. Then the implementation with one list will increase it by at least half once more over the simple implementation.

You can also notice that using object pooling does have an impact on the overall memory usage. Your pool should be sufficiently large to support the estimated number of objects you plan to create. Intuitively you can make it 1.5 or 2 times bigger then the estimated number of objects, just to be safe.

Of course you can probably figure out a implementation, where the size of the pool increases or decreases dynamically. If you really can not estimate the number of your objects, then that might be a good solution. Although that will have a small impact on the performance as new memory needs to be allocated on the fly.

Example Uses

Like mentioned above, you should use an object pool when:

• You have to create and destroy a large number (~100+) of small objects often
• You have to create and destroy a small number (~10) of large objects often

Because this is an optimization pattern, then it is recommended to implement it when you foresee or already have problems with performance.

Prime examples include:

• Particle systems – Often quite a large number of small objects with lifetime.
• Enemies – Often small in number, but large in memory footprint. Usually created in bulk and destroyed by the user.

Note that sometimes even if you have a single object, which has a large memory footprint (a Boss for example) then you would want to create it during a loading screen and just hide it (mark as dead) until the player actually needs to see or interact with it. It would not be an object pool though, as there is only one object, which does not frequently change its state (unless you spawn multiple instance of the Boss and respawn them after they have died).