我需要分配,并释放大量固定大小的小(16字节)内存块,没有固定的顺序.我可以为每个人调用malloc并释放,但这可能效率很低.一个更好的解决方案可能是调用malloc并释放更大的块,并处理这些块本身的分配.
问题是,如何最好地做到这一点？
这似乎不应该是一个非常不寻常的问题或罕见的问题,它应该已经"解决",但我似乎找不到任何东西.有什么指针吗？
为了澄清,我知道内存池库,什么不存在,但这些也需要一个大小参数.如果大小是恒定的,那么可以使用更高效算法的不同选项,这些是否有任何实现？
你是对的,这是一个常见的问题[编辑:如何进行固定大小的分配,我的意思是." malloc正在减慢我的应用程序"并不像你想象的那么常见].
如果你的代码太慢而且malloc是一个看似合理的罪魁祸首,那么一个简单的单元分配器(或"内存池")可能会改进.几乎可以肯定在某个地方找到一个,或者写起来很容易:
分配一个大块,并在每个16字节单元的开头放置一个单链接列表节点.把它们连在一起.要分配,请从列表中删除并返回它.要释放,请将单元格添加到列表的开头.当然,如果你尝试分配并且列表为空,那么你必须分配一个新的大块,将它分成单元格,然后将它们全部添加到空闲列表中.
如果你愿意,你可以避免那么大的前期工作.分配大块时,只需存储指向它结尾的指针.要分配,请将指针移回块中的16个字节并返回新值.当然,除非它已经在块[*]的开头.如果发生这种情况,并且空闲列表也是空的,则需要一个新的大块.Free不会更改 - 只需将节点添加到空闲列表即可.
您可以选择是先退出该块,还是先检查空闲列表(如果已用尽),或先检查空闲列表,如果空白,则处理该块.我不知道哪个往往更快 - 一个倒数第一的免费列表的好处是它是缓存友好的,因为你使用的是最近使用的内存,所以我可能会尝试第一.
请注意,在分配单元时不需要列表节点,因此每个单元的开销基本上为零.除了速度之外,这可能比malloc其他通用分配器更具优势.
请注意,丢弃整个分配器几乎是将内存释放回系统的唯一方法,因此计划分配大量单元,使用它们并将它们全部释放的用户应该创建自己的分配器,使用它,然后摧毁它.两者都是为了性能(您不必释放所有单元格)并防止碎片式效果,如果任何单元格正在使用中必须保留整个块.如果你不能这样做,你的记忆使用将是你的程序运行时间的最高标记.对于某些有问题的程序(例如,长时间运行的程序,内存使用偶尔会出现大量峰值,在内存受限的系统上).对于其他人来说,它绝对没问题(例如,如果使用的细胞数量增加,直到非常接近程序结束,或者在你真正不关心你使用的内存超出严格要求的范围内波动.对于一些它的主动需求(如果你知道你将要使用多少内存,你可以预先分配它,而不必担心失败).就此而言,一些实现malloc 难以将内存从进程释放回操作系统.
[*]其中"块的开始"可能意味着"块的开始,加上用于维护所有块列表的某个节点的大小,因此当单元分配器被销毁时它们都可以被释放".