我在我的一个项目中使用自定义堆实现.它由两个主要部分组成:
修复了大小块堆.即只分配特定大小的块的堆.它分配更大的内存块(虚拟内存页或来自另一个堆),然后将它们分成原子分配单元.
它快速执行分配/释放(在O(1)中)并且没有内存使用开销,没有考虑外部堆强加的事情.
全球通用堆.它由上面(固定尺寸)堆的桶组成.WRT它选择适当存储桶的请求分配大小,并通过它执行分配.
由于整个应用程序(大量)是多线程的 - 全局堆在其操作期间锁定适当的存储桶.
注意:与传统堆相比,此堆不仅要求分配大小,还要求释放分配大小.这允许在没有搜索或额外的内存开销的情况下识别适当的桶(例如在分配的块之前保存块大小).虽然不太方便,但在我的情况下这是好的.此外,由于"桶配置"在编译时是已知的(通过C++模板voodoo实现) - 在编译时确定适当的桶.
到目前为止,一切看起来(并且有效).
最近我研究了一种能够大量执行堆操作的算法,并且自然会受到堆性能的影响.分析显示其锁定会对其性能产生很大影响.也就是说,堆本身工作得非常快(典型的分配只涉及一些内存解除引用指令),但由于整个应用程序是多线程的 - 适当的存储桶受关键部分的保护,它依赖于互锁指令,这些指令很多重.
我通过给这个算法提供了自己的专用堆来解决这个问题,这个堆不受关键部分的保护.但这在代码级别强加了几个问题/限制.例如,需要在堆栈深处传递上下文信息,无论堆可能在哪里.也可以使用TLS来避免这种情况,但这可能会导致我在特定情况下重新进入时出现一些问题.
这让我想知道:是否有一种已知的技术来优化堆(但不限于)单线程使用？
编辑:
特别感谢@Voo建议查看google的tcmalloc.
它似乎与我做的更多或更少(至少对于小对象)的工作类似.但此外,他们通过维护每线程缓存来解决我所遇到的确切问题.
我也想过这个方向,但我想保持每线程堆.然后释放从属于另一个线程的堆分配的内存块有点棘手:应该将其插入到一个锁定队列中,并且应该通知其他线程,并异步释放挂起的分配.异步释放可能会导致问题:如果该线程由于某种原因而忙(例如执行积极的计算) - 实际上不会发生内存释放.此外,在多线程场景中,释放的成本要高得多.
OTOH使用缓存的想法似乎更简单,更有效.我会尝试解决它.
非常感谢.
PS:
事实上谷歌的tcmalloc很棒.我相信它的实现与我所做的非常相似(至少是固定大小的部分).
但是,要迂腐,有一件事我的堆优越.根据文档,tcmalloc大约1%的开销(渐近),而我的开销是0.0061%.确切地说是4/64K.
:)
Eri*_* J. 10
一种想法是为每个线程维护一个内存分配器.从全局内存池为每个分配器预先分配相当大的内存块.设计算法以从相邻的内存地址分配块状块(稍后将详细介绍).
当给定线程的分配器内存不足时,它会从全局内存池中请求更多内存.此操作需要锁定,但发生频率远低于当前情况.当给定线程的分配器释放它的最后一个字节时,将该分配器的所有内存返回到全局内存池(假设线程终止).
这种方法将比您当前的方法更早耗尽内存(可以为一个永远不需要它的线程保留内存).问题的严重程度取决于应用程序的线程创建/生命周期/销毁配置文件.您可以以额外的复杂性为代价来缓解这种情况,例如通过引入给定线程的内存分配器内存不足的信号,并且全局池已用完,其他内存分配器可以通过释放一些内存来响应.
该方案的一个优点是它将倾向于消除错误共享,因为给定线程的存储器倾向于在连续的地址空间中分配.
另外,如果你还没有读过它,我建议IBM的内存管理文章给任何实现自己内存管理的人.
UPDATE
如果目标是为多线程环境优化非常快的内存分配(而不是学习如何自己完成),请查看备用内存分配器.如果目标是学习,也许可以查看他们的源代码.
| 归档时间： |
|
| 查看次数： |
697 次 |
| 最近记录： |