多线程阵列数组？

Question

我有一个数据结构，它由1000个数组元素，每个阵列元素是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的工作，然后在最后合并结果。这样在处理过程中根本不需要同步。

但这一切都回到了度量和分析。这不是一个简单的问题。