优化

一天中最美好的时刻莫过于夜晚。你已经完成了当天的工作，现在可以放松身心，享受它了。

石黑一雄，《长日将尽》

如果我还住在新奥尔良，我会把本章称为“lagniappe”，即额外赠送给顾客的小东西。你已经拥有了一整本书和一个完整的虚拟机，但我希望你能在 clox 上进行更多有趣的编程。这次，我们将追求纯粹的性能。我们将对虚拟机应用两种截然不同的优化。在此过程中，你将对度量和改进语言实现（或任何程序）的性能有一个直观的感受。

30 . 1性能度量

优化是指对一个工作应用程序进行性能改进。一个优化的程序会做同样的事情，只是它需要更少的资源来完成。我们通常在优化时考虑的资源是运行时速度，但减少内存使用量、启动时间、持久存储大小或网络带宽也很重要。所有物理资源都有成本（即使成本主要体现在浪费的人力时间），因此优化工作通常能带来回报。

在计算机发展的早期，一个熟练的程序员可以将整个硬件体系结构和编译器管道牢记在心，并且可以通过认真思考来理解程序的性能。那些日子早已一去不复返了，如今微代码、缓存行、分支预测、深度编译管道和庞大的指令集将它们与现在隔开了。我们喜欢假装 C 是一种“底层”语言，但从

printf("Hello, world!");

到屏幕上显示问候语之间的那层技术栈现在已经高耸入云了。

如今，优化是一门经验科学。我们的程序就像一只边境牧羊犬，在硬件的障碍课程中疾驰。如果我们想让它更快地到达终点，我们不能只是坐着冥思苦想犬类生理学，直到顿悟降临。相反，我们需要观察它的性能，看看它在哪里绊倒，然后找到更快路径供它通行。

就像敏捷训练针对的是特定的犬只和障碍课程，我们不能假设我们的虚拟机优化将使所有 Lox 程序在所有硬件上运行更快。不同的 Lox 程序会对 VM 的不同部分施加压力，不同的体系结构有其自身的优缺点。

30 . 1 . 1基准测试

当我们添加新功能时，我们会通过编写测试来验证正确性（即使用某个功能并验证 VM 行为的 Lox 程序）。测试确定了语义，并确保我们在添加新功能时不会破坏现有的功能。我们在性能方面也拥有类似的需求。

1. 我们如何验证优化确实提高了性能，并且提高了多少？

2. 我们如何确保其他无关的更改不会降低性能？

我们用来完成这些目标的 Lox 程序是基准测试。这些程序经过精心设计，可以对语言实现的某些部分施加压力。它们衡量的是程序做什么，而是完成这些操作需要花费多少时间。

通过测量更改前后基准测试的性能，你可以看到更改的结果。当你完成优化时，所有测试都应该与之前表现完全相同，但希望基准测试运行得更快。

一旦你拥有了一整套基准测试，你就可以衡量优化不仅会改变性能，还会改变哪些类型的代码。通常你会发现，一些基准测试变得更快，而另一些则变慢。然后你必须做出艰难的决定，即你的语言实现要针对哪些类型的代码进行优化。

你选择编写的基准测试套件是该决策的关键部分。就像你的测试将你对正确行为的理解编码起来一样，你的基准测试是你对性能优先级的体现。它们将指导你实现哪些优化，因此要谨慎选择基准测试，并且不要忘记定期反思它们是否在帮助你实现更大的目标。

基准测试是一门微妙的艺术。就像测试一样，你需要平衡不要过度拟合你的实现，同时也要确保基准测试确实会触及你关心的代码路径。当你测量性能时，你需要补偿 CPU 节流、缓存和其他奇怪的硬件和操作系统怪癖造成的差异。我在这里不会对你进行长篇大论，但要将基准测试视为一项随着实践而提升的技能。

30 . 1 . 2性能分析

好吧，你现在已经有一些基准测试了。你想让它们运行得更快。现在怎么办？首先，假设你已经完成了所有显而易见、简单的工作。你正在使用正确的算法和数据结构，或者至少没有使用明显错误的算法和数据结构。我不认为使用哈希表而不是线性搜索一个巨大的无序数组是“优化”，更像是“良好的软件工程”。

由于硬件过于复杂，我们无法从第一性原理推断程序的性能，因此我们必须进行实地考察。这意味着性能分析。性能分析器（如果你从未使用过）是一个工具，它会运行你的程序，并在代码执行时跟踪硬件资源使用情况。简单的性能分析器会显示你在程序中的每个函数中花费了多少时间。复杂的性能分析器会记录数据缓存未命中、指令缓存未命中、分支预测错误、内存分配以及各种其他指标。

各种操作系统和语言都提供了许多性能分析器。无论你使用什么平台进行编程，都值得熟悉一个不错的性能分析器。你不需要成为大师。我在将程序扔给性能分析器几分钟内就学到了东西，而这些东西如果通过试错的方式来发现，可能需要我花费数天时间。性能分析器是神奇的工具。

30 . 2更快的哈希表探测

少说废话，让我们让一些性能图表向上向右走。事实证明，我们将进行的第一个优化是我们可以对 VM 做出的最微不足道的改变。

当我第一次让 clox 继承的字节码虚拟机运行起来时，我做了任何一个自尊自重的 VM 黑客都会做的事情。我草草拼凑了一些基准测试，启动了性能分析器，然后通过我的解释器运行这些脚本。在像 Lox 这样的动态类型语言中，用户代码中很大一部分是字段访问和方法调用，因此我的一个基准测试看起来像这样

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;

如果你以前从未见过基准测试，这可能看起来很荒谬。这里发生了什么？该程序本身并不打算做任何有用的事情。它所做的是调用大量的方法并访问大量字段，因为这些是我们要关注的语言部分。字段和方法位于哈希表中，因此它会谨慎地在这些表中填充至少几个有趣的键。所有这些都包装在一个大循环中，以确保我们的性能分析器有足够的执行时间来深入分析并了解周期在哪里流逝。

在我告诉你我的性能分析器显示了什么之前，花一分钟时间猜一猜。你认为 clox 代码库中的哪个函数占用了大部分执行时间？我们之前在章节中编写的代码中，你怀疑哪些代码特别慢？

我发现：当然，包含时间最多的函数是run()。（包含时间是指某个函数及其所有调用函数中花费的总时间，即从你进入该函数到它返回之间的总时间。）由于run() 是主要的字节码执行循环，因此它驱动着所有其他部分。

在run() 内，在字节码开关中的各种情况下都散布着少量的执行时间，用于常见的指令，例如OP_POP、OP_RETURN 和OP_ADD。最繁重的指令是OP_GET_GLOBAL，占执行时间的 17%，OP_GET_PROPERTY 占 12%，而OP_INVOKE 占了惊人的 42% 的总运行时间。

所以我们有三个热点需要优化？实际上，并没有。因为事实证明，这三条指令几乎所有时间都花在了调用同一个函数上：tableGet()。这个函数占用了整个执行时间的 72%（同样是包含的）。现在，在动态类型语言中，我们预计会花费大量时间在哈希表中查找内容—这算是动态性的代价。但是，仍然，哇。

30 . 2 . 1缓慢的密钥包装

如果你看一下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)) {
        // Empty entry.
        return tombstone != NULL ? tombstone : entry;
      } else {
        // We found a tombstone.
        if (tombstone == NULL) tombstone = entry;
      }
    } else if (entry->key == key) {
      // We found the key.
      return entry;
    }

    index = (index + 1) % capacity;
  }
}

在运行之前的基准测试—至少在我的机器上—虚拟机花费了 70% 的总执行时间在一个函数中的一行上。你能猜到是哪一行吗？不知道？就是这一行

  uint32_t index = key->hash % capacity;

指针解引用不是问题。是那个小%。事实证明，取模运算符非常慢。比其他算术运算符慢得多。我们能做点什么来改善吗？

一般来说，用用户代码重新实现基本算术运算符，使其比 CPU 本身能够做到的更快，实际上非常困难。毕竟，我们的 C 代码最终会编译成 CPU 自己的算术运算。如果有我们可以用来加快速度的技巧，芯片早就已经在使用它们了。

然而，我们可以利用这样一个事实，即我们对自己的问题比 CPU 更了解。我们在这里使用取模运算来获取密钥字符串的哈希码，并将其包装以适应表格的条目数组的范围。这个数组最初有八个元素，每次增长两倍。我们知道—而 CPU 和 C 编译器不知道—我们的表格的大小总是 2 的幂。

因为我们是聪明的比特玩弄者，我们知道一种更快的方法来计算一个数字对 2 的幂取模的余数：**位掩码**。假设我们要计算 229 对 64 取模。答案是 37，在十进制中并不明显，但在你将这些数字以二进制形式查看时就更加清晰了

在插图的左侧，注意结果 (37) 只是被除数 (229) 去掉了最高两位？这两个最高位是位于除数的单个 1 位的左边或与其相邻的位。

在右侧，我们通过将 229 与 63 进行按位AND运算来得到相同的结果，63 比我们最初的 2 的幂除数小 1。从 2 的幂中减去 1 会给你一系列 1 位。这正是我们需要用来去除这两个最左侧位的掩码。

换句话说，你可以通过简单地将一个数字与那个 2 的幂减 1 进行AND运算来计算它对任何 2 的幂取模的结果。我并不是一个足够优秀的数学家来向你证明这一点，但如果你仔细思考，它应该是合理的。我们可以用一个非常快的减法和按位AND运算来替换那个缓慢的取模运算符。我们只需将那段有问题的代码更改为以下代码

static Entry* findEntry(Entry* entries, int capacity,
                        ObjString* key) {

  uint32_t index = key->hash & (capacity - 1);

  Entry* tombstone = NULL;

CPU 喜欢按位运算符，所以很难改进它。

我们的线性探测搜索可能需要绕过数组的末尾，因此findEntry()中还有一个取模运算来更新。

      // We found the key.
      return entry;
    }

    index = (index + 1) & (capacity - 1);

  }

这一行没有显示在探查器中，因为大多数搜索都不会绕过。

findEntry()函数有一个姊妹函数tableFindString()，它对字符串进行哈希表查找，用于字符串驻留。我们也可以在那里应用相同的优化。这个函数只在进行字符串驻留时调用，我们的基准测试并没有对它进行大量的压力测试。但是，一个创建大量字符串的 Lox 程序可能会明显受益于这种改变。

  if (table->count == 0) return NULL;

  uint32_t index = hash & (table->capacity - 1);

  for (;;) {
    Entry* entry = &table->entries[index];

以及线性探测绕过数组末尾时。

      return entry->key;
    }

    index = (index + 1) & (table->capacity - 1);

  }

让我们看看我们的修复是否值得。我调整了那个动物园基准测试，让它统计在十秒钟内可以运行多少个包含 10,000 次调用的批次。更多的批次意味着更快的性能。在我的机器上使用未优化的代码，基准测试可以完成 3,192 个批次。经过这种优化之后，它跃升到了 6,249 个批次。

这几乎是相同时间内完成的工作量的两倍。我们让虚拟机的速度提高了两倍（通常的警告：在该基准测试上）。在优化方面，这是一个巨大的胜利。通常情况下，如果你能在这里或那里争取到几个百分点，你会感觉很好。由于方法、字段和全局变量在 Lox 程序中非常普遍，这个微小的优化提高了整个程序的性能。几乎每个 Lox 程序都将从中受益。

现在，这一节的重点不是取模运算符非常邪恶，你应该从你编写的每个程序中清除它。也不是说微优化是一项至关重要的工程技能。很少有性能问题有如此狭窄而有效的解决方案。我们很幸运。

重点是，我们并不知道取模运算符是性能瓶颈，直到我们的探查器告诉我们。如果我们盲目地在虚拟机的代码库中漫游，猜测热点，我们可能不会注意到它。我希望你能从中学到的是，在你的工具箱中拥有探查器是多么重要。

为了加强这一点，让我们继续在现在已经优化的虚拟机中运行原始基准测试，看看探查器显示了什么。在我的机器上，tableGet()仍然是执行时间相当大的一部分。对于动态类型语言来说，这是可以预料的。但是，它已经从总执行时间的 72% 下降到了 35%。这更符合我们希望看到的结果，也表明我们的优化不仅使程序更快，而且使程序以我们期望的方式更快。探查器对于验证解决方案和发现问题一样有用。

30 . 3NaN 装箱

下一个优化感觉非常不同。谢天谢地，尽管名字奇怪，它并不涉及打你的祖母。它不同，但并不，就像，那么不同。在我们的上一个优化中，探查器告诉我们问题出在哪里，我们只需运用一些巧妙的方法来想出一个解决方案。

这种优化更加微妙，它的性能影响更分散在虚拟机中。探查器不会帮助我们想出这个方法。相反，它是某人深入思考机器架构的最低级别而发明的。

正如标题所说，这种优化被称为 **NaN 装箱**，有时也称为 **NaN 标记**。我个人更喜欢后一个名字，因为“装箱”往往意味着某种堆分配的表示，但前者似乎是使用更广泛的术语。这种技术改变了我们在虚拟机中表示值的方式。

在 64 位机器上，我们的 Value 类型占用了 16 个字节。该结构有两个字段，一个类型标签和一个用于有效载荷的联合体。联合体中最大的字段是 Obj 指针和 double，它们都是 8 个字节。为了使联合体字段与 8 字节边界对齐，编译器在标签之后也会添加填充

这相当大。如果我们能将其缩小，那么虚拟机就可以在相同数量的内存中打包更多的值。如今，大多数计算机都有大量的 RAM，因此直接的内存节省并不是什么大问题。但是，更小的表示意味着更多的 Value 可以容纳在一个高速缓存行中。这意味着更少的高速缓存未命中，这会影响速度。

如果 Value 需要与它们最大的有效载荷大小对齐，并且 Lox 数字或 Obj 指针需要完整的 8 个字节，我们怎样才能缩小呢？在像 Lox 这样的动态类型语言中，每个值不仅需要携带它的有效载荷，还需要携带足够的信息来确定该值的类型，以便在运行时使用。如果 Lox 数字已经使用了完整的 8 个字节，我们可以在哪里偷偷地塞入几个额外的位来告诉运行时“这是一个数字”？

这是动态语言黑客们经常遇到的问题之一。它特别困扰他们，因为静态类型语言通常没有这个问题。每个值的类型在编译时就已经知道，因此在运行时不需要额外的内存来跟踪它。当你的 C 编译器编译一个 32 位整数时，生成的变量将获得正好 32 位的存储空间。

动态语言的人讨厌输给静态阵营，因此他们想出了许多非常巧妙的方法将类型信息和有效载荷打包到少量位中。NaN 装箱就是其中之一。它特别适合像 JavaScript 和 Lua 这样的语言，这些语言中的所有数字都是双精度浮点数。Lox 也属于这种情况。

30 . 3 . 1什么是（以及不是什么）数字？

在我们开始优化之前，我们需要真正了解我们的朋友 CPU 是如何表示浮点数的。如今，几乎所有机器都使用相同的方案，该方案被编码在古老的卷轴IEEE 754中，凡人称之为“IEEE 浮点数运算标准”。

在你的计算机看来，一个64 位、双精度、IEEE 浮点数看起来像这样

• 从右边开始，前 52 位是 **分数**、**尾数** 或 **有效数字** 位。它们代表了数字的有效数字，以二进制整数的形式。

• 紧挨着它的是 11 个 **指数** 位。它们告诉你尾数相对于小数点（实际上是二进制点）移动了多远。

• 最高位是符号位，它指示数字是正数还是负数。

我知道这有点模糊，但这章不是对浮点表示的深入研究。如果你想知道指数和尾数如何协同工作，已经有比我写的更好的解释了。

对我们而言，重要的是规范中特别指定了一种特殊情况下的指数。当所有指数位都被设置时，它就不再表示一个非常大的数字，而是具有不同的含义。这些值是“非数字”（因此，NaN）值。它们表示无穷大或除以零的结果等概念。

任何指数位都被设置为 1 的双精度浮点数都是 NaN，无论尾数位如何。这意味着存在许多不同的 NaN 位模式。IEEE 754 将它们分为两类。最高尾数位为 0 的值称为信号 NaN，其他值为静默 NaN。信号 NaN 旨在作为错误计算的结果，例如除以零。当产生这些值之一时，芯片可能会检测到并完全中止程序。如果你试图读取它们，它们可能会自毁。

静默 NaN 应该是更安全的。它们不表示有用的数值，但至少在触摸它们时不会着火。

每个指数位都被设置为 1 且最高尾数位也被设置为 1 的双精度浮点数都是静默 NaN。这留下了 52 位未被考虑。我们将避免其中一位，这样我们就不会踩到 Intel 的“QNaN 浮点不定值”，只剩下 51 位。这些剩余的位可以是任何值。我们谈论的是 2,251,799,813,685,248 种独特的静默 NaN 位模式。

这意味着 64 位双精度浮点数有足够的空间来存储所有不同的数值浮点数，以及还有 51 位的空间，我们可以随意使用。这足以分配几个位模式来表示 Lox 的 nil、true 和 false 值。但是关于 Obj 指针呢？指针不需要完整的 64 位吗？

幸运的是，我们还有另外一个诀窍。是的，从技术上讲，在 64 位架构上的指针是 64 位的。但是，据我所知，没有哪种架构真正使用整个地址空间。相反，如今大多数广泛使用的芯片只使用最小的48 位。其余的 16 位要么未指定，要么总是为零。

如果我们有 51 位，我们可以塞入一个 48 位指针，还剩下 3 位。这 3 位足以存储微小的类型标签，以区分 nil、布尔值和 Obj 指针。

这就是 NaN 装箱。在一个 64 位双精度浮点数中，你可以存储所有不同的数值浮点数、一个指针，或几个其他特殊哨兵值。与我们当前的 Value 结构相比，内存使用量减少了一半，同时保留了所有精度。

这种表示的特别之处在于，无需将数值双精度浮点数转换为“装箱”形式。Lox 数字就是普通的 64 位双精度浮点数。我们仍然需要在使用它们之前检查它们的类型，因为 Lox 是动态类型的，但我们不需要进行任何位移或指针间接寻址才能从“值”变为“数字”。

当然，对于其他值类型，有一个转换步骤。但幸运的是，我们的虚拟机将从值到原始类型的机制隐藏在少数宏后面。重新编写这些宏以实现 NaN 装箱，虚拟机的其余部分应该可以正常工作。

30 . 3 . 2条件支持

我知道这种新的表示的细节在你脑海中还没有清晰。别担心，在我们完成实现的过程中，它们会逐渐清晰。在开始之前，我们将先构建一些编译时脚手架。

对于我们之前的优化，我们重写了之前运行缓慢的代码并宣布完成。这次略有不同。NaN 装箱依赖于芯片表示浮点数和指针的一些非常底层的细节。它可能适用于你可能遇到的大多数 CPU，但你永远无法完全确定。

如果我们的虚拟机只是因为其值表示而完全失去了对某一种架构的支持，那将很糟糕。为了避免这种情况，我们将继续支持 Value 的旧标记联合实现和新的 NaN 装箱形式。我们使用此标志在编译时选择我们想要的表示形式

#include <stdint.h>

#define NAN_BOXING

#define DEBUG_PRINT_CODE

如果定义了该标志，虚拟机将使用新的形式。否则，它将恢复到旧样式。一小部分关注值表示细节的代码—主要是用于包装和解包 Value 的少数宏—根据此标志是否设置而有所不同。虚拟机的其余部分可以继续愉快地运行。

大部分工作都在“value”模块中完成，我们在其中添加了一个新类型的部分。

typedef struct ObjString ObjString;

#ifdef NAN_BOXING

typedef uint64_t Value;

#else

typedef enum {

启用 NaN 装箱后，Value 的实际类型是一个扁平的无符号 64 位整数。我们可以使用 double，这将使处理 Lox 数字的宏更简单。但是所有其他宏都需要进行位操作，而 uint64_t 是一个更友好的类型。在这个模块之外，虚拟机的其余部分并不真正关心。

在我们开始重新实现这些宏之前，我们在旧表示形式的定义末尾关闭了 #else 分支。

#define OBJ_VAL(object)   ((Value){VAL_OBJ, {.obj = (Obj*)object}})

#endif

typedef struct {

我们剩下的任务就是用新实现的 #ifdef 部分填充第一个 #ifdef 部分，这些实现与 #else 部分中已经存在的所有内容相同。我们将从最简单的开始，逐个处理每个值类型，直到最难的。

30 . 3 . 3数字

我们首先处理数字，因为它们在 NaN 装箱下具有最直接的表示形式。为了将 C 的 double 转换为 NaN 装箱的 clox Value，我们不需要修改任何位—表示形式完全相同。但我们需要让 C 编译器相信这一点，而我们通过将 Value 定义为 uint64_t 使得这一任务变得更加困难。

我们需要让编译器将它认为是 double 的一组位作为 uint64_t 使用，反之亦然。这被称为类型穿透。C 和 C++ 程序员从喇叭裤和 8 轨磁带时代就开始这样做，但语言规范一直犹豫不决地说哪些方法是官方认可的。

我知道一种将 double 转换为 Value 并返回的方法，我相信 C 和 C++ 规范都支持这种方法。不幸的是，它不适合用单个表达式来完成，因此转换宏必须调用辅助函数。以下是第一个宏

typedef uint64_t Value;

#define NUMBER_VAL(num) numToValue(num)

#else

该宏将 double 传递到这里

#define NUMBER_VAL(num) numToValue(num)

static inline Value numToValue(double num) {
  Value value;
  memcpy(&value, &num, sizeof(double));
  return value;
}

#else

我知道，很奇怪吧？将一系列字节视为具有不同类型的唯一方法而不改变其值是使用 memcpy()？这看起来很慢：创建一个局部变量。通过系统调用将它的地址传递给操作系统以复制几个字节。然后返回结果，该结果与输入完全相同。值得庆幸的是，由于这是类型穿透的受支持的惯用法，因此大多数编译器都会识别这种模式并完全优化掉 memcpy()。

“解包”Lox 数字是镜像操作。

typedef uint64_t Value;

#define AS_NUMBER(value)    valueToNum(value)

#define NUMBER_VAL(num) numToValue(num)

该宏调用此函数

#define NUMBER_VAL(num) numToValue(num)

static inline double valueToNum(Value value) {
  double num;
  memcpy(&num, &value, sizeof(Value));
  return num;
}

static inline Value numToValue(double num) {

它的工作原理完全相同，只是我们交换了类型。同样，编译器会将其全部删除。即使对 memcpy() 的调用将消失，我们仍然需要向编译器展示我们正在调用哪个 memcpy()，因此我们还需要一个包含。

#define clox_value_h

#include <string.h>

#include "common.h"

这花费了大量的代码，最终只做了沉默 C 类型检查器的工作。对 Lox 数字进行运行时类型测试会更有趣。如果我们只有 double 的位，我们如何判断它是一个 double？现在该进行位操作了。

typedef uint64_t Value;

#define IS_NUMBER(value)    (((value) & QNAN) != QNAN)

#define AS_NUMBER(value)    valueToNum(value)

我们知道，每个不是数字的 Value 都将使用特殊的静默 NaN 表示。我们假设我们已经正确地避免了任何可能由数字运算产生的有意义的 NaN 表示。

如果 double 的所有 NaN 位都被设置为 1，并且静默 NaN 位被设置为 1，以及另外一位，我们可以非常肯定它是我们自己为其他类型保留的位模式之一。为了检查这一点，我们屏蔽除了我们的静默 NaN 位集之外的所有位。如果所有这些位都被设置为 1，那么它一定是被 NaN 装箱的另一种 Lox 类型的 value。否则，它实际上是一个数字。

静默 NaN 位集的声明方式如下

#ifdef NAN_BOXING

#define QNAN     ((uint64_t)0x7ffc000000000000)

typedef uint64_t Value;

如果 C 支持二进制字面量就好了。但如果你进行转换，你会发现该值与以下值相同

这正是所有指数位，加上静默 NaN 位，再加一位以避免 Intel 的值。

30 . 3 . 4Nil、true 和 false

下一个要处理的类型是 nil。这很简单，因为只有一个 nil 值，因此我们只需要一个位模式来表示它。还有另外两个单例值，这两个布尔值，true 和 false。这需要三个独特的位模式。

两个位给了我们四种不同的组合，这已经足够了。我们声明我们未使用的尾数空间中的最低两位作为“类型标签”，以确定我们正在查看这三个单例值中的哪一个。三个类型标签的定义如下

#define QNAN     ((uint64_t)0x7ffc000000000000)

#define TAG_NIL   1 // 01.
#define TAG_FALSE 2 // 10.
#define TAG_TRUE  3 // 11.

typedef uint64_t Value;

因此，我们对 nil 的表示形式是定义我们静默 NaN 表示形式所需的所有位，以及 nil 类型标签位

在代码中，我们这样检查位

#define AS_NUMBER(value)    valueToNum(value)

#define NIL_VAL         ((Value)(uint64_t)(QNAN | TAG_NIL))

#define NUMBER_VAL(num) numToValue(num)

我们只需对静默 NaN 位和类型标签进行按位 OR 操作，然后进行一些强制类型转换来告诉 C 编译器我们希望这些位代表什么。

由于 nil 只有一个位表示，因此我们可以使用 uint64_t 上的等式来查看一个 Value 是否为 nil。

typedef uint64_t Value;

#define IS_NIL(value)       ((value) == NIL_VAL)

#define IS_NUMBER(value)    (((value) & QNAN) != QNAN)

你可以猜到我们是如何定义 true 和 false 值的。

#define AS_NUMBER(value)    valueToNum(value)

#define FALSE_VAL       ((Value)(uint64_t)(QNAN | TAG_FALSE))
#define TRUE_VAL        ((Value)(uint64_t)(QNAN | TAG_TRUE))

#define NIL_VAL         ((Value)(uint64_t)(QNAN | TAG_NIL))

这些位看起来像这样

要将 C 布尔值转换为 Lox 布尔值，我们依赖于这两个单例值和传统的条件运算符。

#define AS_NUMBER(value)    valueToNum(value)

#define BOOL_VAL(b)     ((b) ? TRUE_VAL : FALSE_VAL)

#define FALSE_VAL       ((Value)(uint64_t)(QNAN | TAG_FALSE))

可能有一种更巧妙的按位方法可以做到这一点，但我直觉是编译器可以比我更快地找出一种方法。反方向更简单。

#define IS_NUMBER(value)    (((value) & QNAN) != QNAN)

#define AS_BOOL(value)      ((value) == TRUE_VAL)

#define AS_NUMBER(value)    valueToNum(value)

由于我们知道 Lox 中只有两种布尔位表示—不像 C 中，任何非零值都可以被认为是“真”—如果它不是 true，它一定是 false。此宏假设你只对你知道是 Lox 布尔值的 Value 调用它。要检查这一点，还有一个宏。

typedef uint64_t Value;

#define IS_BOOL(value)      (((value) | 1) == TRUE_VAL)

#define IS_NIL(value)       ((value) == NIL_VAL)

看起来有点奇怪。一个更明显的宏看起来像这样

#define IS_BOOL(v) ((v) == TRUE_VAL || (v) == FALSE_VAL)

不幸的是，这并不安全。扩展中两次提到了 v，这意味着如果该表达式有任何副作用，它们将被执行两次。我们可以让宏调用一个单独的函数，但是，唉，太麻烦了。

相反，我们对值进行按位 OR 1 操作，将两种有效的布尔位模式合并。这使得值可能处于三种状态

1. 它是 FALSE_VAL，现在已转换为 TRUE_VAL。

2. 它是 TRUE_VAL，| 1 没有任何作用，它仍然是 TRUE_VAL。

3. 它是一些其他非布尔值。

此时，我们可以简单地将结果与 TRUE_VAL 进行比较，以查看我们是在前两种状态还是第三种状态。

30 . 3 . 5对象

最后一种值类型是最难的。与单例值不同，有数十亿个不同的指针值需要打包到 NaN 中。这意味着我们需要某种标签来表明这些特定的 NaN 是 Obj 指针，以及用于存储地址本身的空间。

我们用于单例值的标签位位于我决定存储指针本身的区域，因此我们不能轻易在那里使用另一个 位 来表明该值为对象引用。但是，我们还有一个没有使用的位。由于我们所有的 NaN 值都不是数字—名字就说明了一切—符号位没有用于任何事情。我们将使用它作为对象的类型标签。如果我们静默 NaN 之一设置了它的符号位，那么它就是一个 Obj 指针。否则，它一定是之前提到的单例值之一。

如果符号位被设置，那么剩余的低位存储指向 Obj 的指针

要将原始 Obj 指针转换为 Value，我们获取指针并设置所有静默 NaN 位和符号位。

#define NUMBER_VAL(num) numToValue(num)

#define OBJ_VAL(obj) \
    (Value)(SIGN_BIT | QNAN | (uint64_t)(uintptr_t)(obj))

static inline double valueToNum(Value value) {

指针本身是完整的 64 位，原则上，它可能会与一些静默 NaN 和符号位重叠。但实际上，至少在我测试过的架构上，指针中第 48 位以上的位始终为零。这里有很多强制类型转换，我发现这是满足一些最挑剔的 C 编译器所必需的，但最终结果只是将一些位组合在一起。

我们这样定义符号位

#ifdef NAN_BOXING

#define SIGN_BIT ((uint64_t)0x8000000000000000)

#define QNAN     ((uint64_t)0x7ffc000000000000)

要将 Obj 指针取回，我们只需屏蔽掉所有这些额外的位即可。

#define AS_NUMBER(value)    valueToNum(value)

#define AS_OBJ(value) \
    ((Obj*)(uintptr_t)((value) & ~(SIGN_BIT | QNAN)))

#define BOOL_VAL(b)     ((b) ? TRUE_VAL : FALSE_VAL)

波浪号 (~)，如果你还没有进行足够的位操作来遇到它，它就是按位 NOT。它将操作数中的所有 1 和 0 反转。通过使用静默 NaN 和符号位的按位取反对值进行掩码，我们清除了这些位，并保留了指针位。

最后一个宏

#define IS_NUMBER(value)    (((value) & QNAN) != QNAN)

#define IS_OBJ(value) \
    (((value) & (QNAN | SIGN_BIT)) == (QNAN | SIGN_BIT))

#define AS_BOOL(value)      ((value) == TRUE_VAL)

存储 Obj 指针的 Value 设置了它的符号位，但任何负数也是如此。要判断一个 Value 是否是 Obj 指针，我们需要检查符号位和所有静默 NaN 位是否都被设置。这类似于我们如何检测单例值的类型，只是这一次我们使用符号位作为标签。

30 . 3 . 6值函数

VM 的其余部分通常在使用 Value 时会使用宏，因此我们快完成了。但是，“value”模块中有一些函数可以直接查看 Value 的黑盒内部并使用其编码。我们也需要修复它们。

第一个是 printValue()。它对每种值类型都有单独的代码。我们不再有可以使用的显式类型枚举，因此我们使用一系列类型测试来处理每种值类型。

void printValue(Value value) {

#ifdef NAN_BOXING
  if (IS_BOOL(value)) {
    printf(AS_BOOL(value) ? "true" : "false");
  } else if (IS_NIL(value)) {
    printf("nil");
  } else if (IS_NUMBER(value)) {
    printf("%g", AS_NUMBER(value));
  } else if (IS_OBJ(value)) {
    printObject(value);
  }
#else

  switch (value.type) {

从技术上讲，这比 switch 稍微慢一点，但与实际写入流的开销相比，可以忽略不计。

我们仍然支持原始的带标签的联合表示，因此我们保留旧代码并将其包含在 #else 条件部分中。

  }

#endif

}

另一个操作是测试两个值是否相等。

bool valuesEqual(Value a, Value b) {

#ifdef NAN_BOXING
  return a == b;
#else

  if (a.type != b.type) return false;

它不会比这更简单了！如果两个位表示相同，则这些值相等。这对于单例值是正确的，因为每个单例值都有唯一的位表示，并且它们仅与其自身相等。对于 Obj 指针，这也是正确的，因为对象使用标识来进行相等性比较—只有当两个 Obj 引用指向同一个对象时，它们才是相等的。

对于数字来说，它基本是正确的。大多数具有不同位表示的浮点数是不同的数值。唉，IEEE 754 包含一个陷阱让我们陷入困境。出于我并不完全理解的原因，规范规定 NaN 值不等于自身。这对我们用于自身目的的特殊静默 NaN 来说不是问题。但有可能在 Lox 中生成一个“真实”的算术 NaN，如果我们想正确地实现 IEEE 754 数字，那么结果值不应等于自身。更具体地说

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

IEEE 754 说这个程序应该输出“false”。它使用我们旧的带标签的联合表示做对了，因为 VAL_NUMBER 案例将 == 应用于 C 编译器知道是 double 的两个值。因此，编译器会生成正确的 CPU 指令来执行 IEEE 浮点数比较。

我们的新表示通过将 Value 定义为 uint64_t 来打破这一点。如果我们想完全符合 IEEE 754，我们需要处理这种情况。

#ifdef NAN_BOXING

  if (IS_NUMBER(a) && IS_NUMBER(b)) {
    return AS_NUMBER(a) == AS_NUMBER(b);
  }

  return a == b;

我知道，这很奇怪。并且每次我们检查两个 Lox 值是否相等时，进行此类型测试都会带来性能成本。如果我们愿意牺牲一点 兼容性—谁真的在乎 NaN 是否不等于自身？—我们可以忽略它。我将由你决定你想成为多么吹毛求疵的人。

最后，我们关闭了旧实现周围的条件编译部分。

  }

#endif

}

就这样。这种优化已经完成，我们的 clox 虚拟机也是如此。这是本书中最后一行新代码。

30 . 3 . 7评估性能

代码已经完成，但我们仍然需要弄清楚我们是否真的通过这些更改获得了改进。评估像这样的优化与之前那个非常不同。在那里，我们在分析器中看到一个明显的热点。我们修复了代码的那部分，并立即看到热点变快了。

更改值表示的效果更分散。宏在它们使用的地方被展开，因此性能变化散布在整个代码库中，许多分析器难以很好地跟踪，尤其是在 优化 版本中。

我们也不能轻易推断出我们更改的影响。我们使值更小了，这减少了整个 VM 的缓存未命中。但这项更改的实际实际性能影响高度依赖于正在运行的 Lox 程序的内存使用情况。一个微小的 Lox 微基准可能没有足够的散布在内存中的值，因此效果不会显而易见，甚至 C 内存分配器分配给我们的地址也会影响结果。

如果我们做对了，基本上所有东西都会变得更快，尤其是在更大、更复杂的 Lox 程序上。但也有可能我们对 NaN 装箱值进行的额外按位运算抵消了更好的内存使用带来的收益。进行这种性能工作令人不安，因为你无法轻松地证明你已经让 VM 变得更好。你不能指向一个单独的手术目标微基准并说，“看，就是这样？”

相反，我们真正需要的是一组更大型的基准。理想情况下，它们应该从现实世界应用程序中提取—当然，对于像 Lox 这样的玩具语言来说，并没有这样的东西。然后，我们可以测量所有这些基准的整体性能变化。我尽力拼凑了一些更大的 Lox 程序。在我的机器上，新的值表示似乎使所有东西的整体速度提高了大约 10%。

这并不是很大的改进，尤其是与使哈希表查找速度更快带来的巨大影响相比。我添加这种优化很大程度上是因为它是一个很好的例子，说明了您可能会遇到的某种类型的性能工作，并且坦率地说，因为我认为它在技术上非常酷。如果我认真地试图让 clox 变得更快，这可能不是我会首先尝试的事情。可能还有其他更容易实现的改进。

但是，如果你发现自己正在处理一个程序，其中所有简单的改进都已经完成，那么在某个时候，你可能想要考虑调整你的值表示。我希望本章能让你了解到你在这个领域的一些选择。

30 . 4下一步去哪里

我们将在 Lox 语言和我们的两个解释器中结束。我们可以永远地对其进行调整，添加新的语言特性并改进速度。但对于这本书，我认为我们已经找到了一个自然的地方来宣布我们的工作完成。我不会重新讨论过去几页中我们学到的所有内容。你一直都在我的身边，你记得。相反，我想花点时间谈谈你下一步可以做什么。你编程语言之旅的下一步是什么？

你们中的大多数人可能不会在职业生涯中花很大一部分时间从事编译器或解释器的工作。这在计算机科学学术界中只占很小的比例，而在工业界中的软件工程领域中比例更小。这没关系。即使你一生中不再从事编译器工作，你也一定会使用它，我希望这本书能让你更好地理解你使用的编程语言是如何设计和实现的。

你已经学习了一些重要的基本数据结构，并积累了一些进行低级分析和优化工作的经验。无论你在哪个领域进行编程，这种专业知识都有帮助。

我还希望我给你一种看待和解决问题的新方法。即使你以后不再从事语言工作，你可能会惊讶地发现有多少编程问题可以被视为语言类似的。也许你需要编写的报告生成器可以建模为一系列基于堆栈的“指令”，生成器“执行”这些指令。你需要渲染的用户界面看起来很像遍历 AST。

如果你想更深入地了解编程语言的兔子洞，这里有一些关于探索隧道中哪个分支的建议。

• 我们简单的单遍字节码编译器将我们推向了主要以运行时优化为主。在一个成熟的语言实现中，编译时优化通常更重要，编译器优化领域非常丰富。获取一本经典的编译器书籍，并重建 clox 或 jlox 的前端，使其成为一个复杂的编译管道，其中包含一些有趣的中介表示和优化过程。

  动态类型会对你走多远有一些限制，但你仍然可以做很多事情。或者，也许你想迈出一大步，为 Lox 添加静态类型和类型检查器。这无疑会让你的前端有更多的事情要处理。

• 在这本书中，我力求正确，但并非特别严谨。我的目标主要是让你对进行语言工作有直觉和感觉。如果你想要更多精确性，那么整个编程语言学术界都在等着你。语言和编译器在计算机出现之前就已经被正式研究了，因此关于解析理论、类型系统、语义和形式逻辑的书籍和论文并不缺乏。走这条路也会教你如何阅读 CS 论文，这本身就是一个有价值的技能。

• 或者，如果你真的喜欢黑客攻击和制作语言，你可以把 Lox 变成你自己的玩具。将语法更改为你喜欢的东西。添加缺少的功能或删除你不喜欢的功能。在里面加入新的优化。

  最终，你可能会达到一个你觉得其他人也可以使用的程度。这会让你进入编程语言流行的截然不同的世界。预计你将花大量时间编写文档、示例程序、工具和有用的库。这个领域挤满了争夺用户的语言。要想在这个领域蓬勃发展，你必须戴上你的营销帽子，开始推销。不是每个人都喜欢这种面向公众的工作，但如果你喜欢，看到人们使用你的语言来表达自己会令人难以置信地欣慰。

或者，也许这本书已经满足了你的渴望，你会在这里停下来。无论你走哪条路，或者不走哪条路，我希望有一点教训能深深地铭刻在你的心中。就像我一样，你可能最初会被编程语言吓倒。但在这些章节中，你已经看到，即使是最具挑战性的材料，只要我们动手实践，一步一步地学习，我们凡人也能克服。如果你能处理编译器和解释器，你就可以做任何你想做的事情。