integer - 为什么 OCaml 中的 int 只有 31 位？

Question

还没有在其他任何地方看到过这个“功能”。我知道第 32 位用于垃圾收集。但是为什么它只适用于整数而不适用于其他基本类型呢？

Answer 1

这被称为标记指针表示，并且是几十年来在许多不同的解释器、VM 和运行时系统中使用的一种非常常见的优化技巧。几乎每个 Lisp 实现都使用它们，许多 Smalltalk VM，许多 Ruby 解释器，等等。

通常，在这些语言中，您总是传递指向对象的指针。一个对象本身由一个对象头组成，其中包含对象元数据(如对象的类型、它的类、可能访问控制限制或安全注释等)，然后是实际的对象数据本身。因此，一个简单的整数将被表示为一个指针加上一个由元数据和实际整数组成的对象。即使使用非常紧凑的表示，对于一个简单的整数来说，这也类似于 6 字节。

此外，您不能将这样的整数对象传递给 CPU 来执行快速整数运算。如果要添加两个整数，实际上只有两个指针，它们指向要添加的两个整数对象的对象头的开头。因此，您首先需要对第一个指针执行整数运算，以将偏移量添加到存储整数数据的对象中。然后您必须取消引用该地址。对第二个整数再次执行相同操作。现在您有两个整数，您实际上可以要求 CPU 相加。当然，您现在需要构造一个新的整数对象来保存结果。

所以，为了执行一个整数加法，你实际上需要执行三个整数加法加两个指针解引用加一个对象构造。而你几乎占用了 20 字节。

然而，诀窍在于，对于所谓的不可变值类型(如整数)，您通常不需要对象头中的所有元数据:您可以将所有这些内容都保留下来，然后简单地合成它(这是 VM-nerd-说“假货”)，当有人愿意看的时候。整数将始终具有类 Integer ，无需单独存储该信息。如果有人使用反射来计算整数的类别，您只需回复 Integer没有人会知道您实际上并没有将这些信息存储在对象头中，事实上，甚至没有对象头(或对象)。

因此，诀窍是将对象的值存储在指向对象的指针中，有效地将两者合二为一。

有些 CPU 在指针(所谓的标记位)内实际上有额外的空间，允许您在指针本身内存储有关指针的额外信息。额外的信息，如“这实际上不是一个指针，这是一个整数”。示例包括 Burroughs B5000、各种 Lisp 机器或 AS/400。不幸的是，目前大多数主流 CPU 都没有该功能。

然而，有一个出路:本地址在字边界上不对齐时，大多数当前的主流 CPU 的工作速度会明显变慢。有些甚至根本不支持非对齐访问。

这意味着实际上，所有指针都可以被 4 整除，这意味着它们总是以两个 0 结尾。位。这使我们能够区分真正的指针(以 00 结尾)和实际上是伪装整数的指针(以 1 结尾的指针)。它仍然给我们留下了所有以 10 结尾的指针。可以自由地做其他事情。此外，大多数现代操作系统为自己保留了非常低的地址，这给了我们另一个可以处理的区域(例如，以 24 0 s 开头并以 00 结尾的指针)。

因此，您可以将 31 位整数编码为指针，只需将其向左移动 1 位并添加 1。到它。你可以用它们执行非常快速的整数运算，只需适本地移动它们(有时甚至不需要)。

我们如何处理那些其他地址空间？嗯，典型的例子包括编码 float s 在其他大地址空间和许多特殊对象，如 true , false , nil 、127个ASCII字符、一些常用的短字符串、空列表、空对象、空数组等0附近地址。

例如，在 MRI、YARV 和 Rubinius Ruby 解释器中，整数按照我上面描述的方式进行编码，false被编码为地址 0 (恰好也是 C 中 false 的表示)，true作为地址 2 (恰好是 true 移位一位的 C 表示)和 nil如 4 .