質問

C++でパフォーマンス重視のソフトを開発しています。そこでは並列ハッシュマップが必要で、それを実装しています。そこで、私たちの並列ハッシュマップが、以下のものと比較してどれくらい遅いかを把握するためにベンチマークを書きました。 std::unordered_map .

しかし std::unordered_map は信じられないほど遅いようです...。これはマイクロベンチマークです（同時実行マップでは、ロックが最適化されないように新しいスレッドを生成しています。 google::dense_hash_map でベンチマークを行うためです。）

boost::random::mt19937 rng;
boost::random::uniform_int_distribution<> dist(std::numeric_limits<uint64_t>::min(), std::numeric_limits<uint64_t>::max());
std::vector<uint64_t> vec(SIZE);
for (int i = 0; i < SIZE; ++i) {
    uint64_t val = 0;
    while (val == 0) {
        val = dist(rng);
    }
    vec[i] = val;
}
std::unordered_map<int, long double> map;
auto begin = std::chrono::high_resolution_clock::now();
for (int i = 0; i < SIZE; ++i) {
    map[vec[i]] = 0.0;
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
std::cout << "inserts: " << elapsed.count() << std::endl;
std::random_shuffle(vec.begin(), vec.end());
begin = std::chrono::high_resolution_clock::now();
long double val;
for (int i = 0; i < SIZE; ++i) {
    val = map[vec[i]];
}
end = std::chrono::high_resolution_clock::now();
elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
std::cout << "get: " << elapsed.count() << std::endl;

(編集：ソースコード全体はこちらでご覧になれます。 http://pastebin.com/vPqf7eya )

の結果は std::unordered_map は

inserts: 35126
get    : 2959

については google::dense_map :

inserts: 3653
get    : 816

私たちのハンドバックされた同時実行マップ（ベンチマークはシングルスレッドですが、別のスレッドでロックします）のために。

inserts: 5213
get    : 2594

pthreadをサポートせずにベンチマークプログラムをコンパイルし、すべてをメインスレッドで実行すると、手で裏打ちした同時実行マップでは次のような結果が得られます。

inserts: 4441
get    : 1180

以下のコマンドでコンパイルしています。

g++-4.7 -O3 -DNDEBUG -I/tmp/benchmap/sparsehash-2.0.2/src/ -std=c++11 -pthread main.cc

で、特に挿入されるのは std::unordered_map への挿入は、他のマップが3-5秒であるのに対し、35秒と非常に時間がかかるようです。また、ルックアップ時間もかなり高いようです。

私の質問：これはなぜですか？私はstackoverflowで他の質問を読みました。 std::tr1::unordered_map が彼自身の実装よりも遅い理由を尋ねています。そこでは、最も高く評価された回答は、次のように述べています。 std::tr1::unordered_map はより複雑なインターフェイスを実装する必要があると述べています。しかし、私はこの議論を理解できません。私たちのconcurrent_mapではバケツ型のアプローチを使っています。 std::unordered_map もバケツ・アプローチを使用しています ( google::dense_hash_map はそうではありませんが std::unordered_map は、少なくとも我々の手でバックアップした同時並行安全バージョンと同じくらい速くなるはずです?） それとは別に、私は、ハッシュマップのパフォーマンスが悪くなるような機能を強制するようなインターフェイスを見ることはできません。

そこで私の質問ですが std::unordered_map が非常に遅いというのは本当ですか？もしそうでないなら：何が問題なのでしょうか？もしそうなら：その理由は何ですか。

そして私の主な質問：なぜ値を std::unordered_map に値を挿入するのは、なぜそれほどまでに高価なのでしょうか (最初に十分なスペースを確保しても、パフォーマンスはそれほど良くなりません。）

EDIT。

まず最初に: そうです、提示されたベンチマークは完璧ではありません - これは私たちがいろいろと遊んでみた結果、単なるハックに過ぎないからです (たとえば uint64 ディストリビューションで int を生成するのは実際には良いアイデアではなく、ループで 0 を除外するのはちょっと馬鹿げてるなど) です。

現時点では、ほとんどのコメントは、unordered_map のために十分なスペースを事前に割り当てることによって、より速くすることができると説明しています。私たちのアプリケーションでは、これは不可能です。私たちはデータベース管理システムを開発しており、トランザクション中にいくつかのデータ (たとえば、ロック情報) を格納するためにハッシュ マップを必要としています。つまり、このマップは1エントリ（ユーザーが1回挿入してコミットするだけ）から数十億エントリ（テーブルのフルスキャンが発生する場合）にもなり得ます。ここに十分なスペースを事前に割り当てることは不可能です (そして、最初に多くを割り当てると、あまりにも多くのメモリを消費してしまいます)。

さらに、私の質問を十分に明確に述べなかったことをお詫びします。私は、unordered_map を高速にすることにあまり興味がなく (googles dense hash map を使用して、私たちにとってはうまくいきます)、この大きなパフォーマンスの違いがどこから来るのか本当に理解していません。これは単なる事前割り当てではありません (十分な事前割り当てメモリがあっても、密集したマップは unordered_map よりも桁違いに高速で、私たちのハンドバックされた同時マップはサイズ 64 の配列から始まるので unordered_map よりも小さいものです)。

のパフォーマンスが悪い理由は何でしょうか？ std::unordered_map ? あるいは別の問いかけをします。の実装を書くことは可能でしょうか？ std::unordered_map インターフェイスの実装を書くことはできますか? それとも、実装者が非効率的な方法を選んで実装するよう強制する何かが標準にあるのでしょうか？

EDIT 2:

プロファイリングしてみると、整数の割り算に多くの時間を使っていることがわかります。 std::unordered_map は配列のサイズに素数を使用していますが、他の実装では2の累乗を使用しています。なぜ std::unordered_map は素数を使うのでしょうか？ハッシュが悪いものであった場合に、より良いパフォーマンスをするためでしょうか？良いハッシュの場合、それは何の違いもありません。

編集 3:

これらの数値は std::map :

inserts: 16462
get    : 16978

なぜ、挿入は std::map に挿入する方が std::unordered_map ... つまり、WAT? std::map は局所性が悪く（木 対 配列）、より多くの割り当てが必要で（挿入ごと 対 リハッシュごと + さらに衝突ごとに ~1）、最も重要なのは、別のアルゴリズム複雑性（O(logn) 対 O(1)) があることです!

どのように解決するのか?

gcc-4.7の問題です!

とは gcc-4.7

inserts: 37728
get    : 2985

とは gcc-4.6

inserts: 2531
get    : 1565

そこで std::unordered_map が壊れています (または、私のインストールは、Ubuntu 上の gcc-4.7.0 のインストールであり、別のインストールは debian testing 上の gcc 4.7.1 です。)。

私はバグレポートを提出します。を使用しないでください。 std::unordered_map を gcc 4.7 で使ってはいけません!