作者 | xcat

在詳細(xì)介紹 JavaScript 的垃圾回收算法之前，我們先來了解下 V8 引擎中的分代布局。

一、分代布局

分代假說（The Generational Hypothesis）認(rèn)為大多數(shù)對象的生命周期非常短暫，即從垃圾回收的視角來看，大多數(shù)對象在被分配后幾乎立即變成不可訪問狀態(tài)。這一規(guī)律不僅適用于 V8 或 JavaScript，對大多數(shù)動(dòng)態(tài)語言都成立。

V8 的分代式堆內(nèi)存布局正是基于這種對象生命周期特征而設(shè)計(jì)。堆內(nèi)存被分為「年輕代」（進(jìn)一步劃分為新生區(qū)和中間區(qū)兩個(gè)子代）和「老年代」。對象首先會(huì)被分配在「新生區(qū)」。如果它們在下一次垃圾回收中存活，就會(huì)被保留在年輕代但晉升為「中間區(qū)」?fàn)顟B(tài)。如果它們再次在垃圾回收中存活，就會(huì)晉升至老年代。

JavaScript 的垃圾回收算法分為兩種：

• 次要垃圾回收：使用「Scavenger 算法」，回收年輕代中的垃圾
• 主要垃圾回收：使用「標(biāo)記-清除算法」，回收老年代中的垃圾

二、Scavenger 算法

V8 中的次要垃圾回收（Minor GC）正是基于分代假說，使用的是 Scavenger 算法。

它分為「標(biāo)記」、「轉(zhuǎn)移」和「指針更新」三個(gè)步驟：

• 標(biāo)記（marking）：找到年輕代中的活躍對象
• 轉(zhuǎn)移（evacuating）：將標(biāo)記的對象復(fù)制到中間區(qū)或老年代（取決于是否已轉(zhuǎn)移過）
• 指針更新（pointer-updating）：更新被復(fù)制對象的所有引用指針

1. 標(biāo)記

Scavenger 算法的第一步是找到年輕代中的活躍對象。這個(gè)類似于標(biāo)記-清除算法中的標(biāo)記階段，需要從 GC Roots 開始，遍歷完整個(gè)引用圖，才能確定年輕代中哪些是存活的（其他的都是死亡的）。

(1) GC Roots

GC Roots（根集合）是垃圾回收器進(jìn)行可達(dá)性分析的起點(diǎn)，所有從 GC Roots 出發(fā)能直接或間接訪問到的對象都被視為存活對象。GC Roots 主要包括以下內(nèi)容：

①全局對象

• awindow
• global

②當(dāng)前執(zhí)行上下文中的活動(dòng)對象

• 正在執(zhí)行的函數(shù)內(nèi)部的變量
• 閉包中引用的外部變量

③DOM 節(jié)點(diǎn)

• 所有未被移除的 DOM 元素的引用

④活動(dòng)線程和事件隊(duì)列中的引用

• setTimeout、Promise 回調(diào)中引用的對象
• 未解綁的事件監(jiān)聽器

⑤內(nèi)置對象和系統(tǒng)引用

• 當(dāng)前正在執(zhí)行的作用域鏈（Scope Chain）
• 內(nèi)置對象（如 Math、JSON）的引用

(2) 跨代引用列表

根據(jù)分代假說，老年代中的對象大部分都是長期存活的，這意味本來只是為了找出年輕代中的活躍對象，結(jié)果卻遍歷了幾乎整個(gè)老年代對象。

為了避免遍歷幾乎整個(gè)老年代，V8 實(shí)現(xiàn)了一個(gè)機(jī)制，通過寫屏障（Write Barrier）維護(hù)了一個(gè)「老年代對年輕代的跨代引用列表」（a list of old-to-new references）。然后從 GC Roots 開始遍歷時(shí)，遇到老年代對象就直接跳過，僅遍歷其中的年輕代對象，這樣可以找到所有「從 GC Roots 出發(fā)，不經(jīng)過老年代的年輕代」。接著再將跨代引用列表中的對象加入到 GC Roots 中遍歷，同樣是遇到老年代對象就直接跳過，這樣就可以找到所有「被老年代引用的年輕代」。

通過維護(hù)了一個(gè)「跨代引用列表」的方式，V8 不遍歷老年代就能找到所有年輕代中的存活對象。

(3) 寫屏障

寫屏障是一種在垃圾收集過程中用于保持對象引用完整性和一致性的重要技術(shù)。在 V8 引擎中，寫屏障不僅在次要垃圾回收的標(biāo)記階段用于維護(hù)跨代引用列表，也在主要垃圾回收的并發(fā)標(biāo)記和增量標(biāo)記階段用于更新存活的對象。

寫屏障在 js 執(zhí)行寫操作（比如 object.field = vaule）的時(shí)候會(huì)被觸發(fā)，若一個(gè)對象更新了其引用信息，則會(huì)在寫屏障中更新跨代引用列表。保證 Scavenger 算法的標(biāo)記階段能夠獲得準(zhǔn)確的跨代引用信息。寫屏障在并發(fā)標(biāo)記和增量標(biāo)記的應(yīng)用將會(huì)在后續(xù)章節(jié)中介紹。

2. 轉(zhuǎn)移

Scavenger 算法的第二步是將標(biāo)記的對象復(fù)制到中間區(qū)或老年代（取決于是否已轉(zhuǎn)移過一次）。

復(fù)制（轉(zhuǎn)移）是垃圾回收中開銷非常大的操作。不過根據(jù)分代假說，年輕代中實(shí)際存活的對象比例極低，需要復(fù)制的對象也很少。通過僅移動(dòng)存活對象，其他所有內(nèi)存都成為了可回收的垃圾。這意味著我們只需承擔(dān)與存活對象數(shù)量成正比（而非與總分配量成正比）的復(fù)制成本。

(1) 半空間

在針對年輕代的回收過程中，存活的對象始終會(huì)被轉(zhuǎn)移到新的內(nèi)存頁。V8 為年輕代采用了半空間（Semi-Space）設(shè)計(jì)，這意味著總空間的一半始終預(yù)留為空，以支持轉(zhuǎn)移操作。

在回收期間，初始為空的部分稱為 To-Space，而需要復(fù)制的來源區(qū)域稱為 From-Space。轉(zhuǎn)移步驟會(huì)將所有存活對象移動(dòng)到連續(xù)的內(nèi)存塊中（位于同一內(nèi)存頁內(nèi)），從而完全消除內(nèi)存碎片（即死對象留下的間隙）。

隨后會(huì)交換兩個(gè)半空間的角色——To-Space 變?yōu)镕rom-Space，F(xiàn)rom-Space 變?yōu)?To-Space。垃圾回收完成后，新對象的內(nèi)存分配將從新的 From-Space 的下一個(gè)空閑地址開始。

下一次垃圾回收時(shí)，F(xiàn)rom-Space 中剛分配的對象會(huì)被轉(zhuǎn)移到 To-Space，而 From-Space 中已經(jīng)移動(dòng)過一次的對象則會(huì)被轉(zhuǎn)移到老年代：

3. 指針更新

Scavenger 算法的最后一步是更新引用地址。注意無論對象是第一次轉(zhuǎn)移（從 From-Space 到 To-Space），還是第二次轉(zhuǎn)移（從 From-Space 到老年代），都會(huì)在原來的位置留下一個(gè)轉(zhuǎn)發(fā)地址，用于更新原始指針的地址。

接下來 V8 需要知道內(nèi)存中哪些地方引用了這次轉(zhuǎn)移的對象，更新它們的指針。那么如何找到所有引用了這些對象的對象呢？由于對象的引用是單向的關(guān)系，似乎只能重新完全遍歷一次所有內(nèi)存，才能找到引用了該對象的對象。這肯定是不現(xiàn)實(shí)的，它會(huì)非常慢。所以 V8 引入了存儲(chǔ)緩沖區(qū)，將對象的引用關(guān)系由單向變成了雙向的，解決了「如何找到引用了該對象的對象」這個(gè)問題。

(1) 存儲(chǔ)緩沖區(qū)

V8 在內(nèi)存中每個(gè)對象建立引用關(guān)系時(shí)，反向記錄了一個(gè)地址，指向了引用該對象的對象，使得對象的引用關(guān)系就不是單向的了，而是雙向的。這個(gè)信息就存儲(chǔ)在「存儲(chǔ)緩沖區(qū)」（Store Buffer）中：

如圖所示，Page1 中的對象如果移動(dòng)了位置，就能通過 Page1 的 Store Buffer 找到引用了 ObjectA 和 ObjectB 的所有對象，然后分別更新其指針即可。但是這樣的結(jié)構(gòu)有個(gè)缺點(diǎn)，兩個(gè)存儲(chǔ)緩沖區(qū)可能包含了同一個(gè)指針記錄，當(dāng)多線程并行執(zhí)行指針更新時(shí)，多個(gè)線程可能同時(shí)更新同一個(gè)指針，造成數(shù)據(jù)競爭。V8 使用了「記憶集」來解決這個(gè)問題。

(2) 記憶集

為了解決多線程并行執(zhí)行指針更新時(shí)的數(shù)據(jù)競爭問題，V8 使用了「記憶集」（Remembered Set）替代「存儲(chǔ)緩沖區(qū)」來記錄對象的引用關(guān)系。

因?yàn)槊總€(gè)內(nèi)存頁的大小是固定的，所以可以給 Page2 分配一個(gè)固定大小的記憶集，將它「引用的對象的地址的偏移量的位置」標(biāo)記為紅色：

這樣的話，一旦 Page1 中的對象移動(dòng)了位置，就可以在每頁的記憶集中尋找固定偏移量的位置，看看是否為紅色，如果為紅色，則說明 Page2 需要更新該引用的指針。多線程可以按頁來分配任務(wù)，每個(gè)線程更新自己的頁的指針即可，如此一來，再也不會(huì)出現(xiàn)多個(gè)線程更新同一個(gè)頁的指針的情況了。

Scavenger 算法中，標(biāo)記、轉(zhuǎn)移、指針更新這三個(gè)步驟是交錯(cuò)進(jìn)行的，而不是嚴(yán)格分階階段完成。具體來說，標(biāo)記步驟會(huì)遍歷 GC Roots，一旦找到活對象，則立即將它轉(zhuǎn)移到 To-Space（或老年代），然后立即更新它的引用指針，接著再繼續(xù)遍歷 GC Roots。這樣交錯(cuò)執(zhí)行的好處是可以減少 GC 過程的內(nèi)存占用，提高復(fù)制效率。

4. 并行

并行（Parallel）是將垃圾回收任務(wù)分配給多個(gè)線程并行執(zhí)行，但它仍然會(huì)阻塞主線程（GC Stop-The-World），只是相對來說阻塞的時(shí)間變少了：

并發(fā)（Concurrent）則是將任務(wù)完全交給其他線程，完全不阻塞主線程：

并行是一種相對簡單的技術(shù)，因?yàn)橹骶€程的 js 已經(jīng)暫停了，不會(huì)再修改內(nèi)存。只需要確保多個(gè)線程訪問同一個(gè)對象時(shí)能得到及時(shí)的同步。而并發(fā)則是比較困難的技術(shù)，因?yàn)?js 主線程可能隨時(shí)讀寫內(nèi)存，使得垃圾回收中的標(biāo)記任務(wù)變得無效，還需擔(dān)心主線程和輔助線程讀寫同一個(gè)對象時(shí)造成的數(shù)據(jù)競爭。

次要垃圾回收時(shí)，因?yàn)橹恍枰獟呙枘贻p代內(nèi)存，所以標(biāo)記階段耗時(shí)很小。大部分耗時(shí)都在轉(zhuǎn)移階段，而轉(zhuǎn)移階段是無法并發(fā)的——轉(zhuǎn)移階段肯定不能讓主線程繼續(xù)執(zhí)行 js。次要垃圾回收只能在標(biāo)記和指針更新階段引入并發(fā)，帶來的性能提升很小，反而還增加了寫屏障、線程同步等耗時(shí)，得不償失。所以次要垃圾回收只使用了并行技術(shù)。

在 v6.2 之前，V8 的次要垃圾回收使用的是一種沒有并行技術(shù)的「單線程 Cheney 半空間復(fù)制算法」（Single-threaded Cheney’s Semispace Copy）。這種算法其實(shí)就是前文中介紹 Scavenger 算法中不包含并行的部分，它簡單易實(shí)現(xiàn)，適合單核環(huán)境，但也會(huì)完全阻塞主線程，沒有利用到多核的性能優(yōu)勢。

V8 對比了以下這三種算法，最終選擇了如今這種「并行的 Scavenger 算法」：

• 單線程 Cheney 半空間復(fù)制算法
• 并行標(biāo)記-轉(zhuǎn)移算法
• 并行的 Scavenger 算法

這里我簡單介紹下這三種算法的差異。

(1) 單線程 Cheney 半空間復(fù)制算法

這個(gè)算法其實(shí)就是前文中介紹 Scavenger 算法中不包含并行的部分：

將內(nèi)存空間分位年輕代和老年代，年輕代分位兩個(gè)半空間 From-Space 和 To-Space。垃圾回收器從 GC Roots 開始遍歷，交錯(cuò)的執(zhí)行這三個(gè)步驟：

• 標(biāo)記（marking）：找到年輕代中的活躍對象
• 轉(zhuǎn)移（evacuating）：將標(biāo)記的對象復(fù)制到 To-Space 或老年代（取決于是否已轉(zhuǎn)移過）
• 指針更新（pointer-updating）：更新被復(fù)制對象的所有引用指針

這三個(gè)步驟交錯(cuò)進(jìn)行，而不是嚴(yán)格分階階段完成。

(2) 并行標(biāo)記-轉(zhuǎn)移算法

將單線程 Cheney 半空間復(fù)制算法改造成多線程的難點(diǎn)在于：

• 單線程環(huán)境下，對引用圖的遍歷是線性的，如果多線程并行遍歷，則容易同時(shí)遍歷到同一個(gè)對象，造成數(shù)據(jù)競爭
• 多線程并行轉(zhuǎn)移對象時(shí)，內(nèi)存分配容易沖突
• 指針更新時(shí)，另一個(gè)線程可能已讀取了未轉(zhuǎn)移的對象

并行標(biāo)記-轉(zhuǎn)移算法（Parallel Mark-Evacuate）為了解決這幾個(gè)問題，放棄了單線程 Cheney 半空間復(fù)制算法中的交錯(cuò)執(zhí)行方式，改為階段性執(zhí)行：

• 標(biāo)記階段：多線程并行執(zhí)行標(biāo)記任務(wù)，即使重復(fù)標(biāo)記了也沒關(guān)系
• 轉(zhuǎn)移階段：等所有標(biāo)記任務(wù)全部完成后，再給多線程分配轉(zhuǎn)移任務(wù)，并行轉(zhuǎn)移到 To-Space 或老年代中。轉(zhuǎn)移時(shí)每個(gè)線程都有自己的本地分配緩沖區(qū)（local allocation buffers, LABs），轉(zhuǎn)移完成后會(huì)合并到一起
• 指針更新階段：轉(zhuǎn)移任務(wù)全部完成后，才會(huì)多線程并行執(zhí)行指針更新任務(wù)

并行標(biāo)記-轉(zhuǎn)移算法使用了分階段執(zhí)行這種簡單的方式解決了數(shù)據(jù)競爭、內(nèi)存分配等問題。但是它沒有考慮到任務(wù)的負(fù)載均衡問題，部分線程可能任務(wù)負(fù)載過重，而另一部分線程比較空閑，沒有充分利用到多線程的優(yōu)勢。

(3) 并行的 Scavenger 算法

V8 最終使用的并行的 Scavenger 算法（Parallel Scavenge）則是更為極致的優(yōu)化，它維護(hù)了一個(gè)全局工作列表，多線程首先從多個(gè) GC Roots 出發(fā)并行遍歷，每個(gè)線程不會(huì)遍歷完它的整個(gè)圖，而是在遍歷時(shí)選擇性的將子節(jié)點(diǎn)的遍歷任務(wù)加入到全局工作列表中。當(dāng)單個(gè)線程空閑時(shí)，就會(huì)從全局工作列表「竊取」（stealing）一個(gè)任務(wù)來處理。

這樣就解決了線程間的負(fù)載均衡問題。

另外，并行的 Scavenger 算法中實(shí)現(xiàn)了一個(gè)屏障（barrier）機(jī)制，使得在遍歷時(shí)如果遇到一些不適合并行處理的任務(wù)時(shí)，不會(huì)將它放到全局工作列表中（比如線性對象鏈 linear chain of objects）。這個(gè)屏障也保證了標(biāo)記、轉(zhuǎn)移、指針更新這三個(gè)階段可以交錯(cuò)執(zhí)行而不會(huì)出錯(cuò)。

通過升級(jí)為并行的 Scavenger 算法，次要垃圾回收總時(shí)間減少了 55%

5. 增量垃圾回收

增量垃圾回收是一種在瀏覽器空閑時(shí)段進(jìn)行垃圾回收的技術(shù)。

(1) 空閑時(shí)段

大多數(shù)瀏覽器的刷新率是 60Hz，這也是衡量網(wǎng)頁是否卡頓的標(biāo)準(zhǔn)。所以 Chrome 在繪制每一幀之間，有 16.6 毫秒的時(shí)間來計(jì)算渲染任務(wù)。如果 Chrome 在不到 16.6 毫秒的時(shí)間內(nèi)完成了任務(wù)，那么在開始渲染下一幀之前，瀏覽器就有空做一些其他時(shí)間，這個(gè)時(shí)間段就稱為空閑時(shí)段（Idel period）。瀏覽器提供了一個(gè)接口 requestIdleCallback 可以用來注冊空閑任務(wù)。

空閑時(shí)段只能執(zhí)行低優(yōu)先級(jí)的任務(wù)，包括 js 注冊的空閑任務(wù)和空閑垃圾回收任務(wù)，空閑任務(wù)會(huì)有一個(gè)截止期限，這是調(diào)度器對其預(yù)計(jì)空閑時(shí)間的預(yù)估，它的上限是 50ms，以確保瀏覽器能及時(shí)響應(yīng)用戶突然的輸入。空閑任務(wù)使用截止期限來估計(jì)它可以完成多少工作而不會(huì)導(dǎo)致輸入響應(yīng)卡頓或延遲。

為了在空閑期間執(zhí)行這些操作，V8 會(huì)將垃圾回收的空閑任務(wù)提交給調(diào)度器。當(dāng)這些空閑任務(wù)運(yùn)行時(shí)，它們會(huì)設(shè)定一個(gè)應(yīng)該完成的最后期限。V8 的垃圾回收空閑時(shí)間管理器會(huì)評估應(yīng)該執(zhí)行哪些垃圾回收任務(wù)，以減少內(nèi)存消耗，同時(shí)遵守最后期限以避免未來在幀渲染或輸入延遲方面的卡頓?？臻e垃圾回收任務(wù)可能包括次要垃圾回收或主要垃圾回收。

次要垃圾回收的速度很快，如果在空閑時(shí)段執(zhí)行的是次要垃圾回收，則會(huì)在這次任務(wù)中完成整個(gè)次要垃圾回收任務(wù)。而主要垃圾回收只會(huì)在空閑時(shí)段執(zhí)行增量標(biāo)記任務(wù)。這將在下一章介紹。

三、標(biāo)記-清除算法

標(biāo)記-清除（Mark-and-sweep）是垃圾回收中的經(jīng)典算法。JavaScript 中的主要垃圾回收（Major GC）就是使用這個(gè)算法來收集老年代中的垃圾。

它分為「標(biāo)記」、「清除」兩個(gè)主要步驟，以及「壓縮」這一可選步驟：

• 標(biāo)記（marking）：找到活躍對象
• 清除（sweeping）：回收死內(nèi)存
• 壓縮（Compacting）（可選）：整理內(nèi)存碎片

1. 標(biāo)記階段

標(biāo)記階段用來確定哪些對象可以被回收，它是垃圾回收的核心環(huán)節(jié)。

垃圾回收器通過「可達(dá)性」來判斷對象的「存活狀態(tài)」。這意味著當(dāng)前運(yùn)行時(shí)環(huán)境中所有可達(dá)的對象必須保留，而不可達(dá)的對象則需要被回收。標(biāo)記過程即尋找可達(dá)對象的過程。垃圾回收器從一組已知的指針起點(diǎn)（稱為 GC Roots）開始遍歷，沿著每個(gè)指向 JavaScript 對象的指針進(jìn)行追蹤，將找到的對象標(biāo)記為可達(dá)?；厥掌鲿?huì)遞歸地追蹤這些對象內(nèi)部的所有指針，直到標(biāo)記出運(yùn)行時(shí)環(huán)境中所有可達(dá)對象。

(1) 并發(fā)標(biāo)記

并行（Parallel）是將垃圾回收任務(wù)分配給多個(gè)線程并行執(zhí)行，但它仍然會(huì)阻塞主線程，只是阻塞的時(shí)間變少了：

并發(fā)（Concurrent）則是將任務(wù)完全交給其他線程，完全不阻塞主線程：

并行是一種相對簡單的技術(shù)，因?yàn)橹骶€程的 js 已經(jīng)暫停了，不會(huì)再修改內(nèi)存。只需要確保多個(gè)線程訪問同一個(gè)對象時(shí)能得到及時(shí)的同步。而并發(fā)則是比較困難的技術(shù)，因?yàn)?js 主線程可能隨時(shí)讀寫內(nèi)存，使得垃圾回收中的標(biāo)記任務(wù)變得無效，還需擔(dān)心主線程和輔助線程讀寫同一個(gè)對象時(shí)造成的數(shù)據(jù)競爭。

次要垃圾回收時(shí)，因?yàn)橹恍枰獟呙枘贻p代內(nèi)存，所以標(biāo)記階段耗時(shí)很小。大部分耗時(shí)都在轉(zhuǎn)移階段，而轉(zhuǎn)移階段是無法并發(fā)的。所以次要垃圾回收只使用了并行技術(shù)。引入并發(fā)只能減少標(biāo)記和指針更新階段耗時(shí)，反而增加了寫屏障、線程同步等耗時(shí)，得不償失。

主要垃圾回收時(shí)，因?yàn)樾枰獟呙枵麄€(gè)老年代內(nèi)存，所以標(biāo)記階段耗時(shí)比較長。所以主要垃圾回收可以利用并發(fā)標(biāo)記技術(shù)，使得 V8 的標(biāo)記階段都在輔助線程中執(zhí)行時(shí)，完全不阻塞 js 主線程：

(2) 三色標(biāo)記

標(biāo)記階段的工作可以看作是圖的遍歷。堆內(nèi)存上的對象就是圖的節(jié)點(diǎn)，一個(gè)對象對另一個(gè)對象的指針就是圖的邊。標(biāo)記階段的目標(biāo)就是從 Roots 出發(fā)，找到所有引用到的對象。

假如是單線程遍歷圖，可以在一個(gè)調(diào)用棧中直接廣度或深度遍歷即可。但要實(shí)現(xiàn)多線程并發(fā)標(biāo)記，則需要有一個(gè)標(biāo)記工作列表（marking worklist），每個(gè)線程都從標(biāo)記工作列表中拿取一個(gè)工作，并且把下一層級(jí)的工作推入到標(biāo)記工作列表中。

V8 在標(biāo)記階段會(huì)將每個(gè)節(jié)點(diǎn)標(biāo)記為三種顏色：

• 白色：尚未發(fā)現(xiàn)的節(jié)點(diǎn)
• 灰色：發(fā)現(xiàn)白色節(jié)點(diǎn)，將其推入到標(biāo)記工作列表中，變成灰色節(jié)點(diǎn)
• 黑色：從標(biāo)記工作列表中拿取一個(gè)灰色節(jié)點(diǎn)，訪問其所有字段，這些字段中若有白色節(jié)點(diǎn)則推入到標(biāo)記工作列表中變成灰色節(jié)點(diǎn)，訪問完所有字段后，將該節(jié)點(diǎn)變成黑色

當(dāng)標(biāo)記工作列表為空時(shí)，就意味著完成了整個(gè)標(biāo)記階段，確定了圖中所有的活躍對象（黑色節(jié)點(diǎn)）和死亡對象（白色節(jié)點(diǎn)）。

(3) 寫屏障

并發(fā)標(biāo)記時(shí)，主線程還在執(zhí)行 js：

此時(shí)主線程可能修改內(nèi)存中的引用關(guān)系，多線程的讀寫操作造成了數(shù)據(jù)競爭，這導(dǎo)致輔助線程中的三色標(biāo)記失效。

寫屏障解決了數(shù)據(jù)競爭的問題。寫屏障在 js 執(zhí)行寫操作（比如 object.field = vaule）的時(shí)候會(huì)被觸發(fā)，若一個(gè)字段從一個(gè)對象指向一個(gè)新的對象時(shí)，寫屏障會(huì)檢查并調(diào)整新對象的顏色（標(biāo)記狀態(tài)），如果該對象是白色（未被標(biāo)記為活的），將其改為灰色并加入待處理隊(duì)列。

寫屏障會(huì)帶來一定的性能開銷，但它確保了三色標(biāo)記的正確性。

(4) 并行標(biāo)記

大部分情況下，并發(fā)標(biāo)記不阻塞主線程，是更優(yōu)的選擇。

但有時(shí)候，對象的引用關(guān)系可能涉及復(fù)雜的線程同步問題，使得標(biāo)記工作難以并發(fā)執(zhí)行。

此時(shí)輔助線程會(huì)將此標(biāo)記工作任務(wù)推送到一個(gè)名為救援工作列表（Bailout worklist）的列表中，求助于主線程通過阻塞 js 來執(zhí)行此標(biāo)記任務(wù)。

救援工作列表中的任務(wù)只會(huì)被主線程取走，此時(shí)會(huì)阻塞主線程的 js 執(zhí)行，所有線程都會(huì)并行的執(zhí)行標(biāo)記任務(wù)：

(5) 增量標(biāo)記

瀏覽器在下一幀渲染之前，可能有一些空閑時(shí)段，這個(gè)時(shí)段也可以用來做主要垃圾回收的增量標(biāo)記任務(wù)。

為了減少對應(yīng)用程序性能的影響，增量標(biāo)記任務(wù)可以在多個(gè)空閑時(shí)段中執(zhí)行，每個(gè)空閑時(shí)段內(nèi)執(zhí)行一段時(shí)間，然后中斷以便其他重要任務(wù)（如主線程的 JavaScript 任務(wù)）可以繼續(xù)執(zhí)行。在下一個(gè)空閑時(shí)段，再繼續(xù)未完成的標(biāo)記任務(wù)。

在增量標(biāo)記過程中，垃圾回收并非一次性完成，而是分成許多小的步驟。在主線程 js 執(zhí)行過程中，內(nèi)存中對象的引用關(guān)系可能發(fā)生變化，這會(huì)導(dǎo)致之前的標(biāo)記失效了。為了解決這個(gè)問題，V8 使用寫屏障來標(biāo)記那些引用關(guān)系發(fā)生變化的對象。這樣，即便在垃圾回收暫停期間對象的引用關(guān)系發(fā)生了變化，垃圾回收器依然能夠準(zhǔn)確地識(shí)別和處理這些變化。

由于清除任務(wù)和壓縮任務(wù)的耗時(shí)較長，空閑時(shí)段不會(huì)用來做清除任務(wù)和壓縮任務(wù)。

(6) 黑色分配

根據(jù)分代假說，大多數(shù)對象的生命周期非常短暫，在次要垃圾回收中就會(huì)被回收掉。而經(jīng)歷了兩次次要垃圾回收都沒被回收的對象，就會(huì)被晉升到老年代。

我們可以認(rèn)為，剛從新生代晉升到老年代的對象，大概率是一個(gè)長期活躍的對象，至少在下次主要垃圾回收時(shí)也還是活躍的對象，不會(huì)被回收——假如一個(gè)剛晉升到老年代的對象馬上就被回收了，說明這個(gè)分代假說本身就有問題了。既然它大概率在下次主要垃圾回收時(shí)還保持活躍，那么就沒必要在標(biāo)記階段掃描它了，直接將它標(biāo)記為活躍即可。這就是黑色分配的理論依據(jù)——?jiǎng)倳x升到老年代的對象，至少應(yīng)該在下一次主要垃圾回收中存活下來。

在次要垃圾回收的標(biāo)記階段，V8 將準(zhǔn)備從新生代晉升到老年代的對象染成黑色。在次要垃圾回收的轉(zhuǎn)移階段，黑色對象會(huì)被移動(dòng)到一個(gè)特殊的黑色內(nèi)存頁中，這個(gè)內(nèi)存頁的所有對象都是黑色的。在下次主要垃圾回收的標(biāo)記階段，將會(huì)直接跳過黑色內(nèi)存頁的掃描。

黑色分配這一優(yōu)化手段將吞吐量和延遲得分提高了約 30%，同時(shí)由于標(biāo)記進(jìn)度更快且整體垃圾收集工作更少，內(nèi)存使用量減少了約 20%。

2. 清除階段

清除過程會(huì)將死亡對象留下的內(nèi)存空隙加入名為「空閑列表（free-list）」的數(shù)據(jù)結(jié)構(gòu)。當(dāng)標(biāo)記完成后，垃圾回收器會(huì)掃描整個(gè)堆內(nèi)存，找到由不可達(dá)對象形成的連續(xù)內(nèi)存空隙，并將其加入對應(yīng)大小的空閑列表。空閑列表按內(nèi)存塊大小分類存儲(chǔ)以便快速檢索。后續(xù)需要分配內(nèi)存時(shí)，只需查詢空閑列表即可找到合適大小的內(nèi)存塊。

(1) 并發(fā)清除

因?yàn)榇宄膬?nèi)存都是死亡內(nèi)存，絕對不會(huì)再被主線程訪問到了。所以清除任務(wù)可以完全放在輔助線程中并發(fā)執(zhí)行。并且即使主線程 js 已經(jīng)恢復(fù)執(zhí)行時(shí)，輔助線程的清除任務(wù)還可以繼續(xù)執(zhí)行。

3. 壓縮階段

基于碎片化啟發(fā)式算法（fragmentation heuristic），主要垃圾回收會(huì)選擇性地對某些內(nèi)存頁執(zhí)行對象遷移/壓縮操作。

這個(gè)過程可以類比老式電腦的硬盤碎片整理：我們將存活對象復(fù)制到當(dāng)前未被壓縮的其他內(nèi)存頁（利用其空閑列表）。通過這種方式，可以充分利用死亡對象遺留在內(nèi)存中的零散小空隙。復(fù)制存活對象存在一個(gè)潛在問題：復(fù)制大量長生命周期對象會(huì)帶來高昂成本。因此我們選擇只壓縮碎片化程度較高的內(nèi)存頁，而對其他內(nèi)存頁僅執(zhí)行清除操作（不復(fù)制存活對象）。壓縮階段會(huì)阻塞 js 主線程，避免數(shù)據(jù)競爭帶來的問題。壓縮階段會(huì)并行執(zhí)行。

最后總結(jié)一下，標(biāo)記-清除算法的整個(gè)流程如下：

(1) 并發(fā)、增量標(biāo)記：當(dāng)堆內(nèi)存接近動(dòng)態(tài)計(jì)算的上限時(shí)，V8 會(huì)啟動(dòng)并發(fā)、增量標(biāo)記。瀏覽器會(huì)在主線程空閑階段執(zhí)行增量標(biāo)記，在非空閑階段執(zhí)行并發(fā)標(biāo)記。主線程執(zhí)行期間可能會(huì)產(chǎn)生新的對象引用關(guān)系，V8 采用寫屏障（Write Barrier）機(jī)制來記錄 js 在并發(fā)、增量標(biāo)記階段創(chuàng)建的新對象引用，確保標(biāo)記結(jié)果的準(zhǔn)確性，當(dāng)遇到難以并發(fā)執(zhí)行的標(biāo)記任務(wù)時(shí)，會(huì)推入到救援工作列表中，交給最終標(biāo)記階段執(zhí)行。

(2) 最終標(biāo)記（并行標(biāo)記）：并發(fā)、增量標(biāo)記完成后，主線程會(huì)暫停執(zhí)行 js，此時(shí)進(jìn)入最終標(biāo)記階段（marking finalization），多線程并行執(zhí)行救援工作列表的工作，然后重新掃描 GC Roots，確保所有存活對象都被標(biāo)記了。

(3) 并行壓縮階段：主線程繼續(xù)暫停執(zhí)行 js，多線程并行執(zhí)行壓縮任務(wù)，將存活對象移動(dòng)到連續(xù)內(nèi)存塊以減少碎片，并更新相關(guān)指針。部分無法壓縮的頁則通過空閑列表（free-list）進(jìn)行內(nèi)存回收。

(4) 并發(fā)清除階段：與此同時(shí)，輔助線程執(zhí)行并發(fā)清除任務(wù)，這些任務(wù)與并行壓縮及主線程代碼執(zhí)行同時(shí)進(jìn)行，即使主線程 js 恢復(fù)運(yùn)行，清除任務(wù)仍可在輔助線程中繼續(xù)執(zhí)行。

四、垃圾回收的觸發(fā)時(shí)機(jī)

JavaScirpt 的垃圾回收時(shí)機(jī)無法用程序控制，這是設(shè)計(jì)如此的：

• 程序員可能希望在時(shí)間關(guān)鍵的應(yīng)用階段關(guān)閉垃圾回收，以避免因垃圾回收引起的幀丟失。然而，這會(huì)使應(yīng)用邏輯變得復(fù)雜，維護(hù)變得困難。如果在代碼的某個(gè)分支中忘記重新開啟垃圾回收，可能會(huì)導(dǎo)致內(nèi)存耗盡。
• 程序員無法預(yù)估手動(dòng)觸發(fā)的垃圾回收需要多長時(shí)間，可能會(huì)導(dǎo)致應(yīng)用程序本身引入卡頓，反而無法達(dá)到預(yù)期的性能優(yōu)化效果。
• 這會(huì)給 js 引擎帶來額外的工作，手動(dòng)觸發(fā)垃圾回收可能會(huì)干擾垃圾回收器的啟發(fā)式算法，導(dǎo)致不可靠的內(nèi)存管理行為。

1. 次要垃圾回收

• 當(dāng)年輕代的活動(dòng)空間被填滿時(shí)觸發(fā)
• 當(dāng)程序請求分配新的內(nèi)存，并且年輕代沒有足夠內(nèi)存時(shí)觸發(fā)
• 當(dāng)空閑時(shí)段有足夠的空閑時(shí)間時(shí)觸發(fā)。但并不是一定會(huì)觸發(fā)，因?yàn)轭l繁的觸發(fā)可能導(dǎo)致本可以在次要垃圾回收中得到回收的對象被移入了老年代

2. 主要垃圾回收

• 當(dāng)老年代中的對象占用空間增長到超過某個(gè)啟發(fā)式計(jì)算的內(nèi)存限制時(shí)觸發(fā)
• 如果整個(gè)堆的使用情況超過了特定的內(nèi)存閾值，基于啟發(fā)式算法，系統(tǒng)可能觸發(fā)主要垃圾回收
• 當(dāng)堆大小達(dá)到某個(gè)策略設(shè)定的開始增量標(biāo)記的限制時(shí)，會(huì)開始在空閑時(shí)段執(zhí)行增量標(biāo)記，增量標(biāo)記完成后，開始清除和壓縮，最終完成主要垃圾回收
• 在檢測到應(yīng)用的長期不活躍狀態(tài)時(shí)，甚至在沒有達(dá)到內(nèi)存限制的情況下，可能主動(dòng)進(jìn)行主要垃圾回收來減少內(nèi)存占用

3. 動(dòng)態(tài)的垃圾回收頻率

在一次完整的垃圾收集結(jié)束時(shí)，V8 的堆增長策略會(huì)根據(jù)存活對象的數(shù)量和內(nèi)存的余量，來決定下一次垃圾收集的時(shí)間。所以垃圾回收的頻率會(huì)根據(jù)內(nèi)存的狀態(tài)實(shí)時(shí)變化。

4. 低內(nèi)存模式

垃圾回收的吞吐量、造成的頁面延遲以及占用內(nèi)存之間是一個(gè)不可能三角。針對不同的設(shè)備，需要有不同的內(nèi)存回收策略。對于內(nèi)存較低的移動(dòng)設(shè)備，即內(nèi)存少于 512 MB 的設(shè)備，優(yōu)先考慮延遲和吞吐量而不是內(nèi)存消耗可能會(huì)導(dǎo)致內(nèi)存不足而崩潰。

為了更好地平衡這些低內(nèi)存移動(dòng)設(shè)備的權(quán)衡，V8 引入了一種特殊的低內(nèi)存模式，該模式調(diào)整了一些垃圾收集啟發(fā)模式以降低 JavaScript 垃圾收集堆的內(nèi)存使用量。一般來說，在一次完整的垃圾收集結(jié)束時(shí)，V8 會(huì)根據(jù)存活對象的數(shù)量和內(nèi)存余量來決定下一次垃圾收集的時(shí)間。在低內(nèi)存模式下，內(nèi)存余量更少，所以垃圾回收會(huì)更頻繁的觸發(fā)。

一般來說，主要垃圾回收會(huì)在內(nèi)存還有空余時(shí)觸發(fā)，此時(shí)會(huì)在空閑時(shí)段執(zhí)行增量標(biāo)記，等標(biāo)記任務(wù)完全完成后，才會(huì)阻塞主線程，開始執(zhí)行清除和壓縮。但在低內(nèi)存模式下，由于內(nèi)存余量更少，可能在增量標(biāo)記還未完成時(shí)，就觸發(fā)了主線程的垃圾回收，此時(shí)主線程 js 阻塞，主線程和輔助線程并行的執(zhí)行剩余的標(biāo)記任務(wù)和后續(xù)的清除、壓縮任務(wù)。低內(nèi)存模式雖然使垃圾回收更頻繁了，但是也使得移動(dòng)端設(shè)備上的堆內(nèi)存消耗減少了 50%

5. 不活躍的網(wǎng)頁

一般來說，瀏覽器會(huì)對每個(gè)網(wǎng)頁限制內(nèi)存，一旦達(dá)到限值，則會(huì)啟動(dòng)主要垃圾回收。然而，如果網(wǎng)頁在達(dá)到分配限制之前變得不活躍，那么在網(wǎng)頁整個(gè)不活躍期間都不會(huì)進(jìn)行主要的垃圾回收——這正是大多數(shù)網(wǎng)頁會(huì)遇到的情況——大多數(shù)網(wǎng)頁在加載頁面時(shí)會(huì)使用較多內(nèi)存，因?yàn)樗鼈冋诔跏蓟鋬?nèi)部數(shù)據(jù)結(jié)構(gòu)，加載后不久（幾秒或幾分鐘內(nèi)），網(wǎng)頁通常變得不活躍。如果此時(shí)還未達(dá)到內(nèi)存限值，就不會(huì)進(jìn)行主要垃圾回收了。

這會(huì)導(dǎo)致不活躍的網(wǎng)頁遲遲得不到內(nèi)存回收。所以 Chrome 實(shí)現(xiàn)了一個(gè)名為「Memory Reducer」的控制器，它會(huì)檢測網(wǎng)頁何時(shí)變得不活躍，并主動(dòng)調(diào)度一次主要垃圾回收——即使此時(shí)還未達(dá)到內(nèi)存分配限制。