计算机原则五讲(六):没有免费的优化
这四条原则看起来分属数据结构、编译优化、组合数学与内存管理,但它们处理的是同一件事:代价守恒,只是分期方式不同。
- 空间换时间把计算成本提前付掉,换成使用时更便宜的「取」;
- JIT 把编译成本从启动时分摊到运行期,用预热换稳态吞吐;
- 鸽巢原理说明容量不够时重复是必然的,代价只能推迟,不能取消;
- 引用计数与 GC 决定释放成本是摊在每次赋值,还是集中在一个时刻。
四条合起来给出一条判断:没有免费的优化,只有换一种付法。 说某个方案「更快」而不说它把成本挪到了哪里,通常意味着那个地方还没被观测到。
flowchart LR
Q["一份成本<br/>总得有人付"] --> A["提前付:预计算 / 建表"]
Q --> B["运行时付:预热 / 编译"]
Q --> C["推迟付:扩容 / 稀释"]
Q --> D["分期付:每次赋值 / 集中扫描"]
A --> A2["空间换时间<br/>换来更快的取"]
B --> B2["JIT<br/>换来更高的稳态"]
C --> C2["鸽巢<br/>换来更大的容量"]
D --> D2["引用计数与 GC<br/>换来不同的停顿形状"]
下面四节各自独立,实跑与推算分开标注。
一、空间换时间
「空间换时间」(space-time tradeoff)不是某个人在某一年提出的单一理论,而是计算这门手艺里最古老的经验之一,线索能拉得很长。
查表法在没有计算机的年代就已存在:水手算航海位置要靠对数表,把对数预先算好印成册子,用时翻书而不是现场算。这是最朴素的空间换时间——一本书的纸张,换掉每次航行里的重复计算。哈希表在 1953 年由 IBM 的 Hans Peter Luhn 在内部备忘录里提出,用散列把键映射到数组下标,让查找从线性扫描变成一步定位。存储层次在 1960 年代成型,寄存器到缓存到主存到磁盘,每一层都是用靠近 CPU 的宝贵空间缓存下一层的常用数据。索引在 1970 年由 Bayer 与 McCreight 的 B 树给出:额外一份有序结构,把随机查找换成树上的少量跳转。
这四件事时代不同、层次不同,动作完全相同:先花一笔空间,把「算」变成「取」。
本质一句话:空间换时间是把反复要用的计算结果提前算好、就近存好,让每次使用只花「取」的力气,不花「算」的力气。
flowchart LR
T["同一个需求的两种做法"] --> A["每次现算<br/>空间占用小<br/>耗时随调用次数线性增长"]
T --> B["预计算加查表<br/>先付一笔建表成本<br/>之后每次只付一次访存"]
A --> A2["总成本 = 调用次数 × 单次现算"]
B --> B2["总成本 = 建表 + 调用次数 × 单次访存"]
A2 --> X["回本点:调用次数 > 建表成本 / 单次省下的时间"]
B2 --> X
本机实跑:建表贵、查表便宜
1 | 【1】判定 [2, 200000) 内全部素数(实测,两种做法结果一致) |
注意第二组里那行「回本所需查询次数:18」。这个数字改变了整件事的性质:同一个方案,查 18 次以上是优化,查 3 次就是浪费。 「用筛法比试除快」这句话之所以不完全对,就是因为它漏了这个条件。
第一组则给出了另一面:判定 2 到 20 万之间全部素数时,筛法快 60 倍。差别不在算法优劣,而在调用次数——这里查了 18 万次,建表成本被彻底摊薄。
落地形态在四个层次上都能找到:
- 语言层。Python 的
dict用开放寻址加紧凑数组,把「按 key 找值」从O(n)变成O(1),代价是每个键值对都占着一段不存数据的表空间。 - 数据库层。B 树索引把随机磁盘查找换成树上几次跳转,代价是索引文件本身要占空间,并且每次写入都要维护它。
- 系统层。页缓存把磁盘数据常驻内存,用内存换 I/O;预读把「下一次可能要用的块」提前搬进来,用带宽换延迟。
- 业务层。计数器、排行榜、物化视图,都是把「每次聚合」换成「每次读一个现成的数」。
边界与反例
- 写多读少时反噬。索引和缓存都假设读远多于写。若写入极频繁,每次写都要更新索引或失效缓存,维护成本会超过省下的查询时间——日志表、流水表通常刻意少建索引,就是这个道理。
- 新鲜度是隐形账单。缓存里的副本可能过期:缓存了用户资料,用户改完名,缓存没失效,就查到旧名字。你换来的时间,有一部分要用「保证一致」的复杂度去还。
- 空间本身稀缺时,买卖要反过来。数据量大到放不进内存时,人们反而用时间换空间:gzip 用 CPU 时间换存储,稀疏矩阵只存非零元,流式处理宁可重复算也不存全量。原则永远是双向的,方向由哪头更贵决定。
- 最坏情况不买账。哈希表平均
O(1),但恶意构造的键能全部撞进同一桶,退化成O(n),这就是 HashDoS 的由来;索引在选择性差的列上(比如性别)也形同虚设。空间花出去了、时间没换回来,是这条原则最典型的失败形态。
二、JIT 即时编译
JIT 的直系祖先是动态语言的实现者,因为只有他们非这么做不可——解释执行太慢,而静态编译又拿不到运行时的类型信息。
- 1984 年,Xerox PARC:Deutsch 与 Schiffman 的《Efficient Implementation of the Smalltalk-80 System》提出 dynamic translation,把字节码在运行时翻译成机器码。这是 JIT 作为透明优化手段的起点。
- 1987 到 1994 年,Self 语言:Ungar、Smith、Urs Hölzle、Chambers 等人做出完整形态的自适应优化。关键的 1994 年 PLDI 论文确立了今天所有 JIT 的核心机制:靠运行时类型反馈做优化决策,并允许优化失效后去优化回到安全状态。
- 1999 年,Java HotSpot VM:Sun 收购了 Self 与 Strongtalk 团队创办的 Animorphic,C1 加 C2 的分层编译由此进入工业主流。
- 2008 年,V8:早期干脆不做解释器,直接全量编译;2015 年引入 Ignition 加 TurboFan 组成分层与去优化骨架;2021 年又补上 Sparkplug 与 Maglev,形成四级阶梯。
- 同一条路线的其他成员:PyPy、LuaJIT、PHP 8.0、.NET RyuJIT,以及 WebAssembly 规范里的分层编译。
本质一句话:JIT 用运行期的真实信息换更激进的优化——代价是预热成本、内存占用与去优化抖动,收益是稳态吞吐;它把编译从一次性开销变成了一个持续的投资决策。
「持续的投资决策」这个说法是关键。AOT 编译只决定一次:编还是不编、优化到什么程度。JIT 则在运行中反复决定:这段代码值不值得编译、值不值得按当前类型特化、什么时候作废重来。它优化的是决策质量,付出的是决策成本。
flowchart TD
A["字节码 / 中间表示"] --> B["① 解释器 Ignition<br/>逐条分派执行<br/>启动最快 · 稳态最慢<br/>同时采集类型反馈与分支计数"]
B -->|"函数反复被调用<br/>超过阈值"| C["② 基线编译器 Sparkplug<br/>不做激进优化<br/>只把字节码快速翻译成机器码"]
C -->|"更热 · 反馈更充分"| D["③ 优化编译器 Maglev / TurboFan<br/>内联 · 类型特化 · 逃逸分析"]
D -->|"推测成立"| E["稳定机器码<br/>稳态吞吐最高"]
D -->|"推测失效:来了别的类型<br/>或对象形状变了"| B
E -->|"新形态出现,守卫失败"| B
本机实跑:三档模式的差距
1 | Node v22.22.2 / V8 12.4.254.21-node.39 |
三行数字给出一个很容易被低估的量级:同一段代码,纯解释执行比 JIT 全开慢 12.5 倍。 更有意思的是「单态调用」那一列:默认模式 24.9 亿次每秒,纯解释器 3691 万次每秒,差 67 倍。这个差距不是来自「翻译成机器码」本身,而来自类型特化:JIT 看到这个调用点一直只遇到一种形状,就把它内联成一次内存偏移;解释器每次都还要查表。
预热不是抽象的代价,它能被逐次测出来:
1 | 默认模式:同一个 work(4000) 连续调用 400 次,逐次单次耗时(µs,越小越快) |
1 | 各模式的冷启动差距(前 40 次均值 ÷ 第 200 次之后均值): |
逐次序列里有两个台阶值得看:第 7 次左右从 60 多微秒降到 37 微秒,是基线编译生效;第 19 到 21 次之间从 39 微秒掉到 4.7 微秒,是优化编译器接手。这两次跃迁之间,同一段代码的执行路径完全不同,而代码本身一个字都没改。
第二块表的 --no-opt 那行很说明问题:关闭优化编译器之后,冷热差只有 1.14 倍,也就是说大部分「冷热差」正是优化编译器带来的,而不是解释与编译的差别。
边界与反例
- JIT 对短命进程基本没有价值。编译器、CLI 工具、一次性脚本、批处理里的小任务,进程活不过预热期,付出的是纯成本。这也是 Go、Rust、C++ 在这类场景胜出的根本原因:AOT 不是更先进的编译,而是另一组取舍。
- 预热期就是尾延迟。服务刚发布、实例刚扩容、缓存刚失效时,请求正好落在还没优化的代码路径上,平均延迟好看,p99 难看。
- 去优化会造成性能断崖。一旦运行中出现新类型或新形状,优化代码被丢弃、回到解释器、重新预热。「通常很快」和「突然变慢」会在同一进程里交替出现,这在压测里常被误判为抖动。
- 内存成本是真实的。机器码、profile 数据、元数据,让 JIT 运行时的内存占用明显高于解释器。移动端与嵌入式设备上,这个成本经常比性能收益更关键。
- 它扩大了安全面。可写可执行内存带来 JIT spraying 这类攻击;推测执行侧信道也需要 JIT 生成的 gadget 才能发挥,很多运行时因此提供了关闭 JIT 的开关。
- 优化绝不能改变语义。浮点与
NaN的处理、对象身份比较、GC 可见性、eval与反射都会限制优化空间。如果某个优化会改变可观察行为,那它就不是优化,是 bug。
三、鸽巢原理
这条原理的正式提出者是 Peter Gustav Lejeune Dirichlet(狄利克雷),时间是 1834 年。他在研究用有理数逼近无理数时,需要一个「必然存在」的结论,不是「大概率存在」。他在论文里把它命名为 Schubfachprinzip,直译就是抽屉原理:如果把 n 件东西放进 m 个抽屉,且 n > m,那么至少有一个抽屉里放了不止一件东西。
本质一句话:鸽巢原理讲的是规模超过容量时,重复不是意外而是必然——它把「会不会撞」这个问题,变成了一道只有加减乘除的算术题。
flowchart TD
Q["我要判断会不会撞"] --> A{"东西数大于格子数?"}
A -->|"是"| B["必然有格子装不止一件<br/>纯计数,无需概率"]
A -->|"否"| C["可能不撞,也可能撞"]
C --> D{"格子数相对东西数<br/>有多宽裕"}
D -->|"刚好够"| E["撞的概率接近一半<br/>生日悖论区"]
D -->|"宽裕很多"| F["撞的概率很低<br/>但不等于零"]
B --> G["工程动作:预留空位<br/>设计冲突处理"]
E --> G
F --> H["工程动作:仍然要有冲突处理<br/>因为迟早会撞"]
本机实跑:从纯计数到概率
1 | 抽屉总数 : 365 |
1 | 人数 n | 理论 P(碰撞) | 实测频率 | 位数 |
第一组是原教旨版本:366 > 365,所以必然有抽屉装了 2 只以上,实测最大是 5 只。注意「≥ 2」和「实测 5」的差别,那是原理本身的信息边界——它只保证存在,不保证有几个。
第二组是它在概率上的延伸,也就是常说的生日悖论:23 个人就有超过一半的概率撞生日。这里的关键数字不是 23,而是 C(23,2) = 253——虽然只有 23 个人,但两两配对的组合有 253 对,而抽屉只有 365 个。比较的对象从来不是人数与抽屉数,而是配对数与抽屉数。
哈希表里的表现更贴近日常:
1 | 哈希桶数 = 1000,插入元素数 = 1000(负载因子正好 1.0) |
1 | 负载因子 | 平均链长 | 最长链长(2000 轮均值) | 相对 0.75 的查找成本 |
这两块解释了哈希表为什么普遍把负载因子卡在 0.75 左右:桶数和元素数相等时,仍有 37% 的桶是空的,同时又有 37% 的插入发生了碰撞。 「浪费三成空间」和「承受三成碰撞」同时成立,看起来矛盾,其实是同一件事的两面——空桶不是浪费,它是把碰撞概率压下去所付的价。而负载因子从 0.75 涨到 3.0,查找成本涨 2.29 倍,这就是「省空间」要交的钱。
这也解释了定向攻击为什么有效:
1 | 场景:哈希函数只取低位(m = 64 桶),攻击者提交 64 个精心构造的 key |
64 个元素全进一个桶,一次查找退化成遍历 64 个节点。鸽巢原理在这里没有教你「一定会撞」,它教你「攻击者可以决定撞在哪里」。 随机化哈希的作用就是把「撞在哪」变回不可控。
边界与反例
- 它只管有重复,不管重复几次。366 只鸽子放进 365 个抽屉,原理只保证至少有一个抽屉装 2 只以上,实测可能是 5。想要更强的结论得用广义鸽巢原理:n 件放 m 个抽屉,必有抽屉不少于
⌈n/m⌉件。 - 它不告诉你哪一对撞了。这是存在性证明的通病。工程上想定位冲突,只能靠记录与比对。
- 它假设格子是固定的。一旦格子能动态扩张(哈希表扩容、分片增加节点),冲突就可以被稀释——但扩容本身有成本,而且扩容只是把「必然撞」推迟到更大的规模,没有取消它。
- 拿它硬套会闹笑话。「50 个人里必有两人头发数相同」成立,因为头发数远小于 50 亿;「50 个人里必有两人身高相同」不成立,因为身高是连续量。「格子数有限」是前提,值域连续时这条原理要么不适用、要么得先量化精度。
- 它和随机是正交的。随机化能让单次碰撞概率可控,但消不掉必然性。正确姿势是双管齐下:用随机化哈希抵御定向攻击,用冲突处理(链地址、开放寻址、扩容)接住必然发生的那次碰撞。
- 它解释了唯一索引为什么不是银弹。唯一索引能防住重复,代价是插入时要查一次、冲突时要报错。把「不可能重复」换成「如果重复了怎么办」,正是因为按鸽巢原理,重复是迟早的事,只是这次撞在了业务键上,而不是哈希桶上。
四、引用计数与垃圾回收
很有意思的是,这两种方案诞生在同一年:1960 年。
引用计数:George E. Collins 在《A Method for Overlapping and Erasure of Lists》里提出,给每个对象记一个「有多少人在引用我」的计数,计数归零就释放。思路直观得像物理常识:没人拿着了,就可以扔了。追踪式 GC:同一年,John McCarthy 为 Lisp 实现 GC 时提出 mark-and-sweep,从一组确定的根(栈、寄存器、全局变量)出发,把所有能到达的对象标记一遍,没被标记的就是垃圾。
本质一句话:引用计数和追踪式 GC 回答的是同一个问题——这块内存还有用吗——但一个用「谁还引用我」这种局部信息来回答,另一个用「从根能不能到达」这种全局信息来回答;这个差异决定了一个没有停顿但有循环泄漏、另一个没有循环泄漏但有全局停顿。
flowchart LR
subgraph RC["引用计数:成本摊在每次赋值"]
A1["每次赋值 / 出作用域"] --> A2["计数 +1 / -1"]
A2 --> A3{"计数归零?"}
A3 -->|"是"| A4["立刻释放"]
A3 -->|"否"| A5["什么都不做"]
end
subgraph GC["追踪式 GC:成本集中在一个时刻"]
B1["平时分配"] --> B2["分配计数到阈值 / 内存吃紧"]
B2 --> B3["stop-the-world 扫描"]
B3 --> B4["标记:从根遍历可达对象"]
B4 --> B5["清除:回收不可达对象"]
end
style A4 fill:#e6ffe6,stroke:#009900
style B3 fill:#ffe6e6,stroke:#cc0000
本机实跑:确定性析构与循环死穴
1 | [1] 引用计数:对象一被引用就 +1,引用离开就 -1,归零即释放 |
1 | [3] 引用计数的死穴:循环引用,计数永远不为零 |
那 3.90 微秒是引用计数最值钱的性质:它把「什么时候释放」从一个不可控的时刻,变成一个可以写进代码因果链的时刻。 这正是 C++ 的 RAII 与 Swift 的 ARC 能成立的基础——析构时机可预测,就能拿它做资源管理(关文件、放锁、提交事务)。
而循环引用是它的结构性缺陷:计数是局部信息,两个对象互相引用时,各自的计数都不为零,但整体已经不可达。这不是实现不够聪明,是信息不足——局部信息无法判断全局可达性。
flowchart TD
N["新分配对象 → 进入 gen0"] --> Q{"活过一次 gen0 回收?"}
Q -->|"否,绝大多数"| D["直接回收"]
Q -->|"是,少数"| G1["晋升 gen1"]
G1 --> Q2{"活过一次 gen1 回收?"}
Q2 -->|"否"| D
Q2 -->|"是,更少"| G2["晋升 gen2 老年代"]
G2 --> S["此后很少被扫描<br/>只在 Full GC 时处理"]
style D fill:#f2f2f2,stroke:#888888
style G2 fill:#ffe6e6,stroke:#cc0000
追踪式 GC 的代价在暂停时间上,而暂停时间的形状很不一样:
1 | [4] 暂停时间:引用计数释放 vs GC 一次完整回收 |
同样的 60 万个节点,引用计数 16 ms,追踪式一次完整回收 144 ms,差 9 倍。但结论不能只读到这一层:引用计数那 16 ms 是分散在 60 万次 del 里的,单次约 27 纳秒,平稳;追踪式那 144 ms 是一次停顿,业务线程完全停下。两者总成本接近,形状完全不同——而在线服务里,形状往往比总量更重要。
1 | [5] 分代假说:绝大多数对象活不过第一代 |
分代回收是鸽巢原理的另一种形态:如果大多数对象很快死,就把扫描预算按存活概率分配。 gen0 扫了 366 次,gen2 一次没扫,这正是把「反复扫描全堆」换成「频繁扫小堆、偶尔扫大堆」。
1 | 语言 / 运行时 主机制 循环处理 补充 |
边界与反例
- 引用计数不是没有停顿,只是停顿分散。一次
del一个十万节点的树,照样有毫秒级卡顿。「无停顿」是相对追踪式的 stop-the-world 说的,不是绝对承诺。 - 追踪式的暂停也可能是假象。现代 JVM 的并发 GC(G1、ZGC)把大部分标记工作放在业务线程之外,暂停被压到毫秒甚至亚毫秒。「Java 一定有几百毫秒停顿」这个印象早已过时,选型要看具体收集器,不是看语言。
- 引用计数有计数溢出风险。32 位计数在极端场景下会回绕,一些实现为此在超大对象上改用 64 位或特殊处理。
- 循环不是唯一的麻烦,还有多线程下的原子计数。
+1/-1在多线程里必须原子,这个写屏障开销可能吃掉它相对追踪式的优势,这也是很多高并发运行时最终选追踪式加并发标记的原因。 - 分代假说不永远成立。如果程序大量分配长寿对象(比如启动期构建一个巨大缓存),分代策略会把大量对象搬来搬去,反而更慢。
- 别再问哪种更好,先问在优化什么。追求低延迟与可预测(实时系统、游戏引擎、音频处理),偏向引用计数或低停顿 GC;追求高吞吐(批处理、Web 后端),偏向分代加并发。同一个语言的不同 GC 实现,服务的就是不同的目标函数。
五、横向对照
| 原则 | 把成本付在哪一刻 | 一句话判据 | 什么时候不成立 |
|---|---|---|---|
| 空间换时间 | 提前付:预计算与建表 | 调用次数能否过回本点 | 写多读少,或散列不均匀 |
| JIT | 运行中付:预热与重编译 | 进程活得够久吗 | 短命进程,或形态频繁变化 |
| 鸽巢 | 推迟付:扩容与稀释 | 配对数与格子数的比 | 值域连续,或格子可动态扩张 |
| 引用计数与 GC | 分期付:每次赋值或集中扫描 | 要低延迟还是要高吞吐 | 循环引用,或长寿对象过多 |
四条合起来,其实是一张「成本去哪儿了」的对照表:
| 看到的收益 | 实际付掉的是 |
|---|---|
| 查表快 600 多倍 | 建表时间加 0.19 MiB 内存,且查询次数要够多 |
| JIT 稳态快 12 倍 | 前 40 次调用慢 7.3 倍,内存更高,还有去优化断崖 |
哈希表 O(1) |
37% 的空桶,以及一次必然发生的碰撞 |
| 引用计数无全局停顿 | 每次赋值的一次计数增减,加上循环引用的补充收集 |
这张表的用法很直接:下次看到「这个方案快多少倍」时,先问它把成本挪到哪一行。 挪到的地方如果正好是你的短板(内存、尾延迟、启动时间、写入频率),那这次优化对你就是负收益——尽管它在别人的场景里确实是优化。
🐾 收尾一句:性能没有免费的午餐,只有不同的分期方案;看清分期,才知道这笔账该不该借。
相关阅读:

