了解垃圾回收機制

這是改編自 《Real World OCaml》書中的 了解垃圾回收機制 章節，經授權在此轉載。

本章節包含 Stephen Weeks 和 Sadiq Jaffer 的貢獻。

我們在先前的 值的記憶體表示法 中已經描述過個別 OCaml 變數的執行期格式。當您執行程式時，OCaml 會透過定期掃描已分配的值，並在不再需要時釋放它們，來管理這些變數的生命週期。這反過來意味著您的應用程式不需要手動實作記憶體管理，並且大大降低記憶體洩漏潛入程式碼的可能性。

OCaml 執行期是一個 C 函式庫，提供可以從執行中的 OCaml 程式呼叫的常式。執行期管理一個堆積，它是從作業系統取得的記憶體區域集合。執行期使用此記憶體來保存堆積區塊，並在 OCaml 程式提出分配請求時，用 OCaml 值填滿這些區塊。

標記與清除垃圾回收

當沒有足夠的記憶體來滿足已分配堆積區塊池的分配請求時，執行期系統會調用垃圾回收器（GC）。OCaml 程式在完成值的使用後無法明確釋放值。相反地，GC 會定期判斷哪些值是活的，哪些值是死的，也就是不再使用。死的數值會被回收，它們的記憶體會被釋放以供應用程式重複使用。

GC 不會持續追蹤值的分配和使用情況。相反地，它會定期從應用程式始終可以存取的一組根值（例如堆疊）開始掃描它們。GC 維護一個有向圖，其中堆積區塊是節點，如果 `b1` 的某些欄位是指向 `b2` 的指標，則從堆積區塊 `b1` 到堆積區塊 `b2` 之間會有一條邊。

所有可從根透過圖中邊到達的區塊都必須保留，而無法到達的區塊可以被應用程式重複使用。OCaml 用來執行此堆積遍歷的演算法通常稱為標記與清除垃圾回收，我們現在將進一步解釋它。

分代垃圾回收

一般的 OCaml 編程風格涉及分配許多小型值，這些值會在短時間內使用，然後不再存取。OCaml 利用這個事實，透過使用分代 GC 來提高效能。

分代 GC 維護單獨的記憶體區域，以根據區塊存活時間的長短來保存區塊。OCaml 的堆積分為兩個這樣的區域

• 一個小型、固定大小的次要堆積，其中大多數區塊最初會被分配

• 一個較大、大小可變的主要堆積，用於存放存活時間較長的區塊

典型的函數式程式設計風格意味著年輕的區塊往往會早逝，而舊的區塊往往會比年輕的區塊停留更長的時間。這通常被稱為分代假設。

OCaml 對主要堆積和次要堆積使用不同的記憶體佈局和垃圾回收演算法，以考慮這種分代差異。我們接下來將更詳細地解釋它們的差異。

快速次要堆積

次要堆積是存放大多數短暫值的地方。它由一個包含一系列 OCaml 區塊的連續虛擬記憶體區塊組成。如果有空間，分配新區塊是一個快速、恆定時間的操作，只需要幾個 CPU 指令。

為了對次要堆積區進行垃圾回收，OCaml 使用複製回收機制，將次要堆積區中所有存活的區塊移動到主要堆積區。這需要的工作量與次要堆積區中存活的區塊數量成正比，根據世代假說，這個數量通常很小。一般來說，垃圾收集器在執行時會停止世界（也就是暫停應用程式），這也是為什麼它必須快速完成，讓應用程式能以最小的干擾繼續執行的原因。

在次要堆積區上配置記憶體

次要堆積區是虛擬記憶體中一個連續的區塊，大小通常為數 MB，以便可以快速掃描。

執行時環境將次要堆積區的邊界儲存在兩個指標中，這兩個指標界定了堆積區的起始和結束位置（caml_young_start 和 caml_young_end，但為了簡潔起見，我們將省略 caml_young 前綴）。base 是系統 malloc 返回的記憶體位址，而 start 則是以 base 為基礎，對齊到下一個最近的字邊界，以便更容易儲存 OCaml 值。

在一個新的次要堆積區中，limit 等於 start，而目前的 ptr 將等於 end。當區塊被配置時，ptr 會遞減，直到達到 limit，此時會觸發次要垃圾回收。

在次要堆積區中配置一個區塊，只需要將 ptr 遞減區塊的大小（包括標頭），並檢查它是否不小於 limit。如果沒有足夠的空間可以容納該區塊，而不會遞減超過 limit，則會觸發次要垃圾回收。在大多數 CPU 架構上，這是一個非常快速的檢查（沒有分支）。

了解配置

您可能會想知道為什麼需要 limit，因為它似乎總是等於 start。這是因為執行時環境排程次要堆積區回收最簡單的方法是將 limit 設定為等於 end。完成此操作後，下一次的配置永遠不會有足夠的空間，並且總是會觸發垃圾回收。這種提早回收的原因有很多內部因素，例如處理待處理的 UNIX 訊號，但它們通常對應用程式程式碼沒有影響。

可以以迴圈或遞迴的方式編寫程式碼，這些程式碼可能需要很長時間才能進行配置（如果有的話）。為了確保需要中斷執行中的 OCaml 程式的 UNIX 訊號和其他內部管理仍然會發生，編譯器會在產生的原生程式碼中引入輪詢點。

這些輪詢點會檢查 ptr 是否小於 limit，開發人員應該預期它們會放置在每個函式的開頭和迴圈的後邊緣。編譯器包含一個資料流傳遞，它會移除所有點，只留下確保在有限時間內進行這些檢查所需的最小集合。

# open Core;;
# let c = Gc.get ();;
val c : Gc.Control.t =
  {Core.Gc.Control.minor_heap_size = 262144; major_heap_increment = 15;
   space_overhead = 120; verbose = 0; max_overhead = 500;
   stack_limit = 1048576; allocation_policy = 2; window_size = 1;
   custom_major_ratio = 44; custom_minor_ratio = 100;
   custom_minor_max_size = 8192}
# Gc.tune ~minor_heap_size:(262144 * 2) ();;
- : unit = ()

壽命較長的主要堆積區

主要堆積區是儲存程式中壽命較長且較大的值的地方。它由任意數量的非連續虛擬記憶體區塊組成，每個區塊都包含分散著可用記憶體區域的存活區塊。執行時系統維護一個空閒列表資料結構，該結構索引它已配置的所有可用記憶體，並使用它來滿足 OCaml 區塊的配置請求。

主要堆積區通常比次要堆積區大得多，並且可以擴展到數 GB 的大小。它是透過標記-清除垃圾回收演算法來清理的，該演算法分幾個階段執行

• 標記階段會掃描區塊圖，並透過在區塊標頭的標籤中設定一個位元（稱為顏色標籤）來標記所有存活的區塊。

• 清除階段會依序掃描堆積區區塊，並識別先前未標記的死區塊。

• 壓縮階段會將存活的區塊重新放置到新配置的堆積區中，以消除空閒列表中的間隙。這可以防止長時間執行的程式中堆積區區塊的碎片化，並且通常比標記和清除階段發生得少得多。

主要垃圾回收也必須停止世界，以確保區塊可以移動，而不會被執行中的應用程式觀察到。標記和清除階段會逐步在堆積區的切片上執行，以避免長時間暫停應用程式，並且每個切片之前都會進行快速的次要回收。只有壓縮階段會一次接觸所有記憶體，而且這是一個相對罕見的操作。

在主要堆積區上配置記憶體

主要堆積區由依虛擬位址遞增順序排序的連續記憶體區塊的單向連結清單組成。每個區塊都是透過 malloc(3) 配置的單個記憶體區域，由標頭和資料區域組成，其中包含 OCaml 堆積區塊。堆積區塊標頭包含

• 包含區塊的記憶體區域的 malloc 虛擬位址

• 資料區域的大小（以位元組為單位）

• 在堆積區壓縮期間用來合併小區塊以減少堆積區碎片化的配置大小（以位元組為單位）

• 指向清單中下一個堆積區塊的連結

• 指向可能包含未檢查欄位且稍後需要掃描的區塊範圍的起始和結束位置的指標。僅在標記堆疊溢位後使用。

每個區塊的資料區域都從頁面邊界開始，其大小是頁面大小 (4 KB) 的倍數。它包含一個連續的堆積區塊序列，這些區塊可能小到一個或兩個 4 KB 頁面，但通常以 1 MB 的區塊配置（或在 32 位元架構上為 512 KB）。

控制主要堆積區增量

Gc 模組使用 major_heap_increment 值來控制主要堆積區的成長。這定義了每次擴充時添加到主要堆積區的字數，並且是作業系統在初始啟動後從 OCaml 執行時環境觀察到的唯一記憶體配置操作（因為次要堆積區的大小是固定的）。

在主要堆積區上配置 OCaml 值時，首先會檢查區塊的空閒列表，以尋找適合放置它的區域。如果空閒列表中沒有足夠的空間，執行時環境會透過配置一個足夠大的新堆積區塊來擴充主要堆積區。然後將該區塊添加到空閒列表，並再次檢查空閒列表（這次肯定會成功）。

舊版本的 OCaml 需要為主要堆積區增量設定固定的位元組數。這是一個很難正確設定的值：太小的值可能會導致許多較小的堆積區塊分散在虛擬記憶體的不同區域，這需要在 OCaml 執行時環境中進行更多的管理才能追蹤它們；太大的值可能會浪費具有小堆積區的程式的記憶體。

您可以使用 Gc.tune 來設定該值，但由於向後相容性的原因，這些值有點違反直覺。小於 1000 的值會被解釋為百分比，預設值為 15%。1000 及以上的值會被視為原始位元組數。但在大多數情況下，您根本不會設定該值。

記憶體配置策略

主要堆積區會盡力以盡可能有效的方式管理記憶體配置，並依靠堆積區壓縮來確保記憶體保持連續且未碎片化。預設的配置策略通常適用於大多數應用程式，但值得注意的是，還有其他選項。

在主要堆積區中配置新區塊時，始終首先檢查區塊的空閒列表。預設的空閒列表搜尋稱為最佳適配配置，還有其他可用的 下一個適配 和 第一個適配 演算法。

最佳適配配置

最佳適配配置器是兩種策略的組合。第一種是大小隔離的空閒列表，基於 OCaml 中幾乎所有主要堆積區配置都很小的觀察（考慮到只有幾個機器字的清單元素和元組）。最佳適配為最多 16 個字的大小保留單獨的空閒列表，這為大多數配置提供了快速路徑。這些大小的配置可以從其隔離的空閒列表提供服務，或者，如果它們是空的，則從具有空間的下一個大小提供服務。

第二種策略是用於較大配置，使用稱為伸展樹的專用資料結構作為空閒列表。這是一種適應最近存取模式的搜尋樹。對於我們的用途而言，這表示最常請求的配置大小是最快存取的。

當隔離的空閒列表中沒有更大的大小可用時，以及大於 16 個字的大型配置，都會從主空閒列表提供服務。查詢空閒列表以尋找至少與請求的配置一樣大的最小區塊。

最佳適配配置是預設的配置機制。它代表了配置成本（就 CPU 工作而言）和堆積區碎片化之間的良好折衷。

下一個適配配置

下一個適配配置保留一個指向空閒列表中最近用於滿足請求的區塊的指標。當有新請求時，配置器會從下一個區塊搜尋到空閒列表的末尾，然後從空閒列表的開頭搜尋到該區塊。

下一個適配配置是一種非常便宜的配置機制，因為同一個堆積區塊可以在配置請求之間重複使用，直到用完為止。這反過來表示有很好的記憶體局部性，可以更好地利用 CPU 快取。下一個適配的最大缺點是，由於大多數配置都很小，因此空閒列表開頭的大型區塊會變得非常碎片化。

首次適配分配 (First-Fit Allocation)

如果您的程式分配許多大小不一的值，您可能會發現您的可用列表變得零散。在這種情況下，即使存在可用的記憶體區塊，垃圾收集器 (GC) 仍被迫執行昂貴的壓縮操作，因為沒有任何單獨的區塊足夠大，可以滿足請求。

首次適配分配的重點是減少記憶體碎片 (並因此減少壓縮次數)，但代價是記憶體分配速度較慢。每次分配都會從頭開始掃描可用列表，以尋找合適的可用區塊，而不是像下次適配分配器那樣重複使用最近的堆積區塊。

對於某些需要在負載下具有更多即時行為的工作負載而言，堆積壓縮頻率的降低將抵消額外的分配成本。

控制堆積分配策略

您可以透過呼叫 Gc.tune 來設定堆積分配策略

# Gc.tune ~allocation_policy:First_fit ();;
- : unit = ()

相同的行為可以透過設定環境變數來控制，方法是將 OCAMLRUNPARAM 設定為 a=0 表示下次適配，a=1 表示首次適配，或 a=2 表示最佳適配。

標記和掃描堆積

標記過程可能需要很長時間才能在整個主要堆積上執行，並且在活動期間必須暫停主要應用程式。因此，它會透過標記切片中的堆積來增量執行。堆積中的每個值在其標頭中都有一個 2 位元的顏色欄位，用於儲存有關該值是否已被標記的資訊，以便 GC 可以在切片之間輕鬆恢復。

• 藍色：位於可用列表上，目前未使用
• 白色 (在標記期間)：尚未到達，但可能可達
• 白色 (在清除期間)：無法到達，可以釋放
• 黑色：可達，並且其欄位已掃描

值標頭中的顏色標籤儲存了標記過程的大部分狀態，允許它暫停並稍後恢復。在分配時，所有堆積值最初都會被賦予白色，表示它們可能可達但尚未掃描。GC 和應用程式會在標記主要堆積的切片和實際執行程式邏輯之間交替進行。OCaml 執行階段會根據分配速率和可用記憶體計算出每個主要堆積切片的合理大小。

標記過程從一組永遠存在的根值開始 (例如應用程式堆疊和全域變數)。這些根值的顏色設定為黑色，並被推送到稱為標記堆疊的特殊資料結構上。標記的進行方式是從堆疊中彈出一個值並檢查其欄位。任何包含白色區塊的欄位都會更改為黑色並推送到標記堆疊上。

這個過程會重複執行，直到標記堆疊為空且沒有更多值需要標記。但是，這個過程中存在一個重要的邊緣情況。標記堆疊只能增長到一定的大小，之後 GC 將無法再遞迴到中間值，因為它在追蹤其欄位時沒有地方儲存它們。這稱為標記堆疊溢位，並且會開始一個稱為修剪的過程。修剪會完全清空標記堆疊，並將每個區塊的位址彙總為每個堆積區塊標頭中的起始和結束範圍。

在標記過程的稍後階段，當標記堆疊為空時，會透過重新變黑堆積來重新填充。這從第一個具有需要重新變黑的區塊 (即在修剪期間從標記堆疊中移除的區塊) 的堆積區塊 (按位址) 開始，並且將重新變黑範圍中的項目新增到標記堆疊，直到它達到四分之一滿。清空和重新填充的循環會持續進行，直到沒有堆積區塊剩下要重新變黑的範圍。

控制主要堆積收集

您可以透過 major_slice 呼叫來觸發主要 GC 的單一切片。這會先執行次要收集，然後執行單一切片。切片的大小通常由 GC 自動計算為適當的值，並傳回此值，以便您可以在未來呼叫中根據需要修改它。

# Gc.major_slice 0;;
- : int = 0
# Gc.full_major ();;
- : unit = ()

space_overhead 設定控制 GC 在將切片大小設定為較大尺寸時的積極程度。這表示用於活動資料的記憶體比例，這些記憶體將被「浪費」，因為 GC 不會立即收集無法到達的區塊。Core 將此預設為 100，以反映沒有過度記憶體限制的典型系統。如果您有大量記憶體，則可以將此設定更高，或者設定較低以使 GC 更努力地工作並更快地收集區塊，但代價是使用更多的 CPU 時間。

堆積壓縮

在完成一定次數的主要 GC 循環後，堆積可能會因為值從分配順序中取消分配而開始碎片化。這使得 GC 更難找到用於新分配的連續記憶體區塊，這反過來又會導致堆積不必要地增長。

堆積壓縮循環會透過將主要堆積中的所有值重新定位到一個新的堆積中來避免這種情況，該堆積會再次將它們連續地放置在記憶體中。該演算法的簡單實作將需要額外的記憶體來儲存新的堆積，但 OCaml 會在現有堆積內執行就地壓縮。

# Gc.tune ~max_overhead:0 ();;
- : unit = ()

跨世代指標

世代收集的一個複雜性來自於次要堆積掃描比主要堆積收集頻繁得多的事實。為了知道次要堆積中的哪些區塊是活動的，收集器必須追蹤哪些次要堆積區塊是由主要堆積區塊直接指向的。如果沒有此資訊，每次次要收集都還需要掃描更大的主要堆積。

OCaml 維護一組這樣的跨世代指標，以避免主要堆積和次要堆積收集之間的這種相依性。每當修改主要堆積區塊以指向次要堆積區塊時，編譯器都會引入寫入屏障來更新這個所謂的已記憶集合。

可變寫入屏障

寫入屏障可能對您的程式碼結構產生深遠的影響。這也是為什麼使用不可變的資料結構並分配一個帶有更改的新副本，有時會比就地變更記錄更快的原因之一。

OCaml 編譯器會追蹤任何可變的類型，並在進行變更之前新增對執行階段 caml_modify 函數的呼叫。這會檢查目標寫入的位置及其變更的值，並確保已記憶集合是一致的。雖然寫入屏障相當有效率，但有時可能會比僅在快速的次要堆積上分配一個新值並執行一些額外的次要收集要慢。

讓我們用一個簡單的測試程式來看看這一點。在編譯此程式碼之前，您需要透過 opam install core_bench 安裝 Core 基準測試套件

open Core
open Core_bench

module Mutable = struct
  type t =
    { mutable iters : int
    ; mutable count : float
    }

  let rec test t =
    if t.iters = 0
    then ()
    else (
      t.iters <- t.iters - 1;
      t.count <- t.count +. 1.0;
      test t)
end

module Immutable = struct
  type t =
    { iters : int
    ; count : float
    }

  let rec test t =
    if t.iters = 0
    then ()
    else test { iters = t.iters - 1; count = t.count +. 1.0 }
end

let () =
  let iters = 1_000_000 in
  let count = 0.0 in
  let tests =
    [ Bench.Test.create ~name:"mutable" (fun () ->
          Mutable.test { iters; count })
    ; Bench.Test.create ~name:"immutable" (fun () ->
          Immutable.test { iters; count })
    ]
  in
  Bench.make_command tests |> Command_unix.run

此程式定義了類型 t1 (可變) 和 t2 (不可變)。基準測試迴圈會迭代兩個欄位並遞增計數器。使用一些額外的選項編譯並執行此程式碼，以顯示發生的垃圾收集量

$ opam exec -- dune exec -- ./barrier_bench.exe -ascii alloc -quota 1
Estimated testing time 2s (2 benchmarks x 1s). Change using '-quota'.

  Name        Time/Run   mWd/Run   mjWd/Run   Prom/Run   Percentage
 ----------- ---------- --------- ---------- ---------- ------------
  mutable       5.06ms    2.00Mw     20.61w     20.61w      100.00%
  immutable     3.95ms    5.00Mw     95.64w     95.64w       77.98%

這裡存在空間/時間的權衡。可變版本比不可變版本需要更長的時間才能完成，但分配的次要堆積字數比不可變版本少得多。OCaml 中的次要分配速度非常快，因此通常最好使用不可變的資料結構，而不是更傳統的可變版本。另一方面，如果您很少變更值，則接受寫入屏障的影響而不進行分配可能會更快。

唯一確定方法是使用 Core_bench 在真實場景下對您的程式進行基準測試，並嘗試權衡取捨。命令列基準測試二進位檔案有許多有用的選項會影響垃圾收集行為和輸出格式

$ opam exec -- dune exec -- ./barrier_bench.exe -help
Benchmark for mutable, immutable

  barrier_bench.exe [COLUMN ...]

Columns that can be specified are:
	time       - Number of nano secs taken.
	cycles     - Number of CPU cycles (RDTSC) taken.
	alloc      - Allocation of major, minor and promoted words.
	gc         - Show major and minor collections per 1000 runs.
	percentage - Relative execution time as a percentage.
	speedup    - Relative execution cost as a speedup.
	samples    - Number of samples collected for profiling.
...

將終結器函數附加到值

OCaml 的自動記憶體管理保證當一個值不再使用時，最終會透過 GC 清除它或程式終止來釋放它。有時，在值被 GC 釋放之前執行額外的程式碼很有用，例如，檢查檔案描述子是否已關閉，或是否已記錄記錄訊息。

Core 提供了一個 Heap_block 模組，該模組會動態檢查給定的值是否適合終結。Core 會將註冊終結器的函數保存在 Core.Gc.Expert 模組中。終結器可以在任何執行緒中的任何時間執行，因此在多執行緒環境中很難對它們進行推理。我們在使用 Async 的並行程式設計中討論的 Async，使用其自己的模組來遮蔽 Gc 模組，該模組包含一個函數 Gc.add_finalizer，該函數是並發安全的。特別是，終結器會在它們自己的 Async 工作中排程，並且 Async 會小心地捕捉例外並將它們提出給適當的監視器以進行錯誤處理。

讓我們用一個小型範例來探索這一點，該範例會終結不同類型的值，所有這些值都是在堆積中分配的。

open Core
open Async

let attach_finalizer n v =
  match Heap_block.create v with
  | None -> printf "%20s: FAIL\n%!" n
  | Some hb ->
    let final _ = printf "%20s: OK\n%!" n in
    Gc.add_finalizer hb final

type t = { foo : bool }

let main () =
  attach_finalizer "allocated variant" (`Foo (Random.bool ()));
  attach_finalizer "allocated string" (Bytes.create 4);
  attach_finalizer "allocated record" { foo = Random.bool () };
  Gc.compact ();
  return ()

let () =
  Command.async
    ~summary:"Testing finalizers"
    (Command.Param.return main)
  |> Command_unix.run

建置並執行此程式碼應該會顯示以下輸出

$ opam exec -- dune exec -- ./finalizer.exe
    allocated record: OK
    allocated string: OK
   allocated variant: OK

GC 會按照取消分配的順序呼叫終結函數。如果多個值在同一個 GC 週期中變得無法到達，則終結函數將按照對 add_finalizer 的對應呼叫的相反順序呼叫。每次呼叫 add_finalizer 都會新增到函數集合中，當值變得無法到達時，這些函數會執行。如果您願意，可以讓許多終結器都指向同一個堆積區塊。

在垃圾收集確定堆積區塊 b 無法到達後，它會從與 b 相關聯的終結器集合中移除所有函數，並依次將這些函數應用於 b。因此，附加到 b 的每個終結器函數最多會執行一次。但是，程式終止不會導致所有終結器在執行階段結束之前執行。

終結器可以使用 OCaml 的所有功能，包括可以使值重新可訪問的賦值，進而阻止它被垃圾回收。它也可以永遠循環，這會導致其他終結器與它交錯執行。