正常
复杂度不是一切:O(1) 怎么输给了 O(n)
这一系列笔记的来历
这一系列基于 CppCon 2025 上 Jonathan Müller 的演讲 Cache-Friendly C++ 做的二次发散。Jonathan 长期做低延迟 C++,这场他从根上讲 CPU 缓存。原讲视频在 YouTube。笔者把演讲里的每个关键论断都配了一段本机实测,数字是笔者自己跑出来的,不是 PPT 上的截图。
很多人学 C++ 的时候,选容器靠的是一条刻板公式:unordered_set 查找 O(1),set 查找 O(log n),vector 查找 O(n),所以查找这件事"显然"该用 unordered_set。教科书这么写,面试这么考,笔者以前也这么信。直到自己写个基准测一下,才发现这条公式在真实机器上根本不是这么回事。这一篇咱们就从这个"反直觉"的现象切入,把复杂度迷信先打破,缓存机制留到下一篇细讲。
四个选手,一场查找比赛
要测的场景很简单:往容器里塞 N 个整数,然后查 10 万次(一半命中一半落空,打乱顺序),看耗时怎么随 N 变化。参赛的是四个常见选择:
std::vector(无序):push_back塞入,std::find线性扫描,O(n)。std::vector(排序):排好序,std::lower_bound二分查找,O(log n)。std::set:红黑树,O(log n)。std::unordered_set:哈希表,均摊 O(1)。
按复杂度教条,排名应该是 unordered_set 一骑绝尘,set 和排序 vector 并列第二,无序 vector 垫底。咱们来看看本机(GCC 16.1.1,-O2)的真实数据,先看无序 vector 的线性查找:
text
N= 16 vec线性= 482.0 us set= 603.0 us unordered= 638.0 us
N= 64 vec线性= 994.0 us set= 951.0 us unordered= 622.0 us
N= 256 vec线性= 3099.0 us set= 1375.0 us unordered= 660.0 us
N= 1024 vec线性= 12464.0 us set= 2115.0 us unordered= 715.0 us
N= 8192 vec线性= 89199.0 us set= 3556.0 us unordered= 782.0 us
N= 65536 vec线性=568461.0 us set= 14071.0 us unordered= 1161.0 us咱们盯着第一行看。N=16 的时候,O(n) 的 vector 线性查找赢了 O(1) 的 unordered_set,也赢了 O(log n) 的 set。一个理论上最慢的方案,在实际机器上最快。这不是噪声,跑五轮取中位数的结果稳定如此。
继续往下看,N 增大之后无序 vector 的 O(n) 本性暴露,耗时陡增(N=65536 时 568 毫秒),unordered_set 的 O(1) 优势这时才确立。但即便在 N=65536 这种规模,unordered_set 也只比 set 快一个量级,远没有"O(1) vs O(log n)"听上去那么悬殊。
同为 O(log n),缓存友好的那个碾压
无序 vector 在小数据量下逆袭,已经够打破教条了。但更有说服力的是把两个同为 O(log n) 的选手拉出来单挑:排序 vector 的二分查找,对 std::set 的红黑树查找。复杂度一样,都是 O(log n),按教条它们应该并驾齐驱。
text
N= 64 vec二分= 1059.0 us set= 949.0 us unordered= 630.0 us
N= 1024 vec二分= 2041.0 us set= 2022.0 us unordered= 713.0 us
N= 8192 vec二分= 3037.0 us set= 3946.0 us unordered= 796.0 us
N= 65536 vec二分= 5425.0 us set= 10766.0 us unordered= 1092.0 us
N=262144 vec二分= 8090.0 us set= 19903.0 us unordered= 1483.0 usN=64 和 N=1024 时两者差不多(N=1024 时 2041 对 2022,几乎打平)。但从 N=8192 开始,排序 vector 反超,而且差距越拉越大:N=65536 时 vec二分 5425 us 对 set 10766 us,快了将近一倍;N=262144 时 8090 对 19903,快了两倍多。
复杂度完全相同,一个把另一个甩出两倍多。这用大 O 表示法是解释不了的。
大 O 骗了你什么
问题出在大 O 表示法对"操作"的定义上。大 O 数的是操作的次数——几次比较、几次哈希,但它对每次操作的代价是完全盲的。而在真实机器上,同样一次"操作",代价可以差出两个数量级。
std::set 的底层是红黑树,每个节点是一块独立 new 出来的内存,散落在堆的各个角落。查找时你顺着指针一路跳:根节点 → 左孩子 → 右孩子的右孩子……每跳一次节点,访问的都是一个相距上一次很远的新地址,极大概率是一次缓存未命中(cache miss)。而一次缓存未命中,要等几十到上百纳秒(具体数字下一篇讲),相当于几十上百次普通运算的时间。
排序 vector 完全相反。它的数据是连续排布在一段内存里的。二分查找虽然每次跳到的位置在逻辑上离上一次很远(从中间跳到四分之一处),但物理上它们都挤在同一段连续内存里。更重要的是,CPU 搬数据不是按字节搬的,而是按缓存行(cache line,通常 64 字节)整块搬。你读了数组中间那个元素,它前后好几个元素跟着整块进了缓存,后面几次二分跳到的位置很可能已经在缓存里了。再加上硬件预取器发现你在按某种模式访问连续内存,会主动把后面的数据提前拉进来。
于是局面变成这样:set 每跳一次节点付一次可能的主存访问代价,操作次数少但每次贵;vec二分 操作次数多一点,但绝大多数都命中缓存,每次几乎零代价。两相权衡,缓存友好的那个完胜。N 越大,set 的节点散得越开、缓存越不友好,差距就越大。
unordered_set 在大数据量下能赢,是因为它的哈希表设计上就尽量让桶数组连续,加上 O(1) 的操作次数确实少,综合下来最快。但它的 O(1) 也不是免费的——哈希表节点之间仍然有跳转,所以小数据量下它的常数因子比连续内存的 vector 大,会被逆袭。这就是 N=16 那一行发生的事。
所以容器到底该怎么选
理解了上面的机制,容器选择的思路就得改:不能只看复杂度,得看数据量级和访问模式。给一个务实的决策参考:
查找为主、数据量小(几十到几百):优先无序 vector。它插入快(push_back),数据连续缓存友好,小数据量下线性查找比你想的快得多。代码还简单。
查找为主、数据量中等(几千到几十万)、可排序:排序 vector 配 std::lower_bound。缓存友好让它在同等复杂度下击败 set,内存开销也小得多(没有节点指针)。
需要频繁插入+查找、数据量大:unordered_set/unordered_map。记得 reserve 避免 rehash。这时 O(1) 的优势才真正兑现。
需要有序遍历或按范围查询:std::set 或排序 vector。注意 set 的缓存劣势。
这只是起手参考,不是教条。 Jonathan 在演讲里反复强调一条原则:永远在你的目标数据规模和访问模式下实测。别人的 benchmark 数字(包括上面这几张表)只能给你方向,不能给你答案,因为缓存行为跟 CPU 微架构、数据分布、甚至周围其他代码的内存占用都强相关。
这一层的边界
这一篇咱们用实验打破了"复杂度低就一定快"的迷信,看到了缓存局部性在小数据量下能碾压算法复杂度。但"为什么缓存这么重要"这件事,咱们还只说了结论,没讲机制——为什么一次缓存未命中要等那么久?缓存到底按什么单位搬数据?L1、L2、L3 各级缓存延迟差多少?顺序访问为什么比随机访问快十几倍?这些是下一篇的主角,搞清楚它们,你才能在设计数据结构时主动利用缓存,而不是碰运气。