V8中的並行標記

本文介紹了一種稱為_並行標記_的垃圾回收技術。此優化使 JavaScript 應用程式能在垃圾回收器掃描堆進行標記存活物件時繼續執行。基準測試顯示，並行標記可將主執行緒上的標記時間減少60%–70%。並行標記是Orinoco專案的最後一塊拼圖——該專案旨在逐步將舊的垃圾回收器替換為新的大部分並行和平行垃圾回收器。並行標記在 Chrome 64 和 Node.js v10中為預設啟用。

背景

標記是 V8的Mark-Compact垃圾回收器的一個階段。在此階段，回收器會發現並標記所有存活物件。標記從已知存活物件的集合開始，比如全局物件和當前活動的函數——即所謂的根。回收器將根標記為存活，並跟蹤其中的指針以發現更多存活物件。回收器繼續標記新發現的物件並跟蹤指針，直到沒有更多物件需要標記。在標記結束時，堆上的所有未標記物件對應用程式不可訪問，可安全回收。

我們可以將標記視為一種圖遍歷。堆上的物件是圖的節點，物件之間的指針是圖的邊。給定圖中的一個節點，我們可以使用物件的隱藏類型來找到該節點的所有輸出邊。

V8 使用兩個標記位和一個標記工作列表來實現標記。兩個標記位編碼三種顏色：白色 (00)、灰色 (10) 和黑色 (11)。起初所有物件均為白色，表示回收器尚未發現它們。當回收器發現一個白色物件並將其推送到標記工作列表時，它就會變為灰色。當回收器從標記工作列表中彈出灰色物件並訪問其所有字段時，灰色物件變為黑色。這種方案稱為三色標記。當灰色物件不再存在時，標記結束。所有剩余的白色物件都是不可訪問的，可以安全回收。

注意，上述標記算法僅在應用程式在標記進行期間暫停時才能正常工作。如果我們允許應用程式在標記期間運行，那麼應用程式可能會更改圖並最終使回收器誤釋存活物件為可釋放物件。

減少標記暫停

一次完成的標記可能會使大型堆花費數百毫秒。

如此長的暫停會使應用程式無法響應並導致較差的使用者體驗。2011年，V8從全停標記切換為增量式標記。在增量式標記中，垃圾回收器將標記工作拆分為更小的片段，並允許應用程式在片段之間運行：

垃圾回收器選擇在每個片段中進行多少增量標記工作，以匹配應用程式的分配速率。在常見情況下，這大大提升了應用程式的響應速度。對於大型堆且內存壓力大時，隨著回收器試圖跟上分配速度，仍可能出現長時間的暫停。

增量式標記並非免費。應用程式需要通知垃圾回收器所有更改物件圖的操作。V8 使用 Dijkstra風格的寫入屏障來實現通知。在 JavaScript 中，執行類似object.field = value的寫入操作後，V8 插入寫入屏障代碼：

// 在執行 `object.field = value` 後調用。
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

寫屏障強制執行一個不變式，即黑色物件不可以指向白色物件。這也被稱為強三色不變式，並保證應用程式無法隱藏垃圾收集器的存活物件，因此在標記結束時所有白色物件對應用程式而言都是真正不可到達的，並且可以安全地釋放。

增量標記可以很好地與空閒時間垃圾收集的調度結合，如早期博客文章中所述。Chrome 的 Blink 任務調度器可以在主線程的空閒時間中安排微小的增量標記步驟，而不會引起停滯。如果有可用的空閒時間，這種優化效果非常好。

由於寫屏障的開銷，增量標記可能會減少應用程式的吞吐量。通過使用額外的工作線程，可以同時改善吞吐量和暫停時間。有兩種方式可以在工作線程上進行標記：並行標記和並發標記。

並行標記發生在主線程和工作線程上。在整個並行標記階段，應用程式是暫停的。這是停止世界式標記的多線程版本。

並發標記主要發生在工作線程上。在並發標記進行時應用程式可以繼續運行。

以下兩個部分描述了我們如何在 V8 中新增對並行和並發標記的支援。

並行標記

在並行標記期間，我們可以假設應用程式不會同時運行。這大大簡化了實現，因為我們可以假設物件圖是靜態的並且不會改變。為了並行標記物件圖，我們需要使垃圾收集器數據結構具有線程安全性，並找到一種在線程之間高效共享標記工作的方式。下圖顯示了並行標記中涉及的數據結構。箭頭表示數據流方向。為簡化起見，圖中省略了為堆碎片整理所需的數據結構。

注意線程僅從物件圖讀取數據而不更改它。對物件的標記位和標記工作列表必須支援讀取與寫入訪問。

標記工作列表和工作竊取

標記工作列表的實現對於性能至關重要，並需要平衡快速的線程本地性能與其他線程在用完工作後能夠接收分配工作的能力。

在該折衷範圍的極端方向是（a）使用完全並發的數據結構以達到最佳共享，因為所有物件都可能被共享；以及（b）使用完全線程本地的數據結構，不共享任何物件，優化線程本地吞吐量。圖 6 顯示了 V8 如何通過使用基於段的標記工作列表來滿足這些需求，實現線程本地的插入和移除。當段滿時，它會發布到共享的全局池中，供竊取使用。這樣 V8 允許標記線程盡可能在本地運作並避免同步，並且在單個線程到達一個新的物件子圖時，能處理另一線程耗盡其本地段的情況。

並發標記

並發標記允許 JavaScript 在主線程上運行，同時工作線程訪問堆上的物件。這為許多潛在的數據競爭打開了大門。例如，JavaScript 可能在工作線程讀取字段的同時寫入物件字段。數據競爭可能使垃圾收集器誤釋一個存活的物件為非存活的，或者將原始值與指針混淆。

主線程上的每個改變物件圖的操作都是數據競爭的潛在來源。由於 V8 是一個性能優異的引擎，具有許多物件佈局優化，潛在數據競爭來源的列表相當長。以下是高階的概述：

• 物件分配。
• 寫入物件字段。
• 物件佈局更改。
• 從快照反序列化。
• 函數反優化期間的物件物化。
• 年輕代垃圾收集期間的撤離。
• 代碼修補。

主線程需要在這些操作上與工作線程同步。同步的成本和複雜性取決於操作。大多數操作允許使用輕量級同步，比如原子內存操作，但少數操作需要對物件進行獨占訪問。在以下分節中，我們強調了一些有趣的案例。

寫屏障

由寫入物件字段引起的數據競爭通過將寫入操作轉換為鬆弛的原子寫入並調整寫屏障來解決：

// 在 atomic_relaxed_write(&object.field, value) 完成後調用；
write_barrier(object, field_offset, value) {
  如果 (color(value) == white 且 atomic_color_transition(value, white, grey)) {
    marking_worklist.push(value);
  }
}

將其與之前使用的寫屏障進行比較：

// 在 `object.field = value` 之後調用。
write_barrier(object, field_offset, value) {
  如果 (color(object) == black 且 color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

有兩個更改：

1. 去掉了對源對象顏色的檢查（color(object) == black）。
2. value 的顏色從白色到灰色的轉變是以原子方式進行的。

沒有源對象顏色檢查的情況下，寫屏障變得更加保守，即它可能將對象標記為活動狀態，即使這些對象實際上並不可達。 我們移除了該檢查，以避免在寫操作和寫屏障之間需要昂貴的內存屏障：

atomic_relaxed_write(&object.field, value);
memory_fence();
write_barrier(object, field_offset, value);

沒有內存屏障，對象顏色加載操作可能會在寫操作之前重新排序。 如果我們不防止重新排序，那麼寫屏障可能會觀察到灰色對象顏色並退出，而工作線程則在未看到新值的情況下標記該對象。 Dijkstra 等人提出的原始寫屏障也沒有檢查對象顏色。他們這麼做是為了簡單，但我們這麼做是為了正確性。

退出工作列表

某些操作，例如代碼修補，需要對對象的獨佔訪問。一開始我們決定避免使用每個對象鎖，因為它們可能導致優先級倒置問題，其中主線程必須等待被解調度的工作線程，當它仍持有對象鎖時。取而代之，我們允許工作線程退出訪問該對象。工作線程通過將該對象推入退出工作列表來完成退出，該列表僅由主線程處理：

工作線程退出優化的代碼對象、隱藏類和弱集合，因為訪問它們需要鎖定或昂貴的同步協議。

回顧來看，退出工作列表非常適合增量開發。 我們從所有對象類型的工作線程退出啟動實現，並逐個新增並發處理。

對象佈局更改

對象的一個字段可以存儲三種類型的值：標記指針、標記小整數（也稱為 Smi）或非標記值（如未裝箱浮點數）。 指針標記 是一種眾所周知的技術，可以高效地表示未裝箱整數。 在 V8 中，標記值的最低有效位表示它是指針還是整數。 這依賴於指針是字對齊的事實。 有關字段是否標記或非標記的信息存儲在對象的隱藏類中。

在 V8 中，一些操作通過將對象轉換到另一個隱藏類來將對象字段從標記更改為非標記（或相反）。 此類對象佈局更改對並發標記是不安全的。 如果更改發生在工作線程正在同時使用舊的隱藏類訪問該對象時，則可能會發生兩種類型的錯誤。 首先，工作線程可能會錯過一個指針，認為它是非標記值。 寫屏障可以防止這種錯誤。 其次，工作線程可能將未標記值視為指針並解引用它，這將導致無效內存訪問，通常緊隨其後的是程序崩潰。 為了處理這種情況，我們使用了一種對象標記位的快照同步協議。 該協議涉及兩方：更改對象字段從帶標記到非標記的主線程，以及訪問對象的工作線程。 在更改字段之前，主線程確保該對象標記為黑色，並將其推入退出工作列表，以供稍後訪問：

atomic_color_transition(object, white, grey);
如果 (atomic_color_transition(object, grey, black)) {
  // 該對象將在主線程排空退出工作列表期間被重新訪問。
  bailout_worklist.push(object);
}
unsafe_object_layout_change(object);

如下面的代碼片段所示，工作線程首先加載該對象的隱藏類，並使用 原子釋放加載操作 快照該對象隱藏類指定的所有指針字段。 然後它嘗試使用原子比較和交換操作將該對象標記為黑色。 如果標記成功，那麼這意味著快照必須與隱藏類一致，因為主線程在更改佈局之前將對象標記為黑色。

snapshot = [];
hidden_class = atomic_relaxed_load(&object.hidden_class);
for (field_offset in pointer_field_offsets(hidden_class)) {
  pointer = atomic_relaxed_load(object + field_offset);
  snapshot.add(field_offset, pointer);
}
if (atomic_color_transition(object, grey, black)) {
  visit_pointers(snapshot);
}

請注意，假如白色物件經歷了不安全的佈局變更，必須在主執行緒上進行標記。不安全的佈局變更相對少見，因此這對實際應用程式的效能影響不大。

綜合說明

我們將併發標記整合至現有的增量標記基礎架構中。主執行緒通過掃描根物件並填充標記工作列表來啟動標記。之後，它在工作執行緒上發布併發標記任務。工作執行緒通過協作性地排空標記工作列表，有助於主執行緒更快地推進標記進度。主執行緒不時地參與標記工作，通過處理失敗工作列表和標記工作列表。一旦標記工作列表變空，主執行緒會完成垃圾回收。在最終化過程中，主執行緒會重新掃描根物件，可能會發現更多的白色物件。這些物件在工作執行緒的幫助下以並行方式進行標記。

成果

我們的真實世界基準測試框架顯示，每次垃圾回收週期，主執行緒上的標記時間在行動裝置和桌面上分別減少了約65%和70%。

併發標記還減少了 Node.js 中的垃圾回收卡頓現象。這一點尤為重要，因為 Node.js 從未實現閒置時間垃圾回收排程，因此無法在非卡頓關鍵階段隱藏標記時間。併發標記已隨 Node.js v10 發布。