私はしばらくの間、この質問を熟考してきました:
複数の CPU があるという事実を利用して、マルチコア マシン上でより高速な基本データ構造 (つまり、リンク リスト、ハッシュ テーブル、セット、スキップリスト、ブルーム フィルター、レッド ブラック ツリーなど) を構築できますか?
pthread で予備実験を行ったところ、pthread_create() は 30us 程度かかることがわかりましたが、単純な hash_map の挿入は、シングル コアの場合よりもはるかに短い時間で済みました。したがって、同期プリミティブとスレッドの作成が非常に遅いため、より高速な hash_map<> を作成することを想像するのが難しくなりました。ツリーのトラバーサルとバランシングを並行して行うことも想像できますが、やはり、同期プリミティブはランタイムを短くするのではなく、長くするように見えます。
「CPUが増えたので、もっと速くできるはずだ」というのは今でも直感的に感じますが、その声明の証明または反証に頭を悩ませることはできません. 私は C++ でかなりの実験をしてきましたが、他の言語がこのタスクに対してより良い解決策 (erlang?) を提供するのではないかと疑っています。考え？
編集の詳細: 頻繁に使用されるプログラミング/データ構造パラダイムがいくつかあり、高速化できる可能性があると思います。たとえば、基本的に次のようなコードを頻繁に書いていることに気付きます (実際のデータは "rand()" に置き換えられています)。
static const int N = 1000000;
static const int M = 10000000; // 10x more lookups
hash_map<int, int> m;
// batch insert a bunch of interesting data
for (int i = 0; i < N; i++) m[rand()] = rand();
// Do some random access lookups.
for (int i = 0; i < M; i++) m[rand()]++;
この種のパラダイムは、名前と値の設定と構成データ、バッチ処理などによく使用されます。10 倍 (またはそれ以上) の検索/挿入比により、従来の hash_map<> はこの種の操作に理想的です。
これは、挿入フェーズと検索フェーズで簡単に半分に分割できます。並行世界では、2 つの半分の間に「フラッシュ キュー」操作が存在する場合があります。より難しいのは、インターリーブされた挿入 + ルックアップ バージョンです。
hash_map<int, int> m;
for (int i = 0; i < N; i++) {
if (rand() % LOOKUP_RATIO == 0)
hash_map[rand()]++; // "lookup"
else
hash_map[rand()] = rand(); // "insert"
}
そのシナリオでは、各ルックアップの前に挿入キューがフラッシュされている限り、挿入は非同期である可能性があり、LOOKUP_RATIO が十分に大きい場合 (たとえば、>1000)、上記のバッチの例と非常に似ていますが、いくつかのキューイングがあります。ただし、キューイングは同期プリミティブを意味します。
次のスニペットを想像してみてください。
hash_map<int,int> a;
hash_map<int,int> b;
for (int i = 0; i < N; i++) {
// the following 2 lines could be executed in parallel
a[rand()] = rand();
b[rand()] = rand();
}
したがって、ルックアップは次の方法で「並列」に実行できます。
int lookup(int value) {
// The following 2 lines could be executed in parallel:
v1 = a[value];
v2 = b[value];
if (v1) // pseudo code for "value existed in a"
return v1;
else
return v2;
}