简介
本文继续讨论中文编程语言的性能优化问题，
比如在其原始代码中，key->hash % capacity;是性能瓶颈。
由于表容量总是2的幂，作者提出使用位掩码(key->hash & (capacity - 1);)替代模运算，以提高效率。
这个优化使基准测试中的执行批次几乎翻倍，提升了VM性能。
此外，文章还提及了一种名为NaN boxing的技术，用于减少动态类型语言中值的表示大小，
通过利用浮点数的NaN位存储额外信息，如类型标签和指针，从而提高缓存效率。
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;
}
}
当运行以前的基准-我的机器上，至少-在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%。
这更符合我们希望看到的情况，并表明我们的优化不仅使程序更快，而且以我们预期的方式使其更快 。
探查器对于验证解决方案和发现问题一样有用。
2 黑盒法
下一个优化有非常不同的感觉。值得庆幸的是，尽管名字很奇怪，但它并不涉及冒犯
你。
它是不同的，但并没有那么不同。通过我们之前的优化，分析器会告诉我们问题出在哪里，我们只需要巧妙地想出解决方案。
这种优化更加微妙，其性能影响更加分散在虚拟机中。分析器不会帮助我们想出这个。
相反，它是由深入思考机器架构的最低层次的人发明的。
我不确定是谁首先提出了这个。我能找到的最早来源是 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 在同一条船上。
3 什么是（或不是）数字？
在开始优化之前，我们需要真正了解 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 的其余部分应该可以正常工作。
4 有条件的支持
我知道你脑子里还不清楚这个新表示的细节。别担心，它们会随着我们的实施而具体化。在我们开始之前，我们将放置一些编译时脚手架。
对于我们之前的优化，我们重写了之前的慢代码，并称之为完成。这个有点不同。
NaN 装箱依赖于芯片如何表示浮点数和指针的一些非常底层的细节。
它 可能适用于您可能遇到的大多数 CPU，但您永远无法完全确定。
如果我们的 VM 仅仅因为其价值表示而完全失去对架构的支持，那将会很糟糕。
为了避免这种情况，我们将同时支持 Value 的旧标记联合实现和新的 NaN-boxed 形式。
我们在编译时使用这个标志选择我们想要的表示：
如果已定义，VM 将使用新形式。否则，它将恢复到旧样式。
关心值表示细节的几段代码——主要是用于包装和解包值的少数宏——根据是否设置了这个标志而有所不同。
虚拟机的其余部分可以继续其愉快的方式。
大多数工作发生在“值”模块中，我们为新类型添加了一个部分。
当启用 NaN 装箱时，Value 的实际类型是一个平面的、无符号的 64 位整数。
我们可以使用 double 代替，这将使处理 OTao 数的宏更简单一些。
但是所有其他宏都需要进行按位运算，而 uint64_t 是一种更友好的类型。
在这个模块之外，VM 的其余部分并不真正关心一种或另一种方式。
在我们开始重新实现这些宏之前，我们关闭旧表示定义末尾的#else分支 #ifdef。
我们剩下的任务只是简单地#ifdef用已经在#else边上的所有东西的新实现来填充第一部分。我们将一次处理一种值类型，从最简单到最难。
5 数字的支持
我们将从数字开始，因为它们在 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 位，再加上一个额外的以躲避英特尔值。
