A Simple Object Pool

This is the first post in a series about object pools in C++.

An Introduction to Memory Pools

Memory pools are a useful tool for managing memory in high performance applications. Rather than using new or malloc to create objects on the heap, pools manually manage a fixed chunk of memory with several benefits:

• Reduced perfomance cost of allocating and deallocating objects by reusing memory and avoiding complicated implementations of new/malloc or requesting additional memory from the OS

• Reduced heap fragmentation (the forming of many small gaps in heap memory) which can occur when a program runs for a while and frequently allocates and deallocates memory

• Improved locality of data by placing all allocated objects contiguously in memory

Design

Our simple memory pool will be designed with the follow considerations:

• All objects in the pool will be the same type
• The number of objects the pool can store is fixed
• Typesafe
• Enforced construction/destruction of objects

These restrictions allow us to keep the implementation as simple as possible.

Storing the Objects

The underlying store of our objects is going to be a simple array. To provide the type of the stored object, we will template the class on the type of stored object.

We can define our class like this and use RAII to allocate an array of objects in the constructor and free the array in the destructor:

template <typename ObjectType>
class SimplePool
{
public:
  SimplePool(size_t nPoolSize)
  {
    // create an array of objects on the heap
    m_pObjectStore = new ObjectType[nPoolSize];
  }

  ~SimplePool()
  {
    // free our array
    delete [] m_pObjectStore;
  }

private:
  ObjectType* m_pObjectStore;
};

This is a good start, but this wont work for types that cannot be default constructed. When we create the array of objects using new, it will attempt to default construct every object in the array. This isn’t really what we want though. We would like to allocate space for the objects without actually initializing them. To do this some indirection is needed, we can instead wrap the objects to store them without actually initializing them.

template <typename ObjectType>
struct PoolObjectWrapper
{
  union Storage
  {
    ObjectType object;

    U() {}
    ~U() {}
  };
  Storage u;
};

Our PoolObjectWrapper uses a union to wrap our ObjectType. We also provide a constructor for the union which does nothing and prevents our objects from being initialized when the union is created. An additional benefit of using a union in this context is that it will preserve the alignment requirements of our ObjectType, even if we add additional types to the union later.

We can now change our storage array type to utilize our wrapper class and allow our pool to support objects that cannot be default constructed.

PoolObjectWrapper<ObjectType>* m_pObjectStore;

Keeping Track of Free and Allocated Objects

In order to start allocating memory in the pool we are going to need to know which object wrappers are free and which are in-use. We could try and keep track of a free index, indicating the next slot of memory to give away and incrementing the index each time we allocate, though consider:

• What happens when memory is given back to the pool?
• What happens if memory is freed in a different order than it is allocated?

While our program runs, free regions of the array can become interleaved with in-use regions. Keeping track with a single free index will not be sufficient.

Linked List to the Rescue

Instead of storing the index of the next free slot, what if we store a pointer to the next free slot? Furthermore, what if each free slot also contained a pointer to the next free node after it?

We already have our PoolObjectWrapper struct wrapping our ObjectTypes, it would be trivial to add a pointer member to that struct. Even better, because we only need to store free items in the list, we can save space by making the next pointer a member of our union.

Our PoolObjectWrapper class then becomes:

template <typename ObjectType>
struct PoolObjectWrapper
{
  union Storage
  {
    ObjectType object;
    PoolObjectWrapper<ObjectType>* pNext;

    U() {}
    ~U() {}
  };
  Storage u;
};

We will then need to update our class to store a pointer to the head of the free list. We also need to update our constructor to assemble our linked list of free slots after we initialize our array.

Updated, our class now looks like this:

template <typename ObjectType>
class SimplePool
{
public:
  SimplePool(size_t nObjectCapacity)
    : m_nCapacity(std::max(nObjectCapacity, (size_t)1))
  {
    m_pObjectStore = new PoolObjectWrapper<ObjectType>[m_nCapacity];
    m_pFreeListHead = &m_pObjectStore[0];
    for (size_t i = 1; i < m_nCapacity; ++i)
    {
      m_pObjectStore[i - 1].u.pNext = &m_pObjectStore[i];
    }
    m_pObjectStore[m_nCapacity - 1].u.pNext = nullptr;
  }

  ~SimplePool()
  {
    delete[] m_pObjectStore;
  }
private:
  const size_t m_nCapacity;
  PoolObjectWrapper<ObjectType>* m_pObjectStore;
  PoolObjectWrapper<ObjectType>* m_pFreeListHead;  
};

Allocating an Object in the Pool

With our new approach to storing a linked list of free slots, allocating a new node on the pool is easy!

// use variadic template to take any
// number of args for ObjectType's constructor
template <typename... Args>
ObjectType* allocate(Args&&... args)
{
  // If we're full return nullptr
  if (!m_pFreeListHead)
    return nullptr;

  // take the first node from the list of free nodes
  PoolObjectWrapper<ObjectType>* pNode = m_pFreeListHead;
  m_pFreeListHead = m_pFreeListHead->u.pNext;
  ++m_nUsage;

  // use placement new to construct our object in the slot
  // launder the result to prevent the compiler from
  // being too clever.
  return std::launder(new (&pNode->u.object) 
      ObjectType(std::forward<Args>(args)...));
}

Returning an Object to the Pool

Returning an object to the pool is a little bit more complicated than taking from the pool. The main complication arises from the fact that we are given a pointer to the object, but our pool stores object wrappers. We need to go from a pointer to the object to a pointer to the object wrapper. Thankfully there is a handy offsetof macro we can use to help us perform this mapping. The end result looks like this:

void free(ObjectType* pObject)
{
  // if our type is complicated make sure we invoke its destructor
  if constexpr (!std::is_trivially_destructible_v<ObjectType>)
    pObject->~ObjectType();

  // find the offset from the top of a PoolObjectWrapper
  // to our Object
  constexpr size_t nItemOffset = 
    offsetof(PoolObjectWrapper<ObjectType>, u.object);

  // Use the offset to obtain a pointer to the PoolObjectWrapper
  PoolObjectWrapper<ObjectType>* pNode =
    reinterpret_cast<PoolObjectWrapper<ObjectType>*>(
      reinterpret_cast<char*>(pObject) - nItemOffset);

  // Stick the newly freed node at the head of 
  // the free list to be reused
  pNode->u.pNext = m_pFreeListHead;
  m_pFreeListHead = pNode;
}

Conclusion

When we put all of this together we have a very simple fixed size pool with O(1) insertion and deletion. While this pool is fully functional, it may not be the most useful. In real applications, if we run out of space in the pool we will still want to create our object. Because this pool doesn’t resize it’s not the most versatile and can only be used in situations where we know the max number of objects needed ahead of time.

Download

The full source of this pool can be found here.

Part Two: Resizing Pool

• Cpp
• Gamedev
• Devlog