8

我正在寻找堆管理器的想法来处理非常具体的情况：很多非常小的分配，每个分配范围从 12 到 64 字节。任何更大的东西，我都会传递给常规的堆管理器，所以只需要处理小块。只需要 4 字节对齐。

我主要担心的是

  1. 高架。常规的 libc 堆通常会将分配四舍五入为 16 字节的倍数，然后添加另一个 16 字节标头 - 这意味着 20 字节分配的开销超过 50%，这很糟糕。
  2. 表现

一个有用的方面是 Lua（它是这个堆的用户）会在调用 free() 时告诉你它正在释放的块的大小——这可能会启用某些优化。

我会发布我目前的方法，它工作正常，但如果可能的话，我想改进它。有任何想法吗？

4

6 回答 6

6

可以构建一个对大小相同的对象非常有效的堆管理器。您可以为所需的每种大小的对象创建其中一个堆，或者如果您不介意使用一点空间，则为 16 字节对象创建一个，为 32 字节对象创建一个，为 64 个字节创建一个。最大开销为31 字节分配 33 字节（将在 64 块大小的堆上进行）。

于 2008-10-23T00:55:02.953 回答
6

为了扩展 Greg Hewgill 所说的，实现超高效的固定大小堆的一种方法是：

  1. 将大缓冲区拆分为节点。节点大小必须至少为 sizeof(void*)。
  2. 使用每个空闲节点的第一个 sizeof(void*) 字节作为链接指针，将它们串在一起形成一个单链表（“空闲列表”）。分配的节点不需要链接指针，因此每个节点的开销为 0。
  3. 通过删除列表的头部并返回它来分配（2 个加载，1 个存储）。
  4. 通过在列表头部插入来释放（1 个加载，2 个存储）。

显然，第 3 步还必须检查列表是否为空，如果是，则需要进行大量工作以获取新的大缓冲区（或失败）。

正如 Greg D 和 hazzen 所说，更有效的是通过递增或递减指针（1 次加载，1 次存储）进行分配，而根本不提供释放单个节点的方法。

编辑：在这两种情况下，免费都可以处理“我在常规堆管理器上传递的任何更大的东西”的复杂性，因为您可以在调用 free 时恢复大小。否则，您将查看一个标志（每个节点的开销可能为 4 个字节），或者在您使用的缓冲区的某种记录中查找。

于 2008-10-23T01:10:08.600 回答
3

答案可能取决于这些对象的生命周期模式。如果对象在您继续进行时全部实例化，然后一举全部删除，则创建一个非常简单的堆管理器可能有意义，该堆管理器通过简单地递增指针来分配内存。然后，当你完成后，吹走整个堆。

Raymond Chen 发表了一篇有趣的文章，可能对您有所启发。:)

于 2008-10-23T01:02:15.370 回答
1

我喜欢onebyones的回答。

您也可以考虑为您的固定大小堆集使用伙伴系统。

于 2008-10-23T02:20:16.947 回答
0

如果在进行下一轮分配之前分配、使用和释放了一堆内存，我建议使用最简单的分配器：

typedef struct _allocator {
    void* buffer;
    int start;
    int max;
} allocator;

void init_allocator(size_t size, allocator* alloc) {
    alloc->buffer = malloc(size);
    alloc->start = 0;
    alloc->max = size;
}

void* allocator_malloc(allocator* alloc, size_t amount) {
    if (alloc->max - alloc->start < 0) return NULL;
    void* mem = alloc->buffer + alloc->start;
    alloc->start += bytes;
    return mem;
}

void allocator_free(allocator* alloc) {
    alloc->start = 0;
}
于 2008-10-23T01:05:38.313 回答
0

我主要使用 O(1) 小块内存管理器 (SBMM)。基本上它是这样工作的：

1) 它从操作系统分配更大的超级块，并将开始+结束地址作为一个范围进行跟踪。SuperBlock 的大小是可调的，但 1MB 是一个相当不错的大小。

2) 超级块被分成块（大小也可调节……4K-64K 好，具体取决于您的应用程序）。这些块中的每一个都处理特定大小的分配，并将块中的所有项目存储为单链表。当你分配一个 SuperBlock 时，你会创建一个 Free Blocks 的链表。

3) 分配一个项目意味着 A) 检查是否有一个带有空闲项目的块处理该大小 - 如果没有，则从超级块分配一个新块。B) 从块的空闲列表中删除该项目。

4) 通过地址释放项目意味着 A) 找到包含地址的超级块 (*) B) 在超级块中找到块（减去超级块的起始地址并除以块大小） C) 将项目推回到块的空闲项目列表中。

正如我所说，这个 SBMM 非常快，因为它以 O(1) 的性能 (*) 运行。在我实现的版本中，我使用了一个 AtomicSList（类似于 Windows 中的 SLIST），因此它不仅是 O(1) 性能，而且在实现中还有 ThreadSafe 和 LockFree。如果您愿意，您实际上可以使用 Win32 SLIST 来实现该算法。

有趣的是，从 SuperBlocks 分配 Blocks 或从 Blocks 分配项目的算法导致几乎相同的代码（它们都是 O(1) 的空闲列表分配）。

(*) SuperBlocks 排列在一个范围图中，平均性能为 O(1)（但在 N 是 SuperBlocks 数量的最坏情况下可能存在 O(Lg N)）。范围图的宽度取决于大致了解您需要多少内存才能获得 O(1) 性能。如果你过冲，你会浪费一点内存，但仍然可以获得 O(1) 性能。如果您低于目标，您将接近 O(Lg N) 性能，但 N 用于 SuperBlock 计数 - 而不是项目计数。由于 SuperBlock 计数与 Item 计数相比非常低（在我的代码中大约是 20 个二进制数量级），因此它不像分配器的其余部分那么重要。

于 2009-09-28T04:30:56.610 回答