高效的堆管理器,用于大批量、小型allocs?

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

要扩展Greg Hewgill所说的内容,实现超高效固定大小堆的一种方法是:

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

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

编辑:在这两种情况下,free都可以处理“我在常规堆管理器上传递的任何更大的东西”这一复杂问题,这是一个有用的事实,即您可以在调用free时重新获得大小。否则,您将查看标志(开销可能是每个节点4个字节),或者查找您使用的缓冲区的某种记录。

陈雷蒙做了一个演讲 interesting post 这可能有助于激励你。:)

我喜欢一个接一个的回答。

你也可以考虑 buddy system 用于固定大小的堆集。

如果在进入下一轮分配之前分配、使用和释放了大量内存,我建议使用最简单的分配器:

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

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

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

2) 超级块分为块(大小也可调整…4K-64K根据应用程序而定)。每个块处理特定大小的分配,并将块中的所有项存储为单链表。分配超级块时,将生成可用块的链接列表。

4) 按地址释放项意味着A)查找包含地址(*)的超块B)查找超块中的块(减去超块开始地址并除以块大小)C)将项推回到块的自由项列表上。

正如我所说的,这个SBMM运行速度非常快,因为它具有O(1)性能(*)。在我已经实现的版本中,我使用了一个AtomicSList(类似于Windows中的SLIST),因此在实现中它不仅是O(1)性能,而且是线程安全和无锁的。如果愿意,您可以使用Win32 SLIST实现该算法。

(*)超块以O(1)平均性能排列在一个范围图中(但对于最坏的情况,潜在的O(Lg N),其中N是超块的数量)。范围图的宽度取决于大致知道要获得O(1)性能需要多少内存。如果过冲,将浪费一点内存,但仍会获得O(1)性能。如果未命中,将接近O(Lg N)性能,但N表示超级块计数,而不是项目计数。由于超级块计数与项计数相比非常低(在我的代码中大约是20个二进制数量级),因此它不像分配器的其余部分那么重要。