6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Without reading your code: have you considered interning instead? Every time I allocate a data structure, I check in the pool to see if anything with that type/arguments (which is just sizeof(struct), &struct for any struct) already exists. Then at the end there is a "free everything in the pool", which just iterates over the vector and frees each pointer. \$\endgroup\$ – o11c Jun 17 '15 at 8:26
  • \$\begingroup\$ @o11c, I didn't quite understand what you meant by 'interning'? Do you mean coupling the pool with the object stored itself? Like some intrusive data structure? \$\endgroup\$ – glampert Jun 17 '15 at 17:48
  • \$\begingroup\$ Interning means that if you try to allocate two objects with the same data, the allocator will actually return the same pointer. I have this implementation with example uses in bridge.c (simple interning) and mre_nfa.c (mapped interning) \$\endgroup\$ – o11c Jun 17 '15 at 18:29
  • \$\begingroup\$ Naive interning only works if all "arguments" are directly in the object, not via pointers or something, but you can work around this by interning the members as you assign them to the stack (non-interned) version of the object. This is used in the implementation of pool_intern_map (in pool.c, see new_key). \$\endgroup\$ – o11c Jun 17 '15 at 18:32
  • 1
    \$\begingroup\$ The one disadvantage of interning is that it disallows mutable data structures. But that's usually a good idea anyway. \$\endgroup\$ – o11c Jun 17 '15 at 18:50
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Interesting considerations. Thanks for the input! Yes, I was indeed thinking about wrapping the stats counters into compiler switches. But I if I do that it'll be more at the end of the project when there is nothing else to optimize. \$\endgroup\$ – glampert Jun 16 '15 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.