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.

The problem

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

A first implementation

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

{
    inactiveObjects =  Stack<Bat>();

     ( i = ; i < n; i++)
    {
        inactiveObjects.Push( Bat());
    }
}

() => inactiveObjects.// what  the stack is empty
 Release(obj) => inactiveObjects.we will use the pool like this:

() = ()
// Later...

(

This implementation suffers from a few issues:

A stack based pool

 {
     Capacity { get; }
    bool HasAvailableObject { get; }
     InactiveObjectCount { get; }
    ;
    ;
    ;
    ;
}

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

  StackPool<T> : IPool<T>
{
     readonly Stack<T> inactiveObjects = ();
     readonly Func<T> createActive;
     readonly Action<T> activate;
     readonly Action<T> deactivate;
     readonly Action<T> destroy;

      Capacity { get;  set; }
      InactiveObjectCount => inactiveObjects.;
     bool HasAvailableObject => inactiveObjects. > ;

     StackPool(
         capacity,
        Func<T> createActive,
        Action<T> activate,
        Action<T> deactivate,
        Action<T> destroy)
    {
        Capacity = capacity;
        .createActive = createActive;
        .activate = activate;
        .deactivate = deactivate;
        .destroy = destroy;

        CreateActive(capacity);
    }

      CreateActive( capacity)
    {
         ( i = ; i < capacity; i++)
        {
            var newObject = createActive();
            deactivate(newObject);
            inactiveObjects.(newObject);
        }
    }

     T Get()
    {
         (inactiveObjects. == )
        {
              InvalidOperationException();
        }

        var obj = inactiveObjects.();
        activate(obj);
         obj;
    }

      Release(T obj)
    {
        deactivate(obj);
        inactiveObjects.(obj);
    }

      IncreaseCapacity( increment)
    {
        Capacity += increment;
        CreateActive(increment);
    }

      DecreaseCapacity( decrement)
    {
         inactiveDecrement = inactiveObjects. < decrement ? inactiveObjects. : decrement;

         ( i = ; i < inactiveDecrement; i++)
        {
            var obj = inactiveObjects.();
            destroy(obj);
        }

        Capacity -= inactiveDecrement;
         inactiveDecrement;
    }
}

Note the following:

For pool users: how to implement the pool delegates

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

Pool variations

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

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.

  SelfGrowingPool<T> : IPool<T>
{
     StackPool<T> pool;

      Capacity => pool.Capacity;

      InactiveObjectCount => pool.InactiveObjectCount;

      HasAvailableObject => pool.HasAvailableObject;

    => pool =  StackPool<T>(initialCapacity, createActive, activate, deactivate, destroy);

    {
         (!pool.HasAvailableObject)
        {
            pool.IncreaseCapacity();
        }

         pool.Get();
    }

    => pool.Release(obj);
    => pool.IncreaseCapacity(increment);
    => pool.DecreaseCapacity(decrement);
}

Active object tracking pools

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

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.

Priority pools

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.

  PriorityPool<T, TPriority> : ITrackedPool<T>
{
     readonly Action<T> reactivate;
     readonly Func<T, TPriority> getPriority;
     StackPool<T> pool;
     readonly IndexPriorityQueue<T, TPriority> activeObjects;
     readonly Dictionary<T, > objectToIndex;

      Capacity => pool.Capacity;    
      ActiveObjectCount => activeObjects.Count;
      InactiveObjectCount => pool.InactiveObjectCount;
      HasAvailableObject => pool.HasAvailableObject;

    {
        .reactivate = reactivate;
        .getPriority = getPriority;
         objectCount = ;
        pool =  StackPool<T>(initialCapacity, CreateActive, activate, deactivate, Destroy);
        activeObjects =  IndexPriorityQueue<T, TPriority>(initialCapacity, priorityComparer);
        objectToIndex =  Dictionary<T, >(objectComparer);

        ;

        {
            var obj = createActive();
            objectToIndex[obj] = objectCount++;
             obj;
        }

        {}
    }

    {
        T obj;
         index;

         (pool.HasAvailableObject)
        {
            obj = pool.Get();
            index = objectToIndex[obj];
        }

        {
            (index, obj) = activeObjects.Dequeue();
            reactivate(obj);
        }

        activeObjects.Enqueue(index, obj, getPriority(obj));
         obj;
    }

    {
        ( _, var obj) = activeObjects.Dequeue();
        Release(obj);
    }

    {
        pool.Release(obj);
        activeObjects.Remove(objectToIndex[obj]);
    }

    {
         releasedCount = ;
         (releasedCount < count && !activeObjects.IsEmpty)
        {
            ReleaseMin();
            releasedCount++;
        }

         releasedCount;
    }

    {
         index = objectToIndex[obj];
         (!activeObjects.Contains(index))
        {
              InvalidOperationException();
        }

        activeObjects.UpdateValue(index, obj, getPriority(obj));
    } 

    =>   NotSupportedException();
    =>   NotSupportedException();
}

Fake pools

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.

  FakePool<T> : IPool<T>
{
     readonly Func<T> create;
     readonly Action<T> destroy;

      Capacity { get;  ; }
      HasAvailableObject => InactiveObjectCount > ;
      InactiveObjectCount { get;  ; }

    {
        Capacity = capacity;
        .create = create;
        .destroy = destroy;
    }

    {
         (!HasAvailableObject)
        {
              InvalidOperationException();
        }

        InactiveObjectCount--;
         create();
    }

    {
        destroy(obj);
        InactiveObjectCount++;
    }

    => Capacity += increment;

    => Capacity -= decrement;
}

More design techniques

Managing pooled objects through an interface

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.

 interface IReusableObject
{
     IsActive { get; }
    ;
    ;
     Id { get; }
}

 interface IReusableObject<out T> : IReusableObject
{
     T Value { get; }
}

  ReusableObjectPool : IPool<IReusableObject>
{
     readonly StackPool<IReusableObject> pool;

      Capacity => pool.Capacity;    
      InactiveObjectCount => pool.InactiveObjectCount;
      HasAvailableObject => pool.HasAvailableObject;

    {
        pool =  StackPool<IReusableObject>(initialCapacity, createActive, Activate, Deactivate, destroy);

        ;

        => obj.Activate();
        => obj.Deactivate();
    }

    => pool.Get();

    => pool.Release(obj);

    => pool.IncreaseCapacity(increment);

    => pool.DecreaseCapacity(decrement);
}

  ReusableObjectPool<T> : IPool<T>
    where T : IReusableObject
{
     readonly StackPool<T> pool;

      Capacity => pool.Capacity;    
      HasAvailableObject => pool.HasAvailableObject;
      InactiveObjectCount => pool.InactiveObjectCount;

    {
        pool =  StackPool<T>(initialCapacity, createActive, Activate, Deactivate, destroy);

        ;

        => obj.Activate();
        => obj.Deactivate();
    }

    => pool.Get();
    => pool.Release(obj);
    => pool.IncreaseCapacity(increment);
    => pool.DecreaseCapacity(decrement);
}

And here is the priority pool implemented in this way:

 interface IPrioritizedObject<out TPriority>
{
    TPriority Priority { get; }
}

  PriorityReusableObjectPool<T, TPriority> 
    where T : IReusableObject, IPrioritizedObject<TPriority>
{
     readonly StackPool<T> pool;
     readonly IndexPriorityQueue<T, TPriority> activeObjects;

    {
         counter = ;

        var objectToIndex =  Dictionary<T, >(objectComparer);
        activeObjects =  IndexPriorityQueue<T, TPriority>(capacity, priorityComparer);
        pool =  StackPool<T>(capacity, CreateActive, Activate, Deactivate, destroy);

        ;

        {
            var obj = createActive();
            objectToIndex[obj] = counter++;
             obj;
        }

        {
            obj.Activate();
            activeObjects.Enqueue(objectToIndex[obj], obj, obj.Priority);
        }

        {
            obj.Deactivate();
            activeObjects.Remove(objectToIndex[obj]);
        }
    }

    {
         (pool.HasAvailableObject)
        {
             pool.Get();
        }

        ( index, var obj) = activeObjects.Dequeue();
        obj.Deactivate();
        obj.Activate();
        activeObjects.Enqueue(index, obj, obj.Priority);
         obj;
    }

    => pool.Release(obj);
}

Self-releasing objects

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.

 interface ISelfReleasingObject<out T>
{
    T Value { get; }
    ;
}

  SelfReleasingObjectPool<T> : IPool<ISelfReleasingObject<T>>
{
      SelfReleasingObject : ISelfReleasingObject<T>
    {
         readonly IPool<SelfReleasingObject> owner;
         T Value { get; }

        {
            Value = value;
            .owner = owner;
        }

        => owner.Release();
    }

     readonly StackPool<SelfReleasingObject> pool;

      Capacity => pool.Capacity;    
      InactiveObjectCount => pool.InactiveObjectCount;    
      HasAvailableObject => pool.HasAvailableObject;

    {
        pool    =  StackPool<SelfReleasingObject>(initialCapacity, CreateActive, Activate, Deactivate, Destroy);
        ;

        {
            var obj =  SelfReleasingObject(createActive(), pool);
             obj;
        }

        {
            destroy(obj.Value);
        }

        => activate(obj.Value);
        => deactivate(obj.Value);
    }

     ISelfReleasingObject<T> Get()
    {
        var obj = pool.Get();
         obj;
    }

    => pool.Release((SelfReleasingObject)obj);
    => pool.IncreaseCapacity(increment);
    => pool.DecreaseCapacity(decrement);
}

Wrapping unsuitable types

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:

 {
    T Value { ; }
}

  {
     {
         readonly Id<IHashable<T>> id = ();
         T Value { ; }
          int GetHashCode() => id.GetHashCode();
         IdHashable(T value) => Value = value;
    }

      IPool<IHashable<T>> GetPoolWithActiveTrackingForNonHashables<T>(
        int initialCapacity, 
        Func<T> createActive, 
        Action<T> activate,
        Action<T> deactivate, 
        Action<T> destroy)
        where T : {
         GetPoolWithActiveTracking(initialCapacity, CreateActive, Activate, Deactivate, Destroy, );

        IHashable<T> CreateActive() =>  IdHashable<T>(createActive());
         Destroy(IHashable<T> obj) => destroy(obj.Value);
         Activate(IHashable<T> obj) => activate(obj.Value);
         Deactivate(IHashable<T> obj) => deactivate(obj.Value);
    }
}

Hiding creation and destruction

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:

 interface IEnemy
{
      Health { get; ; }
}

  EnemyPool
{
     readonly ReusableObjectPool<Enemy> pool;

      Enemy : IEnemy, IReusableObject
    {
          Health { get; ; }
          IsActive { get;  ;}

         readonly Id<Enemy> id = ();
          Id => id.value;

        {
            Debug.Assert(!IsActive);

            IsActive = ;
        }

        {
            Debug.Assert(IsActive);

            IsActive = ;
        }

        => id.value;
    }

    => pool =  ReusableObjectPool<Enemy>(initialCapacity, CreateEnemy, DestroyEnemy);

    => pool.Get();
    => pool.Release((Enemy)enemy);
    => ();
    { }
}

Best Practices

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