多线程数组阵列？

Question

我有一个由1,000个数组元素组成的数据结构,每个数组元素是一个8个整数的较小数组:

std::array<std::array<int, 8>, 1000>

数据结构包含两个"指针",它们跟踪最大和最小的填充数组元素(在"外部",1000元素数组中).例如,他们可能是:

min = 247 
max = 842

如何从多个线程读取和写入此数据结构？我担心推/弹元素和维持两个"指针"之间的竞争条件.我的基本操作方式是:

// Pop element from current index
// Calculate new index
// Write element to new index
// Update min and max "pointers"

Answer 1

您当前的算法不是线程安全的，这是正确的，有很多地方可能会发生争用。

如果没有更多信息，这是不可能优化的。在进行改进之前，您需要知道速度下降的地方，为此您需要指标。分析您的代码并找出哪些位实际占用了时间，因为您只能通过并行化这些位来获得收益，即使这样您也可能会发现实际上是内存或其他东西才是限制因素，而不是 CPU。

最简单的方法就是锁定整个过程的整个结构。仅当线程还执行大量其他处理时，这才有效，否则与单线程相比，您实际上会损失性能。

之后，您可以考虑为数据结构的不同部分使用单独的锁。您需要正确分析您在何时何地使用的内容，并找出哪些内容对拆分有用。例如，您可能有子数组块，每个块都有自己的锁。

不过，在这种情况下要小心死锁，您可能有一个线程声明 32，然后需要 79，而另一个线程已经声明了 79，然后需要 32。请确保始终以相同的顺序声明锁。

最快的选择（如果可能）甚至可能是为每个线程提供自己的数据结构副本，每个线程处理 1/N 的工作，然后在最后合并结果。这样在处理过程中根本不需要同步。

但这一切又回到了指标和分析。这不是一个简单的问题。