大量互斥锁的性能影响
Performance implications of a large number of mutexes
假设我有一个包含 1,000,000 个元素的数组，以及多个工作线程，每个工作线程都在处理该数组中的数据。工作线程可能正在用新数据更新已经填充的元素，但每个操作仅限于单个数组元素，并且独立于任何其他元素的值。
使用单个互斥锁来保护整个数组显然会导致高争用。在另一个极端，我可以创建一个与原始数组长度相同的互斥体数组，并且对于每个元素 array[i] 我会在对其进行操作时锁定 mutex[i] 。假设数据分布均匀，这将主要消除锁争用，但会占用大量内存。
我认为更合理的解决方案是拥有一个 n 互斥量数组（其中 1 < n < 1000000）。然后对于每个元素 array[i] 我会在对其进行操作时锁定 mutex[i % n] 。如果 n 足够大，我仍然可以尽量减少争用。
所以我的问题是，除了增加内存使用量之外，以这种方式使用大量（例如 >= 1000000）互斥量是否会降低性能？如果是这样，在开始看到性能下降之前，您可以合理使用多少个互斥体？
我确定这个问题的答案在某种程度上是特定于平台的；我在 Linux 上使用 pthreads。我也在努力建立自己的基准，但我正在处理的数据规模非常耗时，所以一些初步指导将不胜感激。
这是最初的问题。对于那些询问有关该问题的更多详细信息的人，我有 4 个多 GB 的二进制数据文件，描述了正在分析的 50 亿个事件附近的某个地方。有问题的数组实际上是支持非常大的链式哈希 table 的指针数组。我们将四个数据文件读入散列 table，如果它们具有某些共同特征，则可能将它们聚合在一起。现有的实现有 4 个线程，每个线程读取一个文件并将该文件中的记录插入哈希 table。散列 table 有 997 个锁和 997*9973 = ~10,000,000 个指针。当插入一个hash为h的元素时，我先锁定mutex[h % 997]，然后再插入或修改bucket[h % 9943081]中的元素。这一切正常，据我所知，我们没有遇到太多争用问题，但存在性能瓶颈，因为我们只使用了 16 核机器的 4 个核。 （随着我们的进展，文件的大小通常会越来越少。）一旦所有数据都被读入内存，我们就会对其进行分析，这会使用新的线程和针对不同文件调整的新锁定策略工作量。
我正在尝试通过切换到线程池来提高数据加载阶段的性能。在新模型中，我仍然为每个文件分配一个线程，它简单地以 ~1MB 块的形式读取文件，并将每个块传递给池中的工作线程以进行解析和插入。到目前为止，性能提升微乎其微，我所做的分析似乎表明锁定和解锁阵列所花费的时间可能是罪魁祸首。锁定内置于我们正在使用的散列 table 实现中，但它确实允许指定要使用的锁的数量，而与 table 的大小无关。我希望在不更改哈希 table 实现本身的情况下加快速度。
（对您问题的非常片面且可能是间接的回答。）
曾经（在 CentOS 上）尝试将锁的数量从 ~1K 的素数增加到 ~1M 的素数，从而获得了巨大的性能提升。虽然我从来没有完全理解它的原因，但我最终发现（或者只是说服自己）这是一个错误的问题。
假设您有一个长度为 M 的数组，其中有 n 个工人。此外，您使用散列函数通过 m < M 锁（例如，通过一些随机分组）来保护 M 元素。然后，使用 Square Approximation to the Birthday Paradox，两个工人之间发生碰撞的机会 - p - 由下式给出：
p ~ n2 / (2m)
因此，您需要的互斥锁数量 m 根本不取决于 M - 它是仅 p 和 n。
在 Linux 下，除了与更多互斥锁关联的内存之外，没有任何成本。
但是，请记住，您的互斥体使用的内存必须包含在您的工作集中 - 如果您的工作集大小超过相关缓存大小，您将看到显着的性能下降。这意味着您不想要一个过大的互斥数组。
正如 指出的那样，争用取决于互斥锁的数量和线程的数量，而不是受保护的数据元素的数量 - 因此没有理由 link 互斥锁的数量数据元素的数量（有一个明显的附带条件，即拥有比元素多更多个互斥锁是没有意义的）。
一般情况下，我会建议
简单地锁定整个数组（很简单，通常 "good enough" 如果您的应用程序除了访问数组之外大部分时间都在做 "other stuff"）
...或...
对整个数组实施 read/write 锁定（假设读取等于或超过写入）
显然你的情况不符合这两种情况。
问：您是否考虑过实施某种 "write queue"？
最坏的情况，你只需要一个互斥。最好的情况是，您甚至可以使用无锁机制来管理您的队列。在这里寻找一些可能适用的想法：https://msdn.microsoft.com/en-us/library/windows/desktop/ee418650%28v=vs.85%29.aspx
假设我有一个包含 1,000,000 个元素的数组，以及多个工作线程，每个工作线程都在处理该数组中的数据。工作线程可能正在用新数据更新已经填充的元素，但每个操作仅限于单个数组元素，并且独立于任何其他元素的值。
使用单个互斥锁来保护整个数组显然会导致高争用。在另一个极端，我可以创建一个与原始数组长度相同的互斥体数组，并且对于每个元素 array[i] 我会在对其进行操作时锁定 mutex[i] 。假设数据分布均匀，这将主要消除锁争用，但会占用大量内存。
我认为更合理的解决方案是拥有一个 n 互斥量数组（其中 1 < n < 1000000）。然后对于每个元素 array[i] 我会在对其进行操作时锁定 mutex[i % n] 。如果 n 足够大，我仍然可以尽量减少争用。
所以我的问题是，除了增加内存使用量之外，以这种方式使用大量（例如 >= 1000000）互斥量是否会降低性能？如果是这样，在开始看到性能下降之前，您可以合理使用多少个互斥体？
我确定这个问题的答案在某种程度上是特定于平台的；我在 Linux 上使用 pthreads。我也在努力建立自己的基准，但我正在处理的数据规模非常耗时，所以一些初步指导将不胜感激。
这是最初的问题。对于那些询问有关该问题的更多详细信息的人，我有 4 个多 GB 的二进制数据文件，描述了正在分析的 50 亿个事件附近的某个地方。有问题的数组实际上是支持非常大的链式哈希 table 的指针数组。我们将四个数据文件读入散列 table，如果它们具有某些共同特征，则可能将它们聚合在一起。现有的实现有 4 个线程，每个线程读取一个文件并将该文件中的记录插入哈希 table。散列 table 有 997 个锁和 997*9973 = ~10,000,000 个指针。当插入一个hash为h的元素时，我先锁定mutex[h % 997]，然后再插入或修改bucket[h % 9943081]中的元素。这一切正常，据我所知，我们没有遇到太多争用问题，但存在性能瓶颈，因为我们只使用了 16 核机器的 4 个核。 （随着我们的进展，文件的大小通常会越来越少。）一旦所有数据都被读入内存，我们就会对其进行分析，这会使用新的线程和针对不同文件调整的新锁定策略工作量。
我正在尝试通过切换到线程池来提高数据加载阶段的性能。在新模型中，我仍然为每个文件分配一个线程，它简单地以 ~1MB 块的形式读取文件，并将每个块传递给池中的工作线程以进行解析和插入。到目前为止，性能提升微乎其微，我所做的分析似乎表明锁定和解锁阵列所花费的时间可能是罪魁祸首。锁定内置于我们正在使用的散列 table 实现中，但它确实允许指定要使用的锁的数量，而与 table 的大小无关。我希望在不更改哈希 table 实现本身的情况下加快速度。
（对您问题的非常片面且可能是间接的回答。）
曾经（在 CentOS 上）尝试将锁的数量从 ~1K 的素数增加到 ~1M 的素数，从而获得了巨大的性能提升。虽然我从来没有完全理解它的原因，但我最终发现（或者只是说服自己）这是一个错误的问题。
假设您有一个长度为 M 的数组，其中有 n 个工人。此外，您使用散列函数通过 m < M 锁（例如，通过一些随机分组）来保护 M 元素。然后，使用 Square Approximation to the Birthday Paradox，两个工人之间发生碰撞的机会 - p - 由下式给出：
p ~ n2 / (2m)
因此，您需要的互斥锁数量 m 根本不取决于 M - 它是仅 p 和 n。
在 Linux 下，除了与更多互斥锁关联的内存之外，没有任何成本。
但是，请记住，您的互斥体使用的内存必须包含在您的工作集中 - 如果您的工作集大小超过相关缓存大小，您将看到显着的性能下降。这意味着您不想要一个过大的互斥数组。
正如
一般情况下，我会建议
简单地锁定整个数组（很简单，通常 "good enough" 如果您的应用程序除了访问数组之外大部分时间都在做 "other stuff"）
...或...
对整个数组实施 read/write 锁定（假设读取等于或超过写入）
显然你的情况不符合这两种情况。
问：您是否考虑过实施某种 "write queue"？
最坏的情况，你只需要一个互斥。最好的情况是，您甚至可以使用无锁机制来管理您的队列。在这里寻找一些可能适用的想法：https://msdn.microsoft.com/en-us/library/windows/desktop/ee418650%28v=vs.85%29.aspx