为什么unordered_map和map的性能相同？

Question

这是我的代码，我的unordered_map和map表现相同，并且执行时间相同。我是否在这些数据结构上遗漏了什么？

更新：根据下面的答案和评论，我已经更改了代码。我删除了字符串操作以减少在分析中的影响。现在只测量find()，它占用了我的代码近40%的CPU。分析显示unordered_map比map快3倍，然而，是否有其他方法使这段代码更快？

#include <map>
#include <unordered_map>
#include <stdio.h>

struct Property {
    int a;
};

int main() {
    printf("Performance Summery:\n");
    static const unsigned long num_iter = 999999;

    std::unordered_map<int, Property > myumap;
    for (int i = 0; i < 10000; i++) {
        int ind = rand() % 1000;
        Property p;
        p.a = i;
        myumap.insert(std::pair<int, Property> (ind, p));
    }

    clock_t tStart = clock();
    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        std::unordered_map<int, Property >::iterator itr = myumap.find(ind);
    }

    printf("Time taken unordered_map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

    std::map<int, Property > mymap;
    for (int i = 0; i < 10000; i++) {
        int ind = rand() % 1000;
        Property p;
        p.a = i;
        mymap.insert(std::pair<int, Property> (ind, p));
    }

    tStart = clock();
    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        std::map<int, Property >::iterator itr = mymap.find(ind);
    }

    printf("Time taken map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
}

输出在这里。

Performance Summery:
Time taken unordered_map: 0.12s
Time taken map: 0.36s

- codetiger

---

0.06与大多数系统上标准时钟的分辨率非常接近，因此所有这些都是在说明两者所需的计算时间都不到一格。将你的外部循环乘以100或更多并观察会发生什么。 - Ken Y-N

你的代码实际上没有对地图执行任何可观察的操作，所以很可能优化器将其删除了。 - juanchopanza

使用完整优化进行编译，并将迭代次数增加几个数量级，看看是否有所改善。 - Galik

你正在测量字符串创建和转换的时间。 - n. m.

你应该明确地说明你是否开启了优化编译。如果你正在编译一个未经过优化或者是“调试”版本，那么结果就毫无意义。 - PaulMcKenzie

@PaulMcKenzie 是的，我正在使用优化级别为None（-O0）和启用调试的代码进行编译。让我检查一下相同的代码，使用更高的优化级别（-Os）。 - codetiger

Answer 1

不考虑你的代码，我想提一些一般性的评论。

1. 你到底在测量什么？你的分析包括填充和扫描数据结构。鉴于（可能）填充有序映射需要更长时间，同时测量两者反对有序映射增益（或缺陷）的想法。确定你要测量的内容，然后只测量它。
2. 代码中还有很多与你要分析的内容可能无关的东西：大量的对象创建，字符串连接等等。这可能是你实际上正在测量的。专注于仅对你想要测量的东西进行分析（见点1）。
3. 10000个案例太少了。在这个规模下，其他考虑因素可能会压倒你正在测量的内容，特别是当你正在测量所有内容时。

- Phil Wallach

---

谢谢你的回答，我已经根据你的建议改进了我的代码，现在我正在尝试让这段代码更快，因为它在我的应用程序中占用了40%的CPU。 - codetiger

Answer 2

我们喜欢获得 最小化、完整化和可验证的 示例，这是有道理的。以下是我的代码：

#include <map>
#include <unordered_map>
#include <stdio.h>

struct Property {
    int a;
};

static const unsigned long num_iter = 100000;
int main() {
    printf("Performance Summery:\n");
    clock_t tStart = clock();
    std::unordered_map<int, Property> myumap;

    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        Property p;
        //p.fileName = "hello" + to_string(i) + "world!";
        p.a = i;
        myumap.insert(std::pair<int, Property> (ind, p));
    }

    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        myumap.find(ind);
    }

    printf("Time taken unordered_map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

    tStart = clock();
    std::map<int, Property> mymap;

    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        Property p;
        //p.fileName = "hello" + to_string(i) + "world!";
        p.a = i;
        mymap.insert(std::pair<int, Property> (ind, p));
    }

    for (int i = 0; i < num_iter; i++) {
        int ind = rand() % 1000;
        mymap.find(ind);
    }

    printf("Time taken map: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
}

运行时间为:

Performance Summery:
Time taken unordered_map: 0.04s
Time taken map: 0.07s

请注意，我正在运行比你运行的迭代次数多10倍。

我怀疑你的版本存在两个问题。第一个是你运行的迭代次数太少，无法产生明显效果。第二个是你在计数循环内部执行了昂贵的字符串操作。运行字符串操作所需的时间大于使用无序映射节省的时间，因此你没有看到性能差异。

- Shachar Shemesh

---

你是怎么编译这个的？ - juanchopanza

g++ -std=c++11 so.cpp -o so -O3。实际上，原先编译时没有加上 -O3 选项，但在添加了它（并将迭代次数再次乘以10）后，比率仍然保持不变。 - Shachar Shemesh

我很惊讶居然有任何差异，因为那段代码应该被优化掉了。 - juanchopanza

优化器能够识别的范围是有限的，显然。 - Shachar Shemesh

对于MSVC15，添加 #include <ctime>。 - robor

Answer 3

无论是树（std::map）还是哈希表（std::unordered_map），哪个更快实际上取决于条目数和键的特性（值的变化性，比较和哈希函数等）。

但是，从理论上讲，树比哈希表慢，因为在二叉树中插入和搜索的复杂度为O(log2(N))，而在哈希表中插入和搜索的复杂度大约为O(1)。

你的测试没有显示出来，因为：

1. 你在循环中调用了rand()。与映射插入相比，这需要很长时间。它为你测试的两个映射生成不同的值，进一步扭曲了结果。使用轻量级生成器，例如minstd LCG。

2. 你需要一个更高分辨率的时钟和更多迭代，以便每个测试运行至少需要几百毫秒。

3. 你需要确保编译器不会重新排列你的代码，使计时调用发生在应该发生的地方。这并不总是容易的。在定时测试周围放置内存屏障通常有助于解决这个问题。

4. 由于你没有使用它们的值，因此find()调用很可能被优化掉（我只是碰巧知道至少GCC在-O2模式下不会这样做，所以我保留它原样）。

5. 与之相比，字符串拼接也非常慢。

以下是我的更新版本：

#include <atomic>
#include <chrono>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <unordered_map>

using namespace std;
using namespace std::chrono;

struct Property {
  string fileName;
};

const int nIter = 1000000;

template<typename MAP_TYPE>
long testMap() {
  std::minstd_rand rnd(12345);
  std::uniform_int_distribution<int> testDist(0, 1000);
  auto tm1 = high_resolution_clock::now();
  atomic_thread_fence(memory_order_seq_cst);
  MAP_TYPE mymap;

  for (int i = 0; i < nIter; i++) {
    int ind = testDist(rnd);
    Property p;
    p.fileName = "hello" + to_string(i) + "world!";
    mymap.insert(pair<int, Property>(ind, p));
  }
  atomic_thread_fence(memory_order_seq_cst);

  for (int i = 0; i < nIter; i++) {
    int ind = testDist(rnd);
    mymap.find(ind);
  }

  atomic_thread_fence(memory_order_seq_cst);
  auto tm2 = high_resolution_clock::now();
  return (long)duration_cast<milliseconds>(tm2 - tm1).count();
}

int main()
{
  printf("Performance Summary:\n");
  printf("Time taken unordered_map: %ldms\n", testMap<unordered_map<int, Property>>());
  printf("Time taken map: %ldms\n", testMap<map<int, Property>>());
}

使用-O2编译后，它会给出以下结果：

Performance Summary:
Time taken unordered_map: 348ms
Time taken map: 450ms

因此，在这种特定情况下使用unordered_map比其他方式快大约20-25%。

- rustyx

Answer 4

使用unordered_map不仅查找速度更快，这个稍微修改过的测试还比较填充时间。

我做了一些修改:

1. 增加了样本大小
2. 两个映射现在都使用相同的随机数序列。

-

#include <map>
#include <unordered_map>
#include <vector>
#include <stdio.h>

struct Property {
    int a;
};

struct make_property : std::vector<int>::const_iterator
{
    using base_class = std::vector<int>::const_iterator;
    using value_type = std::pair<const base_class::value_type, Property>;
    using base_class::base_class;

    decltype(auto) get() const {
        return base_class::operator*();
    }

    value_type operator*() const
    {
        return std::pair<const int, Property>(get(), Property());
    }
};

int main() {
    printf("Performance Summary:\n");
    static const unsigned long num_iter = 9999999;

    std::vector<int> keys;
    keys.reserve(num_iter);
    std::generate_n(std::back_inserter(keys), num_iter, [](){ return rand() / 10000; });


    auto time = [](const char* message, auto&& func)
    {
        clock_t tStart = clock();
        func();
        clock_t tEnd = clock();
        printf("%s: %.2gs\n", message, double(tEnd - tStart) / CLOCKS_PER_SEC);
    };

    std::unordered_map<int, Property > myumap;
    time("fill unordered map", [&]
    {
        myumap.insert (make_property(keys.cbegin()),
                       make_property(keys.cend()));
    });


    std::map<int, Property > mymap;
    time("fill ordered map",[&]
         {
             mymap.insert(make_property(keys.cbegin()),
                          make_property(keys.cend()));
         });

    time("find in unordered map",[&]
         {
             for (auto k : keys) { myumap.find(k); }
         });

    time("find in ordered map", [&]
         {
             for (auto k : keys) { mymap.find(k); }
         });
}

例子输出：

Performance Summary:
fill unordered map: 3.5s
fill ordered map: 7.1s
find in unordered map: 1.7s
find in ordered map: 5s

- Richard Hodges