C++测量unordered_set查找等极快操作的耗时差异疑问

• 这个问题不适合发布在代码评审板块。代码评审板块的适配场景是代码可正常运行、寻求代码风格、可维护性、设计逻辑层面的优化建议，你当前的核心诉求是解释性能测试结果的底层原理，属于C++标准库实现、计算机体系结构相关的技术问答范畴，发在通用技术问答板块更合适。

测试引入头文件 #

#include <iostream>
#include <vector>
#include <chrono>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <map>

完整测试代码 #

std::vector<int> eurastothenes_sieve(size_t count){
    std::vector<bool> sieve(count * std::log2(count), true);
    sieve[0] = false;
    sieve[1] = false;
    auto factor = 2;
    while(factor * factor < sieve.size()) {
        for (auto not_prime_idx = factor * 2; not_prime_idx < sieve.size(); not_prime_idx+= factor) {
            sieve[not_prime_idx] = false;
        }
        while(!sieve[++factor]);
    }
    std::vector<int> primes;
    for(int idx = 0; idx < sieve.size(); idx++){
        if(sieve[idx]){
            primes.push_back(idx);
        }
    }
    return primes;
}

std::vector<int> numbers_to_find(int max, size_t count) {
    std::vector<int> v(count);
    auto p_rand = [max](){
        return std::rand() % max;
    };
    std::generate(v.begin(), v.end(), p_rand);
    return v;
}

int main() {
    auto primes = eurastothenes_sieve(1000);
    std::unordered_set<decltype(primes)::value_type> primeset(primes.begin(), primes.end());

    std::map<int, double> timings;

    for(int i = 100; i <= 1000; i+=100 ){
        auto find_me = numbers_to_find(primes[i], 10000);
        auto start = std::chrono::steady_clock::now();
        auto found = 0;
        int count = 10000;
        while(count--)
        for(auto val: find_me)
        {
            if(primeset.find(val) != primeset.end()){
                found++;
            }
        }

        auto end = std::chrono::steady_clock::now();

        std::cout << "In " << (end - start).count() << " ns";
        std::cout << " we found " << found << "\n";
        timings.insert({i, (end - start).count() / (10000.0 * 10000)});
    }
    for(auto n_t : timings){
        std::cout << "N = " << n_t.first << ": " << n_t.second << "ns\n";
    }
}

unordered_set查找测试结果 #

N = 100: 15.5874ns
N = 200: 15.4113ns
N = 300: 15.3488ns
N = 400: 15.4806ns
N = 500: 15.4009ns
N = 600: 15.5415ns
N = 700: 15.3537ns
N = 800: 15.4371ns
N = 900: 15.2567ns
N = 1000: 15.3602ns

校准用累加测试代码 #

for(auto val: find_me)
    {
            found+=val;         
    }

累加测试结果 #

N = 100: 0.0657845ns
N = 200: 0.0657359ns
N = 300: 0.0649369ns
N = 400: 0.0651398ns
N = 500: 0.0649169ns
N = 600: 0.0650553ns
N = 700: 0.0654992ns
N = 800: 0.0645845ns
N = 900: 0.065315ns
N = 1000: 0.0649747ns

待澄清的疑问 #

• 已知unordered_set为O(1)时间复杂度的访问结构，该特性符合测试结果，测试搭建逻辑无明显问题
• 为什么取模运算+内存查找（unordered_set的核心查找逻辑）的耗时，是寄存器+缓存值操作（简单整数累加）的200倍？
• 简单累加测试结果是否真实，即代码真的能做到每0.06纳秒完成一次随机整数加法吗？
• 核心疑问：为什么取模和内存查找操作的耗时这么高？测试已尽量做缓存友好设计，测试所用CPU的L1缓存为32K，编译选项为CMake Release模式、g++ -O2优化等级。

0.06ns/次的累加结果完全不反映单步加法的真实耗时。目前消费级CPU主频普遍在3_{5GHz，单时钟周期约0.2}0.3ns，物理上不可能做到0.06ns完成一次整数加法。这个数值是编译器优化叠加CPU硬件特性带来的：-O2优化等级下，编译器会对纯累加的循环做向量化展开、循环不变量外提，甚至直接推导批量求和的计算逻辑，根本不会逐次执行单步加法；再加上CPU本身的多发射流水线、乱序执行能力，可以同时并行处理多条无依赖的加法指令，你测到的是批量计算摊薄后的平均耗时，不是单操作的真实执行时间。

你测到的unordered_set单次查找15ns左右的耗时完全在合理范围内，不存在异常偏高的问题，核心原因有三个：

• 你认为的“缓存友好”实际不成立：gcc等主流标准库的unordered_set是链式哈希表实现，每个元素都是独立分配的堆节点，哪怕总数据量很小，节点的内存地址也不是连续的。查找时算完哈希位置后，需要通过指针跳转随机访问节点内存，哪怕所有数据都落在L1缓存里，单次L1访存就有1ns左右的延迟，还没算其他操作的开销。
• unordered_set的查找流程远不止“取模+读内存”两步：首先要对key做哈希计算（哪怕int类型的默认哈希是恒等映射，取模计算桶索引本身就要几个时钟周期），之后读取对应桶的头指针，再跳转读取节点存储的key值做比对，如果遇到哈希冲突还要顺着桶内的链表继续遍历下一个节点。整个流程的每一步都强依赖上一步的执行结果，必须等上一步的值算完、读回来才能走下一步，完全是串行阻塞的，没法像无依赖的累加操作那样被CPU并行调度。
• 两者的执行场景没有可比性：纯累加操作的所有操作数都可以放在寄存器里，没有任何内存访问开销，CPU可以同时塞满流水线并行执行几十条累加指令；而哈希查找全程夹杂随机访存、分支判断、依赖链阻塞，能跑到15ns/次已经是小数据量全命中L1缓存的优秀结果，要是数据量涨到超过L1/L2缓存，单次查找耗时会直接涨到几十甚至上百纳秒。

内容的提问来源于stack exchange，提问作者Captain Giraffe