C++中的多線程多讀寫很少數組/向量迭代

我需要幾乎不斷地以只讀方式迭代一系列結構，但對於每讀取一次1M +，其中一個線程可能會附加一個項目。我認爲使用互斥鎖會在這裏過度殺傷，而且我也在某處讀過讀者鎖定它們自己的缺點。C++中的多線程多讀寫很少數組/向量迭代

我在考慮在std :: vector上使用reserve（），但這個回答Iterate over STL container using indices safe way to avoid using locks?似乎無效。

任何想法可能是最快的？最重要的是讀者能夠儘可能快地和有效地進行迭代，儘可能避免爭用。寫作操作不是時間敏感的。

更新：我的另一個用例是「list」可以包含指針而不是結構體。即，std :: vector。同樣的要求適用。

更新2：假設性例子

全局可訪問：

typedef std::vector<MyClass*> Vector; 
Vector v; 
v.reserve(50);

讀線程1-10：（這些運行幾乎所有運行的時間）

. 
. 
int total = 0; 
for (Vector::const_iterator it = v.begin(); it != v.end(); ++it) 
{ 
    MyClass* ptr = *it; 
    total += ptr->getTotal(); 
} 
// do something with total 
. 
.

寫線程11- 15：

MyClass* ptr = new MyClass(); 
v.push_back(ptr);

這基本上是在這裏發生的。雖然通常只有1-2個讀線程和1-2個寫線程，但線程1-15可以同時運行。

來源

2013-03-13 stgtscc

這些向量有多大？他們必須是數組/矢量嗎？你需要內存塊連續性嗎？你可以改變它，即元素列表或1024elements塊列表等元素？ – quetzalcoatl 2013-03-13 14:06:04

同時存在的結構數是否有界？他們是否曾經被移除，或是在原地發生了變異，或者您是否真的只是一遍又一遍地讀取相同的值？有多少讀者？ – Useless 2013-03-13 14:25:45

@quetzalcoatl向量範圍從2到20個項目，平均值在7左右。它們不需要mem連續性，但我認爲具有連續性可能更適合w.r.t緩存局部性。我願意接受任何建議。 – stgtscc 2013-03-13 15:05:26

我覺得可以在這裏工作是自己實現的vector，這樣的事情：

template <typename T> class Vector 
{ 
// constructor will be needed of course 
public: 
    std::shared_ptr<const std::vector<T> > getVector() 
     { return mVector; } 
    void push_back(const T&); 

private: 
    std::shared_ptr<std::vector<T> > mVector; 
};

然後，只要讀者需要訪問特定Vector，他們應該叫getVector()和保持返回shared_ptr直到完成閱讀。

但作家應該總是使用Vector的push_back來增加新的值。然後這個push_back應該檢查mVector.size() == mVector.capacity()是否爲真，並且分配新的vector並且將其分配給mVector。例如：

template <typename T> Vector<T>::push_back(const T& t) 
{ 
    if (mVector->size() == mVector->capacity()) 
    { 
     // make certain here that new_size > old_size 
     std::vector<T> vec = new std::vector<T> (mVector->size() * SIZE_MULTIPLIER); 

     std::copy(mVector->begin(), mVector->end(), vec->begin()); 
     mVector.reset(vec); 
    } 
// put 't' into 'mVector'. 'mVector' is guaranteed not to reallocate now. 
}

這裏的想法受RCU（讀取 - 複製 - 更新）算法的啓發。如果存儲空間耗盡，只要至少有一個讀取器訪問舊存儲，新存儲就不應使舊存儲失效。但是，應該分配新的存儲空間，並且分配之後的任何讀者應該能夠看到它。只要沒有人再使用舊存儲器（所有讀取器都已完成），應該立即釋放舊存儲器。由於大多數硬件架構提供了一些方法來實現原子增量和減量，我認爲shared_ptr（因此Vector）將能夠完全無鎖地運行。

雖然這種方法的一個缺點是，根據讀者持有多長時間shared_ptr，最終可能會得到data的多個副本。

PS：希望我沒有在代碼中犯太多尷尬的錯誤:-)

來源

2013-03-14 09:23:36 user2116939

這實際上是*完全無鎖*嗎？如果是的話，那對我的需求來說絕對是完美的。寫入可能非常昂貴，但讀取速度要快，爭用最少。 – stgtscc 2013-03-15 17:49:48

我想知道這是否會工作，並且實際上push_back（）方法中不需要鎖定。 – stgtscc 2013-03-15 17:59:25

@stgtscc：我很確定它是無鎖的_if，只有當'shared_ptr'使用特定於硬件的原子增量和減量時。有關詳細信息，您需要找出您的編譯器/庫爲您的特定硬件所做的工作。 – 2013-03-15 18:03:39

...使用儲備（）在一個std :: vector的...

這可以，如果你能保證的矢量永遠需要增長只是有用的。你已經說過，如果物品的數量是而不是以上，那麼你不能提供保證。

儘管有關聯的問題，但您可以想象使用std::vector只是爲了管理內存，但它會採用額外的邏輯層來解決接受答案中確定的問題。

實際的答案是：最快的做法是儘量減少同步的數量。什麼最小的同步數量是取決於你沒有指定的代碼和使用的細節。

例如，我使用固定大小塊的鏈接列表繪製了一個解決方案。這意味着您的常見用例應該與數組遍歷一樣高效，但是您可以動態增長而無需重新分配。

然而，實現原來是敏感到這樣的問題：

是否需要刪除項目
- 時，他們正在讀？
- 只能從前面或從其他地方？
您是否希望讀者忙等待，如果容器是空
- 是否這應該使用某種補償的
需要什麼樣的一致性程度？

來源

2013-03-13 16:56:09 Useless

我添加了一個代碼示例，如果它有幫助。儘管我認爲上面的shared_ptr解決方案可能適合該法案。我希望同步最小化。 – stgtscc 2013-03-15 19:50:34

C++中的多線程多讀寫很少數組/向量迭代

回答

相關問題