Fixed Size Object Pool

As I get ready to have all game entities assigned a unique ID upon creation, I realized this would be the perfect time to impose another restriction upon them and require them to be created using a memory pool!

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

My implementation functions a lot like new, requesting a new object from the pool constructs it within the pool’s internal memory buffer, and freeing the object simply flags the memory it was constructed upon as free to use again. Where the pool differs from new, however, is that the pool knows that all object it will be creating will be of the same size and type. This allows us to simplify everything greatly by using an array of objects as the internal storage type of the pool rather than a linked list of arbitrarily sized items.

We aren’t able to avoid linked lists all together though. When the pool is first created every node in the pool is free. When the user asks for memory we can just give them the first node, then the second, then third, and so on. Eventually some of the memory will be given back to the pool and it might not be be in the order it was given away. This will lead to us having free and in-use nodes interleaved through our internal array and finding the free nodes will become harder. A simple approach to finding free nodes once this happens is to just iterate over all the nodes in the pool until you find a free one. We can do better than this though. Rather than storing just objects as our pool nodes, we can make each node a union containing either an object or a pointer to the next free node. Our pool class now only needs to hold a pointer to the head of the free node list to have access to all free nodes in constant time. Additionally, storing the free nodes in a separate data structure eliminates the need for nodes to know whether they are free or in-use, this allows the nodes to be no bigger than the size of the object stored in the pool.

A clever feature of the pool is its use of placement new to emplace new objects within their union. Modern C++ makes use of constructors and destructors extensively to safely manage resources (among other things). When a user requests a new object from the pool it explicitly constructs a new object in the node and when an object is returned to the pool its destructor is explicitly invoked.

I don’t have any fun pictures related to the memory pool but the code is just as fun, right? Below is the full implementation ready to be copied and pasted into any project.

#pragma once

#include <algorithm>
#include <cstddef>
#include <string>

template <typename T>
class GenericPool
{
  struct PoolNode
  {
    union U {
      T object;
      PoolNode* pNext;

      U() : pNext(nullptr) {}
      ~U() {}
    };

    U u;
  };


public:
  GenericPool(const std::string& strPoolName, size_t nObjectCapacity)
    : m_strName(strPoolName)
    , m_nCapacity(std::max(nObjectCapacity, (size_t)1))
    , m_nUsage(0)
  {
    m_pDataArray = new PoolNode[m_nCapacity];
    m_pFreeListHead = &m_pDataArray[0];
    for (size_t i = 1; i < m_nCapacity; ++i)
    {
      m_pDataArray[i - 1].u.pNext = &m_pDataArray[i];
    }
  }

  ~GenericPool()
  {
    delete [] m_pDataArray;
  }

  template <typename... Args>
  T* emplaceGet(Args&&... args)
  {
    if (!m_pFreeListHead)
    {
      printf("ran out of space in pool: %s\n", m_strName.c_str());
      std::abort();
    }

    PoolNode* pNode = m_pFreeListHead;
    m_pFreeListHead = m_pFreeListHead->u.pNext;
    ++m_nUsage;

    // placement new on top of the existing one
    return new (&pNode->u.object) T(std::forward<Args>(args)...);
  }

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

    // convert our type into a PoolNode
    constexpr size_t nItemOffset = offsetof(PoolNode, u.object);
    PoolNode* pNode = 
      reinterpret_cast<PoolNode*>(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;
  }

private:
  GenericPool() = delete;
  GenericPool(const GenericPool<T>&) = delete;

  const std::string m_strName;
  const size_t m_nCapacity;
  size_t m_nUsage;
  PoolNode* m_pFreeListHead;
  PoolNode* m_pDataArray;
};

• Cpp
• Gamedev
• Devlog