c++ - gcc std::unordered_map 实现速度慢吗？如果是这样 - 为什么？

Question

我们正在用 C++ 开发一个高性能的关键软件。我们需要一个并发哈希映射并实现一个。所以我们写了一个基准来计算，我们的并发哈希映射与 std::unordered_map 相比慢了多少。 .

但是，std::unordered_map似乎非常慢......所以这是我们的微基准测试(对于并发映射，我们生成了一个新线程以确保锁定不会被优化掉并注意我从不插入 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;

(编辑:整个源代码可以在这里找到: http://pastebin.com/vPqf7eya)
std::unordered_map 的结果是:

inserts: 35126
get    : 2959

对于 google::dense_map :

inserts: 3653
get    : 816

对于我们手动支持的并发映射(它会锁定，尽管基准测试是单线程的 - 但在一个单独的 spawn 线程中):

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 秒与其他 map 的 3-5 秒。此外，查找时间似乎相当长。

我的问题:这是为什么？我在有人问的 stackoverflow 上读到另一个问题，为什么 std::tr1::unordered_map比他自己的实现慢。评分最高的答案指出， std::tr1::unordered_map需要实现更复杂的接口(interface)。但是我看不到这个论点:我们在 concurrent_map 中使用了桶方法， std::unordered_map也使用桶方法( google::dense_hash_map 没有，但比 std::unordered_map 应该至少和我们的手支持并发安全版本一样快？)。除此之外，我在界面中看不到任何强制执行使哈希映射性能不佳的功能的任何内容...

所以我的问题是: std::unordered_map 是真的吗？似乎很慢？如果不是:出了什么问题？如果是:这是什么原因。

我的主要问题是:为什么要在 std::unordered_map 中插入一个值如此可怕的昂贵(即使我们在开始时保留了足够的空间，它的性能也不会好多少-因此重新散列似乎不是问题)？

编辑:

首先:是的，所提供的基准测试并非完美无缺——这是因为我们对它进行了很多尝试，它只是一个黑客(例如 uint64 生成整数的分布在实践中并不是一个好主意，排除 0在循环中有点愚蠢等......)。

目前大多数评论都解释说，我可以通过为它预分配足够的空间来使 unordered_map 更快。在我们的应用程序中，这是不可能的:我们正在开发一个数据库管理系统，需要一个哈希映射来存储事务期间的一些数据(例如锁定信息)。所以这个映射可以是从 1(用户只进行一次插入和提交)到数十亿个条目(如果发生全表扫描)的所有内容。在这里预分配足够的空间是不可能的(并且在开始时分配很多会消耗太多内存)。

此外，我很抱歉，我没有足够清楚地说明我的问题:我对快速制作 unordered_map 并不感兴趣(使用谷歌密集哈希图对我们来说很好用)，我只是不明白这种巨大的性能差异来自哪里.它不能只是预分配(即使有足够的预分配内存，密集映射也比 unordered_map 快一个数量级，我们手动支持的并发映射从大小为 64 的数组开始 - 因此比 unordered_map 小)。

那么 std::unordered_map性能不佳的原因是什么？ ?或者换一种方式问:可以写一个 std::unordered_map 的实现吗？符合标准且(几乎)与谷歌密集哈希图一样快的接口(interface)？或者标准中有什么东西强制实现者选择一种低效的方式来实现它？

编辑2:

通过分析，我发现很多时间都用于整数 divions。 std::unordered_map使用素数作为数组大小，而其他实现使用二的幂。为什么 std::unordered_map使用质数？如果散列不好，性能会更好吗？对于好的哈希，恕我直言没有任何区别。

编辑 3:

这些是 std::map 的号码:

inserts: 16462
get    : 16978

Sooooooo:为什么要插入 std::map比插入 std::unordered_map 快......我的意思是WAT？ std::map具有更差的局部性(树与数组)，需要进行更多分配(每次插入与每次重新哈希 + 每次碰撞加 ~1)，最重要的是:具有另一种算法复杂度(O(logn) 与 O(1))!

Answer 1

找到原因了:是gcc-4.7的问题!!

与 gcc-4.7

inserts: 37728
get    : 2985

与 gcc-4.6

inserts: 2531
get    : 1565

所以 std::unordered_map gcc-4.7 坏了(或者我的安装，它是在 Ubuntu 上安装的 gcc-4.7.0 - 另一个安装是在 debian 测试中的 gcc 4.7.1)。

我将提交错误报告......在那之前:不要使用 std::unordered_map使用 gcc 4.7!