简介

编程语言优化意味着采用工作应用程序并提高其性能。

优化的程序做同样的事情，只是需要更少的资源。

1.1 衡量性能

我们在优化时通常想到的资源是运行速度，但减少内存使用、启动时间、持久存储大小或网络带宽也很重要。

所有物理资源都有一定的成本——即使成本主要是浪费在人力上——所以优化工作通常会得到回报。

在计算的早期曾经有一段时间，熟练的程序员可以将整个硬件架构和编译器管道牢记在心，并通过认真思考来理解程序的性能。

那些日子早已一去不复返了，因为微代码、缓存行、分支预测、深度编译器管道和庞大的指令集而与现在分开。

我们喜欢假装 C 是一种“低级”语言，但两者之间的技术堆栈不同。

    printf("Hello!");

出现在屏幕上的问候语现在是危险地高。

今天的优化是一门经验科学。我们的程序是一只边境牧羊犬冲刺通过硬件的障碍路线。
如果我们想让她更快地到达终点，我们不能坐下来思考犬的生理学，直到启蒙来袭。

相反，我们需要观察她的表现，看看她在哪里绊倒，然后为她找到更快的路径。

就像敏捷训练是专门针对一只狗和一个障碍赛一样，我们不能假设我们的虚拟机优化将使所有OTao 程序在所有硬件上运行得更快。

不同的 OTao 程序强调 VM 的不同区域，不同的体系结构各有优缺点。

1.2 基准

当我们添加新的功能，我们通过编写测试验证正确性-使用功能和验证虚拟机的行为OTao方案。
测试确定语义并确保我们在添加新功能时不会破坏现有功能。我们在性能方面也有类似的需求：

    1 我们如何验证优化确实提高了性能，提高了多少？
    2 我们如何确保其他不相关的更改不会倒退的表现？

我们为实现这些目标而编写的 OTao 程序是基准。这些是精心设计的程序，强调语言实现的某些部分。
他们衡量的不是程序做了什么，而是它需要多长时间。

    大多数基准测试测量运行时间。
    但是，当然，您最终会发现自己需要编写基准测试来测量内存分配、在垃圾收集器上花费的时间、启动时间等。

通过测量更改前后基准的性能，您可以了解更改的作用。
当您进行优化时，所有测试的行为都应与之前完全相同，但希望基准测试运行得更快。

一旦你有一个完整的套件的基准，你不能衡量仅仅是一个优化性能的变化，但其 种类的代码。
通常，您会发现某些基准测试变得更快，而其他基准测试变得更慢。然后，您必须就您的语言实现优化哪些类型的代码做出艰难的决定。

您选择编写的基​​准测试套件是该决定的关键部分。
就像您的测试围绕正确行为的外观编码您的选择一样，您的基准测试是您在性能方面的优先级的体现。
它们将指导您实施哪些优化，因此请谨慎选择您的基准，并且不要忘记定期反思它们是否有助于您实现更大的目标。

在 JavaScript VM 的早期扩散中，第一个广泛使用的基准测试套件是来自 WebKit 的 SunSpider。
在浏览器大战期间，营销人员使用 SunSpider 的结果声称他们的浏览器是最快的。这极大地激励了 VM 黑客针对这些基准进行优化。

不幸的是，SunSpider 程序通常与现实世界的 JavaScript 不匹配。
它们主要是微基准测试——快速完成的小玩具程序。这些基准测试会惩罚复杂的即时编译器，这些编译器开始较慢，
但一旦 JIT 有足够的时间来优化和重新编译热代码路径，就会 变得更快。
这让 VM 极客不得不在让 SunSpider 数字变得更好或实际优化真实用户运行的程序类型之间做出选择。

作为回应，谷歌的 V8 团队分享了他们的 Octane 基准测试套件，这在当时更接近真实世界的代码。
多年后，随着 JavaScript 使用模式的不断发展，甚至 Octane 也失去了它的用处。

期望您的基准测试会随着您的语言生态系统的发展而发展。

请记住，最终目标是使用户程序更快，而基准测试只是一个代理。

基准测试是一门微妙的艺术。与测试一样，您需要在不过度拟合您的实现的同时确保基准测试确实验证了您关心的代码路径。

当您测量性能时，您需要补偿由 CPU 节流、缓存和其他奇怪的硬件和操作系统怪癖引起的差异。
我不会在这里给你一个完整的布道，而是将基准测试作为它自己的技能，随着练习而提高。

1.3 剖析

现在您已经获得了一些基准。你想让他们走得更快。怎么办？首先，让我们假设您已经完成了所有显而易见的简单工作。

您使用了正确的算法和数据结构——或者，至少，您没有使用严重错误的算法和数据结构。
我不考虑使用哈希表而不是通过巨大的未排序数组“优化”的线性搜索，而是“良好的软件工程”。

由于硬件太复杂，无法从基本原理推断我们程序的性能，因此我们必须进入该领域。这意味着分析。

一个 分析器，如果你从来没有用过一个，是运行你的一个工具程序的代码执行和跟踪硬件资源的使用。
简单的显示您在程序中的每个函数上花费了多少时间。

复杂的记录数据缓存未命中、指令缓存未命中、分支预测错误、内存分配和各种其他指标。

1 这里的“你的程序”是指运行其他OTao 程序的 OTao VM 本身。我们正在尝试优化 cOTao，而不是用户的 OTao 脚本。

2 当然，选择将哪个 OTao 程序加载到我们的 VM 将极大地影响 cOTao 的哪些部分受到压力，这就是基准测试如此重要的原因。

3 分析器不会向我们显示正在运行的脚本中每个OTao函数花费了多少时间。
我们必须编写我们自己的“OTao 分析器”来做到这一点，这有点超出了本书的范围。

有许多用于各种操作系统和语言的分析器。在您编程的任何平台上，熟悉一个体面的分析器都是值得的。你不需要成为大师。

我在向分析器投掷程序的几分钟内就学到了一些东西，而我自己需要几天才能通过反复试验来发现。分析器是美妙的、神奇的工具。

1.4 更快的哈希表探测

够自以为是，让我们得到一些向上和向右的性能图表。事实证明，我们要做的第一个优化是 我们可以对 VM 进行的最微小的更改。

当我第一次获得 cOTao 的后裔字节码虚拟机时，我做了任何有自尊的 VM 黑客都会做的事情。
我拼凑了几个基准测试，启动了一个分析器，并通过我的解释器运行这些脚本。

在像 OTao 这样的动态类型语言中，很大一部分用户代码是字段访问和方法调用，所以我的一个基准测试看起来像这样：

	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;

如果您以前从未见过基准测试，这可能看起来很荒谬。 该程序本身并不打算做 任何有用的事情。

它所做的是调用一堆方法并访问一堆字段，因为这些是我们感兴趣的语言部分。
字段和方法存在于哈希表中，因此它会注意填充至少一些有趣的键在那些表中。

这一切都包含在一个大循环中，以确保我们的分析器有足够的执行时间来深入挖掘并查看循环的去向。

在我告诉您我的分析器向我展示的内容之前，请花一点时间进行一些猜测。
您认为 VM 在 cOTao 的代码库中的哪个位置花费了大部分时间？
我们在前几章中编写的任何代码您怀疑是否特别慢？

这是我发现的：自然，包含时间最大的函数是 run(). （包含时间是指在某个函数和它调用的所有其他函数上花费的总时间——从你进入函数 到它返回之间的总时间。）

因为run()是主字节码执行循环，它驱动一切。

里面run()，有很多的字节码开关像常见的指令在各种情况下洒时间小块OP_POP，OP_RETURN和 OP_ADD。
大型指令占用OP_GET_GLOBAL17% 的执行时间，OP_GET_PROPERTY占 12%，OP_INVOKE占总运行时间的 42%。

所以我们有三个要优化的热点？实际上，没有。

因为事实证明，这三个指令几乎将所有时间都花在对同一函数的调用中：tableGet().
该函数占用了整整 72% 的执行时间（再次包含）。
现在，在动态类型语言中，我们希望花费相当多的时间在哈希表中查找内容——这是动态的代价。但是，还是，哇。

1.5 慢速封装

如果您查看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;
		  }
		}

当运行以前的基准-我的机器上，至少-在VM上花费的总执行时间的70％，一条线在此功能。猜猜是哪一个？不？是这样的：

    uint32_t index = key->hash % capacity;

那个指针取消引用不是问题。这是一个小%。事实证明，模运算符真的很慢。比其他算术运算符慢得多。我们能不能做得更好？

流水线使得很难谈论单个 CPU 指令的性能，但为了让您感受一下，除法和取模比 x86 上的加法和减法慢大约 30-50倍。

在一般情况下，很难以比 CPU 本身更快的方式在用户代码中重新实现基本算术运算符。
毕竟，我们的 C 代码最终会编译为 CPU 自己的算术运算。如果我们可以使用一些技巧来加快速度，那么芯片早就在使用它们了。

然而，我们可以利用这样一个事实，即我们比 CPU 更了解我们的问题。
我们在这里使用 modulo 来获取键字符串的哈希码并将其包装以适应表条目数组的边界。
该数组从八个元素开始，每次增长两倍。我们知道——而 CPU 和 C 编译器不知道——我们的表的大小总是 2 的幂。

因为我们很聪明，所以我们知道一种更快的方法来计算以 2 的幂为模的数字的余数：位掩码。假设我们要计算 229 模 64。
答案是 37，这在十进制中不是特别明显，但是当您以二进制形式查看这些数字时会更清楚

在插图的左侧，请注意结果 (37) 是如何简单地除掉最高两位的被除数 (229)？这两个最高位是除数的单个 1 位处或左侧的位。

在右侧，我们通过取 229 并与 63 进行按位与运算得到相同的结果，这比我们原来的二除数的幂小 1。
从 2 的幂中减去 1 会得到一系列 1 位。这正是我们需要的掩码，以便去除最左边的那两个位。

换句话说，你可以计算出许多通过简单地模二的任何权力 和与二减一的权力-ing它。
我没有足够的数学家来证明给你这个作品，但如果你认为它通过，它应该是有意义的。

我们可以用一个非常快的递减和按位AND来替换那个缓慢的模运算符。我们只需将有问题的代码行更改为：

	#table.c in findEntry()
	static Entry* findEntry(Entry* entries, int capacity,
                    ObjString* key) {

	  uint32_t index = key->hash & (capacity - 1);
	  Entry* tombstone = NULL;

CPU 喜欢按位运算符，因此很难对其进行改进。

另一个潜在的改进是通过直接存储位掩码而不是容量来消除递减。在我的测试中，这并没有什么不同。
如果 CPU 在其他地方遇到瓶颈，指令流水线可以使某些操作基本上免费。

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

	##table.c in findEntry()
	// We found the key.
  	return entry;
	    }
	replace 1 line
	    index = (index + 1) & (capacity - 1);
	  }

由于大多数搜索不换行，因此该行没有出现在分析器中。

该findEntry()函数有一个姊妹函数，tableFindString()它为实习字符串执行哈希表查找。我们也可以在那里应用相同的优化。

仅在实习字符串时调用此函数，我们的基准测试并没有对它造成很大压力。
但是创建大量字符串的 OTao 程序可能会明显受益于这种变化。 

并且当线性探测环绕时。	     

让我们看看我们的修复是否值得。我调整了动物学基准，以计算它可以在 10 秒内运行多少个 10,000 个调用的批次。

更多的批次等于更快的性能。在我使用未优化代码的机器上，基准测试通过了 3,192 个批次。在此优化之后，它跃升至 6,249。

在相同的时间内，这几乎是工作量的两倍。我们使 VM 的速度提高了两倍（通常需要注意：在此基准测试中）。
在优化方面，这是一个巨大的胜利。如果你能在这里或那里抓住几个百分点，通常你会感觉很好。

由于方法、字段和全局变量在 OTao 程序中非常普遍，因此这种微小的优化可以全面提高性能。几乎每个 OTao 计划都会受益。

    注:
    我们最初的基准确定了工作量，然后测量了时间。更改脚本以计算它在 10 秒内可以执行多少批调用，从而确定了时间并测量了工作量。
    对于性能比较，我喜欢后一种度量，因为报告的数字代表speed。您可以直接比较优化前后的数字。
    在测量执行时间时，您必须做一些算术才能获得良好的相对性能测量。

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

关键是我们不知道模运算符会消耗性能，直到我们的分析器告诉我们。
如果我们在 VM 的代码库中四处游荡，盲目地猜测热点，我们可能不会注意到它。
我希望您从中了解的是，在您的工具箱中拥有一个分析器是多么重要。

为了强调这一点，让我们继续在我们现在优化的 VM 中运行原始基准测试，看看分析器向我们展示了什么。

在我的机器上，tableGet() 仍然有相当大的执行时间。这是动态类型语言所期望的。
但它已从总执行时间的 72% 下降到 35%。

这更符合我们希望看到的情况，并表明我们的优化不仅使程序更快，而且以我们预期的方式使其更快 。
探查器对于验证解决方案和发现问题一样有用。

1.6 黑盒法

下一个优化有非常不同的感觉。值得庆幸的是，尽管名字很奇怪，但它并不涉及冒犯
你。
它是不同的，但并没有那么不同。通过我们之前的优化，分析器会告诉我们问题出在哪里，我们只需要巧妙地想出解决方案。

这种优化更加微妙，其性能影响更加分散在虚拟机中。分析器不会帮助我们想出这个。
相反，它是由深入思考机器架构的最低层次的人发明的。

    我不确定是谁首先提出了这个。我能找到的最早来源是 David Gudeman 1993年的论文“在动态类型语言中表示类型信息”。
    其他人都引用了这一点。但古德曼本人表示，这篇论文不是新颖的作品，而是“汇集了大量民间传说”。

    也许发明者已经迷失在时间的迷雾中，或者它已经被重新发明了很多次。
    任何对 IEEE 754 进行足够长时间思考的人都可能开始考虑尝试将一些有用的东西塞进所有未使用的 NaN 位中。

就像标题所说的那样，这种优化称为NaN boxing或有时 NaN tagging。
我个人喜欢后者，因为“装箱”往往暗示某种堆分配表示，但前者似乎是更广泛使用的术语。
这种技术改变了我们在 VM 中表示值的方式。

在 64 位机器上，我们的 Value 类型占用 16 个字节。
该结构体有两个字段，一个类型标记和一个用于负载的联合。
联合中最大的字段是一个 Obj 指针和一个双精度值，它们都是 8 个字节。

为了保持联合字段与 8 字节边界对齐，编译器也在标记后添加填充：

这是相当大的。如果我们可以减少它，那么 VM 可以将更多值打包到相同数量的内存中。

如今，大多数计算机都有足够的 RAM，因此直接节省内存并不是什么大问题。但是较小的表示意味着更多的值适合缓存行。

这意味着更少的缓存未命中，这会影响 速度。

如果值需要与它们的最大有效载荷大小对齐，并且 OTao 数或 Obj 指针需要完整的 8 个字节，我们如何才能变得更小？

在像 OTao 这样的动态类型语言中，每个值不仅需要携带其有效载荷，还需要携带足够的附加信息来在运行时确定值的类型。

如果一个 OTao 数已经使用了完整的 8 个字节，那么我们可以从哪里删除一些额外的位来告诉运行时“这是一个数字”？

这是动态语言黑客长期面临的问题之一。它特别困扰他们，因为静态类型语言通常没有这个问题。
每个值的类型在编译时是已知的，因此在运行时不需要额外的内存来跟踪它。

当您的 C 编译器编译 32 位 int 时，生成的变量正好获得32 位的存储空间。

动态语言的人讨厌在静态阵营中败下阵来，所以他们想出了许多非常聪明的方法来将类型信息和有效载荷打包成少量的位。

NaN 盲盒法 就是其中之一。它特别适合 JavaScript 和 Lua 等语言，其中所有数字都是双精度浮点数。OTao 在同一条船上。

1.7 什么是（或不是）数字？

在开始优化之前，我们需要真正了解 CPU 是如何表示浮点数的。

今天几乎所有的机器都使用相同的方案，编码在古老的卷轴IEEE 754 中，凡人称为“IEEE 浮点运算标准”。

在您的计算机眼中，一个64 位、双精度、IEEE 浮点数如下所示：

	1 从右边开始，前 52 位是小数位、 尾数位或有效数位。它们将数字的有效数字表示为二进制整数。

	2 旁边是 11 个指数位。这些告诉您尾数偏离十进制（好吧，二进制）点的距离。

	3 最高位是符号位，表示数字是正数还是负数。	

这有点含糊，但本章并不是对浮点表示的深入探讨。
如果你想知道指数和尾数是如何一起工作的，已经有比我能写的更好的解释了。

由于符号位始终存在，即使数字为零，这意味着“正零”和“负零”具有不同的位表示，实际上，IEEE 754 确实区分了它们。

对于我们的目的来说，重要的部分是规范制定了一个特殊的案例指数。
当所有指数位都被设置后，该值就不再只是代表一个非常大的数字，而是具有不同的含义。这些值是“非数字”（因此，NaN）值。
它们代表无穷大或除以零的结果等概念。

无论尾数位如何，其指数位都已设置的任何双精度数都是 NaN。这意味着有很多不同的NaN 位模式。
IEEE 754 将这些分为两类。最高尾数位为 0 的值称为信号 NaN，其他值是安静的 NaN。
信号 NaN 旨在成为错误计算的结果，例如除以零。芯片可能会检测到这些值中的一个何时产生并完全中止程序。
如果您尝试阅读它们，它们可能会自毁。

我不知道是否有任何 CPU 确实执行陷阱信号 NaN 并中止。规范只是说他们可以。

安静的 NaN 应该使用起来更安全。它们不代表有用的数值，但是如果您触摸它们，它们至少不应该让您的手着火。

设置了所有指数位并设置了最高尾数位的每个双精度值都是一个安静的 NaN。

这留下了 52 位下落不明。我们将避免其中之一，这样我们就不会踩到英特尔的“QNaN 浮点不定”值，留下 51 位。

那些剩余的位可以是任何东西。我们正在谈论 2,251,799,813,685,248 个独特的安静 NaN 位模式。

这意味着 64 位 double 有足够的空间来存储所有各种不同的数字浮点值，并且还有空间容纳另外 51 位数据，我们可以随意使用。

这是足够的空间留出一对夫妇的位模式来表示液氧的nil，true和false值。但是 Obj 指针呢？指针也不需要完整的 64 位吗？

幸运的是，我们还有另一个技巧。是的，从技术上讲，64 位架构上的指针是 64 位。
但是，我所知道的架构中没有一个真正使用过整个地址空间。

相反，当今最广泛使用的芯片只使用低48位。其余 16 位要么未指定，要么始终为零。

48 位足以处理 262,144 GB 的内存。现代操作系统还为每个进程提供了自己的地址空间，因此应该足够了。

如果我们有 51 位，我们可以在其中填充一个 48 位的指针，并留出 3 位。
这三个位足以存储微小的类型标签以区分nil、布尔值和 Obj 指针。

那是盲盒法。在单个 64 位双精度数中，您可以存储所有不同的浮点数值、一个指针或几个其他特殊标记值中的任何一个。

我们当前 Value 结构的内存使用量减少了一半，同时保留了所有保真度。

这种表示的特别之处在于不需要 将数字双精度值转换为“装箱”形式。
OTao数字是只是正常的，64位双打。

我们仍然需要在使用它们之前检查它们的类型，因为 OTao 是动态类型的，但我们不需要做任何位移或指针间接从“值”到“数字”。

对于其他值类型，当然有一个转换步骤。但是，幸运的是，我们的 VM 隐藏了从值到原始类型的所有机制，隐藏在少数宏后面。

重写那些以实现 NaN 装箱，VM 的其余部分应该可以正常工作。

1.8 有条件的支持

我知道你脑子里还不清楚这个新表示的细节。别担心，它们会随着我们的实施而具体化。在我们开始之前，我们将放置一些编译时脚手架。

对于我们之前的优化，我们重写了之前的慢代码，并称之为完成。这个有点不同。
NaN 装箱依赖于芯片如何表示浮点数和指针的一些非常底层的细节。

它 可能适用于您可能遇到的大多数 CPU，但您永远无法完全确定。

如果我们的 VM 仅仅因为其价值表示而完全失去对架构的支持，那将会很糟糕。

为了避免这种情况，我们将同时支持 Value 的旧标记联合实现和新的 NaN-boxed 形式。
我们在编译时使用这个标志选择我们想要的表示：

如果已定义，VM 将使用新形式。否则，它将恢复到旧样式。
关心值表示细节的几段代码——主要是用于包装和解包值的少数宏——根据是否设置了这个标志而有所不同。
虚拟机的其余部分可以继续其愉快的方式。

大多数工作发生在“值”模块中，我们为新类型添加了一个部分。

当启用 NaN 装箱时，Value 的实际类型是一个平面的、无符号的 64 位整数。
我们可以使用 double 代替，这将使处理 OTao 数的宏更简单一些。

但是所有其他宏都需要进行按位运算，而 uint64_t 是一种更友好的类型。
在这个模块之外，VM 的其余部分并不真正关心一种或另一种方式。

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

我们剩下的任务只是简单地#ifdef用已经在#else边上的所有东西的新实现来填充第一部分。我们将一次处理一种值类型，从最简单到最难。

1.9 数字

我们将从数字开始，因为它们在 NaN 装箱下具有最直接的表示。要将 C 双精度值“转换”为 NaN 装箱的 cOTao 值，我们不需要触及任何一位—表示完全相同。

但是我们确实需要让我们的 C 编译器相信这一事实，我们通过将 Value 定义为 uint64_t 使这一事实变得更加困难。

规范作者不喜欢类型双关，因为它使优化变得更加困难。
一个关键的优化技术是重新排序指令以填充 CPU 的执行管道。显然，编译器只能在没有用户可见效果的情况下重新排序代码。

指针使这更难。如果两个指针指向相同的值，则不能对通过一个的写入和通过另一个的读取进行重新排序。
但是两个不同类型的指针呢？如果它们可以指向同一个对象，那么基本上任何两个指针都可以是同一个值的别名。
这极大地限制了编译器可以自由重新排列的代码量。

为了避免这种情况，编译器希望采用严格的别名——不兼容类型的指针不能指向相同的值。从本质上讲，类型双关打破了这个假设。

我们需要让编译器采用一组它认为是双精度的位，并将这些位用作 uint64_t，反之亦然。这称为类型双关。
C 和 C++ 程序员从钟形底和 8 轨时代开始就一直在这样做，但是语言规范一直犹豫要说明这样做的众多方法中的哪一种是官方认可的。

规范作者不喜欢类型双关，因为它使优化变得更加困难。
一个关键的优化技术是重新排序指令以填充 CPU 的执行管道。显然，编译器只能在没有用户可见效果的情况下重新排序代码。

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

    ## value.h
    typedef uint64_t Value;
    #define NUMBER_VAL(num) numToValue(num)
    #else

该宏在此处传递双精度值：

    ## value.h
    #define NUMBER_VAL(num) numToValue(num)
            static inline Value numToValue(double num) {
              Value value;
              memcpy(&value, &num, sizeof(double));
              return value;
            }
            #else

该宏在此 定义

很奇怪，对吧？将一系列字节视为具有不同类型而不改变它们的值的方法是memcpy()？
这看起来非常慢：创建一个局部变量。

通过系统调用将其地址传递给操作系统以复制几个字节。然后返回结果，它与输入的字节完全相同。
值得庆幸的是，因为这是类型双关所支持的习惯用法，大多数编译器都能识别该模式并memcpy() 完全优化掉。

“展开”一个 OTao 数是镜像。

    ## value.h
    typedef uint64_t Value;
    #define AS_NUMBER(value)    valueToNum(value)
    #define NUMBER_VAL(num) numToValue(num)

该宏调用此函数：

    ## value.h
    #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()因此我们还需要一个include。

  ## value.h
	#define cOTao_value_h
	#include <string.h>
	#include "common.h"	

那是很多代码，最终除了使 C 类型检查器静音之外什么都不做。对 OTao 数进行运行时类型测试更有趣一些。
如果我们所拥有的只是双精度位，我们如何判断它是双精度数？是时候开始胡闹了。

	## value.h
	typedef uint64_t Value;
	#define IS_NUMBER(value)    (((value) & QNAN) != QNAN)
	#define AS_NUMBER(value)    valueToNum(value)

我们知道每个不是数字的Value 都将使用特殊的安静 NaN 表示。
我们假设我们已经正确地避免了任何可能通过对数字进行算术运算而实际产生的有意义的 NaN 表示。

如果 double 设置了所有的 NaN 位，设置了安静的 NaN 位，还有一个很好的衡量标准，我们可以很确定它是我们自己为其他类型预留的位模式之一。

为了检查这一点，我们屏蔽了除安静 NaN 位之外的所有位。如果设置了所有 这些位，则它必须是某个其他 OTao 类型的 NaN 装箱值。否则，它实际上是一个数字。

可以肯定，但不能严格保证。据我所知，没有什么能阻止 CPU 产生 NaN 值作为某些操作的结果，该操作的位表示与我们声称的那些相冲突。

但是在我对多个架构的测试中，我还没有看到它发生。

这组安静的 NaN 位声明如下：

  ## value.h
	#ifdef NAN_BOXING
	#define QNAN     ((uint64_t)0x7ffc000000000000)
	typedef uint64_t Value;

如果 C 支持二进制文字，那就太好了。但是，如果您进行转换，您会看到该值与此相同：

这正是所有指数位，加上安静的 NaN 位，再加上一个额外的以躲避英特尔值。

1.10 无，真，假，Nil, true, and false

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

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

	## value.h
	#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类型标记位：

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

我们只是简单地按位或将安静的 NaN 位和类型标记，然后做一些演员舞蹈来教 C 编译器我们想要这些位的含义。

由于nil只有一位表示，我们可以在 uint64_t 上使用相等来查看 Value 是否为nil。

您可以猜到我们如何定义true和false值。

	## value.h
	# 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 bool 转换为 OTao 布尔值，我们依赖于这两个单例值和古老的条件运算符。

可能有一种更聪明的按位方式来做到这一点，但我的预感是编译器可以比我更快地找出一个。去另一个方向更简单。

	## value.h
	#define IS_NUMBER(value) (((value) & QNAN) != QNAN)
	#define AS_BOOL(value) ((value) == TRUE_VAL)
	#define AS_NUMBER(value) valueToNum(value)

因为我们知道 OTao 中正好有两个布尔位表示——不像在 C 中任何非零值都可以被视为“真” ——如果它不是true，它必须是false。

这个宏确实假设你只在你知道是OTao 布尔值的值上调用它。为了检查这一点，还有一个宏。

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

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

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

相反，我们将 1按位OR到该值上以合并仅有的两个有效布尔位模式。这留下了价值可能处于的三个潜在状态：

	1 它曾经FALSE_VAL并且现在已经转换为TRUE_VAL.

	2 它是TRUE_VAL，| 1什么也没做，它仍然是TRUE_VAL。

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

在这一点上，我们可以简单地比较结果，TRUE_VAL看看我们是处于前两种状态还是第三种状态。

1.11 对象

最后一个值类型是最难的。与单例值不同，我们需要将数十亿个不同的指针值装入 NaN 中。
这意味着我们既需要某种标记来指示这些特定的 NaN是Obj 指针，也需要为地址本身留出空间。

我们用于单例值的标记位位于我决定存储指针本身的区域中，因此我们不能轻松地在那里使用不同的位来指示该值是一个对象引用。

但是，还有一点我们没有使用。由于我们所有的 NaN 值都不是数字——它就在名称中——符号位不用于任何东西。
我们将继续使用它作为对象的类型标记。如果我们的安静 NaN 之一设置了符号位，那么它就是一个 Obj 指针。
否则，它必须是之前的单例值之一。

即使值是 Obj 指针，我们实际上也可以使用最低位来存储类型标记。
那是因为 Obj 指针总是与 8 字节边界对齐，因为 Obj 包含 64 位字段。

反过来，这意味着 Obj 指针的三个最低位将始终为零。我们可以在那里存储我们想要的任何东西，并在取消引用指针之前将其屏蔽掉。

这是另一种称为指针标记的值表示优化。

如果设置了符号位，则剩余的低位存储指向 Obj 的指针：

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

    ## value.h
    #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 编译器是必要的，但最终结果只是将一些位卡在一起。

当谈到本书中的代码时，我试图遵循法律条文，所以这一段是可疑的。
在优化时，您不仅要突破规范所说的范围，还要突破真正的编译器和芯片让您摆脱困境的界限。

走出规范是有风险的，但在无法无天的领域也有回报。收益是否值得由您来决定。

我们像这样定义符号位：

            ## value.h
            #ifdef NAN_BOXING
            #define SIGN_BIT ((uint64_t)0x8000000000000000)
            #define QNAN     ((uint64_t)0x7ffc000000000000)	

为了取回 Obj 指针，我们只需屏蔽掉所有这些额外的位。

    ## value.h
    #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 和符号位的逐位否定来屏蔽该值，我们清除这些位并保留指针位。
最后一个宏：

	## value.h
	#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)

1.12 值函数

VM 的其余部分在使用值时通常会通过宏，所以我们几乎完成了。
但是，“value”模块中有几个函数可以查看 Value 的其他黑匣子并直接处理其编码。我们也需要解决这些问题。

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

这在技术上比 switch 慢一点，但与实际写入流的开销相比，它可以忽略不计。
我们仍然支持原始的标记联合表示，因此我们保留旧代码并将其包含在#else条件部分中。

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

没有比这更简单的了！如果两个位表示相同，则值相等。
这对单例值来说是正确的，因为每个值都有一个唯一的位表示，并且它们只等于它们自己。
它也为 Obj 指针做了正确的事情，因为对象使用标识来表示相等——两个 Obj 引用只有在它们指向完全相同的对象时才相等。

它对数字也大多是正确的。大多数具有不同位表示的浮点数是不同的数值。
IEEE 754 包含一个坑，让我们绊倒。由于我并不完全清楚的原因，规范要求 NaN 值不等于它们自己。

对于我们用于自己目的的特殊安静 NaN 来说，这不是问题。
但是可以在 OTao 中生成“真正的”算术 NaN，如果我们想正确实现 IEEE 754 数字，那么结果值不应等于自身。更具体地说：

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

IEEE 754 说这个程序应该打印“false”。

它对我们旧的标记联合表示做了正确的事情，因为这种VAL_NUMBER情况适用 ==于 C 编译器知道是双精度的两个值。

因此，编译器生成正确的 CPU 指令来执行 IEEE 浮点等式。

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

我知道，这很奇怪。每次我们检查两个 OTao 值是否相等时，进行这种类型测试都会产生性能成本。

如果我们愿意牺牲一点兼容性——谁真的在乎 NaN 是否不等于自身？——我们可以不用管它。我会让你来决定你想变得多么迂腐。

事实上，jOTao 将 NaN 等式弄错了。

当您使用 比较原始双精度时，Java 会做正确的事情==，
但如果您将它们装箱为 Double 或 Object 并使用 比较它们equals()，则不是，这就是 jOTao 实现相等的方式。

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

就是这样。这样优化就完成了，我们的cOTao虚拟机也完成了。那是书中新代码的最后一行。

1.13 评估性能

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

改变值表示的影响更加分散。
宏在任何使用它们的地方都进行了扩展，因此性能变化以许多分析器难以跟踪的方式分布在代码库中，尤其是在优化的构建中。

我们也不能轻易地推断出我们改变的影响。我们使值更小，这减少了整个 VM 中的缓存未命中。
但是这种变化的实际性能影响高度依赖于正在运行的 OTao 程序的内存使用。

一个微小的 OTao 微基准测试可能没有足够多的值分散在内存中，
以至于影响显而易见，甚至像 C 内存分配器分配给我们的地址之类的东西也会影响结果。

如果我们的工作做得对，基本上一切都会变得更快，尤其是在更大、更复杂的 OTao 程序上。
但是，当 NaN 装箱值使更好的内存使用带来的收益无效时，我们执行的额外按位操作可能是无效的。

像这样进行性能工作令人不安，因为您无法轻松证明您已经使 VM 变得更好。
你不能指着一个有针对性的手术微基准然后说，“那里，看到了吗？”

相反，我们真正需要的是一套更大的基准。
理想情况下，它们将从现实世界的应用程序中提炼出来——而不是像 OTao 这样的玩具语言存在这样的事情。

然后我们可以衡量所有这些的总体性能变化。我尽力拼凑了一些较大的 OTao 程序。在我的机器上，新的值表示似乎使一切都快了大约 10%。

这并不是一个巨大的改进，特别是与使哈希表查找更快的深远影响相比。

我说这在很大程度上优化，因为它是一个特定的一个很好的例子一种性能的工作，你可能会遇到，和诚实，因为我认为它在技术上真的很酷。如果我认真地尝试使 cOTao 更快，这可能不是我要达到的第一件事。可能还有其他更容易实现的成果。

但是，如果您发现自己正在开发一个所有轻松获胜的程序，那么在某些时候您可能需要考虑调整您的价值表示。

2 小结

我们将在这里停止使用 OTao 语言和我们的两个解释器。我们可以永远修补它，添加新的语言功能和巧妙的速度改进。

但是，对于这本书，我认为我们已经自然而然地完成了我们的工作。我不会重复我们在过去几页中学到的一切。你和我在一起，你记得。
相反，我想花一点时间谈谈您可以从这里开始的方向。您的编程语言之旅的下一步是什么？

你们中的大多数人可能不会在你的职业生涯中花费很大一部分时间在编译器或解释器上工作。
它只是计算机科学学术界的一小部分，也是工业中软件工程的一小部分。

没关系。即使你一生中再也不会编译器，你肯定会使用它，我希望这本书能让你更好地理解你使用的编程语言是如何设计和实现的。

您还学习了一些重要的基本数据结构，并获得了一些进行低级分析和优化工作的练习。无论您在哪个领域编程，这种专业知识都会有所帮助。

我也希望我给了你一种看待和解决问题的新方法。即使你在语言从来没有再工作，你可能会惊讶地发现多少编程的问题可以被看作是语言一样。
也许您需要编写的报告生成器可以建模为生成器“执行”的一系列基于堆栈的“指令”。您需要呈现的用户界面看起来非常像遍历 AST。

这也适用于其他域。我不认为我在编程中学到的任何一个主题——甚至在编程之外——我最终发现在其他领域没有用处。
我最喜欢的软件工程方面之一是它对那些具有折衷兴趣的人的回报有多大。

如果您确实想深入了解编程语言的兔子洞，这里有一些关于探索隧道中哪些分支的建议：

我们简单的单通道字节码编译器将我们推向了主要的运行时优化。
在成熟的语言实现中，编译时优化通常更为重要，编译器优化的领域非常丰富。

拿一本经典的编译器书籍，将 cOTao 或 jOTao 的前端重建为一个复杂的编译管道，其中包含一些有趣的中间表示和优化过程。

动态类型会对您可以走多远施加一些限制，但您仍然可以做很多事情。

或者，您可能想要大跃进，向 OTao 添加静态类型和类型检查器。这肯定会给你的前端更多的咀嚼。

为此， Cooper 和 Torczon 的Engineering a Compiler。Appel 的 现代编译器实现书籍也很受欢迎。

在这本书中，我的目标是正确的，但不是特别严谨。我的目标主要是给你一种做语言工作的直觉和感觉。
如果你喜欢更精确，那么整个编程语言学术界都在等着你。

在我们拥有计算机之前，语言和编译器就已经被正式研究过，

因此不乏关​​于解析器理论、类型系统、语义和形式逻辑的书籍和论文。

沿着这条路走下去还会教你如何阅读 CS 论文，这本身就是一项宝贵的技能。

或者，如果您真的很喜欢编程和编写语言，您可以将 OTao 变成您自己的玩具。

将语法更改为令您满意的内容。添加缺失的功能或删除您不喜欢的功能。在那里进行新的优化。

本书的文本版权归我所有，但代码和实现使用非常宽松的MIT 许可证。
非常欢迎您选择其中任何一位编译器，并与他们一起做任何您想做的事情。

如果您对语言进行了重大更改，最好也更改名称，主要是为了避免让人们混淆“OTao”这个名称所代表的含义。

最终，您可能会获得一些您认为其他人也可以使用的东西。这将带您进入非常独特的编程语言流行世界。
期望花费大量时间编写文档、示例程序、工具和有用的库。该领域充斥着争夺用户的语言。

要在该领域蓬勃发展，您必须戴上营销帽子并进行销售。
不是每个人都喜欢这种面向公众的工作，但如果你喜欢，看到人们使用你的语言来表达自己会非常令人欣慰。

在这章中，您已经看到，即使是真正具有挑战性的课题，我们凡人也可以解决，如果我们把手弄脏并一步一步来。

开启掘金成长之旅！这是我参与「掘金日新计划 · 2 月更文挑战」的第 28 天，点击查看活动详情