去年换搜索服务时,压测结果让我们很难解释。旧实现是双层循环,对每个查询词遍历整个词典,标称 O(n²);新实现先建哈希表,再按首字符分组扫描,标称 O(n)。评审时所有人都觉得新实现是明显进步。

结果在小词典上,旧实现反而更快;把词典加到二十万条,新实现才明显反超。同一段代码,小数据量输、大数据量赢,说明「O(n) 比 O(n²) 快」这句话本身漏了条件。

大 O 记号描述的是数据量变大时运算次数怎么增长,它不描述每次运算要花多久。而每次运算花多久,取决于数据在不在缓存、分支猜没猜对、内存分配了几次。这篇用几组本机测量把这些常数拆开,最后要诚实地说清楚:大 n 时高阶项仍然会赢,小 n 的结果不能拿来否定复杂度。

现场:两个实现的压测结果反了

旧实现收到查询词后,遍历词典里的每一条,逐字符比较前缀,匹配就记录下来。外层是查询词,内层是词典,成本大致是词典条数乘比较长度,标称 O(n²)。它的代码简单,没有任何额外结构。

新实现先把词典建成一个按首字符分组的哈希表,查询时只取对应字符的桶,再在桶里比较,标称 O(n)。建表是一次性的,查询次数越多,摊到每次的成本越低,看起来全面占优。

小词典上输的原因有两层。建哈希表本身要时间,查询时算哈希、访问散落在内存里的桶,每一步都不便宜;旧实现虽然比较了 2000 条,但数据挨在一起,读第一条时后面几十条已经被带进缓存,比较的又是短字符串,分支很规律。新实现省下了循环次数,却把每次访问变贵了。

这不是「新代码写得差」,而是小规模下常数项主导了结果。复杂度记号里的 n 还小,高阶项还没长大,谁的单步更便宜、谁的访存更连续,谁就赢。下面先把大 O 记号说清楚。

大 O 只数运算次数,不数时间

大 O 记号描述的是「数据量趋向无穷大时,运算次数增长的数量级」。写 O(n) 的意思是数据量翻一倍,运算次数大约也翻一倍;写 O(n²) 的意思是数据量翻一倍,运算次数大约翻四倍。它关心趋势,不关心具体数值。

为了让这个描述成立,分析时必须先约定一次运算花多少时间。教科书里的默认模型假设:读一个变量、做一次加法、比较一次,都算一步,代价相同;内存访问不分层级,取哪里都一样快。这个模型把真实机器抹平成了一张均匀的纸。

真实机器不是均匀的。CPU 读数据要先看寄存器,再看一级缓存、二级缓存、三级缓存,最后才去内存,越往后越慢,差距可以到几十倍甚至上百倍。数据在不在缓存里,取决于它最近有没有被访问过、和周围的数据是否挨着。大 O 完全不区分这些情况。

寄存器与一级缓存容量最小,速度最快,通常只有几十 KB。刚用过的数据大概率还在这里。
二级、三级缓存容量几 MB 到几十 MB,速度比内存快数倍。数据量超过它,顺序访问也开始变慢。
内存容量大,延迟大约是缓存的几十倍。随机访问时,每次都可能停在这里等。
磁盘与网络比内存再慢几个数量级。数据库和远程调用的大部分时间花在这一层。

大 O 不是错的,它只是第一层近似。它回答「数据量增大时谁先撑不住」,不回答「在当前数据量下谁更快」。工程上判断性能必须把两者分开:先用复杂度排除增长过快的方案,再用测量比较同一量级里的常数。

缓存行与局部性:同样 O(n²) 差五倍

CPU 读内存不是按字节读,而是一次读一整条缓存行,常见大小是 64 字节。读一个 8 字节的浮点数,会把相邻的 56 字节一起搬进缓存。如果接下来的访问正好落在这一行里,就不用再去内存,这叫空间局部性;同一个地址被反复访问,也容易命中,这叫时间局部性。

二维数组在内存里连续存放:先放第一行,再放第二行。按行遍历时,访问顺序和内存顺序一致,后面的元素基本都在同一条或相邻的缓存行里;按列遍历时,每次往下走一行,地址就跳一整行的长度,前一次搬进来的缓存行完全用不上。

const a = new Float64Array(n * n);
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) sum += a[i * n + j];   // 按行
}
for (let j = 0; j < n; j++) {
  for (let i = 0; i < n; i++) sum += a[i * n + j];   // 按列
}

本机 Node.js 24 的测量:n 等于 2000,一共 400 万个浮点数,约 30.5MB,按行遍历平均 2.72 毫秒,按列遍历平均 13.44 毫秒,差了 4.9 倍。n 等于 1000、数据约 7.6MB 时差 2.4 倍;n 等于 500、约 1.9MB 时只差 2.1 倍。两种写法的加法次数完全一样,复杂度完全一样,差别只在数据有没有被提前搬进缓存。

这个数字随机器变化,但方向稳定:数据量越大、越超过缓存容量,按列遍历的劣势越明显。原因是每次跳行都可能是一次新的内存访问,而按行遍历把一次内存访问摊给了同一行里的多个元素。写代码时把访问顺序和存储顺序对齐,往往比换一个更复杂的算法更有效。

小 n:插入排序赢归并排序

排序是常数因子最容易被看见的地方。归并排序把数组分成两半,分别排好再合并,时间复杂度是 O(n log n);插入排序每次把一个元素插到前面已排好的部分,最坏是 O(n²)。按复杂度,任何 n 下归并都该赢,但小 n 时并非如此。

原因是插入排序的内层循环非常紧凑:比较、后移、再比较,数据就在手边,没有递归,没有额外数组。归并排序要反复切分数组、申请新数组、把元素复制来复制去,这些额外动作在 n 很小时占比很大。

function insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const v = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > v) { a[j + 1] = a[j]; j--; }
    a[j + 1] = v;
  }
  return a;
}
function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  const l = mergeSort(a.slice(0, mid));
  const r = mergeSort(a.slice(mid));
  const out = new Array(a.length);
  let i = 0, j = 0, k = 0;
  while (i < l.length && j < r.length) out[k++] = l[i] <= r[j] ? l[i++] : r[j++];
  while (i < l.length) out[k++] = l[i++];
  while (j < r.length) out[k++] = r[j++];
  return out;
}

本机对随机整数排序,每种规模跑几百到几千次取平均:n 等于 64 时,插入 2.0 微秒,归并 5.3 微秒;n 等于 128 时,插入 6.6 微秒,归并 11.5 微秒;n 等于 256 时,插入 20.1 微秒,归并 24.9 微秒,仍然插入更快;到 n 等于 512,插入变成 93.5 微秒,归并 54.2 微秒,交叉点在这附近。再往上,插入按平方增长,n 等于 2048 时已经 1077.7 微秒,归并只要 242.1 微秒。

这也是很多标准库的做法:大数组用归并或快排,切到很小的子数组时改用插入排序。它不是理论上的妥协,而是实测出来的常数优化。交叉点的位置跟语言、实现、数据分布都有关,本机在 256 到 512 之间,换一台机器、换一种语言,可能是 16 到 32。不要记数字,记「小规模时低阶项占主导」这个结论。

一个 O(n) 输给 O(n²) 的实测

再做一个更极端的对照。第一个程序是 O(n):遍历一个大数组,每步读一个元素累加。但它不是顺序读,而是用伪随机数算出下标,每次读的位置几乎都跳着走。数组有 1677 万个 32 位整数,约 64MB,远超常见缓存,每一步都可能去内存取数。

function randomWalk(a, steps) {
  let x = 2463534242, s = 0;
  for (let k = 0; k < steps; k++) {
    x ^= x << 13; x ^= x >>> 17; x ^= x << 5;
    x &= 0x7fffffff;
    s += a[x % a.length];
  }
  return s;
}
function nestedHot(n) {
  const a = new Int32Array(n);
  for (let i = 0; i < n; i++) a[i] = i & 1023;
  let s = 0;
  for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) s += a[j];
  return s;
}

第二个程序是 O(n²):两层循环,n 等于 4096,一共也是约 1677 万次加法。区别是它只用一个 4096 个整数的小数组,约 16KB,完全装得进一级缓存,每次加法读的都是手边的数据。

本机结果:随机访问的 O(n) 版本耗时约 239.1 毫秒;全在缓存里的 O(n²) 版本耗时约 10.82 毫秒。运算次数相同,慢了约 22 倍。这个结果不是「O(n²) 更好」,而是「在这个规模、这种访存模式下,O(n) 的每一步太贵」。把随机数组缩小到能装进缓存,O(n) 版本会快得多;把 O(n²) 的 n 继续加大,它迟早也会超过缓存开始变慢,而且增长更快。

分支预测、内存分配与低阶项

除了缓存,CPU 还有一个影响常数的大机制:分支预测。程序里的 if 会被翻译成条件跳转,CPU 为了提高效率,会猜下一次走哪边,猜对了继续流水线,猜错了要清空重来。猜测的依据是历史,所以大部分时候走同一边的代码快,一半一半随机跳的代码慢。

本机做了一组条件求和:100 万个 0 到 255 的字节,累加大于等于 128 的值。数组如果排好序,条件先全假后全真,只有一次切换,CPU 几乎全猜对,耗时约 0.89 毫秒;数组如果打乱,条件随机跳,预测频繁失败,耗时约 3.90 毫秒,差了 4.4 倍。两段代码的运算次数完全一样。

内存分配也是常数项。本机用三种方式装 100 万个整数:每个整数包成一个对象放进普通数组,耗时约 64.4 毫秒;直接放数字,约 12.3 毫秒;用 Int32Array 预分配,约 2.2 毫秒。同样的数据、同样的循环次数,光「怎么装」就差了几十倍。对象多了还会给垃圾回收增加压力,停顿会出现在业务请求里,而不是基准测试里。

低阶项在小 n 时更明显。O(n log n) 里的 log n 在 n 等于 100 时只有 7,和一个常数差不多;O(n) 里的 n 在 n 等于 10 时,也挡不住一次额外的哈希计算。复杂度分析通常省略低阶项和系数,这个省略在 n 很大时没问题,在 n 很小时会让结论反转。判断当前场景属于哪一边,唯一可靠的办法是拿真实数据量去测。

现象、真实原因与第一步查什么

下面这些现象经常被解释成「算法选错了」,实际原因往往在常数、访存顺序或测量方法上。先按第三列查一件事,再决定要不要换算法。

现象真实原因第一步查什么
标称更优的实现在小数据量下更慢小 n 时常数项和初始化成本占主导测量时用的数据量是否接近真实规模
同样 O(n²),两种写法差好几倍访问顺序和内存布局不一致,缓存未命中内层循环是否按行连续访问
排序在 n 很小时反而慢递归、切分和临时数组的固定开销太大是否对小子数组改用插入排序
把数组改成哈希表后没有变快哈希计算和随机访存吃掉了查找节省的时间数据量是否小到能整体装进缓存
基准测试结果忽快忽慢没有预热,即时编译还没完成,或测量被垃圾回收打断是否预热、是否多次取平均、是否统计了停顿
压测很快,线上很慢压测数据太整齐,分支可预测、缓存全命中压测数据是否和真实数据分布一致
加了并发反而更慢多线程争抢同一缓存行,或锁竞争加剧线程是否在写同一块内存
数据量翻倍后耗时翻了几十倍工作集超过缓存容量,原本的命中消失数据总大小与各级缓存容量

第一行和最后一行最值得记。第一行说明复杂度更优不等于当前更快,很多选型争论其实是在拿不同 n 下的结论互相比;最后一行说明缓存容量是一条看不见的台阶,数据量跨过它,耗时可能突然跳一个量级。看到「翻倍数据量、耗时翻几十倍」,先怀疑工作集越过了缓存,不要先怀疑算法写错了。

边界与代价:大 n 时高阶项仍然赢

这一节必须说清楚,不能让上面的测量变成「复杂度没用」的证据。所有反例都有一个共同前提:n 不大,或者两个实现的访存模式差别极大。一旦 n 足够大,高阶项一定会接管,因为它的增长速度不可能被常数追上。

举个量级上的例子:O(n) 每一步就算比 O(n²) 的每一步贵 100 倍,当 n 从 1000 涨到 100 万时,O(n) 的运算次数涨 1000 倍,O(n²) 涨 100 万倍,后者迟早会超过前者。缓存只能把每一步贵多少拉开几倍到几十倍,拉不开数量级的增长速度。所以正确的结论是:常数决定在哪个 n 之前谁赢,复杂度决定 n 大了之后谁赢。

工程上的做法是把两者都用上。先用复杂度筛掉增长过快的方案,尤其是数据量可能长期增长的接口;再在同一量级的候选里,用真实数据量测常数,选实测更好的那个。只做第一步,可能在小数据量上选了一个更慢的实现;只做第二步,可能在数据涨十倍后被一个平方级实现拖死。

还有几个测量本身的边界要交代。JavaScript 的微基准很受即时编译影响,同一段代码跑第一次和跑第一百次可能差几倍;垃圾回收会在任意时刻打断测量;操作系统的后台任务、CPU 降频也会影响结果。本文的数字都来自同一台机器的同一次会话,只能比较量级,不能当成你机器上的承诺值。换语言、换编译器优化级别,常数会变,结论的方向通常不变。

最后一点:不要为了常数优化牺牲可读性。把按列遍历改成按行遍历、把对象数组改成类型化数组,这类改动通常值得;但为了省一次哈希,把代码写成难以维护的形状,往往不划算。常数优化的收益要用测量证明,不能靠直觉。

当天能做的练习

  1. 写一个二维数组求和,分别按行和按列遍历,n 取 200、500、1000,记录耗时和倍数,说明倍数随 n 变化的原因。
  2. 实现插入排序和归并排序,n 从 16 测到 1024,记录交叉点,再把归并对小于 32 的子数组改用插入排序,比较总耗时。
  3. 把本文的随机访问版本改成顺序访问,保持运算次数不变,记录耗时,解释缓存命中率在结果里起了什么作用。
  4. 做一次分支预测实验:把一百万个随机字节排序后再条件求和,和打乱版本对比,至少跑五次取平均。
  5. 用对象数组、普通数字数组、Int32Array 各装一百万个整数,记录耗时和内存占用,说明数据结构的选择怎样影响常数。
环境说明:本文全部耗时数据来自本机 Node.js 24 的实际运行,测量前做了预热,排序与分支实验多次取平均。不同机器的缓存容量、编译器优化和垃圾回收策略会改变具体数字,文中数字只用于说明常数的量级,不构成性能承诺。

小结与下一篇

三句话收一下:大 O 数的是运算次数,不数每次运算花多久;缓存行、分支预测、内存分配和小 n 时的低阶项,能把同为 O(n) 的实现拉开几倍甚至几十倍;大 n 时高阶项仍然会赢,常数只决定交叉点在哪。

下一篇顺着常数继续往下挖:库函数、递归和实测数字为什么经常对不上。看起来是 O(1) 的数组操作,可能暗地里复制了整个数组;看起来是 O(n) 的字符串拼接,可能在循环里变成 O(n²);看起来同样的递归,尾调用和普通递归的栈开销完全不同。那一篇会把这些隐藏成本逐个拆开,并给出识别它们的办法。