简介

我们已经在某种程度实现了一个中文编程语言，可以查看 https://bbs.huaweicloud.com/blogs/422573
本文将讨论中文编程语言的性能优化问题，
比如在其原始代码中，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 在同一条船上。
ecology/cinavpnweoqx6_6e95b747c16144928c0cecebfc454acc.png)

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