为什么OCaml中的int只有31位?

在其他地方没有看到这个“function”。 我知道第32位是用于垃圾收集。 但是为什么只有整数而不是其他基本types呢?

这被称为带标签的指针表示,是几十年来在许多不同的解释器,虚拟机和运行时系统中使用的一个相当常见的优化技巧。 几乎每个Lisp实现都使用它们,许多Smalltalk VM,许多Ruby解释器,等等。

通常,在这些语言中,你总是传递指向对象的指针。 一个对象本身由一个对象头部组成,它包含对象元数据(如对象types,类别,访问控制限制或安全注解等),然后是实际的对象数据本身。 所以,一个简单的整数将被表示为一个指针加上一个由元数据和实际整数组成的对象。 即使是非常紧凑的表示forms,对于一个简单的整数来说也是6字节。

另外,不能将这样的整数对象传递给CPU来执行快速整数运算。 如果要添加两个整数,则实际上只有两个指针,它们指向要添加的两个整数对象的对象标题的开头。 所以,你首先需要对第一个指针进行整数运算,将偏移量添加到整数数据所在的对象中。 那么你必须取消这个地址。 再次使用第二个整数。 现在你有两个整数你实际上可以要求CPU添加。 当然,你现在需要构造一个新的整数对象来保存结果。

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

然而,诀窍是像所谓的不可变值types,像整型,你通常不需要在对象头中的所有元数据:你可以把所有的东西都拿出来,简单地合成它(这是VM-nerd-说“假”),当有人关心看。 一个整数总是Integer类,不需要单独存储这些信息。 如果有人使用reflection来找出整型的类,那么你只需要回复Integer而且没有人会知道你实际上并没有将这些信息存储在对象头中,事实上,甚至没有对象头(或一个东西)。

所以,诀窍是将对象的值存储在指向对象的指针内,将二者合并为一个。

有一些CPU实际上在指针内有额外的空间(所谓的标签位 ),允许你在指针本身中存储有关指针的额外信息。 额外的信息,如“这实际上不是一个指针,这是一个整数”。 例子包括Burroughs B5000,各种Lisp机器或AS / 400。 不幸的是,目前大多数主streamCPU都没有这个function。

但是,有一个出路:当地址不在字边界上alignment时,大多数当前的主streamCPU工作速度要慢得多。 有些甚至根本不支持未alignment的访问。

这意味着在实践中, 所有的指针都可以被4整除,这意味着它们总是以两个0位结束。 这允许我们区分实际指针(以00结尾)和实际上是伪装的指针(以1结尾的指针)。 而且它仍然留给我们所有的以10结束的指针来做其他的事情。 而且,大多数现代操作系统为自己保留了非常低的地址,这给了我们另一个混乱的地方(以24 0 s开始,以00结尾的指针)。

所以,你可以将一个31位的整数编码成一个指针,只要把它移到左边1位,然后加1即可。 而且你可以用它们来执行非常快的整数运算,只需简单地将它们转换成适当的(有时甚至不需要)。

我们如何处理这些其他地址空间? 那么典型的例子就是在另一个大的地址空间中编码float s以及一些特殊的对象,比如truefalsenil ,127个ASCII字符,一些常用的短string,空列表,空对象,空数组和所以在0地址附近。

例如,在MRI,YARV和Rubinius Ruby解释器中,整数按照上面描述的方式进行编码,将false编码为地址0 (这恰好也是 C中的false的表示),如地址2恰好是true的C代表转移了一位)和nil

请参阅https://ocaml.org/learn/tutorials/performance_and_profiling.html中的“整数,标记位,堆分配值的表示”一节。;

简单的答案是,它是为了performance。 将parameter passing给函数时,它将作为整数或指针传递。 在机器级别的语言级别,无法判断一个寄存器是否包含整数或指针,它只是一个32位或64位的值。 所以OCaml运行时间检查标记位,以确定它收到的是一个整数还是一个指针。 如果标签位被设置,那么该值是一个整数,并传递给正确的过载。 否则,它是一个指针,types被查找。

为什么只有整数有这个标签? 因为一切都是作为指针传递的。 传递的是一个整数或指向其他数据types的指针。 只有一个标签位,只能有两种情况。

这不是完全“用于垃圾回收”。 它用于内部区分指针和未装箱的整数。

我必须添加这个链接来帮助OP了解更多64位OCaml的63位浮点types

虽然文章的标题似乎是float ,但实际上却是在谈论extra 1 bit

OCaml运行时允许通过types的统一表示来进行多态。 每个OCaml值被表示为一个单词,因此可以有一个单一的实现,例如“事物列表”,具有访问(例如List.length)和构build(例如List.map)这些列表的函数无论是整数列表,浮点数列表还是整数列表,它们的工作方式都是一样的。

任何不适合的单词都会分配在堆中的一个块中。 表示这个数据的字就是指向这个块的指针。 由于堆只包含字块,所有这些指针都是alignment的:它们的less数最小有效位总是未设置。

自variables的构造函数(像这样:type fruit = Apple | Orange | Banana)和整数并不代表太多信息,它们需要在堆中分配。 他们的代表是拆箱。 数据直接在单词内部,否则将是一个指针。 所以虽然list的列表实际上是一个指针列表,但是ints列表包含了一个间接一个的ints。 访问和构build列表的函数不会注意,因为ints和指针具有相同的大小。

尽pipe如此,垃圾收集器需要能够识别来自整数的指针。 一个指针指向堆中的一个格式正确的块,这个块在定义上是活着的(因为它正在被GC访问),并且应该被标记为这样。 一个整数可以有任何值,如果不采取预防措施,可能会意外地看起来像一个指针。 这可能会导致死区看起来活跃,但更糟糕的是,它也会导致GC改变它认为是活动块的标题的位,当它实际上跟随一个看起来像一个指针的整数,并搞乱了用户数据。

这就是为什么拆箱整数为OCaml编程器提供31位(对于32位OCaml)或63位(对于64位OCaml)。 在表示中,在幕后,总是设置包含整数的单词的最低有效位,以将其与指针区分开来。 31或63位整数是相当不寻常的,所以任何使用OCaml的人都知道这一点。 OCaml的用户通常不知道为什么64位OCaml没有63位的无箱浮点types。

为什么OCaml中的int只有31位?

基本上,为了在主导运算是模式匹配并且主导数据types是变体types的Coq定理certificate器上获得最佳性能。 最好的数据表示被发现是一个使用标签来区分指针和未装箱数据的统一表示。

但是为什么只有整数而不是其他基本types呢?

不仅是int 。 其他types,如char和枚举使用相同的标记表示。