为什么向量与 unordered_map 的基准查找在每个运行中都会产生不一致的结果？

Question

我遇到了类似这个问题的问题：Timed vector vs map vs unordered_map lookup

但我的案例仅针对 vector 与 unordered_map 的小范围元素（0-100，大部分为 0-20）。所以我更改了作者@gitgregor代码：

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
#include <algorithm>

unsigned dummy = 0;

int main()
{
    std::vector<unsigned> v;
    std::unordered_map<unsigned, unsigned> u;

    unsigned elementCount = 1;

    struct Times
    {
        unsigned long long v;
        unsigned long long u;
    };
    std::map<unsigned, Times> timesMap;

    while (elementCount != 100)
    {
        v.clear();
        u.clear();

        elementCount *= 10;
        std::vector<unsigned int> tmp;
        tmp.reserve(elementCount);
        for (unsigned i = 0; i < elementCount; ++i)
        {
            tmp.push_back(std::rand()%50000);
        }
        // fill vector and unmap with random numbers
        for (const auto integer : tmp)
        {
            v.emplace_back(integer);
            u.insert(std::make_pair(integer, 1));
        }
        // fill a testset with 10000 random numbers to test lookup
        std::vector<unsigned> tmp2;
        tmp2.reserve(10000);
        for (int i = 0; i < tmp2.size(); i++)
        {
            tmp2.push_back(std::rand()%50000);
        }

        std::chrono::time_point<std::chrono::steady_clock> start = std::chrono::high_resolution_clock::now();
        for (const auto integer : tmp2)
        {
            auto findItr = std::find(std::begin(v), std::end(v), integer);
            if (findItr != v.end())
            {
                dummy++;
            }
        }
        auto tp0 = std::chrono::high_resolution_clock::now() - start;
        unsigned long long vTime = std::chrono::duration_cast<std::chrono::nanoseconds>(tp0).count();

        start = std::chrono::high_resolution_clock::now();
        for (const auto integer : tmp2)
        {
            const bool res = u[integer] == 0;
            if (res)
            {
                dummy++;
            }
        }
        auto tp1 = std::chrono::high_resolution_clock::now() - start;
        unsigned long long uTime = std::chrono::duration_cast<std::chrono::nanoseconds>(tp1).count();

        timesMap.insert(std::make_pair(elementCount, Times{ vTime, uTime }));
    }

    for (auto& itr : timesMap)
    {
        std::cout << "Element count: " << itr.first << std::endl;
        std::cout << "std::vector time:        " << itr.second.v << std::endl;
        std::cout << "std::unordered_map time: " << itr.second.u << std::endl;
        std::cout << "-----------------------------------" << std::endl;
    }

    std::cout << dummy;
}

我关闭了优化并有随机数填充 vector 和 unordered_map，并使用 10000 个随机数的数字集来测试查找。但是结果根本不一致：

First run:
Element count: 10
std::vector time:        100
std::unordered_map time: 100
-----------------------------------
Element count: 100
std::vector time:        0
std::unordered_map time: 100
-----------------------------------

Second Run:
Element count: 10
std::vector time:        200
std::unordered_map time: 200
-----------------------------------
Element count: 100
std::vector time:        100
std::unordered_map time: 100
-----------------------------------

Third Run:
Element count: 10
std::vector time:        100
std::unordered_map time: 0
-----------------------------------
Element count: 100
std::vector time:        100
std::unordered_map time: 0
-----------------------------------

结果看起来也很奇怪，只有数字：0、100 和 200。

有人知道为什么吗？

Answer 1

我发现了您的代码无法正确测量的真正原因，因为您的循环 for (int i = 0; i < tmp2.size(); i++) 运行了 0 次，因为 tmp2 的大小在开始时为 0。因此，您正在针对来自 tmp2 的 0 个整数进行测试，因此您的时间几乎为 0（未进行任何操作）。

我修改了您的代码以解决上述问题，还解决了一些编译问题，还将整数（迭代）数设置为 100 万而不是 10000，我还计算了平均运行时间（以纳秒为单位） ) 而不是总时间，还添加了 std::map 测量值，以备不时之需。下面是完整的更正代码。

Try it online!

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
#include <algorithm>
#include <cstdint>

volatile size_t dummy_total = 0;

int main()
{
    std::vector<unsigned> v;
    std::unordered_map<unsigned, unsigned> u;
    std::map<unsigned, unsigned> m;

    unsigned elementCount = 5;

    struct Times
    {
        double v = 0;
        double m = 0;
        double u = 0;
    };
    std::map<unsigned, Times> timesMap;

    while (elementCount <= 80)
    {
        size_t dummy = 0;
        v.clear();
        u.clear();
        m.clear();

        elementCount *= 2;
        std::vector<unsigned int> tmp;
        tmp.reserve(elementCount);
        for (unsigned i = 0; i < elementCount; ++i)
        {
            tmp.push_back(std::rand()%50000);
        }
        // fill vector and unmap with random numbers
        for (const auto integer : tmp)
        {
            v.emplace_back(integer);
            u.insert(std::make_pair(integer, 1));
            m.insert(std::make_pair(integer, 1));
        }
        // fill a testset with 10000 random numbers to test lookup
        std::vector<unsigned> tmp2(1000000);
        for (int i = 0; i < tmp2.size(); i++)
        {
            tmp2[i] = std::rand()%50000; 
        }

        std::chrono::time_point<std::chrono::high_resolution_clock> start = std::chrono::high_resolution_clock::now();
        for (const auto integer : tmp2)
        {
            auto findItr = std::find(std::begin(v), std::end(v), integer);
            if (findItr != v.end())
            {
                ++dummy;
            }
        }
        auto tp0 = std::chrono::high_resolution_clock::now() - start;
        double vTime = double(std::chrono::duration_cast<std::chrono::nanoseconds>(tp0).count()) / tmp2.size();

        start = std::chrono::high_resolution_clock::now();
        for (const auto integer : tmp2)
        {
            const bool res = u.count(integer) != 0;
            if (res)
            {
                ++dummy;
            }
        }
        auto tp1 = std::chrono::high_resolution_clock::now() - start;
        double uTime = double(std::chrono::duration_cast<std::chrono::nanoseconds>(tp1).count()) / tmp2.size();

        start = std::chrono::high_resolution_clock::now();
        for (const auto integer : tmp2)
        {
            const bool res = m.count(integer) != 0;
            if (res)
            { 
                ++dummy;
            }
        }
        auto tp2 = std::chrono::high_resolution_clock::now() - start;
        double mTime = double(std::chrono::duration_cast<std::chrono::nanoseconds>(tp2).count()) / tmp2.size();

        dummy_total = dummy_total + dummy;
        timesMap.insert(std::make_pair(elementCount, Times{ vTime, mTime, uTime }));
    }

    for (auto& itr : timesMap)
    {
        std::cout << "Element count: " << itr.first << std::endl;
        std::cout << "std::vector time:        " << itr.second.v << " ns" << std::endl;
        std::cout << "std::map time: " << itr.second.m << " ns" << std::endl;
        std::cout << "std::unordered_map time: " << itr.second.u << " ns" << std::endl;
        std::cout << "-----------------------------------" << std::endl;
    }

    std::cout << dummy_total;
}

输出：

Element count: 10
std::vector time:        12.8182 ns
std::map time: 26.4334 ns
std::unordered_map time: 10.2652 ns
-----------------------------------
Element count: 20
std::vector time:        24.1431 ns
std::map time: 33.9809 ns
std::unordered_map time: 13.0953 ns
-----------------------------------
Element count: 40
std::vector time:        60.7386 ns
std::map time: 42.3911 ns
std::unordered_map time: 20.1641 ns
-----------------------------------
Element count: 80
std::vector time:        102.167 ns
std::map time: 52.1565 ns
std::unordered_map time: 10.2345 ns
-----------------------------------
Element count: 160
std::vector time:        190.878 ns
std::map time: 68.7916 ns
std::unordered_map time: 13.5962 ns
-----------------------------------
18726

为什么向量与 unordered_map 的基准查找在每个运行中都会产生不一致的结果？

Why Benchmarking lookups for vector vs unordered_map yields inconsistent results in each run?

c++

hashmap

为什么向量与 unordered_map 的基准查找在每个 运行 中都会产生不一致的结果？

Why Benchmarking lookups for vector vs unordered_map yields inconsistent results in each run?

c++

hashmap

为什么向量与 unordered_map 的基准查找在每个运行中都会产生不一致的结果？