大量互斥体的性能影响
假设我有一个包含1,000,000个元素的数组，以及一些工作线程，每个线程操作此数组中的数据。 工作线程可能正在使用新数据更新已填充的元素，但每个操作仅限于单个数组元素，并且与任何其他元素的值无关。
使用单个互斥锁来保护整个arrays显然会导致高争用。 在另一个极端，我可以创建一个与原始数组长度相同的互斥量数组，对于每个元素array[i]我会在操作时锁定mutex[i] 。 假设数据均匀分布，这将主要消除锁争用，代价是大量内存。
我认为更合理的解决方案是拥有一组n互斥体（其中1 <n <1000000）。 然后对于每个元素array[i]我会在操作时锁定mutex[i % n] 。 如果n足够大，我仍然可以最小化争用。
所以我的问题是，除了增加的内存使用量之外，以这种方式使用大量（例如> = 1000000）数量的互斥量会有性能损失吗？ 如果是这样，在开始看到退化之前，您可以合理使用多少互斥锁？
我相信这个问题的答案有点特定于平台; 我在Linux上使用pthreads。 我也在努力建立自己的基准测试，但是我正在研究的数据规模使得这个时间非常耗时，因此我们会对一些初步指导意见表示赞赏。
这是最初的问题。 对于那些要求提供有关该问题的更详细信息的人，我有4个多GB二进制数据文件，描述了正在分析的5亿个事件附近的某个地方。 有问题的数组实际上是支持非常大的链式哈希表的指针数组。 我们将四个数据文件读入哈希表，如果它们共享某些特征，则可能将它们聚合在一起。 现有实现有4个线程，每个线程读取一个文件并将该文件中的记录插入到哈希表中。 哈希表有997个锁和997 * 9973 = ~10,000,000个指针。 当插入带有散列h的元素h ，我首先在插入或修改bucket[h % 9943081]的元素bucket[h % 9943081]之前锁定mutex[h % 997] bucket[h % 9943081] 。 这可以正常工作，据我所知，我们没有太多的争用问题，但是存在性能瓶颈，因为我们只使用16核机器的4核。 （因为我们的文件通常不是都大小相同，所以更少。）一旦所有数据都被读入内存，我们就会分析它，它使用新线程和一个新的锁定策略调整到不同的工作量。
我试图通过切换到线程池来提高数据加载阶段的性能。 在新模型中，我仍然为每个文件都有一个线程，它只是以~1MB块的forms读取文件，并将每个块传递给池中的工作线程进行解析和插入。 到目前为止，性能提升很小，我所做的分析似乎表明锁定和解锁arrays所花费的时间可能是罪魁祸首。 锁定内置于我们正在使用的哈希表实现中，但它允许指定独立于表大小使用的锁数。 我希望在不改变哈希表实现本身的情况下加快速度。
（对你的问题非常局部和可能是间接的答案。）
曾经尝试过（在CentOS上）将锁的数量从~1K的素数提高到~100的素数时获得了巨大的性能。 虽然我从未完全理解其原因，但我最终想出（或只是说服自己）这是错误的问题。
假设你有一个长度为M的数组，有n个工人。 此外，您使用哈希函数来保护具有m
p~n 2 /（2m）
因此，你需要的互斥量m的数量完全不依赖于M – 它只是p和n的函数。
在Linux下，除了与更多互斥锁相关的内存之外，没有任何其他成本。
但是 ，请记住，互斥锁使用的内存必须包含在您的工作集中 – 如果您的工作集大小超过相关的缓存大小，您将看到显着的性能下降。 这意味着您不需要过大的互斥锁arrays。
正如Ami Tavory指出的那样，争用取决于互斥锁的数量和线程数，而不是受保护的数据元素的数量 – 因此没有理由将互斥锁的数量与数据元素的数量联系起来（明显的条件是它拥有比元素更多的互斥体永远没有意义。
在一般情况下，我会建议
-
简单地锁定整个arrays（简单，通常“足够好”，如果您的应用程序除了访问arrays之外主要做“其他东西”）
… 要么 …
-
在整个arrays上实现读/写锁定（假设读取等于或超过写入）
显然你的情况与这两种情况都不匹配。
问：您是否考虑过实施某种“写队列”？
最坏的情况是，你只需要一个互斥锁。 最好的情况是，您甚至可以使用无锁机制来管理队列。 在这里查看可能适用的一些想法： https ： //msdn.microsoft.com/en-us/library/windows/desktop/ee418650%28v=vs.85%29.aspx