私たちは、C++ で非常にパフォーマンスが重要なソフトウェアを開発しています。そこでは、並行ハッシュ マップと実装されたハッシュ マップが必要です。そのため、同時ハッシュ マップが と比較してどれだけ遅いかを把握するためのベンチマークを作成しましたstd::unordered_map。
しかし、std::unordered_map信じられないほど遅いようです...これが私たちのマイクロベンチマークです（並行マップでは、ロックが最適化されないようにするために新しいスレッドを生成しましたgoogle::dense_hash_map。 null 値が必要です):
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非常にコストがかかるようです.35秒対他のマップの3〜5秒. また、検索時間もかなり長いようです。
私の質問：これはなぜですか？誰かが尋ねるスタックオーバーフローに関する別の質問を読みました。なぜ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ですか (最初に十分なスペースを確保しても、パフォーマンスはそれほど向上しません。したがって、再ハッシュは問題ではないようです)。
編集：
まず第一に：はい、提示されたベンチマークは完璧ではありません-これは、私たちがそれでたくさん遊んだためであり、単なるハックです（たとえば、uint64intを生成する配布は実際には良い考えではなく、ループで0を除外しますちょっとばかげているなど...）。
現時点では、ほとんどのコメントが、十分なスペースを事前に割り当てることで unordered_map を高速化できると説明しています。私たちのアプリケーションでは、これはまったく不可能です。データベース管理システムを開発していて、トランザクション中にデータを格納するためにハッシュ マップが必要です (ロック情報など)。したがって、このマップは、1 (ユーザーが 1 つの挿入とコミットを行うだけ) から数十億のエントリ (完全なテーブル スキャンが発生した場合) まで、あらゆる可能性があります。ここで十分なスペースを事前に割り当てることはまったく不可能です (そして、最初に大量に割り当てるだけでは、大量のメモリが消費されます)。
さらに、質問を十分に明確に述べていなかったことをお詫びします。 unordered_map を高速化することにあまり興味がありません (Google の密なハッシュ マップを使用すると問題なく動作します)。この大きなパフォーマンスの違いがどこから来るのかがよくわかりません。 . 単なる事前割り当てではありません (十分な事前割り当てメモリがあっても、高密度マップは unordered_map よりも桁違いに高速です。手動でバックアップされた同時実行マップはサイズ 64 の配列で開始されるため、unordered_map よりも小さい配列になります)。
では、 のこの悪いパフォーマンスの理由は何std::unordered_mapですか? または別の質問:std::unordered_map標準に準拠し、(ほぼ) Google の密なハッシュ マップと同じくらい高速なインターフェイスの実装を作成できますか? それとも、実装者が非効率的な実装方法を選択することを強制する標準の何かがありますか?
編集2：
プロファイリングにより、整数除算に多くの時間が費やされていることがわかります。std::unordered_mapは配列サイズに素数を使用しますが、他の実装では 2 の累乗を使用します。なぜ はstd::unordered_map素数を使用するのですか? ハッシュが悪い場合にパフォーマンスを向上させるには? 良いハッシュの場合、違いはありません。
編集3：
の数値は次のstd::mapとおりです。
inserts: 16462
get : 16978
Sooooooo: への挿入は、へのstd::map挿入よりも速いのはなぜstd::unordered_mapですか...つまり、WAT? std::mapより悪い局所性 (ツリー対配列) を持ち、より多くの割り当てを行う必要があります (挿入ごと対再ハッシュごと + 衝突ごとに最大 1 を加えたもの)、そして最も重要なのは、別のアルゴリズムの複雑さ (O(logn) 対 O(1)) です!