Pool allocator for a scripting language parser

Question

At the moment I'm writing a parser and interpreter for a custom scripting language, to learn more about the basic concepts involved and to get more familiar with tools like bison and flex.

The parsing process requires the allocation of a lot of small data structures to store intermediate language symbols and syntax tree nodes. The allocation pattern consists, in general, of a lot of sequential allocations with very few deallocations, and then everything gets freed at the end of the parsing, when the source code is done processing.

This seems like the perfect case for a pool allocator that can be drained with a single call at the end, to free all memory in one action. A reference on pool allocators.

My current implementation follows. I have tried to keep things as simple as possible. The pool maintains a linked list of small arrays. Objects reside inside these small arrays, so new allocations won't require copying data over to a new portion. There is still some fragmentation, but it is much lower if compared with raw new. Fragmentation can be further mitigated by choosing the best Granularity size for the small arrays to match the use case.

Any comments are appreciated.

#ifndef OBJECT_POOL_HPP
#define OBJECT_POOL_HPP

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstring>

#include <memory>
#include <utility>

// ========================================================
// class ObjectPool:
// ========================================================

//
// Pool of fixed-size memory blocks (similar to a list of arrays).
//
// This pool allocator operates as a linked list of small arrays.
// Each array is a pool of blocks with the size of 'T' template parameter.
// Template parameter `Granularity` defines the size in objects of type 'T'
// of such arrays.
//
// `allocate()` will return an uninitialized memory block.
// The user is responsible for calling `construct()` on it to run class
// constructors if necessary, and `destroy()` to call class destructor
// before deallocating the block.
//
template
<
    class T,
    std::size_t Granularity
>
class ObjectPool final
{
public:

     ObjectPool(); // Empty pool; no allocation until first use.
    ~ObjectPool(); // Drains the pool.

    // Not copyable.
    ObjectPool(const ObjectPool &) = delete;
    ObjectPool & operator = (const ObjectPool &) = delete;

    // Allocates a single memory block of size 'T' and
    // returns an uninitialized pointer to it.
    T * allocate();

    // Deallocates a memory block previously allocated by `allocate()`.
    // Pointer may be null, in which case this is a no-op. NOTE: Class destructor NOT called!
    void deallocate(void * ptr);

    // Frees all blocks, reseting the pool allocator to its initial state.
    // WARNING: Calling this method will invalidate any memory block still
    // alive that was previously allocated from this pool.
    void drain();

    // Calls constructor for `obj`, using placement new:
    static void construct(T * obj, const T & val);
    template<class U, class... Args> static void construct(U * obj, Args&&... args);

    // Calls destructor for `obj`:
    static void destroy(T * obj);
    template<class U> static void destroy(U * obj);

    // Miscellaneous stats queries:
    std::size_t getTotalAllocs()  const;
    std::size_t getTotalFrees()   const;
    std::size_t getObjectsAlive() const;
    std::size_t getGranularity()  const;
    std::size_t getSize()         const;

private:

    union PoolObj
    {
        PoolObj * next;
        alignas(T) std::uint8_t userData[sizeof(T)];
    };

    struct PoolBlock
    {
        PoolBlock * next;
        PoolObj objects[Granularity];
    };

    PoolBlock * blockList;      // List of all blocks/pools.
    PoolObj   * freeList;       // List of free objects that can be recycled.
    std::size_t allocCount;     // Total calls to `allocate()`.
    std::size_t objectCount;    // User objects ('T' instances) currently active.
    std::size_t poolBlockCount; // Size in blocks of the `blockList`.
};

// ========================================================
// ObjectPool inline implementation:
// ========================================================

template<class T, std::size_t Granularity>
ObjectPool<T, Granularity>::ObjectPool()
    : blockList(nullptr)
    , freeList(nullptr)
    , allocCount(0)
    , objectCount(0)
    , poolBlockCount(0)
{
    // Allocates memory when the first object is requested.
}

template<class T, std::size_t Granularity>
ObjectPool<T, Granularity>::~ObjectPool()
{
    drain();
}

template<class T, std::size_t Granularity>
T * ObjectPool<T, Granularity>::allocate()
{
    if (freeList == nullptr)
    {
        PoolBlock * newBlock = new PoolBlock();
        newBlock->next = blockList;
        blockList = newBlock;

        ++poolBlockCount;

        // All objects in the new pool block are appended
        // to the free list, since they are ready to be used.
        for (std::size_t i = 0; i < Granularity; ++i)
        {
            newBlock->objects[i].next = freeList;
            freeList = &newBlock->objects[i];
        }
    }

    ++allocCount;
    ++objectCount;

    // Fetch one from the free list's head:
    PoolObj * object = freeList;
    freeList = freeList->next;

    // Initializing the object with a known pattern
    // to help detecting memory errors.
    #if DEBUG_MEMORY
    std::memset(object, 0xAA, sizeof(PoolObj));
    #endif // DEBUG_MEMORY

    return reinterpret_cast<T *>(object);
}

template<class T, std::size_t Granularity>
void ObjectPool<T, Granularity>::deallocate(void * ptr)
{
    assert(objectCount != 0);
    if (ptr == nullptr)
    {
        return;
    }

    // Fill user portion with a known pattern to help
    // detecting post deallocation usage attempts.
    #if DEBUG_MEMORY
    std::memset(ptr, 0xFE, sizeof(PoolObj));
    #endif // DEBUG_MEMORY

    // Add back to free list's head. Memory not actually freed now.
    PoolObj * object = reinterpret_cast<PoolObj *>(ptr);
    object->next = freeList;
    freeList = object;

    --objectCount;
}

template<class T, std::size_t Granularity>
void ObjectPool<T, Granularity>::drain()
{
    while (blockList != nullptr)
    {
        PoolBlock * block = blockList;
        blockList = blockList->next;
        delete block;
    }

    blockList      = nullptr;
    freeList       = nullptr;
    allocCount     = 0;
    objectCount    = 0;
    poolBlockCount = 0;
}

template<class T, std::size_t Granularity>
std::size_t ObjectPool<T, Granularity>::getTotalAllocs() const
{
    return allocCount;
}

template<class T, std::size_t Granularity>
std::size_t ObjectPool<T, Granularity>::getTotalFrees() const
{
    return allocCount - objectCount;
}

template<class T, std::size_t Granularity>
std::size_t ObjectPool<T, Granularity>::getObjectsAlive() const
{
    return objectCount;
}

template<class T, std::size_t Granularity>
std::size_t ObjectPool<T, Granularity>::getGranularity() const
{
    return Granularity;
}

template<class T, std::size_t Granularity>
std::size_t ObjectPool<T, Granularity>::getSize() const
{
    return poolBlockCount;
}

template<class T, std::size_t Granularity>
void ObjectPool<T, Granularity>::construct(T * obj, const T & val)
{
    ::new(obj) T(val);
}

template<class T, std::size_t Granularity>
template<class U, class... Args>
void ObjectPool<T, Granularity>::construct(U * obj, Args&&... args)
{
    ::new(obj) U(std::forward<Args>(args)...);
}

template<class T, std::size_t Granularity>
void ObjectPool<T, Granularity>::destroy(T * obj)
{
    obj->~T();
}

template<class T, std::size_t Granularity>
template<class U>
void ObjectPool<T, Granularity>::destroy(U * obj)
{
    obj->~U();
}

#endif // OBJECT_POOL_HPP

Answer 1

You may want to change

struct PoolBlock
{
    PoolBlock * next;
    PoolObj objects[Granularity];
};

by

struct PoolBlock
{
    PoolObj objects[Granularity];
    PoolBlock * next;
};

If the PoolBlock is aligned for PoolObj/T you will not have the 4/8 bytes of 'next' disturbing the harmony. At the back there will be no such issue. Besides, it's easier to fit if your next step is using (lazily) mapped memory from the page pool to store a PoolBlock.

If you target high performance and the statistics are not really needed, you may want to get rid of them (i.e.: in a release build) as their relative cost is not negligible.