跳至主要内容

垃圾話：奧里諾科垃圾回收器

· 閱讀時間約 13 分鐘
Peter ‘垃圾處理者’ Marshall ([@hooraybuffer](https://twitter.com/hooraybuffer))

在過去幾年中，V8 的垃圾回收器（GC）發生了很大的變化。奧里諾科項目將一個順序性的全程停頓垃圾回收器轉變為一個主要併行並發且具有增量回退功能的回收器。

備註

注意: 如果您更喜歡觀看演講而不是閱讀文章，那麼請享受下面的視頻！如果不喜歡，可以跳過視頻繼續閱讀。

任何垃圾回收器都需要定期完成一些必要的任務：

  1. 確定存活/死亡物件
  2. 回收/重用死亡物件佔用的記憶體
  3. 壓縮/消除記憶體碎片（可選）

這些任務可以按順序執行，也可以任意交叉執行。一種簡單的方法是暫停 JavaScript 的執行並在主線程上按順序執行每項任務。這可能導致主線程上的卡頓和延遲問題，這在我們之前的 博客文章中已有討論，同時還會降低程序的吞吐量。

主要 GC（全標記壓縮）​

主要 GC 從整個堆中收集垃圾。

主要 GC 有三個階段：標記、清掃和壓縮。

標記​

找出哪些物件可以被回收是垃圾回收的重要一環。垃圾回收器藉由使用可達性作為存活的代理來完成這一工作。這意味著任何當前在運行時中可達的物件都必須保留，而任何不可達的物件則可以回收。

標記是找到可達物件的過程。GC 從一組已知物件指針開始，稱為根集。這包括執行堆疊和全域物件。然後它遵循每個指針到 JavaScript 物件的路徑，並將該物件標記為可達。GC 會跟隨物件內部的每個指針，並遞歸繼續此過程，直到找到並標記運行時中所有的可達物件為止。

清掃​

清掃是在記憶體中死亡物件留下的空隙被添加到一個稱為空閒列表的數據結構中的過程。一旦完成標記，GC 便會找到不可達物件留下的連續空隙，並將其添加到適合的空閒列表中。空閒列表按記憶體塊的大小分隔，以便快速查找。未來當我們需要分配記憶體時，只需檢查空閒列表並找到合適大小的記憶體塊。

壓縮​

主要 GC 還根據碎片化的啟發式方法選擇撤離/壓縮某些頁面。您可以將壓縮類比為舊式 PC 上的硬碟重整。我們將存活的物件複製到其他未壓縮的頁面（使用該頁面的空閒列表）。通過這種方式，我們可以利用因死亡物件留下的小且分散的記憶體空隙。

回收器複製存活物件的潛在弱點是，如果我們分配大量長壽命物件，則對這些物件的複製代價很高。這就是為什麼我們選擇僅壓縮一些高度碎片化的頁面，而其余僅進行清掃，不涉及對存活物件的複製。

世代佈局​

V8 的堆被分為不同的區域，稱為世代。有一個年輕世代（進一步分為‘幼兒期’和‘中期’子世代）和一個老年世代。物件首先分配到幼兒期。如果它們能倖存下一次 GC，它們仍留在年輕世代但被視為‘中期’。如果再一次 GC 中仍然倖存，它們會移到老年世代。

V8 的堆分為不同世代。物件在倖存 GC 時會在世代間移動。

在垃圾回收中有一個重要的術語：“世代假設”。這基本上指的是大多數物件壽命短。換句話說，大多數物件會被分配，然後幾乎立即從 GC 的角度變得不可達。這不僅適用於 V8 或 JavaScript，還覆蓋了大多數動態語言。

V8 的分代堆佈局是為了利用關於物件生命週期的這一特性而設計的。垃圾回收（GC）是一種壓縮/移動式 GC，這意味著它會複製在垃圾回收中存活的物件。這看起來有些違背直覺：在 GC 時複製物件是昂貴的。但根據分代假設，我們知道實際上只有極少數的物件能夠在垃圾回收後存活。通過僅移動存活的物件，其它的分配就變成了「默認垃圾」。這意味著我們僅為存活物件的數量支付複製的成本，而不是分配的數量。

小型 GC (Scavenger)​

V8 有兩個垃圾回收器。大型 GC (Mark-Compact) 對整個堆進行垃圾回收。小型 GC (Scavenger) 則在年輕代中進行垃圾回收。大型 GC 在回收整個堆的垃圾方面非常有效，但分代假設告訴我們新分配的物件非常可能需要進行垃圾回收。

在 Scavenger 中，只對年輕代內部進行回收，存活的物件總是被轉移到新的頁面。V8 使用了一種「半空間」設計來管理年輕代。這意味著，總空間的一半始終是空的，以便執行這種轉移步驟。在進行垃圾回收時，這片最初空置的區域被稱為「To-Space」。我們從中複製的區域被稱為「From-Space」。在最糟糕的情況下，每一個物件都可能存活，因此我們需要複製所有物件。

在進行垃圾回收時，我們還有一組額外的根，它們是舊空間到新空間的參考。這些是舊空間中指向年輕代物件的指針。與其在每次回收時追蹤整個堆的圖形，我們使用寫屏障來維護舊空間到新空間的引用列表。結合堆棧和全局變量，我們可以知道所有指向年輕代的引用，而無需追蹤整個舊代。

轉移步驟將所有存活的物件移動到連續的一塊內存區域（在某個頁面內）。這樣可以完全消除碎片化——由死亡物件留下的空隙。我們然後交換兩個空間，也就是 To-Space 變成 From-Space，反之亦然。一旦 GC 完成，新的分配就會發生在 From-Space 中的下一個空閒地址。

Scavenger 將存活的物件轉移到一個新頁面。

僅僅依靠這種策略，我們很快就會耗盡年輕代的空間。在第二次 GC 後仍然存活的物件將被轉移到舊代，而不是 To-Space。

垃圾回收的最後一步是更新引用移動後原始物件的指針。每個被複製的物件都會留下轉發地址，用來更新原始指針指向新位置。

Scavenger 將「中間」物件轉移到舊代，並將「育成」物件轉移到新頁面。

在垃圾回收過程中，我們實際上將這三個步驟——標記、轉移、和指針更新——交錯執行，而不是分不同階段完成。

Orinoco​

這些算法和優化大多在垃圾回收文獻中非常常見，可在許多垃圾回收語言中找到。但尖端的垃圾回收技術已經取得了很大的進展。一個衡量垃圾回收所花時間的重要指標是執行 GC 時主線程暫停的時間。對於傳統的「停止全世界」垃圾回收器，這段時間可能會迅速累積，而這段執行 GC 的時間會直接影響用戶體驗，表現為頁面卡頓、渲染和延遲性能差。

Orinoco，V8 的垃圾回收器的標誌

Orinoco 是 GC 項目的代號，旨在利用最新最強大的並行、增量和並發垃圾回收技術，以釋放主線程。在 GC 上下文中，有一些術語具有特定含義，值得詳細定義。

並行​

並行是指主線程和輔助線程在同一時間段內完成大致相等的工作。這仍然是一種「停止全世界」的方法，但總暫停時間現在由參與的線程數量平均分配（加上一些同步開銷）。這是三種技術中最簡單的一種。JavaScript 堆被暫停，因為此時沒有 JavaScript 在運行，因此每個輔助線程只需確保它們對其他輔助線程可能想訪問的任何物件的同步訪問。

主線程和輔助線程同時處理相同的任務。

增量​

增量式指主執行緒間歇性地完成少量工作。我們不會在一次增量停頓中執行整個垃圾回收，而是完成垃圾回收所需總工作的一小部分。這更加困難，因為 JavaScript 在每段增量工作之間執行，導致堆的狀態發生變化，可能使以前增量完成的工作無效。從圖表中可以看出，這並沒有減少主執行緒花費的時間（事實上，通常會略微增加），只是將時間分散開來。這仍然是解決我們初始問題之一：主執行緒延遲的一種有效技術。通過允許 JavaScript 間歇性地執行，但同時繼續垃圾回收任務，應用程式仍然可以響應使用者輸入並在動畫上取得進展。

垃圾回收任務的小部分片段交替插入主執行緒的執行過程。

並行​

並行指主執行緒不停地執行 JavaScript，而輔助執行緒在背景中完全執行垃圾回收工作。這是三種技術中最困難的一種：JavaScript 堆上的任何內容隨時可能改變，使我們之前完成的工作無效。此外，還需擔心讀寫競爭，因為輔助執行緒和主執行緒會同時讀取或修改相同的物件。其優勢在於主執行緒能完全自由地執行 JavaScript — 儘管因與輔助執行緒的一些同步操作有些許開銷。

垃圾回收任務完全在背景中運行。主執行緒可以自由執行 JavaScript。

V8 中垃圾回收的現狀​

清除​

目前，V8 使用並行清除技術將青年代垃圾回收的工作分配到輔助執行緒。每個執行緒接收一些指標，按照它們所指向的內容積極地將任何存活物件疏散到 To-Space。當嘗試疏散一個物件時，清除任務需要通過原子讀取/寫入/比較並交換操作進行同步；可能有另一個清除任務通過不同的路徑找到相同的物件並同樣試圖移動它。成功移動物件的輔助執行緒之後會回來更新指標，並留下轉發指標，這樣其他工作者在到達該物件時可以更新其他指標。為了快速進行無需同步的存活物件分配，清除任務使用執行緒本地分配緩衝。

並行清除將清除工作分配到多個輔助執行緒和主執行緒。

主要垃圾回收​

V8 中的主要垃圾回收從並行標記開始。當堆接近動態計算出的限制值時，會開始並行標記任務。輔助執行緒分配到一些指標，並在跟蹤到所發現物件的所有引用時標記它們找到的每個物件。並行標記完全在背景中進行，同時 JavaScript 在主執行緒上執行。寫屏障用於跟蹤 JavaScript 在輔助執行緒並行標記時創建的物件之間的新引用。

主要垃圾回收使用並行標記和清除，並行壓縮和指標更新。

當並行標記完成後，或達到動態分配限制值，主執行緒執行一次快速的標記結束步驟。在此階段開始主執行緒停頓，這表示主要垃圾回收的總停頓時間。主執行緒再次掃描根，確保所有存活物件都被標記，並隨輔助手中的多個幫助者開始並行壓縮和指標更新。舊空間中的並非所有頁面都有資格進行壓縮 — 不符合條件的頁面將使用早些提到的自由列表進行清除。主執行緒在停頓時開始並行清除任務。這些清除任務與並行壓縮任務以及主執行緒本身並行運行，甚至在 JavaScript 在主執行緒上運行時仍可以繼續。

空閒時間垃圾回收​

JavaScript 的使用者無法直接訪問垃圾回收器；它完全由實現定義。然而，V8 提供了一種機制，讓嵌入器可以觸發垃圾回收，儘管 JavaScript 程式本身無法做到。垃圾回收器可以發布‘空閒任務’，這些任務是最終會被觸發的可選工作。像 Chrome 這樣的嵌入器可能對空閒時間有某種概念。例如，Chrome 以 60 幀每秒的速度運行，瀏覽器大約有 16.6 毫秒的時間來渲染每幀動畫。如果動畫工作提前完成，Chrome 可以選擇運行一些垃圾回收器創建的空閒任務，在下一幀之前利用剩餘時間。

空閒垃圾回收利用主執行緒的空閒時間主動執行垃圾回收工作。

如需更多詳細資訊，請參閱我們關於空閒時間垃圾回收的深入發表。

要點​

V8 的垃圾回收器自誕生以來已有了長足的進步。為現有的垃圾回收機制添加並行、增量和並發技術是一項耗時數年的努力，但卻帶來了巨大的回報，許多工作已移到了背景任務中執行。這大幅改善了停頓時間、延遲和頁面加載速度，使動畫、滾動和用戶交互更加流暢。並行 Scavenger 將主執行緒的年輕代垃圾回收總時間減少了約 20%–50%，具體取決於工作負載。閒置時間垃圾回收 在 Gmail 處於閒置狀態時，可以將 JavaScript 堆內存減少 45%。並發標記和清除 將繁重 WebGL 遊戲的停頓時間減少了高達 50%。

但這項工作還未完成。減少垃圾回收的停頓時間對於為用戶提供最佳的網頁體驗仍然很重要，我們正在研究更先進的技術。除此之外，Blink（Chrome 的渲染器）也有一個垃圾回收器（稱為 Oilpan），我們正在努力改進兩個回收器之間的協作，並將 Orinoco 的一些新技術移植到 Oilpan。

大多數開發者在開發 JavaScript 程式時並不需要考慮垃圾回收，但了解一些內部原理可以幫助您思考內存使用和有用的程式設計模式。例如，在 V8 堆的分代結構中，從垃圾回收器的角度來看，短命的對象實際上成本非常低，因為我們只需為在回收中存活的對象付費。這類模式對許多垃圾回收語言（不僅僅是 JavaScript）都非常奏效。