4

マルチスレッド検索アルゴリズムのロックレスハッシュテーブルでの次の試みを検討してください（この論文に触発されました）

struct Data
{
    uint64_t key;
    uint64_t value;
};

struct HashEntry
{
    uint64_t key_xor_value;
    uint64_t value;
};

void insert_data(Data const& e, HashEntry* h, std::size_t tableOffset)
{
    h[tableOffset].key_xor_value = e.key ^ e.value;
    h[tableOffset].value = e.value;
}

bool data_is_present(Data const& e, HashEntry const* h, std::size_t tableOffset)
{
    auto const tmp_key_xor_value = h[tableOFfset].key_xor_value;
    auto const tmp_value = h[tableOffset].value;

    return e.key == (tmp_key_xor_value ^ tmp_value);
}

HashEntry構造体は、構造体の 2 つの 64 ビット ワードの XOR 演算された組み合わせを格納するという考え方ですData。2 つのスレッドが struct の 2 つの 64 ビット ワードへの読み取り/書き込みをインターリーブした場合HashEntry、これは読み取りスレッドによって XOR を再度実行し、元の と比較することによって検出できるという考えですkey。そのため、壊れたハッシュ エントリによって効率が低下する可能性がありますが、デコードされた取得キーが元のキーと一致する場合は、正確性が保証されます。

この論文は、それが次の仮定に基づいていると述べています。

この説明の残りの部分では、64 ビット メモリの読み取り/書き込み操作はアトミックである、つまり 64 ビット値全体が 1 サイクルで読み取り/書き込みされると仮定します。

私の質問は次のとおりです。上記のコードはstd::atomic<uint64_t>、C++ 11 でスレッドセーフであることが保証されていることを明示的に使用していませんか? または、同時読み取り/書き込みによって個々の 64 ビット ワードが破損する可能性はありますか? 64 ビット プラットフォームでも？これは古い C++98 標準とどう違うのでしょうか?

規格からの引用は大歓迎です。

更新: 「無害な」データ競合に関する Hans Boehmによるこの驚くべき論文に基づいて、噛まれる簡単な方法は、コンパイラが両方の XOR をキャンセルinsert_data() しdata_is_present()て常に返すことtrueです。たとえば、次のようなローカル コード フラグメントが見つかった場合

insert_data(e, h, t);
if (data_is_present(e, h, t)) // optimized to true as if in single-threaded code
   read_and_process(e, h, t); // data race if other thread has written
4

3 に答える 3

7

C++11 仕様では、あるスレッドが別のスレッドが書き込んでいるメモリ位置を読み書きしようとするほとんどすべての試みを、未定義の動作として定義しています (アトミックまたはミューテックスを使用して、あるスレッドからの読み取り/書き込みを防止し、別のスレッドが別のスレッドに書き込みを行っている場合を除きます)。書き込み）。

個々のコンパイラはそれを安全にするかもしれませんが、C++11 仕様はそれ自体をカバーしていません。同時読み取りは決して問題ではありません。別のスレッドで読み書きしながら、あるスレッドで書き込んでいます。

これは古い C++98 標準とどう違うのでしょうか?

C++98/03 標準は、スレッド化に関してはカバーしていません。C++98/03 メモリ モデルに関する限り、スレッド化は起こり得ることではありません。

于 2012-09-20T07:29:34.713 に答える
2

使用しているCPU（その命令セット）ほどコンパイラに依存しているとは思いません。仮定が非常に移植可能であるとは思いません。

于 2012-09-20T07:21:35.533 に答える
1

コードは完全に壊れています。コンパイラの分析により、全体的な効果が同一であることが示唆された場合、コンパイラは命令を並べ替える実質的な自由を持っています。insert_dataたとえば、更新がキャッシュに書き戻される前に一時レジスタで行われるかどうか、ましてやキャッシュが更新されるかどうかのkey_xor_value前に が更新されるという保証はありません。マシン コード言語と CPU 命令での「順序」に関係なくvalue実行パイプライン - 更新中のコアまたは複数のコア (関数の途中でコンテキストが切り替えられた場合) のプライベート キャッシュからフラッシュされ、他のスレッドから見えるようになります。コンパイラは、CPU、32 ビットまたは 64 ビットのコンパイル、コンパイル オプションなどに応じて、32 ビット レジスタを使用して段階的に更新を行う場合もあります。

volatileアトミック操作では、コアのキャッシュ全体でデータを同期し、何らかの順序を強制するCAS (Compare and Swap) スタイルの命令やメモリ バリア命令などを必要とする傾向があります。

于 2012-09-20T08:46:50.113 に答える