为什么std :: unordered_map变慢,我可以更有效地使用它来缓解这种情况吗？

Question

我最近发现了一件奇怪的事情.似乎计算Collat​​z序列长度完全没有缓存比使用缓存所有元素快 2倍.std::unordered_map

注意我确实从问题提示中是否gcc std :: unordered_map实现缓慢？如果是这样 - 为什么？我试着用这些知识来std::unordered_map表现我的能力(我使用g ++ 4.6,它确实比g ++的最新版本表现更好,我试着指定一个声音的初始桶数,我使它完全等于最大值地图必须持有的元素数量).

相比之下,使用std::vector缓存一些元素几乎比没有缓存快17倍,比使用缓慢快近40倍std::unordered_map.

我做错了什么,或者这个容器是慢的,为什么？可以让它表现得更快吗？或者,哈希映射本质上是无效的,应该尽可能避免在高性能代码中使用？

有问题的基准是:

#include <iostream>
#include <unordered_map>
#include <cstdint>
#include <ctime>

std::uint_fast16_t getCollatzLength(std::uint_fast64_t val) {
    static std::unordered_map <std::uint_fast64_t, std::uint_fast16_t> cache ({{1,1}}, 2168611);

    if(cache.count(val) == 0) {
        if(val%2 == 0)
            cache[val] = getCollatzLength(val/2) + 1;
        else
            cache[val] = getCollatzLength(3*val+1) + 1;
    }

    return cache[val];
}

int main()
{
    std::clock_t tStart = std::clock();

    std::uint_fast16_t largest = 0;
    for(int i = 1; i <= 999999; ++i) {
        auto cmax = getCollatzLength(i);
        if(cmax > largest)
            largest = cmax;
    }
    std::cout << largest << '\n';

    std::cout << "Time taken: " << (double)(std::clock() - tStart)/CLOCKS_PER_SEC << '\n';
}

它输出: Time taken: 0.761717

而根本没有缓存的基准:

#include <iostream>
#include <unordered_map>
#include <cstdint>
#include <ctime>

std::uint_fast16_t getCollatzLength(std::uint_fast64_t val) {
    std::uint_fast16_t length = 1;
    while(val != 1) {
        if(val%2 == 0)
            val /= 2;
        else
            val = 3*val + 1;
        ++length;
    }
    return length;
}

int main()
{
    std::clock_t tStart = std::clock();

    std::uint_fast16_t largest = 0;
    for(int i = 1; i <= 999999; ++i) {
        auto cmax = getCollatzLength(i);
        if(cmax > largest)
            largest = cmax;
    }
    std::cout << largest << '\n';

    std::cout << "Time taken: " << (double)(std::clock() - tStart)/CLOCKS_PER_SEC << '\n';
}

输出 Time taken: 0.324586

Answer 1

事实上,标准库的地图本质上很慢(std::map特别是但std::unoredered_map也是如此).谷歌的Chandler Carruth在2014年的CppCon演讲中解释了这一点.简而言之:std::unordered_map缓存不友好,因为它使用链表作为存储桶.

这个问题提到了一些有效的哈希映射实现 - 改为使用其中一个.