内存分配缓存

引言

不久前，我发布了一篇文章，描述了一种优化频繁动态分配固定大小内存的技术。

几天前，我和我的朋友聊天，偶尔谈到了这个话题。他告诉我：“在这种情况下，我没有删除不需要的块，而是将它们存储在一个链表中，然后再次重用它们”。

令人印象深刻，不是吗？这种方法甚至比我发明的更简单，它的优点是缓存池可以动态增长，而无需特殊努力或性能损失。

开销：理论上，我们根本不需要任何开销：当已分配的块在使用中时，我们不需要对它进行任何引用，并且一旦它不再需要，我们只需使用它的主体来实现链表节点（假设最小分配大小至少是一个指针的大小，在 Win32 上为 4 个字节）。但另一方面，所有块都是通过堆分配的，它可能需要一些头信息。当分配大小很小时，这可能很重要。在这种情况下，使用我的分配器（我之前描述过）而不是堆是一个好主意。

实现

现在，让我们更仔细地讨论一下。我们需要一个单向链表（堆栈或队列，没关系），它最初是空的。在运行时，我们以常规方式分配块。然后，当它们不再需要时，我们将它们推入我们的链表（而不是删除）。在下一次分配请求时，我们只需从我们的链表中返回一个块。

好的，让我们关注一些陷阱

1. 假设在早期运行阶段出现峰值。换句话说，您突然需要很多分配块，而缓存列表尚未收集太多块。因此，您将不得不快速分配它们，而当您的应用程序需要对此类负载快速响应时，这一点尤其关键！因此，我们的第一个结论是，应该在初始化时预先缓存一定数量的块。
2. 在巨大的峰值过后，我们的列表可能包含很多块，而大多数时候我们只需要其中的一小部分。因此，我们的第二个结论是，当我们的缓存列表变得足够大时，我们以常规方式删除分配块，而不是收集它们。

好吧，一点也不复杂。在这里，我给出了这个想法的一种可能的实现。它缓存分配到某个最大计数，该计数不会改变。但是，一个聪明的应用程序可以以某种方式收集统计数据并动态调整此限制。好吧，这取决于你。祝你好运！

附言：如果存在错误，请原谅，我还没有测试它。

class CAllocaterEx {
    ULONG m_nAllocationSize;
    ULONG m_nPoolMax;
    ULONG m_nCount;

    struct CNode {
        CNode* m_pNext;
    };
    CNode* m_pHead;

    CNode* Pop()
    {
        ASSERT(m_pHead && m_nCount);
        CNode* pHead = m_pHead;
        m_pHead = pHead->m_pNext;
        m_nCount--;
        return pHead;
    }
    void Push(CNode* pNode)
    {
        ASSERT(pNode);
        pNode->m_pNext = m_pHead;
        m_pHead = pNode;
        m_nCount++;
    }

public:
    CAllocaterEx(ULONG nAllocationSize = 0) :
        m_nAllocationSize(nAllocationSize),
        m_nPoolMax(0),
        m_nCount(0),
        m_pHead(NULL)
        {
        }
    ~CAllocaterEx()
    {
        Clear();
    }

    bool Init(ULONG nPoolSize)
    {
        // ensure our allocation size is at least size of a pointer
        if (m_nAllocationSize < sizeof(ULONG_PTR))
            m_nAllocationSize = sizeof(ULONG_PTR);

        Clear();
        return EnsurePoolMin(m_nPoolMax = nPoolSize);
    }
    bool Init(ULONG nPoolSize, ULONG nAllocationSize)
    {
        m_nAllocationSize = nAllocationSize;
        return Init(nPoolSize);
    }

    bool EnsurePoolMin(ULONG nPoolSize)
    {
        while (m_nCount < nPoolSize)
        {
            CNode* pNode = (CNode*) new BYTE[m_nAllocationSize];
            if (!pNode)
                return false;
            Push(pNode);
        }
        return true;
    }
    void EnsurePoolMax(ULONG nPoolSize)
    {
        while (m_nCount > nPoolSize)
            delete[] (PBYTE) Pop();
    }

    void Clear()
    {
        EnsurePoolMax(0);
    }

    PVOID Alloc()
    {
        return EnsurePoolMin(1) ? (PVOID) Pop() : NULL;
    }
    void Free(PVOID pPtr)
    {
        Push((CNode*) pPtr);
        EnsurePoolMax(m_nPoolMax);
    }
};