多線程陣列數組？

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的工作，然後在最後合併結果。這樣在處理過程中根本不需要同步。

但這一切都回到了度量和分析。這不是一個簡單的問題。