垃圾怪客破壞者第二部：Orinoco
在之前的博客文章中，我們介紹了垃圾回收中斷流暢瀏覽體驗所導致的卡頓問題。在這篇文章中，我們介紹了三項優化，它們為 V8 中一個新的垃圾回收器代號為 Orinoco 奠定了基礎。Orinoco 基於這樣一個理念：實現一個大多數並行且併發的垃圾回收器，且不依賴嚴格的代界限，將減少垃圾回收卡頓和內存消耗，同時提供高吞吐量。我們選擇不僅僅作為一個獨立的垃圾回收器來實施 Orinoco，而是分階段在 V8 的樹頂逐步提供 Orinoco 的功能，以便立即為用戶提供益處。本篇文章探討的三個功能是並行壓縮、並行記憶集合處理，以及黑色分配。
V8 實現了一個代際垃圾回收器，其中物件可能在年輕代中移動，從年輕代移至老代，以及在老代內部移動。物件移動是昂貴的，因為需要將物件的底層內存複製到新的位置，並且指向這些物件的指針也需要更新。圖 1 顯示了 Orinoco 之前的階段及其執行方式。基本上，物件先移動，然後才更新這些物件之間的指針，所有這些都是依序完成的，以至於造成可觀察的卡頓。
V8 將其堆內存劃分為固定大小的塊，稱為頁面，這些頁面分配給年輕代或老代空間。物件最初是在年輕代中分配的。在垃圾回收時，活躍物件會在年輕代中移動一次。那些在另一輪垃圾回收中幸存的物件會被提升到老代。對於這兩個階段，我們統稱為年輕代遷移，我們基於頁面對內存複製進行並行化。在年輕代中，移動物件總是涉及在新頁面上分配內存（並釋放舊頁面），留下緊湊的內存佈局。在老代中，這過程有所不同，因為死內存會留下不可用的空洞（或碎片）。某些空洞可以通過空閒列表重新使用，但其他空洞則會被遺留下來，需要壓縮以將活躍物件移至更緊湊（可能是新的）頁面。與年輕代類似，此過程在頁面層級進行並行化。
由於年輕代遷移和老代壓縮之間沒有依賴關係，Orinoco 現在並行執行這些階段，如圖 2 所示。這些改進帶來的結果是壓縮時間從約 7 毫秒減少到平均不到 2 毫秒，減少了 75%。
Orinoco 引入的第二項優化改善了垃圾回收追蹤指針的方式。當物件在堆上改變位置時，垃圾回收器必須找到所有包含移動後物件舊位置的指針，並將它們更新為新位置。由於遍歷堆以查找指針會非常慢，V8 使用了一個稱為 記憶集合 的數據結構來跟踪堆上所有相關指針。如果一個指針指向垃圾回收期間可能移動的物件，那麼它就是相關的。例如，所有從老代指向新代的指針都是相關的，因為新代物件在每次垃圾回收時都會移動。指向重度碎片頁面上的物件的指針也是相關的，因為這些物件在壓縮期間會移動到其他頁面。
過去，V8 以指標地址的陣列（或稱 store buffers）來實現記憶集合。年輕代有一個儲存緩衝區，而每個已分割的舊代頁面也各有一個儲存緩衝區。某頁面的儲存緩衝區包含所有進入指標的地址，如圖 3 所示。在 JavaScript 代碼中，一個 write barrier 保護寫入操作，在這個操作中條目會附加到儲存緩衝區中。這可能會導致重複條目，因為儲存緩衝區可能包含多次出現的同一指標，而兩個不同的儲存緩衝區也可能包含同一指標。重複條目使得指標更新階段的並行化變得困難，因為兩個線程嘗試更新同一指標會造成資料競爭。
Orinoco 通過重組記憶集合來簡化並行化並確保線程獲得可更新的指標的完全不相交集合，從而移除了這種複雜性。現在，各頁面不再以陣列儲存進入的關注指標，而是像圖 4 所示將來源於該頁面的關注指標偏移量存儲在位圖的桶中。每個桶要麼是空的，要麼指向一個固定長度的位圖。位圖中的某一位對應於頁面中的某個指標偏移量。如果某一位被設置，則表明該指標值得關注並在記憶集合中。使用此資料結構，我們可以基於頁面來並行化指標更新。缺乏重複條目以及指標的稠密表示還使得我們去掉了處理記憶集合溢出的複雜代碼。在我們的長時間執行 Gmail 測試中，這種改變減少了垃圾收集進行緊縮時的最大暫停時間，從 42ms 降至 23ms，減少了 45%。
Orinoco 引入的第三項優化是 black allocation，即垃圾收集器標記階段的一項改進。黑分配（在 V8 5.1 中推出）是一種垃圾收集技術，所有在舊代分配的物件（例如 預分配的物件 或垃圾收集器促升的物件）會立刻標記為黑色，以標示其為“存活”。黑分配的直觀想法是，在舊代分配的物件可能是長壽命的。因此，剛分配到舊代的物件應至少存活到下一次舊代垃圾收集，否則會產生誤促升的情況。在為新分配的物件染黑後，垃圾收集器不需要再次訪問它們。我們通過在黑頁面上分配它們（所有物件預設為黑色）來加快染黑物件的速度。黑頁面的另一項好處是無需清理，因為分配在上面的所有物件（根據定義）都是存活的。黑分配加快了增量標記進度，因為標記工作不會因新分配而增加。在 Octane Splay 測試中，黑分配的影響顯而易見，吞吐量和延遲分數提升約 30%，並因更快的標記進度和整體垃圾收集工作減少而使用了約 20% 更少的記憶體。
我們計劃很快推出更多 Orinoco 功能。敬請期待，我們仍在努力改進中！