值的記憶體表示法

這是改編自《值的記憶體表示法》一章，出自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 值並非全部都必須在執行時進行裝箱 (boxed)。相反地，值會使用每個字組 (word) 一個單一位元標籤來區分執行時的整數和指標。如果區塊字組的最低位元為非零值，則該值為整數；如果最低位元為零，則該值為指標。一些 OCaml 型別會對應到這種整數表示法，包括 bool、int、空列表和 unit。某些型別，如變體 (variants)，有時會使用這種整數表示法，有時則不會。特別是對於變體，常數建構子 (constant constructors)，即沒有參數的建構子，如 None，會被表示為整數，但帶有相關值的建構子，如 Some，則會被裝箱。

這種表示法意味著整數在 OCaml 中是未裝箱的執行時值，因此可以直接儲存，而無需配置包裝區塊。它們可以直接以暫存器的形式傳遞給其他函式呼叫，並且通常是 OCaml 中使用最便宜且最快的值。

如果值的最低位元為零，則該值會被視為記憶體指標。儘管如此，指標值仍然可以未經修改地儲存，因為保證指標是對齊字組的 (word-aligned) (最低位元始終為零)。

這種記憶體表示法唯一剩下的問題是如何區分指向 OCaml 值的指標 (應該由 GC 追蹤) 和指向系統堆積中 C 值的指標 (不應該追蹤)。

其機制很簡單，因為執行時系統會追蹤它為 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 型別都會被提取到 values 中，並總結如下。

• int 或 char 直接儲存為值，左移 1 位，最低有效位元設定為 1。

• unit、[]、false 都儲存為 OCaml int 0。

• true 儲存為 OCaml int 1。

• Foo | Bar 變體儲存為遞增的 OCaml int，從 0 開始。

• 帶有參數的 Foo | Bar of int 變體會被裝箱，而沒有參數的變體則不會被裝箱。

• 與普通變體相比，帶有參數的多型變體會被裝箱，並帶有一個額外的標頭字組來儲存值。沒有參數的多型變體則不會被裝箱。

• 浮點數儲存為一個區塊，其中包含一個包含雙精度浮點數的單一欄位。

• 字串是對齊字組的位元組陣列，帶有明確的長度。

• [1; 2; 3] 列表儲存為 1::2::3::[]，其中 [] 是一個整數，而 h::t 是一個標籤為 0 且帶有兩個參數的區塊。

• 元組、記錄和陣列儲存為 C 值陣列。陣列的大小可變，但元組和記錄的大小是固定的。

• 全部為浮點數的記錄或陣列使用特殊的標籤來表示未裝箱的浮點數陣列，或是只有 float 欄位的記錄。

整數、字元和其他基本型別

許多基本型別在執行時會有效率地儲存為未裝箱的整數。原生 int 型別是最明顯的例子，儘管它會因標籤位元而損失一位元的精確度。其他原子型別，如 unit 和空列表 [] 值，會儲存為常數整數。布林值對於 true 和 false 分別具有值 1 和 0。

這些基本型別，如空列表和 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 的值仍然以正常的 OCaml 整數形式儲存，其值分別為 0 和 1。 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

當將字串傳遞到 C 時，保證的 NULL 終止非常方便，但是它並不依賴於從 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 模組提供了一個使用Bigarray內部的類似 String 的介面。Bigbuffer 將這些收集到可擴展的字串緩衝區中，這些緩衝區可以在外部系統記憶體上完全執行。

Lacaml 函式庫不是 Core 的一部分，但提供了廣泛使用的 BLAS 和 LAPACK 數學 Fortran 函式庫的建議介面。這些介面允許開發人員為需要線性代數的應用程式編寫高效能的數值程式碼。它支援大型向量和矩陣，但具有 OCaml 的靜態類型安全性，使其更容易編寫安全的演算法。

結論

我們介紹了從 OCaml 類型到其內部運行時記憶體表示的精確對應關係，這應該使您能夠更好地了解各種除錯和分析工具的輸出，以及如何將 OCaml 程式碼與其他語言的程式碼整合。

其他建議的教學課程

1. 了解垃圾收集器
2. 呼叫 C 函式庫