c++ - 统一 block 集合中的连续 block 的算法

Question

我正在创建一个具有动态内存块大小的预分配器，我需要统一连续的内存块。

struct Chunk // Chunk of memory
{
    Ptr begin, end; // [begin, end) range
}

struct PreAlloc
{
    std::vector<Chunk> chunks; // I need to unify contiguous chunks here
    ...
}

我试过 a naive solution ，也就是说，在根据它们的 begin 对 block 进行排序之后，基本上通过 vector 检查下一个 block 的 begin 是否等于当前 block 的 end。我相信它可以改进。

有没有一个好的算法统一连续范围？

信息:

• block 永远不能“重叠”。
• block 的大小可以大于 0。
• 性能是最重要的因素。

Answer 1

注意:我的原始算法有一个错误，我只考虑了当前 block 左侧的 block 。

使用两个关联表(例如unordered_map)，一个将begin地址映射到Chunk，另一个映射end 到 Chunk。这使您可以快速找到相邻的 block 。或者，您可以更改 Chunk 结构以存储指向相邻 Chunk 的指针/id/任何内容，加上一个标志来标记它是否是空闲的。

该算法包括扫描一次 block vector ，同时保持不变量:如果左边有邻居，则合并它们；如果右边有邻居，则合并它们。最后，只需收集剩余的 block 。

代码如下:

void unify(vector<Chunk>& chunks)
{
    unordered_map<Ptr, Chunk> begins(chunks.size() * 1.25); // tweak this
    unordered_map<Ptr, Chunk> ends(chunks.size() * 1.25); // tweak this

    for (Chunk c : chunks) {        
        // check the left
        auto left = ends.find(c.begin);
        if (left != ends.end()) { // found something to the left
            Chunk neighbour = left->second;
            c.begin = neighbour.begin;
            begins.erase(neighbour.begin);
            ends.erase(left);
        }
        // check the right
        auto right = begins.find(c.end);
        if (right != begins.end()) { // found something to the right
            Chunk neighbour = right->second;
            c.end = neighbour.end;
            begins.erase(right);
            ends.erase(neighbour.end);
        }

        begins[c.begin] = c;
        ends[c.end] = c;
    }
    chunks.clear();
    for (auto x : begins)
        chunks.push_back(x.second);
}

该算法具有 O(n) 复杂性，假设对 begins 和 ends 表的访问是恒定的(这几乎是你得到的你不会触发重新散列，因此“调整这个”评论)。实现关联表有很多选择，请务必尝试几种不同的选择；正如 Ben Jackson 在评论中指出的那样，哈希表并不总是能很好地利用缓存，因此即使是带有二进制搜索的排序 vector 也可能会更快。

如果您可以更改 Chunk 结构以存储左/右指针，您将获得有保证的 O(1) 查找/插入/删除。假设您这样做是为了合并空闲的内存块，在 free() 调用期间可以在 O(1) 中完成左/右检查，因此没有之后需要巩固一下。