Orinoco：年輕代垃圾收集
V8 中的 JavaScript 物件分配在由 V8 的垃圾收集器管理的堆上。在之前的博客文章中，我們已經討論了如何減少垃圾收集暫停時間（多次）和記憶體消耗。在這篇博客文章中，我們介紹了平行 Scavenger，Orinoco，V8 主要併發和平行垃圾收集器的一項最新功能，並討論了我們在過程中實現的設計決策和替代方法。
V8 將其管理的堆劃分為多代，其中物件最初分配在年輕代的“育苗室”中。經過一次垃圾收集後倖存的物件會被複製到中間代，它仍然屬於年輕代。再經過一次垃圾收集後，這些物件會被移動到老代（見圖 1）。V8 實現了兩個垃圾收集器：一個經常收集年輕代，另一個收集包括年輕代和老代在內的完整堆。老代到年輕代的引用是年輕代垃圾收集的根。這些引用是記錄的，以便在移動物件時提供有效的根識別和引用更新。
由於年輕代相對較小（在 V8 中最高 16MiB），它很快會被物件填滿並需要頻繁收集。在 M62 之前，V8 使用了一種 Cheney 的半空間複製垃圾收集器（見下文），該收集器將年輕代分為兩半。在 JavaScript 執行過程中，年輕代的一半僅用於分配物件，而另一半保持空狀態。在一次年輕代垃圾收集中，活動物件會從一半複製到另一半，同時在線壓縮記憶體。已複製一次的活動物件被視為中間代的一部分，並提升到老代。
從 v6.2 開始，V8 將年輕代的默認收集算法切換為平行 Scavenger，類似於 Halstead 的半空間複製收集器，不同之處在於 V8 使用動態工作竊取代替靜態工作竊取，且運行於多個執行緒上。以下我們將解釋三種算法：a）單執行緒的 Cheney 半空間複製收集器，b）平行標記-疏散方案，和 c）平行 Scavenger。
單執行緒 Cheney 的半空間複製
直到 v6.2，V8 使用的 Cheney 的半空間複製算法 非常適合單核心執行和分代計畫。在進行年輕代垃圾收集之前，記憶體的兩個半空間都被提交並分配了適當的標籤：當前物件集合所在頁面稱為 from-space，而物件被複製到的頁面稱為 to-space。
Scavenger 將堆疊中的引用和從老代到年輕代的引用視為根。如圖 2 所示，最初 Scavenger 掃描這些根並將 from-space 中可達但尚未被複製到 to-space 的物件複製過去。已經經歷過垃圾收集的物件會提升（移動）到老代。在根掃描和第一次複製之後，新分配的 to-space 中的物件會被掃描找尋引用。同樣，所有被提升的物件也會被掃描，以找尋指向 from-space 的新引用。這三個階段在主執行緒上交錯進行。算法將不斷執行，直到 to-space 或老代中不再有新的可達物件為止。此時，from-space 僅包含不可達物件，即垃圾。
平行標記-疏散
我們基於 V8 的完整標記-清掃-壓縮收集器實驗了一種平行標記-撤離演算法。主要優勢在於利用完整標記-清掃-壓縮收集器中已存在的垃圾回收基礎設施。此演算法由三個階段組成：標記、複製以及更新指針，如圖 3 所示。為避免在年輕代中清掃頁面以維持空閒列表，年輕代仍然使用半空間技術，通過在垃圾回收時將存活物件複製到_目標空間_來保持壓縮狀態。年輕代首先以平行方式進行標記。在標記後，存活物件被以平行方式複製到其對應的空間。工作根據邏輯頁面分配。參與複製的執行緒保有其自身的本地分配緩衝區 (LAB)，完成複製後這些緩衝區會合併。在複製之後，相同的平行化方案被應用於更新物件間指針。這三個階段以鎖步方式執行，即便各階段是平行進行，執行緒在進入下一階段之前也需要同步。
平行清掃
平行標記-撤離收集器將計算存活性、複製存活物件以及更新指針的階段分開。一個顯而易見的優化是合併這些階段形成一種同時標記、複製和更新指針的演算法。通過合併這些階段，我們實際獲得了 V8 所使用的平行清掃機制，這是一種類似於Halstead’s 半空間收集器的版本，不過 V8 使用了動態工作竊取和一個簡單的負載平衡機制來掃描根節點（見圖 4）。如同單執行緒的 Cheney 演算法，這些階段包括：掃描根節點、在年輕代內複製、推升到老年代以及更新指針。我們發現根集合中的大部分通常是從老年代到年輕代的引用。在我們的實現中，記憶集合是以每頁的形式維護的，這自然地將根集合分佈到各垃圾回收執行緒。物件被以平行方式處理。新發現的物件被加入到一個全域工作列表中，垃圾回收執行緒可以從中竊取工作。該工作列表既提供快速的本地存儲，又提供全域存儲以便共享工作。一個屏障確保執行任務不會在當前處理的子圖不適合工作竊取時（例如物件的線性鏈）過早終止。所有階段都以平行方式執行並在每個任務中交替進行，最大化工人任務的利用率。
結果與結果分析
清掃演算法最初的設計是以單核心最佳性能為目標。自那之後，世界已然改變。即使在低端移動設備上，CPU 核心也通常十分充足。更重要的是，通常這些核心實際上是正在運行的。為了充分利用這些核心，V8 的垃圾收集器之一的清掃器，作為最後的序列化組件之一，需要現代化。
平行標記-撤離收集器的一個巨大優勢是可以獲得準確的存活性資訊。例如，這些資訊可以用來完全避免複製，只需移動並重新連結包含大量存活物件的頁面，而這也是完整標記-清掃-壓縮收集器所執行的功能。然而在實際情況中，這通常只在合成基準測試中可觀察到，在實際網站上很少出現。平行標記-撤離收集器的一個缺點是需要執行三個單獨的鎖步階段所造成的開銷。尤其是在垃圾收集器在一個主要包含死物件的堆上被調用時，這種開銷特別明顯，而在許多真實世界的網頁上情況就是如此。請注意，在主要包含死物件的堆上調用垃圾收集器實際上是理想情況，因為垃圾回收通常受限於存活物件的大小。
平行清掃通過在小或幾乎空的堆上的性能接近優化的 Cheney 演算法同時在堆變大且包含大量存活物件時提供高吞吐量，填補了這一性能差距。
V8 支援許多平台，其中包括 Arm big.LITTLE。在小核心上卸載工作有助於延長電池壽命，但若針對小核心的工作負載過大，則可能導致主執行緒阻塞。我們觀察到，由於頁面數量有限，頁面層級的平行性未必能在年輕代垃圾回收中平衡 big.LITTLE 上的工作負載。清掃器通過使用顯式工作列表和工作竊取提供中等粒度的同步，自然地解決了這一問題。
