第 30 章：优化（Optimization）

原文：Robert Nystrom, Crafting Interpreters, Chapter 30。原书以 CC BY-NC-SA 4.0 协议发布；本译文用于学习与研究。

傍晚是一天中最好的时刻。一天的工作已经完成，现在可以把脚搁起来，好好享受。

Kazuo Ishiguro，《长日将尽》

若作者仍住在新奥尔良，会把本章称为 lagniappe：商家赠给顾客的一点额外礼物。你已经有整本书和完整 VM；这里继续玩 clox，目标纯粹是性能。两项风格截然不同的优化会展示如何测量并改进语言实现，乃至任何程序的性能。

30.1 测量性能（Measuring Performance）

优化是在不改变程序行为的前提下，降低资源消耗。通常关心运行速度，也可能关心内存、启动时间、持久化体积或网络带宽；所有物理资源都有代价，哪怕代价主要是浪费人的时间。

早期计算机时代，优秀程序员或许能在脑中容纳整套硬件架构与编译流水线，仅凭思考推断程序性能。如今微码、缓存行、分支预测、深流水线与巨型指令集早已让这成为过去。我们常说 C 是“低层语言”，但从下列语句到屏幕出现问候语之间，技术栈已经高得惊人：

printf("Hello, world!");

今天的优化是实证科学。不同 Lox 程序压测 VM 的不同部位，不同硬件也各有强弱；不能假定某项优化会让所有程序在所有机器上变快。应先观察性能、找出阻碍，再寻找更快路径。

30.1.1 基准（Benchmarks）

测试验证正确性，固定语义并防止新功能破坏旧行为；基准则是刻意压测实现某一部分、测量耗时而不是程序结果的 Lox 程序。它回答两件事：优化究竟有没有提速、提速多少？以后不相关的改动是否使性能退化？优化前后测试应完全一致，基准最好更快。

完整基准套件还能告诉你不同代码类型的得失。某些基准变快、另一些变慢时，必须做艰难取舍。基准套件本身编码了你的性能优先级，就像测试编码正确性定义；要慎选，并定期反思它是否仍服务于大目标。

JavaScript VM 早期的 SunSpider 曾被浏览器营销广泛使用，强力诱使实现者为其优化；可它多是快速完成的微基准，不能代表真实 JS，还惩罚启动慢但会在热点路径重编译后大幅提速的复杂 JIT。V8 的 Octane 更接近当时的真实代码，但多年后也过时了。最终目标是让用户程序变快，基准只是代理。

基准是一门细致技艺：既不能过度拟合实现，又要真正覆盖关心路径；还要补偿 CPU 降频、缓存与 OS 噪声带来的方差。它和测试一样，会随着练习进步。

30.1.2 剖析（Profiling）

假定算法与数据结构已合理。把巨大无序数组的线性搜索换成哈希表，与其说是优化，不如说是良好软件工程。硬件过于复杂，不能从第一性原理推导性能，因此需要剖析器：运行程序时跟踪硬件资源使用。简单剖析器展示各函数耗时；高级工具还记录数据/指令缓存未命中、分支预测失败、内存分配等。

这里剖析的是执行某个 Lox 脚本的 Lox VM 本身，不是脚本内各 Lox 函数；后者需另写 Lox profiler。任何平台都值得熟悉一个剖析器，它常能在几分钟内发现试错数天才会找到的问题。

30.2 更快的哈希表探测（Faster Hash Table Probing）

先做一个极小却收益惊人的改动。动态语言用户代码大量执行字段访问与方法调用，因而写一个压测字段、方法及哈希表的程序。它在循环中调用六个方法、累积并打印结果；累积值确保 VM 必须执行计算，避免较聪明编译器把无用计算完全消除。

class Zoo {
  init() {
    this.aardvark = 1; this.baboon = 1; this.cat = 1;
    this.donkey = 1; this.elephant = 1; this.fox = 1;
  }
  ant() { return this.aardvark; } banana() { return this.baboon; }
  tuna() { return this.cat; } hay() { return this.donkey; }
  grass() { return this.elephant; } mouse() { return this.fox; }
}
var zoo = Zoo();
var sum = 0;
var start = clock();
while (sum < 100000000) {
  sum = sum + zoo.ant() + zoo.banana() + zoo.tuna()
            + zoo.hay() + zoo.grass() + zoo.mouse();
}
print clock() - start;
print sum;

该程序本身没有实用目的，只是重复触发关心的字段和方法访问，并填入若干键，再用大循环给剖析器足够样本。真正测试哈希表应覆盖不同大小的更多表；此处六个键甚至未超过表的最小八项阈值，只是为避免示例臃肿。

作者剖析后发现 run() 的包含时间最多，理所当然；其内部 OP_GET_GLOBAL 占 17%、OP_GET_PROPERTY 占 12%、OP_INVOKE 高达 42%。但它们几乎都耗在同一个 tableGet()：它占总执行时间的 72%。动态语言确实会频繁做哈希查找，但这个比例仍令人意外。

30.2.1 缓慢的键环绕（Slow key wrapping）

tableGet() 主要包装了真正搜索的 findEntry()：

static Entry* findEntry(Entry* entries, int capacity, ObjString* key) {
  uint32_t index = key->hash % capacity;
  Entry* tombstone = NULL;
  for (;;) {
    Entry* entry = &entries[index];
    if (entry->key == NULL) {
      if (IS_NIL(entry->value)) return tombstone != NULL ? tombstone : entry;
      if (tombstone == NULL) tombstone = entry;
    } else if (entry->key == key) {
      return entry;
    }
    index = (index + 1) % capacity;
  }
}

在作者机器上，VM 总时间约 70% 花在第一行的 %。问题不是解引用，而是模除；x86 上除法/取模约比加减慢 30 到 50 倍。一般不可能比 CPU 自己更快地重做基本运算，但这里知道 CPU 不知道的事实：表从 8 项开始，每次翻倍，容量永远是 2 的幂。

对 2 的幂取模可用位掩码。229 % 64 == 37，而 229 & 63 == 37；64 - 1 的低位全为 1，正好保留被除数的低位：

uint32_t index = key->hash & (capacity - 1);
// 线性探测绕回：
index = (index + 1) & (capacity - 1);

同样修改字符串驻留查找 tableFindString() 的初始索引与绕回。存掩码而非容量可省去减一，但作者测试未见收益；流水线可能让该操作几乎免费。

把基准改成固定十秒、统计完成多少批 10,000 次调用：优化前为 3,192 批，之后为 6,249 批，几乎翻倍。字段、方法与全局变量普遍存在，故这项微小优化惠及几乎所有 Lox 程序。

这并不意味着模运算邪恶，或微优化总是关键；这样的窄而有效的解法罕见。重点是：不是直觉，而是 profiler 告诉我们 % 是问题。优化后再剖析，tableGet() 从 72% 降至 35%，既验证加速，也验证加速发生在预期位置。剖析器既能发现问题，也能验证方案。

30.3 NaN boxing（NaN Boxing）

下一项优化更微妙，效果分散在 VM 各处；profiler 不会直接指出它，而是来自对机器底层表示的思考。它也叫 NaN tagging；作者更喜欢后者，因为 boxing 容易使人联想堆分配，不过前者更通用。此技巧改变 VM 的值表示。

64 位机器上，原 Value 是类型标签加联合体，指针和 double 都有 8 字节。为让联合体按 8 字节对齐，编译器在标签后填充，使 Value 占 16 字节：

缩至 8 字节的直接内存收益未必巨大，但能让更多 Value 落进缓存行，减少缓存未命中并提升速度。问题是动态类型值既要存载荷，又要在运行时存类型；双精度数本已占满 8 字节，额外类型位在哪里？

30.3.1 什么是数，什么不是数（What is and is not a number?）

几乎所有机器都用 IEEE 754 表示双精度浮点数：低 52 位是尾数/有效数，接着 11 位是指数，最高位是正负号。

当指数位全为 1，值不再是普通超大数，而是 NaN。最高尾数位为 0 的称 signalling NaN，可能代表除零等错误；为 1 的是 quiet NaN，较安全但不表示有用数字。避开 Intel 的一个特殊 QNaN 后，quiet NaN 留下 51 个可任意使用的位，即 2,251,799,813,685,248 种模式：

51 位足以为 nil、true、false 留标签。对象指针表面是 64 位，但常见架构实际只用低 48 位地址，高 16 位未使用或为零；48 位可寻址 262,144 GB，进程又各有地址空间。因此 51 位装下指针仍有 3 位可用。

这就是 NaN boxing：一个 64 位字同时表示正常浮点数、对象指针或少量哨兵值，值内存减半。数值无需转换，Lox number 就是普通 double 位模式；其他值则通过几个宏包装和拆包。

30.3.2 条件支持（Conditional support）

此优化依赖浮点与指针的低层假设，虽很可能适用于常见 CPU，却不能绝对保证。因此保留旧 tagged union 和新表示，以编译期开关选择：

#define NAN_BOXING

#ifdef NAN_BOXING
typedef uint64_t Value;
#else
// 原有 ValueType + union 表示。
#endif

选择 uint64_t 是因为其他宏需要位运算；VM 的其他部分无需关心表示。下面的宏替换都在 #ifdef NAN_BOXING 分支内，未启用时仍使用原实现。

30.3.3 数字（Numbers）

数字的位模式完全不变，只需让 C 把同一组位在 double 与 uint64_t 间解释，即 type punning。严格别名规则令“用不同类型指针访问同一对象”的技巧不可靠；可移植的 memcpy() 形式看似昂贵，主流编译器会识别并完全消除它：

static Value numToValue(double num) {
  Value value;
  memcpy(&value, &num, sizeof(double));
  return value;
}
static double valueToNum(Value value) {
  double num;
  memcpy(&num, &value, sizeof(Value));
  return num;
}
#define NUMBER_VAL(num) numToValue(num)
#define AS_NUMBER(value) valueToNum(value)

若编译器不能消除 memcpy()，可改用含 uint64_t bits; double num; 的 union，但规范层面的保证更弱。需要 #include <string.h>。

非数字值由特定 quiet NaN 模式表示，因此遮住 quiet-NaN 位后若全部为 1，便是保留的非数值编码；否则视为数字。实际算术产生的 NaN 理论上可能碰撞，作者多架构测试未见此事：

#define QNAN ((uint64_t)0x7ffc000000000000)
#define IS_NUMBER(value) (((value) & QNAN) != QNAN)

30.3.4 nil、true 与 false

三个单例仅需三种位模式。取未用尾数空间最低两位作 tag，QNAN | TAG_NIL 表示 nil，相等比较即可判断。true、false 同理：

#define TAG_NIL   1
#define TAG_FALSE 2
#define TAG_TRUE  3
#define NIL_VAL   ((Value)(uint64_t)(QNAN | TAG_NIL))
#define FALSE_VAL ((Value)(uint64_t)(QNAN | TAG_FALSE))
#define TRUE_VAL  ((Value)(uint64_t)(QNAN | TAG_TRUE))
#define BOOL_VAL(b) ((b) ? TRUE_VAL : FALSE_VAL)
#define IS_NIL(value) ((value) == NIL_VAL)
#define AS_BOOL(value) ((value) == TRUE_VAL)
#define IS_BOOL(value) (((value) | 1) == TRUE_VAL)

IS_BOOL 不能写为 v == TRUE_VAL || v == FALSE_VAL，因为宏会两次求值 v，若表达式有副作用则出错。| 1 会把 false 变为 true，true 保持 true，其他值仍不等于 true，故仅求值一次。

30.3.5 对象（Objects）

对象指针有大量可能值，既要保存地址又要标识类型。单例 tag 所在低位被指针占用；改用 NaN 的符号位：quiet NaN 且符号位为 1 即对象，剩余低位存 Obj*。对象通常 8 字节对齐，最低三位本可另作 pointer tagging，但这里未采用。

#define SIGN_BIT ((uint64_t)0x8000000000000000)
#define OBJ_VAL(obj) (Value)(SIGN_BIT | QNAN | (uint64_t)(uintptr_t)(obj))
#define AS_OBJ(value) ((Obj*)(uintptr_t)((value) & ~(SIGN_BIT | QNAN)))
#define IS_OBJ(value) (((value) & (QNAN | SIGN_BIT)) == (QNAN | SIGN_BIT))

该做法假定指针高 16 位未用。它可能超出语言规范的严格边界；优化有风险也有收益，应由实现者决定是否值得。

30.3.6 Value 函数（Value functions）

printValue() 不能再 switch 显式类型枚举，改为 IS_BOOL、IS_NIL、IS_NUMBER、IS_OBJ 逐个检查；相对于真正写流的成本，这点额外判断可忽略。

相等性看似只需比较两个 uint64_t：单例各自唯一，对象使用身份比较，都正确。数值几乎也正确，但 IEEE 754 要求 NaN 不等于自身：

var nan = 0 / 0;
print nan == nan; // false

旧 union 中 double == double 自然满足该规则；新表示若直接比位则会错误。因此可在位相等后再判断是否为数字 NaN：

bool valuesEqual(Value a, Value b) {
  if (IS_NUMBER(a) && IS_NUMBER(b)) return AS_NUMBER(a) == AS_NUMBER(b);
  return a == b;
}

这会在每次相等比较中增加类型测试。若愿以兼容性换性能可省略；书中也指出 jlox 因 Java boxing 的 equals() 路径已经处理错 NaN 相等性。

30.3.7 评估性能（Evaluating performance）

哈希表优化有明确热点；值表示的影响却因宏内联而弥散在整个代码库，尤其在优化构建中难被 profiler 归因。必须剖析和基准测试release构建，调试构建的热点可能会被编译器内联等优化消掉。

更小的 Value 减少全局缓存未命中，但效果取决于被执行 Lox 程序的内存形态，甚至分配器给出的地址；额外位运算也可能抵消收益。需要由接近真实应用的大型基准套件评估整体效果。作者的若干较大 Lox 程序在其机器上整体约快 10%。这不如哈希表优化震撼，却是值得理解的性能工作类型；若简单收益已用尽，才应认真考虑调优值表示。

30.4 接下来去哪里（Where to Next）

Lox 与两个解释器在此收束。绝大多数读者不会以编译器为职业，这没有关系：仍会使用编译器，而本书应已让你更理解常用语言的设计与实现。你还练习了关键数据结构、低层剖析与优化，它们在任何领域都有用。很多问题也可从“语言”角度看：报表生成器或许是执行栈式指令，UI 渲染则很像遍历 AST。软件工程奖励兴趣广泛的人。

若想继续深入，可选择这些方向：

1. 单趟编译器迫使本书主要做运行时优化；成熟实现更重视编译期优化。阅读编译器经典教材，重建 clox 或 jlox 前端，引入中间表示和优化 pass；或为 Lox 加静态类型与检查器。
2. 若偏好精确性，深入解析理论、类型系统、语义与形式逻辑；这也会训练阅读计算机科学论文的能力。
3. 若只是热爱造语言，把 Lox 变成自己的玩具：改语法、增删功能、加入优化。书本文字受版权保护，但 jlox/clox 代码使用宽松 MIT 协议，可自由取用。若大改语言，最好改名，避免混淆 “Lox” 的含义。若希望别人使用，还要投入文档、示例、工具与库，并面对语言生态的竞争与推广工作。

也可以就此止步。最重要的是：编程语言起初也许令你畏惧，但这些章节证明，再难的材料只要亲手实践、一步一步推进，普通人也能掌握。能处理编译器和解释器，便能处理想做的任何事。

挑战（Challenges）

1. 启动 profiler，运行若干基准，寻找 VM 的其他热点。运行时还有哪些地方可改进？
2. 真实程序常有一两个字符的短字符串。多数不驻留字符串的 VM 若为每个小字符串分配字符数组、再用指针表示它，会很浪费，指针甚至比字符大。以 clox 原 tagged union 为起点，实现将小字符串字符内联进 Value 的专门表示，写相关基准并评估收益。
3. 回顾本书学习体验：哪些部分有效，哪些无效？自底向上还是自顶向下更易学？插图与比喻是帮助还是干扰？理解自己的学习风格，才能更有效地把知识装进脑中，并主动选择适合自己的材料。