我在我的一个项目中使用了自定义堆实现。它由两个主要部分组成:
固定大小的 block 堆。 IE。仅分配特定大小的 block 的堆。它分配更大的内存块(虚拟内存页或来自另一个堆)，然后将它们划分为原子分配单元。
它快速执行分配/释放(在 O(1) 中)并且没有内存使用开销，不考虑外部堆强加的东西。
全局通用堆。它由上述(固定大小)堆的桶组成。 WRT 请求的分配大小，它选择适当的存储桶，并通过它执行分配。
由于整个应用程序(大量)是多线程的 - 全局堆在其操作期间锁定适当的存储桶。
注意:与传统堆相比，这种堆不仅需要分配大小，还需要释放。这允许在没有搜索或额外内存开销(例如保存分配 block 之前的 block 大小)的情况下识别适当的存储桶。虽然不太方便，但在我的情况下这是可以的。此外，由于“桶配置”在编译时是已知的(通过 C++ 模板 voodoo 实现) - 适当的桶在编译时确定。
到目前为止，一切看起来(并且工作)都很好。
最近我研究了一种算法，该算法会大量执行堆操作，并且自然会受到堆性能的显着影响。分析显示其性能受到锁定的显着影响。也就是说，堆本身的工作速度非常快(典型的分配只涉及一些内存取消引用指令)，但由于整个应用程序是多线程的 - 适当的存储桶受关键部分保护，它依赖于 interlocked 指令，要重得多。
我同时通过为该算法提供自己的专用堆来解决此问题，该堆不受关键部分的保护。但这在代码级别施加了几个问题/限制。例如需要在堆栈深处传递上下文信息的地方可能需要堆。也可以使用 TLS 来避免这种情况，但在我的具体情况下，这可能会导致重新进入时出现一些问题。
这让我想知道:是否有一种已知的技术可以针对(但不限于)单线程使用来优化堆？
编辑:
特别感谢 @Voo 建议检查 google 的 tcmalloc。
它似乎或多或少地与我所做的相似(至少对于小物体)。但此外，他们通过维护每个线程缓存解决了我遇到的确切问题。
我也想过这个方向，但我考虑过维护每个线程的堆。然后释放从属于另一个线程的堆中分配的内存块有点棘手:应该将它插入某种锁定队列中，并且应该通知另一个线程，并异步释放挂起的分配。异步释放可能会导致问题:如果该线程由于某种原因很忙(例如执行激进的计算) - 实际上不会发生内存释放。此外，在多线程场景中，重新分配的成本要高得多。
OTOH 缓存的想法似乎更简单，更有效。我会努力解决的。
非常感谢。
附注:
确实 google 的 tcmalloc 很棒。我相信它的实现与我所做的非常相似(至少是固定大小的部分)。
但是，为了迂腐，有一个问题是我的堆更胜一筹。根据文档，tcmalloc 会产生大约 1% 的开销(渐近)，而我的开销是 0.0061%。准确地说是 4/64K。
:)
最佳答案
一种想法是为每个线程维护一个内存分配器。从全局内存池中为每个分配器预先分配相当大的内存块。设计你的算法来分配来自相邻内存地址的大块(稍后会详细介绍)。
当给定线程的分配器内存不足时，它会从全局内存池中请求更多内存。此操作需要锁定，但发生的频率应该远低于您当前的情况。当给定线程的分配器释放它的最后一个字节时，将该分配器的所有内存返回到全局内存池(假设线程已终止)。
这种方法会比您当前的方法更早地耗尽内存(内存可以保留给一个永远不需要它的线程)。这是一个问题的程度取决于您的应用程序的线程创建/生命周期/销毁配置文件。您可以以增加复杂性为代价来缓解这种情况，例如通过引入一个信号，表明给定线程的内存分配器内存不足，并且全局池已用尽，其他内存分配器可以通过释放一些内存来响应。
这种方案的一个优点是它倾向于消除 false sharing ，因为给定线程的内存往往会分配在连续的地址空间中。
附带说明，如果您还没有阅读，我建议 IBM's Inside Memory Management任何实现自己的内存管理的人的文章。
更新
如果目标是为多线程环境优化非常快速的内存分配(而不是自己学习如何去做)，请查看备用内存分配器。如果目标是学习，不妨看看他们的源代码。
关于c++ - 堆优化(但不限于)单线程使用，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10688479/