1

読み取り専用の方法で一連の構造体をほぼ常に反復処理する必要がありますが、1M 以上の読み取りごとに、スレッドの 1 つがアイテムを追加する場合があります。ここでミューテックスを使用するのはやり過ぎだと思います。また、読み取り/書き込みロックには読者にとって独自の欠点があることもどこかで読みました。

私は std::vector で reserve() を使用することを考えていましたが、この回答ロックの使用を避けるためにインデックスセーフな方法を使用して STL コンテナーを反復処理しますか? それを無効にしているように見えました。

どの方法が最速であるかについてのアイデアはありますか? 最も重要なことは、読者が競合をできるだけ少なくして、迅速かつ効率的に反復できるようにすることです。書き込み操作は時間に依存しません。

更新: 私の使用例のもう 1 つは、「リスト」に構造体ではなくポインターを含めることができるということです。つまり、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 ～ 15 はすべて同時に実行できますが、通常は 1 ～ 2 個の読み取りスレッドと 1 ～ 2 個の書き込みスレッドしかありません。

4

2 に答える 2

4

ここでうまくいくと思うのは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'sを使用push_backして新しい値を追加する必要があります。次に、これpush_backが true かどうかを確認mVector.size() == mVector.capacity()し、true の場合はnew 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 (read-copy-update) アルゴリズムに触発されています。ストレージ スペースが使い果たされた場合、少なくとも 1 つのリーダーがアクセスしている限り、新しいストレージが古いストレージを無効にしないようにする必要があります。ただし、新しいストレージを割り当てる必要があり、割り当て後に来るリーダーはそれを見ることができるはずです。古いストレージは、誰も使用しなくなったらすぐに割り当てを解除する必要があります (すべてのリーダーが終了します)。

shared_ptrほとんどのハードウェア アーキテクチャは、アトミックなインクリメントとデクリメントを行う方法を提供しているため、 (したがってVector) 完全にロックなしで実行できると思います。

ただし、このアプローチの欠点の 1 つは、読者がそれshared_ptrを保持する期間によっては、複数のdata.

PS: コードで恥ずかしいエラーをあまり犯していないことを願っています :-)

于 2013-03-14T09:23:36.297 に答える
0

... std::vector で reserve() を使用 ...

これは、ベクトルが成長する必要がないことを保証できる場合にのみ役立ちます。あなたはアイテムの数が上に制限されていないと述べたので、その保証を与えることはできません.

リンクされた質問にもかかわらず、メモリを管理するためだけに使用することは考えられますがstd::vector、受け入れられた回答で特定された問題を回避するには、上にロジックの追加レイヤーが必要になります。

実際の答えは、同期の量を最小限に抑えることです。同期の最小量は、指定していないコードと使用法の詳細によって異なります。

たとえば、固定サイズのチャンクのリンク リストを使用してソリューションをスケッチしました。これは、一般的なユースケースが配列トラバーサルと同じくらい効率的である必要があることを意味しますが、再割り当てせずに動的に拡張できます。

ただし、実装は次のような質問に敏感であることが判明しました。

  • アイテムを削除する必要があるかどうか
    • 彼らが読まれるときはいつですか？
    • 正面からだけですか、それとも他の場所からですか？
  • コンテナーが空の場合にリーダーをビジー待機させるかどうか
    • これがある種のバックオフを使用するかどうか
  • どの程度の一貫性が必要ですか?
于 2013-03-13T16:56:09.497 に答える