gcc std :: unordered_map的执行速度慢吗？如果是这样 - 为什么？

Question

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

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

(编辑:整个源代码可以在这里找到: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秒.查找时间似乎也很高.

我的问题:这是为什么？我在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生成int 的分布在实践中不是一个好主意,在循环中排除0是一种愚蠢的......等等.

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

此外,我很抱歉,我没有说清楚我的问题:我对制作unordered_map并不感兴趣(使用googles密集哈希映射对我们来说很好),我只是不明白这个巨大的性能差异来自何处.它不能只是预分配(即使有足够的预分配内存,密集映射比unordered_map快一个数量级,我们的手动并发映射以大小为64的数组开始 - 因此比unordered_map小一些).

那么这种糟糕表现的原因是std::unordered_map什么？或者有不同的问题:可以编写一个std::unordered_map标准符合接口的实现,并且(几乎)跟googles密集哈希映射一样快吗？或者标准中是否有某些内容强制实施者选择低效的方式来实现它？

编辑2:

通过分析,我看到很多时间用于整数divions.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

所以std::unordered_map在gcc-4.7中断了(或者我的安装,这是在Ubuntu上安装gcc-4.7.0 - 另一个是在debian测试中安装gcc 4.7.1).

我将提交错误报告..直到那时:不要使用std::unordered_mapgcc 4.7!

Answer 2

我猜你没有正确调整你的尺寸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;
}

我用SIZE的10000000,并且有改变的事情一点我的版本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

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