脚本语言解析器的池分配器

Question

目前，我正在为一种自定义脚本语言编写解析器和解释器，以便更多地了解所涉及的基本概念，并更熟悉bison和flex等工具。

解析过程需要分配大量的小数据结构来存储中间语言符号和语法树节点。通常，分配模式包括大量的顺序分配和很少的释放位置，然后在解析结束时，当源代码完成处理时，所有的东西都会被释放。

对于池分配器来说，这似乎是一个完美的案例，在结束时只需调用一次就可以释放所有内存。池分配器的参考。

下面是我当前的实现。我试着让事情尽可能简单。池维护一个小数组的链接列表。对象驻留在这些小数组中，因此新的分配不需要将数据复制到新的部分。仍然存在一些碎片，但与原始new相比，它要低得多。通过为匹配用例的小型数组选择最佳Granularity大小，可以进一步减轻碎片的影响。

如有任何意见，敬请见谅。

#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

你可能想要改变

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

通过

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

如果PoolBlock是针对PoolObj/T对齐的，那么就不会有4/8个字节的“next”干扰和谐。在后面不会有这样的问题。此外，如果您的下一步是使用页面池中的映射内存来存储PoolBlock，则更容易适应。

如果您以高性能为目标，并且并不真正需要统计数据，您可能想要摆脱它们(即:在发行版构建中)，因为它们的相对成本是不可忽略的。