值的内存表示

这是对书籍 Real World OCaml 中章节 值的内存表示 的改编，经许可在此转载。

本文档涵盖了从 OCaml 类型到运行时值的精确映射，并通过 toplevel 逐步讲解它们。OCaml 值在内存中的内部运行时表示与以下情况相关

• 当你希望与用其他编程语言（例如 C、Rust 等）编写的代码交互时，
• 当你使用各种在 OCaml 二进制文件上运行的外部系统工具时，例如性能分析工具和调试器

OCaml 工具链非常可预测。编译器将它执行的优化魔法数量降至最低，而是依赖于它直接的执行模型来获得良好的性能。凭借一些经验，你可以相当准确地知道一段性能关键的 OCaml 代码在哪里花费了时间。

在本文档的最后，你将能够在 OCaml 值及其内存表示之间进行转换。

OCaml 类型在运行时消失

OCaml 编译器在编译过程中经过几个阶段。第一个阶段是语法检查，在此期间，源文件被解析为抽象语法树 (AST)。下一个阶段是对 AST 进行 _类型检查_。在类型正确的程序中，函数不能使用意外的类型进行应用。例如，print_endline 函数必须接收一个 string 参数，而 int 会导致类型错误。

由于 OCaml 在编译时验证了这些属性，因此它不需要在运行时跟踪太多信息。因此，编译器的后续阶段可以丢弃并简化类型声明，从而使其成为在运行时区分多态值所需的最小子集。与 Java 或 .NET 方法调用相比，这是一个主要的性能优势，在 Java 或 .NET 方法调用中，运行时必须查找对象的具体实例并分派方法调用。这些语言通过 “即时” 动态修补来摊销一部分成本，但 OCaml 更倾向于运行时的简单性。

我们将在 编译器前端：解析和类型检查 和 编译器后端：字节码和原生代码 中更详细地解释此编译管道。-->

我们将在后面的 了解垃圾回收器 中介绍这些值的运行时管理方式。

OCaml 块和值

运行中的 OCaml 程序使用内存块（即 RAM 中连续的字序列）来表示值，例如元组、记录、闭包或数组。当创建这样的值时，OCaml 程序会隐式地分配一块内存

# type t = { foo: int; bar: int };;
type t = { foo : int; bar : int; }
# let x = { foo = 13; bar = 14 };;
val x : t = {foo = 13; bar = 14}

类型声明 t 在运行时不占用任何内存，但随后的 let 绑定会分配一个新的内存块，其中包含两个可用的字空间。一个字包含 foo 字段，另一个字包含 bar 字段。OCaml 编译器将这样的表达式转换为从 OCaml 运行时系统显式分配块。

OCaml 使用统一的内存表示，其中每个 OCaml 变量都存储为一个 _值_。OCaml 值是一个单一的内存字，它可以是一个直接的整数或指向某个其他内存的指针。OCaml 运行时跟踪所有值，以便在不再需要它们时释放它们。因此，它需要能够区分整数和指针值，因为它会扫描指针以查找其他值，但不会跟随不指向任何有意义内容的整数，而只是它们本身的值。

在运行时区分整数和指针

将基本类型（例如整数）封装在记录有关值的额外元数据的另一个数据结构中被称为 _装箱_。装箱值是为了让垃圾回收器 (GC) 更容易地完成它的工作，但以访问装箱值中的数据的额外间接级别为代价。

OCaml 值并不都需要在运行时装箱。相反，值使用每个字的单个标记位来在运行时区分整数和指针。如果块字的最低位为非零，则该值为整数；如果块字的最低位为零，则该值为指针。几种 OCaml 类型映射到此整数表示，包括 bool、int、空列表和 unit。有些类型，比如变体，有时使用此整数表示，有时不使用。特别是，对于变体，常量构造函数，即没有参数的构造函数，例如 None，表示为整数，但像 Some 这样的构造函数，它们携带关联值，则是装箱的。

这种表示方法意味着在 OCaml 中，整数是未装箱的运行时值，因此可以将它们直接存储，而无需分配包装块。它们可以直接传递给其他函数调用，并存储在寄存器中，通常是 OCaml 中使用最便宜、最快的值。

如果值的最低位为零，则该值将被视为内存指针。尽管如此，指针值仍然可以以未修改的方式存储，因为指针保证是字对齐的（底部的位始终为零）。

这种内存表示方法的唯一问题是区分指向 OCaml 值的指针（GC 应该跟踪它们）和指向系统堆的 C 值的指针（GC 不应该跟踪它们）。

该机制很简单，因为运行时系统跟踪了为 OCaml 值分配的堆块。如果指针位于标记为由 OCaml 运行时管理的堆块内，则假定它指向 OCaml 值。如果它指向 OCaml 运行时区域之外，则将其视为指向某个其他系统资源的不透明 C 指针。

关于 OCaml 字对齐指针的一些历史

警觉的读者可能想知道 OCaml 如何保证其所有指针都是字对齐的。在过去，当 Sparc、MIPS 和 Alpha 等 RISC 芯片很常见时，指令集体系结构禁止未对齐的内存访问，这会导致 CPU 异常，从而终止程序。因此，历史上所有指针都被四舍五入到体系结构字大小（通常为 32 或 64 位）。

现代 CISC 处理器（如 Intel x86）确实支持未对齐的内存访问，但如果访问是字对齐的，芯片的运行速度仍然更快。因此，OCaml 只是规定所有指针都必须是字对齐的，这保证了任何有效指针的底部几位都将为零。将最低位设置为非零值是标记整数的一种简单方法，代价是损失了这一个位的精度。

更警觉的读者会想知道使用这种标记表示法进行整数算术的性能影响。由于最低位被设置，对整数的任何操作都必须将最低位右移以恢复“原生”值。在这种情况下，本机代码 OCaml 编译器会生成有效的 x86 汇编代码，利用现代处理器的指令尽可能地隐藏额外的移位操作。加法是一个单独的 LEA x86 指令，减法可以是两个指令，乘法只需要多几个指令。

块和值

OCaml 块是堆上分配的基本单元。块由一个字大小的头部（根据 CPU 架构，可以是 32 位或 64 位）以及可变长度的数据组成，这些数据可以是不透明的字节，也可以是 字段 数组。头部有一个多用途的标记字节，它定义了是否将后续数据解释为不透明的字节或 OCaml 字段。

GC 永远不会检查不透明的字节。如果标记指示存在 OCaml 字段数组，则其内容将被视为更多有效的 OCaml 值。GC 始终检查字段并将其作为前面描述的收集过程的一部分进行跟踪。

size 字段记录块在内存中的长度（以字为单位）。在 32 位平台上，它是 22 位，这就是 OCaml 字符串在该架构上限制为 16 MB 的原因。如果您需要更大的字符串，请切换到 64 位主机，或者使用 Bigarray 模块。

2 位的 color 字段由 GC 用于跟踪标记清除收集过程中的状态。我们将在 了解垃圾收集器 中回到这个字段。无论如何，这个标记都不会暴露给 OCaml 源代码。

块的标记字节是多用途的，它指示数据数组表示不透明的字节还是字段。如果块的标记大于或等于 No_scan_tag（251），则块的数据都是不透明的字节，不会被收集器扫描。最常见的这类块是 string 类型，我们将在本章后面详细介绍。

块内值的精确表示取决于它们的静态 OCaml 类型。所有 OCaml 类型都被提炼成 值，并在下面进行了总结。

• int 或 char 直接存储为值，左移 1 位，最低位设置为 1。

• unit、[]、false 全部存储为 OCaml int 0。

• true 存储为 OCaml int 1。

• Foo | Bar 变体存储为从 0 开始的升序 OCaml int。

• 带参数的 Foo | Bar of int 变体被装箱，而没有参数的变体不被装箱。

• 带参数的多态变体与普通变体相比，在额外的头部词中装箱，以存储值。没有参数的多态变体不被装箱。

• 浮点数存储为一个块，其中包含一个包含双精度浮点数的字段。

• 字符串是字对齐的字节数组，具有显式长度。

• [1; 2; 3] 列表存储为 1::2::3::[]，其中 [] 是一个 int，h::t 是一个带有标签 0 和两个参数的块。

• 元组、记录和数组存储为值的 C 数组。数组可以是可变大小，但元组和记录是固定大小的。

• 所有都是浮点数的记录或数组使用特殊的标记来表示未装箱的浮点数数组，或者仅包含 float 字段的记录。

整数、字符和其他基本类型

许多基本类型在运行时有效地存储为未装箱的整数。本机 int 类型是最明显的，尽管由于标记位，它会损失一位精度。其他原子类型，例如 unit 和空列表 [] 值，存储为常量整数。布尔值分别具有 1 和 0 的值，分别代表 true 和 false。

这些基本类型（如空列表和 unit）使用起来非常有效，因为整数永远不会在堆上分配。如果函数参数不多，它们可以直接传递到寄存器中，并且不会出现在堆栈上。现代体系结构（如 x86_64）拥有大量备用寄存器，可以进一步提高使用未装箱整数的效率。

元组、记录和数组

元组、记录和数组在运行时都被表示为一个带有标签 0 的块。元组和记录具有在编译时确定的固定大小，而数组可以是可变长度的。虽然数组在 OCaml 类型系统中被限制为包含单个类型的元素，但这并非内存表示的要求。

您可以使用 Obj 模块来检查块和直接整数之间的差异，该模块将值的内部表示公开给 OCaml 代码

# Obj.is_block (Obj.repr (1,2,3));;
- : bool = true
# Obj.is_block (Obj.repr 1);;
- : bool = false

Obj.repr 函数检索任何 OCaml 值的运行时表示。Obj.is_block 检查最低位以确定值是块头部还是未装箱的整数。

浮点数和数组

OCaml 中的浮点数始终存储为完整的双精度值。单个浮点值存储为一个块，其中包含一个包含该数字的字段。此块设置了 Double_tag，它向收集器发出信号，表明浮点值不应被扫描

# Obj.tag (Obj.repr 1.0);;
- : int = 253
# Obj.double_tag;;
- : int = 253

由于每个浮点值都装箱在单独的内存块中，因此与未装箱的整数相比，处理大量的浮点数数组可能效率低下。因此，OCaml 特别处理仅包含 float 类型的记录或数组。这些存储在一个块中，该块包含直接打包在数据部分的浮点数，并设置了 Double_array_tag，向收集器发出信号，表明内容不是 OCaml 值。

首先，让我们检查浮点数数组是否确实具有与普通浮点值不同的标记号

# Obj.double_tag;;
- : int = 253
# Obj.double_array_tag;;
- : int = 254

这告诉我们，浮点数数组的标记值为 254。现在让我们使用 Obj.tag 函数测试一些示例值，以检查分配的块是否具有预期的运行时标记，并使用 Obj.double_field 从块内检索浮点数

# Obj.tag (Obj.repr [| 1.0; 2.0; 3.0 |]);;
- : int = 254
# Obj.tag (Obj.repr (1.0, 2.0, 3.0) );;
- : int = 0
# Obj.double_field (Obj.repr [| 1.1; 2.2; 3.3 |]) 1;;
- : float = 2.2
# Obj.double_field (Obj.repr 1.234) 0;;
- : float = 1.234

我们测试的第一件事是，浮点数数组具有正确的未装箱浮点数数组标记值（254）。但是，下一行测试的是浮点值的元组，而不是以相同的方式进行优化，并且具有正常的元组标记值（0）。

只有记录和数组可以具有浮点数数组优化，对于记录，每个字段都必须是浮点数。

变体和列表

没有为其任何分支添加额外参数的基本变体类型，只是存储为 OCaml 整数，从 0 开始（从左边的变体开始，并带有参数）。

# type t = Apple | Orange | Pear;;
type t = Apple | Orange | Pear
# ((Obj.magic (Obj.repr Apple)) : int);;
- : int = 0
# ((Obj.magic (Obj.repr Pear)) : int);;
- : int = 2
# Obj.is_block (Obj.repr Apple);;
- : bool = false

Obj.magic 不安全地强制在任何两种 OCaml 类型之间进行类型转换；在此示例中，int 类型提示将检索运行时整数值。Obj.is_block 确认该值不是更复杂的块，而只是一个 OCaml int。

带有参数的变体稍微复杂一些。它们存储为块，其中值的 标记 从 0 开始升序排列（从带有参数的最左边变体开始计数）。参数存储为块中的词

# type t = Apple | Orange of int | Pear of string | Kiwi;;
type t = Apple | Orange of int | Pear of string | Kiwi
# Obj.is_block (Obj.repr (Orange 1234));;
- : bool = true
# Obj.tag (Obj.repr (Orange 1234));;
- : int = 0
# Obj.tag (Obj.repr (Pear "xyz"));;
- : int = 1
# (Obj.magic (Obj.field (Obj.repr (Orange 1234)) 0) : int);;
- : int = 1234
# (Obj.magic (Obj.field (Obj.repr (Pear "xyz")) 0) : string);;
- : string = "xyz"

在前面的示例中，Apple 和 Kiwi 值仍然存储为具有 0 和 1 值的普通 OCaml 整数。Orange 和 Pear 值都有参数，并且存储为块，它们的标记从 0 开始升序排列（因此 Pear 的标记为 1，如使用 Obj.tag 所验证的那样）。最后，参数是包含块内 OCaml 值的字段，可以使用 Obj.field 检索它们。

列表存储的表示方法与将列表编写为具有 Nil 和 Cons 的变体类型完全相同。空列表 [] 是一个整数 0，后续的块具有标签 0 和两个参数：一个包含当前值的块和一个指向列表其余部分的指针。

Obj 模块被认为是有害的

Obj 是一个未公开的模块，它公开了 OCaml 编译器和运行时的内部机制。它对于检查和理解代码在运行时的行为非常有用，但除非您了解其影响，否则 永远不要 在生产代码中使用它。该模块绕过了 OCaml 类型系统，从而可能导致内存损坏和分段错误。

一些定理证明器（如 Coq）会输出内部使用 Obj 的代码，但外部模块签名永远不会暴露它。除非您也拥有与使用 Obj 相伴的正确性机器证明，否则请避免使用它，除非用于调试！

由于这种编码，每个类型定义大约有 240 个带参数的变体限制，但没有参数的变体数量的唯一限制是本机整数的大小（31 位或 63 位）。这个限制是由于标记字节的大小以及一些高编号的标记是保留的。

多态变体

多态变体在编写代码时比普通变体更灵活，但在运行时效率略低。这是因为在编译时没有太多静态信息可用于优化其内存布局。

没有参数的多态变体存储为一个未装箱的整数，因此只占用一个内存字，就像一个普通的变体一样。这个整数值是通过对变体名称应用哈希函数来确定的。哈希函数通过compiler-libs包公开，该包揭示了OCaml编译器的一些内部细节。

# #require "ocaml-compiler-libs.common";;
# Btype.hash_variant "Foo";;
- : int = 3505894
# (Obj.magic (Obj.repr `Foo) : int);;
- : int = 3505894

哈希函数设计为在32位和64位架构上给出相同的结果，因此内存表示在不同的CPU和主机类型之间是稳定的。

当数据类型构造函数中包含参数时，多态变体使用的内存空间比普通变体多。普通变体使用标签字节来编码变体值并保存内容字段，但这个单个字节不足以编码多态变体的哈希值。它们必须分配一个新的块（带有标签0）并将值存储在那里。因此，带有构造函数的多态变体比普通变体构造函数多使用一个内存字。

另一个比普通变体效率低的情况是，当一个多态变体构造函数具有多个参数时。普通变体将参数作为一个扁平的块来保存，每个条目都有多个字段，但多态变体必须采用更灵活的统一内存表示，因为它们可以在跨编译单元的不同上下文中重用。它们为参数分配一个元组块，该元组块由变体的参数字段指向。因此，这种变体有三个额外的字，以及由于元组而产生的额外的内存间接访问。

额外的空间使用在典型的应用程序中通常并不显著，多态变体比普通变体提供了更多的灵活性。但是，如果你正在编写需要高性能或必须在有限内存范围内运行的代码，那么运行时布局至少是可预测的。OCaml编译器不会因为优化过程而切换内存表示。这使你可以通过参考这些指南和源代码来预测精确的运行时布局。

字符串值

OCaml string（及其可变的表亲bytes）是标准的OCaml块，其头大小定义了字符串的机器字大小。String_tag（252）高于No_scan_tag，表明块的内容对于收集器来说是不透明的。块的内容是字符串的内容，用填充字节对齐块以使其位于字边界。

在32位机器上，填充是根据字符串长度和字大小的模来计算的，以确保结果是字对齐的。64位机器将潜在填充扩展到7个字节而不是3个字节。给定一个字符串长度模4

• 0 的填充为 00 00 00 03
• 1 的填充为 00 00 02
• 2 的填充为 00 01
• 3 的填充为 00

这种字符串表示是一种巧妙的方法，可以确保内容始终被填充字终止，并且仍然可以在不扫描整个字符串的情况下有效地计算其长度。使用以下公式

number_of_words_in_block * sizeof(word) - last_byte_of_block - 1

保证的NULL终止在将字符串传递给C时很方便，但并不依赖于它从OCaml代码中计算长度。因此，OCaml字符串可以在字符串中的任何地方包含NULL字节。

应该注意，任何接收这些缓冲区的C库函数也应该能够处理缓冲区内容中的任意字节，并且不期望C字符串。例如，C memcopy 或 memmove 标准库函数可以操作任意数据，但 strlen 或 strcpy 都需要一个NULL终止的缓冲区，并且它们都没有用于在其内容中编码NULL值的机制。

自定义堆块

OCaml 通过Custom_tag 支持自定义堆块，该标签使运行时能够对OCaml值执行用户定义的操作。自定义块像普通块一样存在于OCaml堆中，可以是用户想要的任何大小。Custom_tag（255）高于No_scan_tag，因此不会被GC扫描。

自定义块中的数据第一个字是指向自定义操作struct的C指针。自定义块不能包含指向OCaml块的指针，并且对GC来说是不透明的。

struct custom_operations {
  char *identifier;
  void (*finalize)(value v);
  int (*compare)(value v1, value v2);
  intnat (*hash)(value v);
  void (*serialize)(value v,
                    /*out*/ uintnat * wsize_32 /*size in bytes*/,
                    /*out*/ uintnat * wsize_64 /*size in bytes*/);
  uintnat (*deserialize)(void * dst);
  int (*compare_ext)(value v1, value v2);
};

自定义操作指定了运行时应如何执行多态比较、哈希和二进制编组。它们还可选地包含一个终结器，运行时在块被垃圾回收之前调用它。这个终结器与普通的OCaml终结器（如由Gc.finalize创建并在理解垃圾收集器中解释）无关。相反，它们用于调用C清理函数，例如free。

使用Bigarray管理外部内存

自定义块的一个常见用法是直接从OCaml内部管理外部系统内存。Bigarray接口最初是为了与Fortran代码交换数据而设计的，它将系统内存块映射为多维数组，可以从OCaml访问。Bigarray操作直接在外部内存上执行，不需要将它复制到OCaml堆中（对于大型数组来说，这是一个潜在的昂贵操作）。

Bigarray的应用范围远远超出了科学计算，许多Core库将其用于通用 I/O。

Iobuf : Iobuf 模块将 I/O 缓冲区映射为一维字节数组。它提供了一个滑动窗口接口，允许消费者进程在缓冲区被生产者填充时从缓冲区读取。这使OCaml能够使用由操作系统外部分配的 I/O 缓冲区，而无需任何额外的数据复制。

Bigstring : Bigstring 模块提供了一个类似于String的接口，它在内部使用Bigarray。Bigbuffer 将这些集合到可扩展的字符串缓冲区中，这些缓冲区可以完全在外部系统内存上运行。

Lacaml 库不是 Core 的一部分，但它提供了对广泛使用的 BLAS 和 LAPACK 数学 Fortran 库的推荐接口。这些允许开发人员为需要线性代数的应用程序编写高性能数值代码。它支持大型向量和矩阵，但具有 OCaml 的静态类型安全性，使其更容易编写安全的算法。

结论

我们涵盖了从OCaml类型到它们在内存中的内部运行时表示的精确映射，这应该使你能够更好地理解各种调试和分析工具的输出，以及如何将你的OCaml代码与来自其他语言的代码集成。

其他推荐的教程

1. 理解垃圾收集器
2. 调用 C 库