高流通量、小分配的高效堆管理器？

在对象大小都相同的情况下，可以构建非常高效的堆管理器。您可以为每个所需的对象大小创建一个这样的堆，或者如果您不介意使用一些空间，可以为 16 字节、32 字节和 64 字节的对象分别创建一个堆。最大的开销将是 33 字节的分配的 31 字节开销（将使用 64 块大小的堆）。

答案可能取决于这些对象的生存期模式。如果对象在您进行操作时全部实例化，然后一次性全部移除，那么创建一个非常简单的堆管理器可能是有意义的，它通过简单地增加指针来分配内存。然后，当您完成后，消除整个堆。

雷蒙德·陈（Raymond Chen）发布了一篇 有趣的帖子，这可能会给您带来灵感。:)

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

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;
}

为了补充Greg Hewgill的观点，一种实现极其高效的固定大小堆的方法如下：

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

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

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

编辑：在两种情况下，free都可以处理“我通过常规堆管理器传递的任何更大的东西”的复杂情况，因为在调用free时会返回大小。否则，您可能会看到要么是标志（每个节点的开销可能为4个字节），要么是在您使用的缓冲区的某种记录中进行查找。

我喜欢 onebyones 的答案。

你也可以考虑为你的固定大小堆设置使用buddy system。

我使用一个基本上是O(1)的小块内存管理器(SBMM)。基本上它的工作方式如下：

1. 它从操作系统中分配更大的SuperBlocks并将其跟踪起始和结束地址作为一个范围。SuperBlock的大小是可以调整的，但1MB是一个非常好的大小。

2. SuperBlocks被分为块(大小也可以调整...4K-64K是好的，根据您的应用程序)。每个块处理特定大小的分配并将所有项存储在块中作为其单链表。当您分配一个SuperBlock时，您会创建一个自由块的链表。

3. 分配一个项目的意思是A)检查是否有处理该大小的空闲项的块 - 如果没有，则从SuperBlocks分配一个新的块。B)从块的自由列表中删除该项。

4. 根据地址释放一个项目的意思是A)查找包含地址的SuperBlock(*) B)在SuperBlock中找到Block(减去SuperBlock起始地址并除以块大小) C)将项目推回到块的自由项列表中。

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

有趣的是，从SuperBlocks分配块或从块分配项目的算法的代码几乎相同(它们都是从Free List中进行O(1)分配)。

(*) SuperBlocks是按O(1)的平均性能排列在范围映射中(但在最坏情况下可能为O(Lg N)，其中N是SuperBlocks的数量)。范围映射的宽度取决于大致知道您需要多少内存才能获得O(1)的性能。如果您超调，您会浪费一些内存，但仍会获得O(1)的性能。如果您保守估计，您将接近O(Lg N)的性能，但N是针对SuperBlock计数 - 而不是项计数。由于SuperBlock计数与项计数相比非常低(在我的代码中大约有20个二进制数量级)，因此它不像分配器的其他部分那样关键。