Dre*_*rew 5 c multithreading pthreads
假设我有一个包含 1,000,000 个元素的数组，以及许多工作线程，每个线程都在处理这个数组中的数据。工作线程可能会用新数据更新已填充的元素，但每个操作仅限于单个数组元素，并且独立于任何其他元素的值。
使用单个互斥锁来保护整个阵列显然会导致高争用。在另一个极端，我可以创建一个与原始数组长度相同的互斥锁数组，并且对于每个元素array[i]我都会mutex[i]在操作时锁定它。假设数据分布均匀，这将主要消除锁争用，代价是大量内存。
我认为更合理的解决方案是拥有一组n互斥体（其中 1 < n < 1000000）。然后对于每个元素，array[i]我会mutex[i % n]在操作时锁定它。如果n足够大，我仍然可以最大限度地减少争用。
所以我的问题是，除了增加内存使用量之外，以这种方式使用大量（例如 >= 1000000）互斥量是否会降低性能？如果是这样，在您开始看到降级之前，您可以合理使用多少互斥锁？
我确信这个问题的答案在某种程度上是特定于平台的；我在 Linux 上使用 pthreads。我也在努力建立我自己的基准，但我正在处理的数据规模使得这很耗时，所以一些初步的指导将不胜感激。
那是最初的问题。对于那些询问有关该问题的更详细信息的人，我有 4 个多 GB 的二进制数据文件，描述了正在分析的大约 50 亿个事件的某个地方。有问题的数组实际上是支持一个非常大的链式哈希表的指针数组。我们将四个数据文件读入哈希表，如果它们共享某些特征，可能会将它们聚合在一起。现有的实现有 4 个线程，每个线程读取一个文件并将该文件中的记录插入到哈希表中。哈希表有 997 个锁和 997*9973 = ~10,000,000 个指针。当插入一个带有 hash 的元素时h，我mutex[h % 997]在插入或修改元素之前先锁定bucket[h % 9943081]. 这一切正常，据我所知，我们没有太多的争用问题，但存在性能瓶颈，因为我们只使用了 16 核机器的 4 个核。（随着我们的深入，甚至更少，因为文件的大小通常不一样。）一旦所有数据都被读入内存，然后我们分析它，它使用新线程和新的锁定策略调整到不同的工作量。
我试图通过切换到线程池来提高数据加载阶段的性能。在新模型中，每个文件我仍然有一个线程，它只是以 ~1MB 的块读取文件，并将每个块传递给池中的工作线程以进行解析和插入。到目前为止，性能提升很小，我所做的分析似乎表明锁定和解锁阵列所花费的时间可能是罪魁祸首。锁定内置于我们正在使用的哈希表实现中，但它允许指定要使用的锁的数量，而与表的大小无关。我希望在不更改哈希表实现本身的情况下加快速度。
（对你的问题的非常片面且可能是间接的回答。）
曾经尝试过这样做（在 CentOS 上），将锁的数量从大约 1K 的素数提高到大约 1M 的素数，从而获得了巨大的性能损失。虽然我从未完全理解其原因，但我最终发现（或者只是说服自己）这是一个错误的问题。
假设你有一个长度为M的数组，有n 个工人。此外，您使用散列函数来保护具有m < M锁的M个元素（例如，通过某种随机分组）。然后，使用生日悖论的平方近似，两个工人之间发生碰撞的机会 - p - 由下式给出：
p ~ n 2 / (2m)
由此可见，您需要的互斥体数量m根本不依赖于M - 它只是p和n的函数。