引擎V8推出「並發標記」，可節省60％-70％的GC時間

作者｜V8 博客

編輯｜覃雲 - 前端之巔公眾號

V8 官方博客宣布 V8 引擎在 GC 技術上獲得重大突破，這項技術名為「並發標記（ concurrent marking）」，在 GC 掃描和標記活動對象時，它允許 JavaScript 應用程序繼續運行。測試顯示，並發標記技術為主線程標記節省了 60％-70％的時間。並發標記是一個用新的平行和並發的 GC 替換舊的 GC 的項目，現在 Chrome 64 和 Node.js v10 已經默認啟用並發標記。

背景介紹

標記是 V8 Mark-Compact GC 工作的一個階段。在這個階段中，收集器發現並標記所有活動對象。標記從一組已知的活動對象開始，如全局對象和激活函數，即所謂的 roots，收集器將 roots 標記為活動的對象，並順著指針去尋找發現更多的活動對象。收集器繼續標記新發現的對象並跟隨指針移動，直到沒有發現更多的對象要標記為止。在標記結束時，所有無法讓應用程序訪問的未標記對象，都可以安全地回收。

我們可以將標記視為圖遍歷（Graph traversal）。堆內存上的對象是下圖中的節點，指針從一個對象指向另一個對象是圖的邊緣。給定圖中的一個節點，我們可以使用該對象的隱藏類找到該節點的所有外邊緣。

V8 使用每個對象的兩個 mark-bits 和一個標記工作表來實現標記。兩個 mark-bits 編碼三種顏色：白色（00），灰色（10）和黑色（11）。最初所有對象都是白色的，這意味著收集器還沒有發現它們。當收集器發現它並將其推到標記工作表上時，白色對象變灰。當收集器將它從標記工作列表中彈出並訪問其全部欄位時，灰色對象變黑，這種方案被稱為三色標記法。當沒有灰色對象時，標記結束。所有剩餘的白色對象都可以安全地被回收。

請注意，上述標記演算法僅適用於在標記進行中應用程序暫停的情況。如果我們允許應用程序在標記過程中運行，那麼應用程序可以更改圖形並最終誘騙收集器釋放活動對象。

減少標記停頓

對大型的堆內存來說，可能需要幾百毫秒才能完成一次標記。

長時間的停頓可能會導致應用程序無法響應，並導致用戶體驗不佳。2011 年，V8 從 stop-the-world 標記切換到增量標誌。在增量標記期間，GC 將標記工作分解為更小的模塊，並允許應用程序在模塊之間運行：

GC 決定每個模塊中執行多少增量標記以匹配應用程序的分配速率。一般情況下，這極大地提高了應用程序的響應速度。但對於大型堆內存來說，收集器試圖跟上應用程序分配速率的過程中，仍然可能會有長時間的停頓。

再者增量標記並不是免費的，應用程序必須通知 GC 關於更改對象圖的所有操作。V8 使用 Dijkstra-style write-barrier 來實現通知，在每次用 JavaScript 寫入 object.field = value 之後，V8 插入 write-barrier 代碼：

增量標記很好地集成了 GC 的閑置時間（idle time）。Chrome 的 Blink 任務調度程序在主線程的閑置時間內可以調度小增量標記步驟，而且不會造成混亂。如果閑置時間可用，優化效果會非常好。

由於 write-barrier 會有消耗，增量標記可能會降低應用程序的吞吐量。通過使用額外的 worker threads 可以提高吞吐量和暫停時間。有兩種方法可以在 worker threads 上進行標記：平行標記（parallel marking）和並發標記（concurrent marking）。

平行標記發生在主線程和工作線程（worker threads）上，應用程序在整個平行標記階段暫停，它是 stop-the-world 標記的多線程版本。

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

以下兩節將講述如何在 V8 中添加對平行標記和並行標記的支持。

平行標記

在平行期間，我們可以假定應用程序沒有運行。這大大簡化了實現過程，因為我們可以假定對象圖是靜態的並且不會發生變化。為了平行標記對象圖，我們需要確保 GC 數據結構是線程安全的，並找到一種方法有效地在線程之間共享標記工作。下圖顯示了平行標記所涉及的數據結構。箭頭指示數據流的方向，為簡單起見，該圖省略了整理堆內存碎片所需的數據結構。

需要注意的是，線程只能從對象圖中讀取並且不會被更改。對象的標記位點和標記工作表必須支持讀取和寫入的訪問。

並發標記

當工作線程正訪問堆內存上的對象時，並發標記允許 JavaScript 在主線程上運行，這為許多潛在的數據競爭（data races) 打開了大門。例如，當工作線程正在讀取欄位時，JavaScript 可能正在寫入對象欄位。數據競爭可能會讓 GC 錯誤地釋放活動對象或將原始值與指針混合在一起。

主線程上每個更改對象圖的操作都是數據競爭的潛在來源。由於 V8 是一款高性能引擎，具有許多對象布局優化功能，因此潛在的數據競爭來源很多。以下是可能導致的部分結果：

對象分配

寫入一個對象欄位

對象布局更改

從 snapshot 中反序列化

Materialization during deoptimization of a function.

在新一代 GC 中疏離（Evacuation）

代碼修補

主線程需要與工作線程同步，同步的成本和複雜程度取決於操作。

Write barrier

寫入對象欄位導致的數據競爭，可將寫入操作調整為 atomic write，並調整 write barrier 來解決：

保釋清單（Bailout worklist）

某些操作（例如代碼修補）需要獨家訪問該對象。早期，我們決定避免對象鎖定，因為它們可能導致優先順序逆轉（ priority inversion）問題，在這個過程中，主線程必須等待一個因為持有鎖定對象而被取消調度的工作線程。我們不鎖定對象，而是允許工作線程訪問該對象。工作線程通過將對象推入保釋清單來完成該工作，這個過程只能由主線程來處理：

工作線程保釋了優化的代碼對象、隱藏類和 weak collections，因為訪問它們需要鎖定或高昂的同步協議。

回顧過去，保釋清單對增量開發來說非常有用，我們開始使用工作線程來釋放所有對象類型並逐個添加並發標記。

更改對象布局

對象的欄位可以存儲三種值：標記的指針、標記的小整數（也稱為 Smi），或未標記的值（如拆箱的浮點數）。

通過將對象轉換為另一個隱藏類，V8 中將對象欄位從標記的狀態變為未標記的狀態（反之亦然），這種更改對象布局的方式對並發標記來說是不安全的。

如果在工作線程中使用舊的隱藏類訪問對象時發生更改，則可能會出現兩種類型的錯誤。首先，worker 可能會錯過一個指針，認為這是一個沒有標記的值。write barrier 可以防止這種錯誤。其次，worker 可能會將未標記的值視為指針並放棄引用它，這會導致無效的內存訪問，通常會導致程序崩潰。為了處理這種情況，我們使用在對象標記位上同步的 snapshotting 協議。協議涉及兩方面：主線程將對象欄位從標記變為未標記，然後工作線程訪問該對象。在更改欄位之前，主線程會確保該對象被標記為黑色，並將其推入保釋清單中供以後訪問：

如下面的代碼片段所示，工作線程首先載入對象的隱藏類，並使用 atomic relaxed 載入操作來快照（snapshots）隱藏類指定對象中的所有指針欄位。然後它會嘗試使用 atomic compare 和 swap 操作將對象標記為黑色。如果標記成功，則意味著快照必須與隱藏類一致，因為主線程在更改其布局之前會將對象標記為黑色。

放在一起

我們將並發標記整合到現有的增量標記基礎設施中，主線程通過掃描 roots 並填充標記工作表來啟動標記。之後，它會在工作線程上發布並發標記任務。工作線程通過合作清空（draining）標記工作表以加快主線程標記進度。主線程偶爾也會通過處理保釋清單和標記工作表參與標記。標記工作表變空後，主線程完成 GC。在最終確定之前，主線程重新掃描 roots ，可能會發現更多的白色對象，這些對象在工作線程的幫助下被平行標記。

結 果

測試結果顯示移動和桌面上每個 GC 周期的主線程標記時間分別減少了 65％和 70％。

最後，我們需要說的是 Node.js v10 現已支持並發標記。

https://v8project.blogspot.com/2018/06/concurrent-marking.html

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！