Deep dive: The design and implementation of object pools

This post first appeared on our blog at Gamelogic.

In software development, particularly in game development and real-time applications, efficient memory management is crucial for maintaining optimal performance. One common technique employed to manage objects efficiently is known as object pooling.

An object pool is a design pattern that pre-allocates a set of objects and keeps them ready for use, rather than creating and destroying objects on the fly. This pool of objects can be reused, significantly reducing the overhead of object creation and garbage collection.

If you are a game programmer, you may have seen the pattern described in Robert Bystrom’s Game Design Patterns. His description and implementation are more relevant to languages such as C++.

Here we look at the design and implementation of pools with a focus on C## and Unity. We will also look at some basic variations, and how the design changes if we require that the onbjects implement an interface. We look at some design techniques that come up in the implementation of pools, and finally, I give what I think is a set of best practices when it comes to the implementation of pools.

Here is more specifically the problems we can solve with an object pool:

Repeatedly obtaining some resource (such as new objects or network connections) creates performance problems.

Allocating and deallocating lots of objects causes garbage collection pauses.

The number of resources of a certain type is limited, or you want to limit them. The number of simultaneous environment sounds is one example.

Our memory allocation pattern causes memory fragmentation, which can make it harder to get big blocks of memory.

The easiest way to implement an object pool is to use a stack of inactive objects.

This implementation suffers from a few issues:

We need to repeat the three methods whenever we want an object pool. This is especially problematic when we need more than one pool in the same class.

We need to slightly modify the stack and methods for different types.

We could accidentally modify the stack in a way that is inconsistent with how we use it as a pool.

Running out of objects is handled poorly.

We need to remember to activate and deactivate objects when getting them from the stack and releasing them.

The code becomes messy if we want to implement a pool policy, such as behavior to execute when we do not have enough inactive objects.

We can solve these issues by encapsulating the methods in a class, and adding a few small features. Since we will be introducing more pool types later, here is the common interface they all will implement:

And here is our stack-based implementation of this interface:

Note the following:

It is much easier to use the pool anywhere we need it.

The stack cannot be accidentally modified by a user.

It is generic, so we can pool objects of different types. To allow this we have to take in the createActive function.

The pool automatically activates and deactivates objects as they are being obtained and released. To allow this we have to take activate and deactivate actions.

The pool provides a way for the user to check whether there is an object available, and throws an exception when the user tries to get an object but cannot.

The pool supports crude resizing. To allow this, we take a destroy action.

The pool user needs to supply the pool with four delegates. Here are notes on how these delegates should be implemented.

createActive: This function should create an active object. The pool will deactivate them after they have been created. If this seems slightly counter-intuitive, note that creation functions (such as Unity’s Instantiate) usually give objects that are active by default, so if we required users to supply inactive objects, they would have to deactivate the objects themselves.

This function should do any work that does not need to be repeated, including allocating the resources for the class to use. If you create and destroy objects in your activate and deactivate actions, that could work against your pooling strategy — so instead those objects should be created and destroyed in the create and destroy delegates, and made active and inactive as the main object itself.

activate: This action should prepare the object for use, for example, make it visible, start coroutines, etc. This action should not create objects. Be careful to not accidentally allocate memory when activating objects (for example, by duplicating a material by setting its color or calling an allocating LINQ method).

deactivate: This action should make the object inactive: make it invisible, stop its update from running, stop coroutines, and so on. It should also make any of the objects it controls inactive, especially if they were created or became active after the object itself became active.

If the object acquired resources that cannot be reused, this action should release them. (If this behavior of your object causes garbage collection pauses, you need to redesign how these resources are managed so they too can be reused instead.)

destroy: This action is only invoked when the capacity of the stack is reduced. It should destroy the object if it is required to do so, as is the case with Unity objects. Generally, this object should not replicate any work of the deactivate action. Instead, the pool should invoke the deactivate action before destroying objects if this is necessary.

Our StackPool class is still pretty crude. In this section, we will look at some variations of pools that are more robust or implement specific pooling policies.

Self-growing pool: Automatically increases capacity as needed.

Active object tracking pool: Keeps track of active objects too, allowing us to forcibly release objects when needed.

Priority pools: Can release active objects based on priorities assigned to them.

Fake pools: Do not really pool and are used for benchmarking.

This pool increases the pool capacity when we need an object and we are out of inactive objects.

We usually start the pool at capacity 0, so it never creates more objects than is required. We usually grow the capacity by one if needed, but if there is overhead involved, we may grow it by a larger number to reduce the effect of this overhead. It is common to allow the user to specify a maximum capacity.

Our simple StackPool does not keep track of objects obtained through Get. This has some problems:

If the user forgets to release objects, they are lost forever.

There is no easy way to release all objects.

We cannot reduce the pool capacity below the number of inactive objects in a robust way.

There is no guarantee that we created an object we are asked to release (potentially causing very subtle bugs).

We can address these issues if we also keep track of the active objects we hand over to the user. For the collection of active objects, we need a data structure that allows us to add and remove specific objects efficiently. This is in contrast with the inactive objects, where we only need to remove any object efficiently.

For pools that are not very big, it is fine to use a list and search for the item. For bigger pools, a set is appropriate.

Here, we will be using hash sets, which work with any type as long as the type is safe to hash. An alternative strategy would be to use ordered sets, which works on any type as long as the type is orderable. We can wrap objects to allow them to be either hashed or ordered.

Using hash sets gives us a better performance guarantee (constant time insertion and deletions, versus logarithmic time for ordered sets). To implement priority pools described below, we also would like to use our objects in dictionaries, so we would need our objects to be hashable anyways.

When are objects safe hash? Objects are safe to hash when equal objects have equal hash codes. This constraint can be violated if a class carelessly overrides one (or both) of the GetHashCode or Equals methods in a way that breaks it. When using a type in a hash set or dictionary, check whether the class has overridden either of these, and if so, whether it has been done to satisfy the hashing constraint.

When we do not have enough inactive objects when a new one is required, one strategy is to release an active object and re-use that instead. Often, we want to do this based on some type of priority — for example, oldest first, or smallest first, or least important first. We will assume these priorities do not change more frequently than we need to get objects from the pool.

To support prioritized release, we need to track active objects, as with an active-tracking pool. And as before, if the amount is small enough to use a list, we may simply look for the least element through the list linearly. For larger pools, we want a data structure that allows efficient adding objects, removing of the minimum, and efficiently removing specific objects. Assuming priorities do not change frequently, a data structure that does this is an index priority queue.

Assuming we do not want to modify the objects we pool, we can use a dictionary to keep track of object indices, making entries into the dictionary as we create objects. As with the active tracking object pools, this means our type needs to be safe to hash.

For priority pools, it is useful to also provide ReleaseMin(int n = 1) method that can be used by the DecreaseCapacity method if you also allow active objects to be destroyed.

If the priorities of objects can change, we need to update them in the index priority queue. We can add a method for this to the pool.

What is an index priority queue? This little-known data structure provides quick access to elements by index, while also maintaining the min element efficiently. It is described in Algorithms 4th Edition (2011) by Robert Sedgewick and Kevin Wayne, and also in Index Priority Queue with Implementation on Geeks for Geeks.

Fake pools implement the pool interface, but instead of pooling objects, they create and destroy them as you would if you did not use pooling. You can easily replace a real pool with a fake one to make comparisons and ensure your pools are giving you the benefits that you are using them for.

So far, we looked at designs of pools that can manage objects of any (safely hashable) type. In this section we look at how the design of pools change if we require that pooled objects implement an interface.

Using this approach simplifies the pool class:

We do not need to pass the activate, deactivate (and even destroy) as actions — we can make them part of the interface and call them directly. If we want to use prioritized release, we can make the priority and object indices part of the interface, and so do not have to pass in an evaluation function, or maintain a dictionary of object indices. There are some disadvantages to this design:

We can only support types outside our control by wrapping them. It couples objects to the pool.

And here is the priority pool implemented in this way:

Sometimes it is convenient to let objects release themselves when they are ready. For example, when we generate a particle whose behavior is completely controlled from within itself, it would be good if it was automatically released when it is at the end of its lifetime. This way we can “get and forget” about the particle.

To do this, you can either reference the pool that owns them, so objects can call the release method with themselves as parameter, or you can create an event that the pool can subscribe to that will be raised when the object wants to be released.

If we want to pool objects of a type that does not satisfy some requirements — typically a type outside our control — we may wrap it to give it what is missing. For example, we can use this to implement a specified interface, or make the objects safe to hash.

The general technique is as follows:

If there is not a public interface the object needs to conform to, provide one. This should give the user everything they need to work with the object.

Define a static class that provides the creation method for the pool.

Define a private inner type that implements the pool interface or the one defined above. This type exposes additional functionality that can be used by pool delegates.

Define the delegates in terms of the public type. The action delegates may cast to the private type to do their work.

Define the static method to create a pool in terms of the public type.

This example shows how to wrap objects to make them hashable.

There are situations where you may want to hide the creation and destruction of objects, so that the only way users can get instances is through the pool.

The general technique is as follows:

Define a public type the user will interact with. This type will not define a constructor.

Define your pool type.

Define a private type of inside the pool type that implements or extends from the public type.

Define private methods for creating and destroying objects of the private type.

In your pool type, define a pool field that you can delegate all the work to. This should be in terms of the private type. This in contrast with how wrapping works, where the pool was defined in terms of the public type. This is because we can do the type conversion in the Get and Release methods, and keeping the pool in terms of the private type is more convenient.

Define Get and Release methods in terms of the public type, doing type conversions as required.

Define any other pool methods you want to support.

This type of pool is usually not useful when you don’t control the creation of the objects. For example, since any MonoBehaviour can be created through the Unity’s Instantiate method, this pool is not very useful to manage any MonoBehaviour.

Measure the effect of your pool on the metrics you are trying to improve. As with all performance measuring, take the measurements in the right contexts (on the same platforms as you are developing for, in circumstances that occur in natural gameplay, with the same number of objects that are typically in play, and so on). You can make a comparison easily by using the fake pool described earlier.

Redo benchmark measurements each time you make changes that could affect the execution of any of the pool delegates.

For pools that control visual effects, consider centralizing pool capacities and policies so you can easily tie these with performance profiles.

Classes that use generic hash tables or dictionaries should take an optional comparer that is fed to the hashtable or dictionary. This ensures your class is truly usable for any object. (In the example implementation the comparison is compulsory, this is to avoid accidentally forgetting to pass a comparator along in this system of pools).

Be careful with pooling structs. Most of the discussion in this post assumes that the objects we want to hash are reference types. Structs are often smaller objects, and their creation does not directly affect garbage collection, so in many cases it may not make sense to pool them at all. Besides, when passing them between methods, their values are copied, so any gains trying to avoid creation will be thwarted. There may well be occasions where pooling structs may be useful. In that case though, the pool designs discussed here will probably not be appropriate.

Be careful when decreasing the pool capacity:

Make sure to destroy inactive objects first.

Decide how to handle active objects. In the implementation here we do not decrease below the number of inactive objects. In active object tracking pools, you can also destroy active objects if you choose. With non-tracking pools, how to interpret what it means to reduce beyond the inactive objects is difficult. What if users try to return objects beyond the current capacity? Do you destroy them then?

If your pool can destroy active objects, let the user specify whether to deactivate active objects first before destroying them.

In any operation where you ask for n things to be done, if it is possible for less than n things to be done, return the actual number of things done. This will enable the user to decide what to do if not everything was done.

For ordinary pool users, the number of active and inactive objects will not be that useful. However, these values are very useful when implementing a new type of pool based on the existing pool, so therefore, include them in your interface.

You can get the code used in the post on BitBucket: https://bitbucket.org/gamelogic/pool/src/main/