先还原一次线上事故。后台一个导出任务,任务进数组队列,由 worker 逐个取出处理。代码只有一层循环,取出、处理、写结果,看起来是标准的线性流程。压测时用 1 万条任务,整段耗时 0.35 毫秒,大家都觉得没问题。上线后真实队列到了 3 万条,单次处理 772 毫秒;4 万条,1.4 秒。数据翻倍,时间翻四倍,这是平方级的形状。

排查半天,问题在循环体里一句 queue.shift()。shift 的意思是「从数组头部取出一个元素」,写起来只有一行,但为了保持数组连续,它要把后面所有元素往前挪一格。取第一个元素要挪 n 减 1 个,取第二个要挪 n 减 2 个,加起来大约 n 的平方除以二。循环只有一层,搬移却有一层。

所以「一层循环就是 O(n)」不成立。复杂度要看每一轮执行了多少次基本操作,而不是数代码里有几个 for。这篇拆四类隐藏成本:库函数里的循环、递归的栈深与重复计算、正则回溯、隐式分配与垃圾回收;再解释实测为什么和理论对不上。

现场:一层循环,平方级的耗时

这段代码是事故的简化版。queue 是数组,job 是任务对象,drain 负责清空队列。它没有嵌套,没有递归,退出条件就是队列为空。

function drain(queue) {
  const ids = [];
  while (queue.length) {
    const job = queue.shift();   // 取出队头,后面的元素整体前移
    ids.push(job.id);
  }
  return ids;
}

单看结构,while 每轮只做取出、处理和写入三件事。可是 shift 内部还有一层循环,把下标 1 到末尾的元素整体前移一位。外层 n 轮,内层平均搬 n/2 个,总搬移约 n 的平方除以二。规模翻倍,搬移翻四倍,正好对上事故里的曲线。

一层循环里其实藏着一层搬移
读出下标 0 的元素
下标 1 到末尾逐个前移
长度减一
下一轮再搬一遍

本机 Node.js 24 用 2 万、3 万、4 万个整数做这个循环,shift 版耗时分别是 350.6、772.2、1401.4 毫秒;改成 for 加下标读取,同样处理完这些元素,耗时分别是 0.020、0.023、0.039 毫秒。4 万条这一组差了约三万五千倍。差别不是 shift 慢一点,而是下标常数时间、shift 线性时间,线性操作放进循环就变成平方。

这里对比的是处理完整个队列的总时间,不是单次取出。单次 shift 在 4 万元素上约几十微秒,听起来能接受;可它被调用了 4 万次,账就变了。看复杂度要看总账。

库函数里藏着的循环

标准库的方法都经过优化,但优化不等于常数时间。接口好用,内部做什么由实现决定;调用的人看不到那层循环,容易把线性操作当成普通读写。下面四类最常见。

头部增删shift 与 unshift 要保持元素连续,必须搬移整段元素。单次 O(n),放进循环就是 O(n²)。
线性查找includes 与 indexOf 从下标 0 逐个比较。单次 O(n),嵌套一层就是 O(n²)。
复制型方法slice、concat、map、filter 都返回新数组,要复制元素。链式调用越长,临时数组越多。
序列化JSON.stringify 与 JSON.parse 要遍历整棵对象图,再生成或解析字符串,成本随数据量线性增长。

两个列表找交集最典型。下面的写法只有一层外层循环,实际每轮都在 listB 里从头扫。两个表各有 n 个元素且不重叠时最坏:外层 n 轮,内层平均扫 n 个,约 n 平方次比较。

let hit = 0;
for (const x of listA) {
  if (listB.includes(x)) hit++;   // 每轮都从头扫一遍 listB
}

本机用 2000、4000、8000 个互不重叠的整数跑这段,includes 版耗时 2.88、12.47、49.30 毫秒,规模翻倍时间约翻四倍;先建一个 Set 再查,耗时 0.126、0.313、1.024 毫秒,规模翻倍只翻一倍多,接近线性。8000 个元素这一组差了约四十八倍。

const setB = new Set(listB);
let hit = 0;
for (const x of listA) {
  if (setB.has(x)) hit++;
}

Set 的 has 平均是常数时间,因为它是哈希表:算成位置直接去取,不用从头比。代价是先扫一遍 listB 建表,还要额外内存。所以 Set 不是无条件更快:只查一两次,或者 listB 只有十几个元素,includes 反而更直接。判断标准是调用次数和输入大小,不是有没有循环。

复制型方法的问题在累积。循环里写 result = result.concat(batch),每轮都把已有结果整体复制,总复制量也会到平方级。正确做法是先把每批 push 进外层数组,最后统一处理。序列化也一样:2000 行、每行三个字段的对象,本机 stringify 加 parse 约 0.8 毫秒;放进一万次循环,按乘法推算约八秒。这个八秒没有在本机跑一万次,标待确认。

shift 还有个容易误判的地方。本机这版 V8 上,1 万个元素的 shift 循环只花 0.35 毫秒,2 万个突然涨到 350 毫秒。引擎对小数组头部做了「左侧裁剪」,只移动起点不搬元素;规模大了才退回逐元素搬移。阈值属于引擎实现细节,换版本可能变,标待确认。但它说明:小规模测量会把隐藏成本藏起来。

递归:调用栈与重复计算

递归是函数直接或间接调用自己,适合把大问题拆成同形状的小问题,比如树的遍历、分治、回溯搜索。隐藏成本有两处:调用栈深度,和同一个子问题被反复计算。

每次调用,引擎要在调用栈(call stack)上压一帧,记录参数和返回位置;返回时再弹出。栈空间有限,本机用 Node.js 24 二分试出约 10280 层的上限,超过就抛 RangeError。数字随引擎和每帧大小变化,只当量级参考。

更常见的问题是重复计算。朴素斐波那契直接照定义写:

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

本机实测,fib(30) 6.38 毫秒,fib(35) 69.47 毫秒,fib(40) 813.51 毫秒。n 每加 5,时间大约乘 11,因为调用次数按黄金比例 1.618 的 n 次方增长,这是指数增长:照这个曲线,fib(50) 会到几十秒的量级。原因是 fib(38) 在 fib(40) 里算一次、在 fib(39) 里又算一次,越往下重复越多。

记忆化(memoization)就是用一个表存算过的结果,再遇到同一个 n 直接取:

function fibMemo(n, memo = new Map()) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, value);
  return value;
}

同一台机器上,每次从空表开始,fib(30)、fib(35)、fib(40) 分别约 0.0014、0.0013、0.0015 毫秒。每个 n 只算一次,总共 O(n) 次调用。fib(40) 从 813.51 毫秒降到 0.0015 毫秒,差五个数量级以上。0.0015 毫秒已经小到计时器快分辨不出来,实际值只当上限参考。

朴素递归

代码接近数学定义,最好读。代价是重叠子问题反复算,时间指数增长,栈深等于 n。适合 n 很小、子问题不重叠的场景。

记忆化递归

多一张表裁掉重复子树,时间降到线性。代价是额外内存和查表开销,栈深仍是 n,输入很深照样栈溢出。

记忆化把时间换成空间。状态到百万级时,Map 占很多内存,GC 压力也上来,这时要用有界缓存或自底向上递推。它也不减少栈深:处理一万层的树,即使每层只算一次,也会碰到栈上限,要么改成显式栈迭代,要么限制输入深度。

正则:一次匹配里的回溯

正则表达式(regular expression)是用符号描述字符串模式的工具,比如校验数字或日期格式。它写起来短,匹配过程不一定短。多数常见引擎,包括 V8 里的 Irregexp,用的是回溯式匹配。

回溯(backtracking)是匹配失败时的退路:引擎记住之前的分支点,失败就退回去换一种分法。分支少的时候没问题,分支互相嵌套时,尝试的组合数会爆炸。看一个刻意写坏的例子:

const re = /^(a+)+$/;
re.test('a'.repeat(24) + '!');   // 结尾不匹配,回溯开始

这个模式要求整串由 a 组成。输入是 24 个 a 再加一个感叹号,结尾不匹配,引擎就要尝试把 24 个 a 切成不同的组,组合数随长度指数增长。本机实测:20、22、24 个 a 分别约 5.5、21.3、85.2 毫秒,长度每加 2,时间约乘 4。同一段输入在不同轮次里会落到 85 到 96 毫秒,波动来自机器状态,但指数形状是稳定的。

改成 ^a+$,同样的输入约 0.023 毫秒,因为只有一条匹配路径,不需要回溯,差了大约四千倍。工程做法:不要给用户输入套嵌套量词,能用字符类和锚点就别用分组重复,避开 (a|aa)+,并限制输入长度。真需要处理不可信长文本,就换线性时间的引擎或手写扫描。Node 主线程被正则卡住,整个事件循环都会停,不是单个请求变慢,而是所有请求一起等。

隐式分配与垃圾回收

最后一类成本在内存分配和垃圾回收(GC,garbage collection,自动回收不再使用的对象)。分配很快,但多了以后 GC 要频繁判断对象是否存活,停顿会打断处理。

循环里每创建一个临时对象、数组、字符串,分配器都要找内存。单个便宜,一百万个就不便宜。本机创建 100 万个带 id 和 name 的对象放进数组,约 95.5 毫秒;100 万个纯数字约 15.3 毫秒,差了六倍。多出来的是对象头和字符串分配。

const rows = [];
for (let i = 0; i < n; i++) {
  rows.push({ id: i, name: 'u' + i });
}

这 95 毫秒里有对象分配、字符串拼接和数组增长。GC 停顿没有单独测,标未在本机实测;服务里这种分配会推高年轻代回收频率,表现为周期性抖动。风险不是单次慢,而是抖动叠在延迟敏感接口上。

常见隐式分配:map、filter、slice 每次返回新数组;展开运算符复制;闭包捕获变量;模板字符串拼接;JSON.parse 生成整棵对象树。这些不是错,错在热循环里反复做。减少分配的办法:循环外复用对象;用下标循环代替创建新数组的链式调用;累积时先 push 再 join;大批量处理分批,让 GC 在批次之间工作。

为什么实测和理论对不上

四类隐藏成本摆出来后,很多人照着理论优化,一测却发现没差别或结果反了。下面五个原因最常见。

第一,预热与 JIT(just-in-time,即时编译)。代码刚跑时由解释器执行,跑热才编译成优化机器码,前几次偏慢。本机 fibMemo 第一次约 0.0029 毫秒,重复几百次后稳定在 0.0008 毫秒,差三倍多。测量前要预热,但冷启动和稳定态要分开看。

第二,测量规模太小。固定开销、缓存命中、引擎快路径会占主导,真正的增长项还没显形。shift 在 1 万条时只花 0.35 毫秒,到 2 万条变成 350 毫秒;includes 在 2000 条时 2.88 毫秒,到 8000 条 49.30 毫秒。只测前一个规模,会得出完全相反的结论。

第三,计算被优化掉。结果没被使用时,编译器可能删掉整段纯计算,测出来接近零。本机试了 2000 万次求和循环,结果丢掉 10.79 毫秒,接进全局变量 11.08 毫秒,差别很小,说明这次 V8 没有删掉它;但别的引擎或写法不一定。判断办法是让结果可观察,比如写进全局变量或打印校验和。

function calc(n) {
  let sum = 0;
  for (let i = 0; i < n; i++) sum += i * i;
  return sum;
}
calc(20000000);                    // 结果丢掉
globalThis.sink = calc(20000000);  // 结果保留

第四,机器噪声。同样 fib(40),五次测量在 790 到 883 毫秒波动,约一成;fibMemo 在 0.0019 到 0.0030 毫秒,相对波动更大。CPU 降频、后台进程、GC 都会影响,单次值没有意义。

第五,只测了一次。单次测量分不清代码快和这一瞬间机器闲。相关错误还有把准备数据算进计时,或两次比较的不是同一个工作量。测量协议要固定:预热若干次,规模至少到毫秒级,每个规模跑 3 到 5 次取中位数,保留原始数据,让结果被使用,换一台机器复核。

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

下面这些现象在性能排查里很常见。先按表里的「第一步」定位,不要一上来就重写整个函数。

现象真实原因第一步查什么
单层循环,数据翻倍耗时约四倍循环体里的 shift、unshift 每轮搬移整段数组循环体里有哪些遍历或复制方法
两个列表比对越跑越慢嵌套 includes、indexOf 是 n 平方次比较是否可以先建 Set 或 Map
一万条很快,三万条突然超时规模跨过引擎快路径,隐藏的线性成本显形把测试数据放大到生产规模再测
同一段代码第二次跑快很多首次解析、JIT 预热和缓存填充是否预热,是否只测了第一次
两种写法测出来差不多规模太小,主要时间花在固定开销上单次工作量是否达到毫秒级
理论上很慢,实测却几乎不花时间结果没被使用,计算可能被优化掉结果是否被写出或校验
多次测量结果上下浮动CPU 降频、后台进程、GC 停顿等噪声看中位数和分布
递归在小数据正常,大一点栈溢出调用栈深度受限,本机约一万层递归深度是否随输入增长
简单正则偶尔卡住几秒嵌套量词触发指数级回溯模式里是否有 (a+)+ 这类结构

最容易误判的是第一行和第三行。第一行看起来像机器变慢,其实是算法从线性变成平方;第三行看起来像线上数据有问题,其实是测试规模没跨过阈值。判断时先列出每一轮做了什么,再问每个操作的成本。

边界与代价

看到隐藏成本,不等于要改掉所有平方级代码。复杂度描述增长趋势,不是绝对时间。n 等于 100 时,n 的平方只有一万次操作,是微秒级;这时把 includes 换成 Set,代码更难读,收益也看不见。要不要修看三个条件:输入会不会变大,代码在不在热路径,复杂度能不能降一个量级。三个都成立才值得动手。

代价是内存。记忆化、Set、缓存都用空间换时间。fib(40) 的表只有几十项,随便存;状态到百万级时,一张 Map 可能占几十兆,GC 压力也上来。这时要有界缓存,或改成不依赖表的递推。用空间换时间前,先想清楚空间上限。

递归还有可读性收益。树遍历、回溯搜索用递归写,通常比手写显式栈短,也更容易证明正确。只要深度可控,比如明确限制在几百层,栈开销可以接受。危险的是深度跟着用户输入走,比如解析不限层级的 JSON。这时限制深度比优化递归更重要。

正则也一样。固定格式、长度有上限的输入,回溯通常不会失控;把整段用户文本塞进复杂模式,就可能从微秒变成秒。不要为了少写几行,把不可信输入交给带嵌套量词的正则。

测量也有成本,不是每个函数都值得写微基准。先用性能分析工具找出热点,再对热点做针对性测量。复杂度分析给方向,实测给量级:先手算找出增长最快的部分,再确认它在你的数据规模上真成了瓶颈。只测不算容易被偶然快慢带偏;只算不测容易在常数上翻车。

当天能做的练习

  1. 写 shift 循环与下标循环,分别处理 1000、10000、20000、40000 个整数,各跑三次取中位数,找出突然变慢的规模区间。
  2. 实现朴素 fib 与记忆化 fib,测 30、35、40 三个输入,验证每加 5 时间约乘 11。
  3. 用 2000、4000、8000 个不重叠整数,比较嵌套 includes 与 Set 查找,解释两条曲线的形状。
  4. 用 ^(a+)+$ 测 20、22、24 个 a 加感叹号的耗时,再换成 ^a+$ 测同一输入,记录差距,并说明回溯发生在哪一步。
  5. 写 2000 万次求和循环,分别丢掉结果和写进全局变量,各测五次,判断计算有没有被优化掉;再对比只测第一次与预热后的数字。
环境说明:本文代码用 Node.js 24 在本机实际运行,规模与耗时与文中一致;正则、递归深度、内存分配几组数据也来自同一台机器。不同语言、不同引擎版本会改变具体数字和 shift 的快路径阈值,文中只用于比较量级和解释机制,不作为绝对性能承诺。

小结与组内回望

三句话收一下:一层循环不代表线性,要算清循环体里每个调用的内部成本;递归的代价是栈深和重复子问题,记忆化用空间换时间但不减少栈深;实测和理论对不上,通常是预热、规模、优化、噪声和单次测量在作怪。

组内回望:这一组从复杂度的记号出发,上一篇《常数与缓存命中率:为什么 O(n) 跑不过 O(n²)》讲的是同一个数量级里,常数和缓存命中率为什么能翻盘;这一篇再往下挖一层,说明常数本身也可能不是常数,而是藏在库函数、递归、正则和内存分配里的另一层 n。O 记号给的是增长方向,不是运行时间;看到同阶要比常数和局部性,看到不同阶也要先确认有没有隐藏的循环。

这是复杂度组的最后一篇。以后遇到「理论上应该很快」的代码,先按顺序问:循环体调了什么,递归重算了什么,正则回溯了什么,循环里分配了什么,再去测。多数问题在第一步就露头。