代码之家 › 专栏 › 技术社区 › MulattoKid

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

pool memory-management memory c++

MulattoKid · 技术社区 · 8 年前

因此,我一直在用C++实现一个内存池类。除了一路上的一些小问题,一切都很顺利。然而,当我今天尝试测试它时,首先使用内存池分配1000个块,然后将其与使用新 ,在使用内存池时,我的性能实际上差了三倍(以纳秒为单位)。我的分配方法如下:

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是池中的块数。

所以我很好奇,是否有人对如何改善分配有任何想法?我最初的想法是使用两个链接列表,而不仅仅是一个,其中一个包含空闲块,另一个包含分配块。当要分配一个新的块时,我只需获取第一个提到的链表中的第一个元素,并将其移动到分配的链表。就我所见,这将消除在分配时进行任何搜索的需要,并且只留下需要搜索才能找到正确块的释放。

任何想法都很感激,因为这是我第一次以这种方式直接处理记忆。谢谢

2 回复 | 直到 8 年前

Peter 8 年前

与其使用手工制作的链表,不如使用 std::list (特别是在使用自定义分配器时)。更不容易出错,并且可能更好地优化。

使用两个列表可以大大简化。无需在列表本身中跟踪块是否空闲-因为这将由块在哪个列表中指定(所需的只是确保块不会以某种方式出现在两个列表中)。

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

如果块大小是固定的,那么分配将简单地通过将第一个可用块从空闲列表移动到分配列表来实现-无需搜索。要解除分配块,您仍然需要在已分配列表中找到它,这意味着您需要映射 T* 对列表中的条目(例如,执行搜索),但解除分配的行为将只是将条目从一个列表移动到另一个列表。

如果块大小可变,则需要做更多的工作。分配将需要在分配时找到至少为请求大小的块。过度分配(分配比需要更大的块)将使分配和释放在性能方面更有效,但也意味着可以从池中分配更少的块。或者,将一大块(从空闲列表中)分成两部分,并在两个列表中放置一个条目(表示已分配的部分和未分配的部分)。如果这样做,在释放时,可能需要合并内存中相邻的块(有效地实现池中空闲内存的碎片整理)。

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

Ver Greeneyes 8 年前

使用固定数量的大小容器,并使每个容器成为链接列表。

例如,假设您的BIN只是系统页面大小的整数倍(通常为4KB),您使用1MB块;那么您有1MiB/4KiB=256个存储箱。如果一个free使块中的n页区域可用,则将其附加到bin n。分配n页区域时,从n到256遍历bin并选择第一个可用块。

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

如果您担心内存开销,您可以只附加每个块一旦对于每个箱。也就是说,即使一个区块有128个可用的1页区域(最大碎片化),bin 1仍将只链接到该区块一次,并重复使用128次。

要做到这一点,您必须在每个块内将这些区域链接在一起,这意味着每个块还需要存储一个大小容器列表-但这可能更节省内存,因为每个块内最多只有256个有效偏移,而该列表需要存储完整指针。

请注意,无论是哪种方式,如果您不希望每个块中的空闲空间变得零碎,您都需要一种快速的方法从列表中的容器中删除块-这意味着使用双链接列表。显然,这会增加额外的内存开销,但可能仍然比对整个列表进行定期的空闲空间碎片整理更好。