在内存池中查找下一个可用块

Question

因此，我花了一些时间在 C++ 中实现内存池 class。一路上除了一些小问题外，还算顺利。然而，当我今天尝试通过首先使用内存池分配 1000 个块然后将其与使用 new 进行比较来测试它时，我实际上已经接近三倍差的性能（以纳秒为单位） ) 使用内存池时。我的分配方法是这样的：

template <class T> T* MemPool<T>::allocate()
{
    Chunk<T>* tempChunk = _startChunk;

    while (tempChunk->_free == false)
    {
        if (tempChunk->_nextChunk == NULL)
            throw std::runtime_error("No available chunks");

        tempChunk = tempChunk->_nextChunk;
    }

    tempChunk->_free = false;
    return &tempChunk->object;
}

我从池中的第一个块开始，通过池的链表进行搜索，直到找到空闲块或到达池的末尾。现在，池越大，搜索所需的时间就越长，因为搜索的时间复杂度为 O(n)，其中 n 是池中的块数。

所以我很好奇是否有人对如何改进分配有任何想法？我最初的想法是使用两个链表，而不是只使用一个链表，其中一个包含空闲块，另一个包含分配块。当要分配一个新块时，我会简单地将第一个提到的链表中的第一个元素移动到分配的链表中。据我所知，这将消除在分配时进行任何搜索的需要，只留下需要搜索以找到正确块的解除分配。

感谢任何想法，因为这是我第一次以这种方式直接处理内存。谢谢！

Answer 1

与其使用手工制作的链表，使用 std::list 可能更有效（特别是如果您将其与自定义分配器一起使用）。不太容易出错，而且可能优化得更好。

使用两个列表可以简化很多事情。不需要在列表本身中跟踪一个块是否空闲——因为这将由该块所在的列表指定（所需要的只是确保一个块不会以某种方式出现在两个列表中）。

您当前的实现意味着您在分配和取消分配时都必须遍历链表。

如果块是固定大小的，那么分配将简单地通过将第一个可用块从空闲列表移动到分配列表来实现——无需搜索。要释放一个块，您仍然需要在分配的列表中找到它，这意味着您需要将 T* 映射到列表中的一个条目（例如执行搜索），但是释放操作将只需将条目从一个列表移动到另一个列表即可。

如果块的大小可变，您需要做更多的工作。分配需要在分配时找到一个至少是请求大小的块。过度分配（分配比需要更大的块）会使分配和释放在性能方面更有效，但也意味着可以从池中分配更少的块。或者，将一大块（来自空闲列表）分成两部分，并在两个列表中放置一个条目（代表已分配的部分和未分配的部分）。如果这样做，在释放时，可能需要合并内存中相邻的块（有效地对池中的空闲内存进行碎片整理）。

您需要决定是否可以从多个线程使用池，并使用适当的同步。

Answer 2

使用固定数量的 size bin，并使每个 bin 成为一个 linked 列表。

例如，假设您的 bin 只是系统页面大小（通常为 4KiB）的整数倍，并且您使用 1MiB 块；那么你有 1MiB/4KiB = 256 个 bin。如果 free 使一个 n 页区域在块中可用，则将其附加到 bin n。分配 n 页区域时，遍历 n 到 256 的 bin，然后选择第一个可用的块。

为了最大化性能，将 bin 与位图相关联，然后从位 n-1 扫描到位 255 以找到第一个设置位（使用 __builtin_clz 和 _BitScanForward 等编译器内部函数计算前导或尾随零).由于 bin 的数量，这仍然不完全是 O(1)，但它非常接近。

如果您担心内存开销，您可以为每个 bin 仅附加每个块一次。也就是说，即使一个块有 128 个单页区域可用（最大碎片），bin 1 仍然只会 link 到块一次并重复使用它 128 次。

要做到这一点，你必须 link 每个块内的这些区域，这意味着每个块还需要存储一个大小箱列表 - 但这可以提高内存效率，因为有每个块内最多只有 256 个有效偏移量，而列表需要存储完整的指针。

请注意，无论哪种方式，如果您不希望每个块中的空闲 space 变得支离破碎，您将需要一种快速的方法来从列表中的垃圾箱中删除块 - 这意味着使用 doubly linked 列表。显然这增加了额外的内存开销，但它可能仍然比对整个列表进行定期免费 space 碎片整理更可取。

在内存池中查找下一个可用块

Find next available chunk in a memory pool

c++

memory

memory-management

pool