是不是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

对于我们手工备份的并发map (它执行锁定，虽然基准测试是单线程的-但在一个单独的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秒与3-5秒的其他地图。此外，查找时间似乎也很长。

我的问题是:为什么会这样？我在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中插入一个值的代价如此之高(即使我们一开始就预留了足够的空间，它的性能也不会好到哪里去--所以重复散列似乎不是问题)？

编辑：

首先:是的，现在的基准测试并不是完美无缺的--这是因为我们对它玩了很多次，它只是一个小技巧(例如，uint64发行版生成整数实际上不是一个好主意，在循环中排除0是一种愚蠢的想法……)。

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

此外，我很抱歉，我没有把我的问题表达得足够清楚:我对让unordered_map变得更快不是很感兴趣(使用谷歌密集的哈希图对我们来说很好)，我只是不太明白这种巨大的性能差异来自哪里。它不能仅仅是预分配(即使有足够的预分配内存，密集的映射比unordered_map快一个数量级，我们的手持式并发映射从一个大小为64的数组开始-所以比unordered_map小)。

那么，std::unordered_map性能如此糟糕的原因是什么呢？或者换一种方式问:是否可以编写一个符合标准的std::unordered_map接口实现，并且(几乎)像googles密集的哈希图一样快？或者是标准中的某些东西迫使实现者选择一种低效的方式来实现它？

编辑2：

通过分析，我发现很多时间都用在整数除数上了。std::unordered_map使用质数表示数组大小，而其他实现使用2的幂。为什么std::unordered_map使用质数？如果散列不好，是否可以更好地执行？对于好的哈希，它不会有什么不同。

编辑3：

这些是std::map的数字

inserts: 16462
get    : 16978

Sooooooo:为什么插入到std::map中的速度比插入到std::unordered_map中的速度要快...我的意思是WAT？std::map有一个更差的局部性(树与数组)，需要进行更多的分配(每次插入vs每次刷新+每次冲突加~1 )，最重要的是:具有另一个算法复杂度(O(logn) vs O(1))！

Answer 1

我找到了原因:这是一个问题的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 -以及另一个安装，在debian测试上是gcc 4.7.1 )。

我会提交一份错误报告..在此之前:请不要在gcc 4.7中使用std::unordered_map！

Answer 2

我猜你没有像Ylisar建议的那样正确地调整unordered_map的大小。当链在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

我的结论是，除了使其等于唯一插入的全部预期数量之外，任何初始哈希表大小都没有太大的性能差异。此外，我也看不到您正在观察的性能差异的数量级。

Answer 3

我已经使用64位/ AMD /4核(2.1 the )计算机运行了你的代码，它给了我以下结果：

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

我没有测试过使用GCC的代码，但我认为它可能与VC的性能相当，所以如果这是真的，那么GCC 4.9 std::unordered_map它仍然是坏的。

编辑

所以，是的，正如有人在评论中所说，没有理由认为GCC 4.9.x的表现可以与VC的表现相提并论。当我有变化的时候，我会在GCC上测试代码。

我的答案就是为其他答案建立某种知识库。