摘要：新生代的對象為存活時間較短的對象，老生代中的對象為存活時間較長或常駐內存的對象。分別對新生代和老生代使用不同的垃圾回收算法來提升垃圾回收的效率。如果指向老生代我們就不必考慮它了。

這篇文章的所有內容均來自 樸靈的《深入淺出Node.js》及A tour of V8:Garbage Collection，后者還有中文翻譯版V8 之旅： 垃圾回收器，我在這里只是做了個記錄和結合

JavaScript使用垃圾回收機制來自動管理內存。垃圾回收是一把雙刃劍，其好處是可以大幅簡化程序的內存管理代碼，降低程序員的負擔，減少因長時間運轉而帶來的內存泄露問題。但使用了垃圾回收即意味著程序員將無法掌控內存。ECMAScript沒有暴露任何垃圾回收器的接口。我們無法強迫其進行垃圾回收，更無法干預內存管理

在瀏覽器中，V8引擎實例的生命周期不會很長（誰沒事一個頁面開著幾天幾個月不關），而且運行在用戶的機器上。如果不幸發生內存泄露等問題，僅僅會影響到一個終端用戶。且無論這個V8實例占用了多少內存，最終在關閉頁面時內存都會被釋放，幾乎沒有太多管理的必要（當然并不代表一些大型Web應用不需要管理內存）。但如果使用Node作為服務器，就需要關注內存問題了，一旦內存發生泄漏，久而久之整個服務將會癱瘓（服務器不會頻繁的重啟）

Node與其他語言不同的一個地方，就是其限制了JavaScript所能使用的內存（64位為1.4GB，32位為0.7GB），這也就意味著將無法直接操作一些大內存對象。這很令人匪夷所思，因為很少有其他語言會限制內存的使用

V8之所以限制了內存的大小，表面上的原因是V8最初是作為瀏覽器的JavaScript引擎而設計，不太可能遇到大量內存的場景，而深層次的原因則是由于V8的垃圾回收機制的限制。由于V8需要保證JavaScript應用邏輯與垃圾回收器所看到的不一樣，V8在執行垃圾回收時會阻塞JavaScript應用邏輯，直到垃圾回收結束再重新執行JavaScript應用邏輯，這種行為被稱為“全停頓”（stop-the-world）。若V8的堆內存為1.5GB，V8做一次小的垃圾回收需要50ms以上，做一次非增量式的垃圾回收甚至要1秒以上。這樣瀏覽器將在1s內失去對用戶的響應，造成假死現象。如果有動畫效果的話，動畫的展現也將顯著受到影響

當然這個限制是可以打開的，類似于JVM，我們通過在啟動node時可以傳遞--max-old-space-size或--max-new-space-size來調整內存限制的大小，前者確定老生代的大小，單位為MB，后者確定新生代的大小，單位為KB。這些配置只在V8初始化時生效，一旦生效不能再改變

V8的堆其實并不只是由老生代和新生代兩部分構成，可以將堆分為幾個不同的區域：
*　新生代內存區：大多數的對象被分配在這里，這個區域很小但是垃圾回特別頻繁
*　老生代指針區：屬于老生代，這里包含了大多數可能存在指向其他對象的指針的對象，大多數從新生代晉升的對象會被移動到這里
*　老生代數據區：屬于老生代，這里只保存原始數據對象，這些對象沒有指向其他對象的指針
*　大對象區：這里存放體積超越其他區大小的對象，每個對象有自己的內存，垃圾回收其不會移動大對象
*　代碼區：代碼對象，也就是包含JIT之后指令的對象，會被分配在這里。唯一擁有執行權限的內存區
*　Cell區、屬性Cell區、Map區：存放Cell、屬性Cell和Map，每個區域都是存放相同大小的元素，結構簡單

每個區域都是由一組內存頁構成，內存頁是V8申請內存的最小單位，除了大對象區的內存頁較大以外，其他區的內存頁都是1MB大小，而且按照1MB對齊。內存頁除了存儲的對象，還有一個包含元數據和標識信息的頁頭，以及一個用于標記哪些對象是活躍對象的位圖區。另外每個內存頁還有一個多帶帶分配在另外內存區的槽緩沖區，里面放著一組對象，這些對象可能指向其他存儲在該頁的對象。垃圾回收器只會針對新生代內存區、老生代指針區以及老生代數據區進行垃圾回收

如何確定哪些內存需要回收，哪些內存不需要回收，這是垃圾回收期需要解決的最基本問題。我們可以這樣假定，一個對象為活對象當且僅當它被一個根對象或另一個活對象指向。根對象永遠是活對象，它是被瀏覽器或V8所引用的對象。被局部變量所指向的對象也屬于根對象，因為它們所在的作用域對象被視為根對象。全局對象（Node中為global，瀏覽器中為window）自然是根對象。瀏覽器中的DOM元素也屬于根對象

垃圾回收器需要面臨一個問題，它需要判斷哪些是數據，哪些是指針。由于很多垃圾回收算法會將對象在內存中移動（緊湊，減少內存碎片），所以經常需要進行指針的改寫

目前主要有三種方法來識別指針：
1. 保守法：將所有堆上對齊的字都認為是指針，那么有些數據就會被誤認為是指針。于是某些實際是數字的假指針，會背誤認為指向活躍對象，導致內存泄露（假指針指向的對象可能是死對象，但依舊有指針指向——這個假指針指向它）同時我們不能移動任何內存區域。
2. 編譯器提示法：如果是靜態語言，編譯器能夠告訴我們每個類當中指針的具體位置，而一旦我們知道對象時哪個類實例化得到的，就能知道對象中所有指針。這是JVM實現垃圾回收的方式，但這種方式并不適合JS這樣的動態語言
3. 標記指針法：這種方法需要在每個字末位預留一位來標記這個字段是指針還是數據。這種方法需要編譯器支持，但實現簡單，而且性能不錯。V8采用的是這種方式。V8將所有數據以32bit字寬來存儲，其中最低一位保持為0，而指針的最低兩位為01

自動垃圾回收算法的演變過程中出現了很多算法，但是由于不同對象的生存周期不同，沒有一種算法適用于所有的情況。所以V8采用了一種分代回收的策略，將內存分為兩個生代：新生代和老生代。新生代的對象為存活時間較短的對象，老生代中的對象為存活時間較長或常駐內存的對象。分別對新生代和老生代使用不同的垃圾回收算法來提升垃圾回收的效率。對象起初都會被分配到新生代，當新生代中的對象滿足某些條件（后面會有介紹）時，會被移動到老生代（晉升）

默認情況下，64位環境下的V8引擎的新生代內存大小32MB、老生代內存大小為1400MB，而32位則減半，分別為16MB和700MB。V8內存的最大保留空間分別為1464MB（64位）和732MB（32位）。具體的計算公式是4*reserved_semispace_space_ + max_old_generation_size_，新生代由兩塊reserved_semispace_space_組成，每塊16MB（64位）或8MB（32位）

大多數的對象被分配在這里，這個區域很小但是垃圾回特別頻繁。在新生代分配內存非常容易，我們只需要保存一個指向內存區的指針，不斷根據新對象的大小進行遞增即可。當該指針到達了新生代內存區的末尾，就會有一次清理（僅僅是清理新生代）

新生代使用Scavenge算法進行回收。在Scavenge算法的實現中，主要采用了Cheney算法。

Cheney算法算法是一種采用復制的方式實現的垃圾回收算法。它將內存一分為二，每一部分空間稱為semispace。在這兩個semispace中，一個處于使用狀態，另一個處于閑置狀態。處于使用狀態的semispace空間稱為From空間，處于閑置狀態的空間稱為To空間，當我們分配對象時，先是在From空間中進行分配。當開始進行垃圾回收算法時，會檢查From空間中的存活對象，這些存活對象將會被復制到To空間中（復制完成后會進行緊縮），而非活躍對象占用的空間將會被釋放。完成復制后，From空間和To空間的角色發生對換。也就是說，在垃圾回收的過程中，就是通過將存活對象在兩個semispace之間進行復制。可以很容易看出來，使用Cheney算法時，總有一半的內存是空的。但是由于新生代很小，所以浪費的內存空間并不大。而且由于新生代中的對象絕大部分都是非活躍對象，需要復制的活躍對象比例很小，所以其時間效率十分理想。復制的過程采用的是BFS（廣度優先遍歷）的思想，從根對象出發，廣度優先遍歷所有能到達的對象

具體的執行過程大致是這樣：

首先將From空間中所有能從根對象到達的對象復制到To區，然后維護兩個To區的指針scanPtr和allocationPtr，分別指向即將掃描的活躍對象和即將為新對象分配內存的地方，開始循環。循環的每一輪會查找當前scanPtr所指向的對象，確定對象內部的每個指針指向哪里。如果指向老生代我們就不必考慮它了。如果指向From區，我們就需要把這個所指向的對象從From區復制到To區，具體復制的位置就是allocationPtr所指向的位置。復制完成后將scanPtr所指對象內的指針修改為新復制對象存放的地址，并移動allocationPtr。如果一個對象內部的所有指針都被處理完，scanPtr就會向前移動，進入下一個循環。若scanPtr和allocationPtr相遇，則說明所有的對象都已被復制完，From區剩下的都可以被視為垃圾，可以進行清理了

舉個栗子(以及湊篇幅)，如果有類似如下的引用情況：

          +----- A對象
          |
根對象----+----- B對象 ------ E對象
          |
          +----- C對象 ----+---- F對象 
                           |
                           +---- G對象 ----- H對象

    D對象

在執行Scavenge之前，From區長這幅模樣

+---+---+---+---+---+---+---+---+--------+
| A | B | C | D | E | F | G | H |        |
+---+---+---+---+---+---+---+---+--------+

那么首先將根對象能到達的ABC對象復制到To區，于是乎To區就變成了這個樣子：

          allocationPtr
             ↓ 
+---+---+---+----------------------------+
| A | B | C |                            |
+---+---+---+----------------------------+
 ↑
scanPtr  

接下來進入循環，掃描scanPtr所指的A對象，發現其沒有指針，于是乎scanPtr移動，變成如下這樣

          allocationPtr
             ↓ 
+---+---+---+----------------------------+
| A | B | C |                            |
+---+---+---+----------------------------+
     ↑
  scanPtr  

接下來掃描B對象，發現其有指向E對象的指針，且E對象在From區，那么我們需要將E對象復制到allocationPtr所指的地方并移動allocationPtr指針：

            allocationPtr
                 ↓ 
+---+---+---+---+------------------------+
| A | B | C | E |                        |
+---+---+---+---+------------------------+
     ↑
  scanPtr  

B對象里所有指針都已被復制完，所以移動scanPtr：

            allocationPtr
                 ↓ 
+---+---+---+---+------------------------+
| A | B | C | E |                        |
+---+---+---+---+------------------------+
         ↑
      scanPtr  

接下來掃描C對象，C對象中有兩個指針，分別指向F對象和G對象，且都在From區，先復制F對象到To區：

                allocationPtr
                     ↓ 
+---+---+---+---+---+--------------------+
| A | B | C | E | F |                    |
+---+---+---+---+---+--------------------+
         ↑
      scanPtr  

然后復制G對象到To區

                    allocationPtr
                         ↓ 
+---+---+---+---+---+---+----------------+
| A | B | C | E | F | G |                |
+---+---+---+---+---+---+----------------+
         ↑
      scanPtr  

這樣C對象內部的指針已經復制完成了，移動scanPtr：

                    allocationPtr
                         ↓ 
+---+---+---+---+---+---+----------------+
| A | B | C | E | F | G |                |
+---+---+---+---+---+---+----------------+
             ↑
          scanPtr  

逐個掃描E，F對象，發現其中都沒有指針，移動scanPtr：

                    allocationPtr
                         ↓ 
+---+---+---+---+---+---+----------------+
| A | B | C | E | F | G |                |
+---+---+---+---+---+---+----------------+
                     ↑
                  scanPtr  

掃描G對象，發現其中有一個指向H對象的指針，且H對象在From區，復制H對象到To區，并移動allocationPtr：

                        allocationPtr
                             ↓ 
+---+---+---+---+---+---+---+------------+
| A | B | C | E | F | G | H |            |
+---+---+---+---+---+---+---+------------+
                     ↑
                  scanPtr  

完成后由于G對象沒有其他指針，且H對象沒有指針移動scanPtr：

                        allocationPtr
                             ↓ 
+---+---+---+---+---+---+---+------------+
| A | B | C | E | F | G | H |            |
+---+---+---+---+---+---+---+------------+
                             ↑
                           scanPtr  

此時scanPtr和allocationPtr重合，說明復制結束

可以對比一下From區和To區在復制完成后的結果：

//From區
+---+---+---+---+---+---+---+---+--------+
| A | B | C | D | E | F | G | H |        |
+---+---+---+---+---+---+---+---+--------+
//To區
+---+---+---+---+---+---+---+------------+
| A | B | C | E | F | G | H |            |
+---+---+---+---+---+---+---+------------+

D對象沒有被復制，它將被作為垃圾進行回收

如果新生代中的一個對象只有一個指向它的指針，而這個指針在老生代中，我們如何判斷這個新生代的對象是否存活？為了解決這個問題，需要建立一個列表用來記錄所有老生代對象指向新生代對象的情況。每當有老生代對象指向新生代對象的時候，我們就記錄下來

當一個對象經過多次新生代的清理依舊幸存，這說明它的生存周期較長，也就會被移動到老生代，這稱為對象的晉升。具體移動的標準有兩種：
1. 對象從From空間復制到To空間時，會檢查它的內存地址來判斷這個對象是否已經經歷過一個新生代的清理，如果是，則復制到老生代中，否則復制到To空間中
2. 對象從From空間復制到To空間時，如果To空間已經被使用了超過25%，那么這個對象直接被復制到老生代

老生代所保存的對象大多數是生存周期很長的甚至是常駐內存的對象，而且老生代占用的內存較多

老生代占用內存較多（64位為1.4GB，32位為700MB），如果使用Scavenge算法，浪費一半空間不說，復制如此大塊的內存消耗時間將會相當長。所以Scavenge算法顯然不適合。V8在老生代中的垃圾回收策略采用Mark-Sweep和Mark-Compact相結合

標記清除分為標記和清除兩個階段。在標記階段需要遍歷堆中的所有對象，并標記那些活著的對象，然后進入清除階段。在清除階段總，只清除沒有被標記的對象。由于標記清除只清除死亡對象，而死亡對象在老生代中占用的比例很小，所以效率較高

標記清除有一個問題就是進行一次標記清楚后，內存空間往往是不連續的，會出現很多的內存碎片。如果后續需要分配一個需要內存空間較多的對象時，如果所有的內存碎片都不夠用，將會使得V8無法完成這次分配，提前觸發垃圾回收。

標記整理正是為了解決標記清除所帶來的內存碎片的問題。標記整理在標記清除的基礎進行修改，將其的清除階段變為緊縮極端。在整理的過程中，將活著的對象向內存區的一段移動，移動完成后直接清理掉邊界外的內存。緊縮過程涉及對象的移動，所以效率并不是太好，但是能保證不會生成內存碎片

標記清除和標記整理都分為兩個階段：標記階段、清除或緊縮階段

在標記階段，所有堆上的活躍對象都會被標記。每個內存頁有一個用來標記對象的位圖，位圖中的每一位對應內存頁中的一個字。這個位圖需要占據一定的空間（32位下為3.1%，64位為1.6%）。另外有兩位用來標記對象的狀態，這個狀態一共有三種（所以要兩位）——白，灰，黑：
* 如果一個對象為白對象，它還沒未被垃圾回收器發現
* 如果一個對象為灰對象，它已經被垃圾回收器發現，但其鄰接對象尚未全部處理
* 如果一個對象為黑對象，說明他步進被垃圾回收器發現，其鄰接對象也全部被處理完畢了

如果將對中的對象看做由指針做邊的有向圖，標記算法的核心就是深度優先搜索。在初始時，位圖為空，所有的對象也都是白對象。從根對象到達的對象會背染色為灰色，放入一個多帶帶的雙端隊列中。標記階段的每次循環，垃圾回收器都會從雙端隊列中取出一個對象并將其轉變為黑對象，并將其鄰接的對象轉變為灰，然后把其鄰接對象放入雙端隊列。如果雙端隊列為空或所有對象都變成黑對象，則結束。特別大的對象，可能會在處理時進行分片，防止雙端隊列溢出。如果雙端隊列溢出，則對象仍然會成為灰對象，但不會被放入隊列中，這將導致其鄰接對象無法被轉變為灰對象。所以在雙端隊列為空時，需要掃描所有對象，如果仍有灰對象，將它們重新放入隊列中進行處理。標記結束后，所有的對象都應該非黑即白，白對象將成為垃圾，等待釋放

清除和緊縮階段都是以內存頁為單位回收內存

清除時垃圾回收器會掃描連續存放的死對象，將其變成空閑空間，并保存到一個空閑空間的鏈表中。這個鏈表常被scavenge算法用于分配被晉升對象的內存，但也被緊縮算法用于移動對象

緊縮算法會嘗試將碎片頁整合到一起來釋放內存。由于頁上的對象會被移動到新的頁上，需要重新分配一些頁。大致過程是，對目標碎片頁中的每個活躍對象，在空閑內存鏈表中分配一塊內存頁，將該對象復制過去，并在碎片頁中的該對象上寫上新的內存地址。隨后在遷出過程中，對象的舊地址將會被記錄下來，在遷出結束后，V8會遍歷所有它所記錄的舊對象的地址，將其更新為新地址。由于標記過程中也記錄了不同頁之間的指針，這些指針在此時也會進行更新。如果一個頁非常活躍，如其中有過多需要記錄的指針，那么地址記錄會跳過它，等到下一輪垃圾回收進行處理

V8的老生代使用標記清除和標記整理結合的方式，主要采用標記清除算法，如果空間不足以分配從新生代晉升過來的對象時，才使用標記整理

由于全停頓會造成了瀏覽器一段時間無響應，所以V8使用了一種增量標記的方式，將完整的標記拆分成很多部分，每做完一部分就停下來，讓JS的應用邏輯執行一會，這樣垃圾回收與應用邏輯交替完成。經過增量標記的改進后，垃圾回收的最大停頓時間可以減少到原來的1/6左右

由于標記完成后，所有的對象都已經被標記，不是死對象就是活對象，堆上多少空間格局已經確定。我們可以不必著急釋放那些死對象所占用的空間，而延遲清理過程的執行。垃圾回收器可以根據需要逐一清理死對象所占用的內存頁

V8后續還引入了增量式整理（incremental compaction），以及并行標記和并行清理，通過并行利用多核CPU來提升垃圾回收的性能