gcc std :: unordered_map实现缓慢吗？ 如果是这样 – 为什么？
我们正在用C ++开发一个高性能的关键软件。 在那里我们需要一个并发哈希映射并实现一个。 所以我们写了一个基准来计算出我们的并发哈希映射与std::unordered_map相比要慢多less。
但是， std::unordered_map似乎是非常慢…所以这是我们的微基准（对于并发映射，我们产生了一个新的线程，以确保locking不会被优化，注意我从来没有inser 0，因为我也基准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;
（编辑：整个源代码可以在这里find： http : //pastebin.com/vPqf7eya ）
std::unordered_map的结果是：
inserts: 35126 get : 2959
对于google::dense_map ：
inserts: 3653 get : 816
对于我们手动支持的并发映射（locking，虽然基准是单线程 – 但在一个单独的产卵线程）：
inserts: 5213 get : 2594
如果我在没有pthread支持的情况下编译基准testing程序并在主线程中运行所有内容，那么对于我们的手持并发映射，我会得到以下结果：
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中使用了bucket方法， std::unordered_map使用了bucket方法（ google::dense_hash_map不是，但是std::unordered_map应该至less和我们的手一样快支持并发安全的版本？）。 除此之外，我无法在界面中看到任何强制使哈希映射performance不佳的function。
所以我的问题：这是真的std::unordered_map似乎很慢？ 如果没有：什么是错的？ 如果是，那是什么原因？
而我的主要问题是：为什么要在std::unordered_map插入一个非常可怕的值（即使我们在开始时预留了足够的空间，但性能并没有那么好 – 所以重新布置似乎不是问题）？
编辑：
首先：是的，提出的基准是不完美的 – 这是因为我们玩了很多，这只是一个黑客（例如uint64分配生成整数实际上不是一个好主意，排除0循环是一种愚蠢的等…）。
目前大多数评论解释说，我可以通过预先分配足够的空间来使unordered_map更快。 在我们的应用程序中，这是不可能的：我们正在开发一个数据库pipe理系统，并且需要一个哈希映射来在事务中存储一些数据（例如locking信息）。 因此，这张地图可以是从1（用户只需进行一次插入和提交）到数十亿条目（如果发生全表扫描）的所有内容。 在这里预先分配足够的空间是不可能的（只是在开始时分配很多内存就会消耗太多内存）。
此外，我很抱歉，我没有清楚地说明我的问题：我并没有真正有兴趣使unordered_map快速（使用Google密码哈希映射对我们很好），我只是不太明白这个巨大的性能差异来自哪里。 它不能只是预分配（即使有足够的预分配内存，密集的地图比unordered_map快一个数量级，我们的手持并发地图以大小64的数组开始 – 因此比unordered_map小一些）。
那么std::unordered_map这个性能不好的原因是什么呢？ 或者有不同的要求：是否可以写一个std::unordered_map接口的实现，这个接口是标准符合（几乎）和谷歌密集哈希映射一样快？ 还是有标准中的某些东西来强制执行者select一种低效率的方式来实现它？
编辑2：
通过分析，我发现大量的时间用于整数除法。 std::unordered_map使用数字大小的素数，而其他实现则使用两次幂。 为什么std::unordered_map使用素数？ 为了更好的执行，如果哈希是坏的？ 对于很好的哈希值，没有任何区别。
编辑3：
这些是std::map的数字：
inserts: 16462 get : 16978
Sooooooo：为什么插入std::map比插入到std::unordered_map更快…我的意思是WAT？ std::map有更差的局部性（tree vs array），需要做更多的分配（每次插入vs每次rehash +加上~1每次冲突），最重要的是：有另一个algorithm的复杂性（O（logn）vs O 1））！
我find了原因：这是一个gcc-4.7的问题！
用gcc-4.7
inserts: 37728 get : 2985
用gcc-4.6
inserts: 2531 get : 1565
因此，gcc-4.7中的std::unordered_map被破坏了（或者我的安装，这是在Ubuntu上安装的gcc-4.7.0，另一个安装在debiantesting中是gcc 4.7.1）。
我将提交一个错误报告..直到那时：不要使用std::unordered_map与gcc 4.7！
我猜测你没有正确地调整你的unordered_map大小，正如Ylisar所说的那样。 当链在unordered_map变得太长时，g ++实现会自动重新哈希到一个更大的哈希表，这会对性能造成很大的阻碍。 如果我没有记错， unordered_map默认为（最小的素数大于） 100 。
我没有在我的系统上chrono ，所以我计时times() 。
template <typename TEST> void time_test (TEST t, const char *m) { struct tms start; struct tms finish; long ticks_per_second; times(&start); t(); times(&finish); ticks_per_second = sysconf(_SC_CLK_TCK); std::cout << "elapsed: " << ((finish.tms_utime - start.tms_utime + finish.tms_stime - start.tms_stime) / (1.0 * ticks_per_second)) << " " << m << std::endl; }
我使用了一个10000000的SIZE ，并不得不改变我的版本的boost 。 另请注意，我预先设定了散列表的大小以匹配SIZE/DEPTH ，其中DEPTH是由于散列冲突而导致的存储区链长度的估计值。
编辑：霍华德在评论中指出， unordered_map的最大加载因子是1 。 所以， DEPTH控制了代码重复的次数。
#define SIZE 10000000 #define DEPTH 3 std::vector<uint64_t> vec(SIZE); boost::mt19937 rng; boost::uniform_int<uint64_t> dist(std::numeric_limits<uint64_t>::min(), std::numeric_limits<uint64_t>::max()); std::unordered_map<int, long double> map(SIZE/DEPTH); void test_insert () { for (int i = 0; i < SIZE; ++i) { map[vec[i]] = 0.0; } } void test_get () { long double val; for (int i = 0; i < SIZE; ++i) { val = map[vec[i]]; } } int main () { for (int i = 0; i < SIZE; ++i) { uint64_t val = 0; while (val == 0) { val = dist(rng); } vec[i] = val; } time_test(test_insert, "inserts"); std::random_shuffle(vec.begin(), vec.end()); time_test(test_insert, "get"); }
编辑：
我修改了代码，使我可以更容易地改变DEPTH 。
#ifndef DEPTH #define DEPTH 10000000 #endif
所以，默认情况下，哈希表的最坏的大小被选中。
elapsed: 7.12 inserts, elapsed: 2.32 get, -DDEPTH=10000000 elapsed: 6.99 inserts, elapsed: 2.58 get, -DDEPTH=1000000 elapsed: 8.94 inserts, elapsed: 2.18 get, -DDEPTH=100000 elapsed: 5.23 inserts, elapsed: 2.41 get, -DDEPTH=10000 elapsed: 5.35 inserts, elapsed: 2.55 get, -DDEPTH=1000 elapsed: 6.29 inserts, elapsed: 2.05 get, -DDEPTH=100 elapsed: 6.76 inserts, elapsed: 2.03 get, -DDEPTH=10 elapsed: 2.86 inserts, elapsed: 2.29 get, -DDEPTH=1
我的结论是，除了使其等于整个期望的唯一插入数量之外，对于任何初始散列表大小没有太大的性能差异。 另外，我没有看到你观察到的数量级差异。
我已经使用64位/ AMD / 4核（2.1GHz）电脑运行你的代码，它给了我以下结果：
MinGW-W64 4.9.2：
使用std :: unordered_map：
inserts: 9280 get: 3302
使用std :: map：
inserts: 23946 get: 24824
VC 2015与我知道的所有优化标志：
使用std :: unordered_map：
inserts: 7289 get: 1908
使用std :: map：
inserts: 19222 get: 19711
我没有使用GCCtesting代码，但我认为它可能与VC的性能相当，所以如果这是真的，那么GCC 4.9 std :: unordered_map它仍然是坏的。
[编辑]
所以是的，就像有人在评论中说的那样，没有理由认为GCC 4.9.x的性能可以和VC的性能相提并论。 当我有变化时，我将在GCC上testing代码。
我的答案只是build立某种知识库的其他答案。
