为什么我们看不到(更多)广泛采用无锁动态内存分配器？

Question

在多线程编程环境中，堆上的锁争用经常成为性能瓶颈。

至少从理论上讲，这个问题的最佳解决方案是让可伸缩/并行的施胶分配程序完全没有锁。然而，在我看来，除了一些研究论文(如15) (其中确实包含有希望的实验结果)之外，完全没有锁的分配程序还没有渗透到生产环境中。如果你能用反例证明我是错的，我会很高兴的。那么，这种缓慢(或根本不存在)采用无锁分配器的实际原因是什么呢？请注意，更广泛使用的可伸缩分配器(如英特尔TBB中的可扩展分配程序)并不是无锁的，尽管它们使用细粒度锁(参见3.中的第315页)。

值得注意的是，我还找到了一个CMU学生项目/论文4.，声称在多达64个核心上实现了一个“略好于谷歌的 tcmalloc”的无锁分配器。这篇论文的另一个有趣之处是，“这些测试中的llalloc是无锁的公司‘S Lockless分配器，它不是100%无锁的(它在全球堆周围有一个锁)”。jemalloc和ptmalloc也在其中进行了基准测试。

参考文献：

1 Michael，M. “可伸缩的无锁动态内存分配” ACM Sigplan注意事项39.6 (2004年)：35-46.我在回复上找到了一个独立的http://people.cs.vt.edu/~scschnei/streamflow/实现迈克尔的算法

2黄，小黄，等。一种适用于许多核心计算机的可伸缩的无锁动态内存分配程序.计算机和信息技术，2010年IEEE第十届国际会议。IEEE，2010年。作为MS论文的免费版本。

3. Kukanov，Alexey和MichaelJ.Voss。英特尔线程构建块中可扩展多核软件的基础。英特尔技术杂志11.4 (2007年)。

4. Alex，不:无锁内存分配器；显然是在2013年根据父目录时间戳和课程名称中的"S13“后缀编写的。

5吉登斯塔姆，安德斯，玛丽娜帕帕特里安塔夫卢，和菲利普齐加斯。NBmalloc:以无锁的方式分配内存算法58.2 (2010年)：304-338。源代码可用于这一项。

作为一个脚注，我看到在这个问题上有4张待决的选票，但我没有看到为什么硬件加速矢量图形没有起飞？。如果有人能解释为什么一个可能会被一些客观业绩数据所回答的问题更多地是基于意见，而不是一个主要因素是2-3家大公司的市场定位的问题，那将是很有趣的。

Answer 1

以下是一些可能的答案：

• IBM已经申请了专利他们的无锁分配器.但是，他们也支持Linux等，因此他们可能有一个动机，至少提供一个实现。XMalloc的人也是为他们的专利申请专利。但我还没有现在还没有为NBmalloc找到任何专利(或专利申请)。
• 另一个本地化的问题是M.Michael似乎在那篇论文之后就停止了在IBM的出版。我不确定他是否还在使用IBM，但让他离开或切换焦点可能是IBM没有尝试生产他的分配器的原因之一，就像IBM在之前的Watson/Watson 2分配程序中将其引入AIX一样。其他的无锁分配器似乎与一家大公司没有联系，而大公司可能会把它们推向产品。
• 最后，一个更普遍的原因是代码复杂度与性能的相对比率。引用A. Gotsman等人对“证明非阻塞算法不阻止”的引用。与基于锁的数据结构相比，非阻塞数据结构通常要复杂得多，但在线程之间存在高争用时可以提供更好的性能。因此，代码复杂性必须由性能方面的显著收益来证明。虽然一些无锁的分配器文件声称.其他的论文则提出了相反的或希望清洗的结果。特别是，流纸，其作者重新实现了迈克尔的算法，声称已经击败了它使用一个不是无锁的分配器。波多尔斯基的课程论文只得到了相对有限的改进。所以我猜如果无锁的分配器值得付出额外的努力的话，陪审团还没有出来。

Answer 2

你怎么知道没有使用无锁的分配器/经销商？例如，以MacOS X和iOS上的malloc为例。你知道没有锁吗？(他们的文档显示，在同一个线程上以短序列调用malloc和free非常快速，这就是您所担心的情况)。