高效流失的高效堆管理器,微小的分配？

我正在寻找一个堆管理器的想法来处理一个非常具体的情况:很多很多非常小的分配,每个分配12到64个字节.任何更大的东西,我都会传递给常规堆管理器,所以只需要为小块提供服务.只需要4字节对齐.

我主要担心的是

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

性能

一个有用的方面是Lua(它是这个堆的用户)将告诉你当它调用free()时它释放的块的大小 - 这可能会启用某些优化.

我会发布我当前的方法,它运作正常,但如果可能的话,我想改进它.有任何想法吗？

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

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

将大缓冲区拆分为节点.节点大小必须至少为sizeof(void*).

将它们一起串联成单链表("空闲列表"),使用每个空闲节点的第一个sizeof(void*)字节作为链接指针.分配的节点不需要链接指针,因此每节点开销为0.

通过删除列表的头部并返回它来分配(2个加载,1个存储).

通过插入列表的头部免费(1个加载,2个商店).

显然,第3步还必须检查列表是否为空,如果是,那么做一堆新的大缓冲区(或失败).

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

编辑:在这两种情况下,free都可以处理复杂的"我在常规堆管理器上传递的任何更大的东西",这是因为你在免费调用中获得了大小.否则,您将查看一个标志(每个节点的开销可能为4个字节),或者在您使用的缓冲区的某种记录中查找.