聊聊Javascript 垃圾回收機制(二)-V8引擎下的垃圾回收機制
作者：安歌
來源：SegmentFault 思否社區(qū)
引子 從修真故事說起
上文大概介紹了垃圾回收的機制和標記清除法的核心思路， 接下來準備深入介紹下v8引擎里的垃圾回收算法。既然是算法類的介紹，那自然是比較枯燥的，如果想完全弄懂，可以收藏下來，多看幾遍（!·_·!）。
為了緩解一下講解的枯燥，我覺得可以先從一個比較有意思的話題來引入。相信大家都看過一些修真玄幻的小說， 渡劫和飛升就是里面常見的橋段，現(xiàn)在來給大家講個故事：
初始大陸上有很多普通的修真者在修仙，隨著時間推移，人數(shù)越來越多，最終到達了這個大陸的承受極限，此時天道必然要出手掌握平衡， 從中選拔留下一下能通過考驗的優(yōu)秀之人，清除掉剩下的修為低下之人，從而騰出大陸空間；天道選拔的方式是：
將這些人挪移到渡劫空間里， 然后開始一場小天劫，等到小天劫結束后，再把活下來的人送回大陸空間，沒有渡過的人就會被清除，身死道消； 循環(huán)往復，只要每次人數(shù)達到大陸空間上限，都會進行一次小天劫，
那么這之中就會有度過數(shù)次天劫的佼佼者， 天道會獎勵他飛升到更高級、更廣闊的遠古大陸去，踏上更高一級的修煉路程，但是我們知道，修仙之路是逆天之路，更高級的地方自然也有更高級的劫數(shù)，遠古大陸雖然更加遼闊，遠勝于初始大陸，但是每隔一定的時間，也會觸發(fā)一次更大級別的大天劫， 清理這個大陸上的修真者。
大部分的修真者生命是短暫的，熬不過一兩次小天劫，只有少數(shù)的修真者能夠脫穎而出，飛升到遠古大陸。
故事暫時就講到這里，接下來就是正題。
堆結構的劃分
在聊垃圾回收之前，要先了解下v8引擎對于堆結構的劃分：
新空間(New-space)：大多數(shù)對象都分配在這里。新空間很小，并且被設計為可以非常快速地進行垃圾回收，而與其他空間無關。其實這個新生空間對應的，就是前文的初始大陸 舊指針空間（Old-pointer-space）：包含大多數(shù)對象，這些對象可能具有指向其他對象的指針。在新空間中生存了一段時間后，大多數(shù)對象都移到了這里。（特例也可以先不管） 舊數(shù)據(jù)空間（Old-data-space）：包含僅包含原始數(shù)據(jù)的對象（沒有指向其他對象的指針）。在新空間中存活了一段時間后，字符串，裝箱的數(shù)字和未裝箱的雙精度數(shù)組會移到此處。舊指針空間和舊數(shù)據(jù)空間合起來就稱為舊空間，就對應前文的遠古大陸。 大對象空間：此空間包含的對象大于其他空間的大小限制。大對象永遠不會被垃圾收集器移動。（可以先不管） 代碼空間：此處分配了包含JIT指令的代碼對象。這是唯一具有可執(zhí)行內存的空間（盡管可以在大對象空間中分配代碼，并且這些代碼也是可執(zhí)行的。（可以先不管）
介紹到這里，相信有些同學已經(jīng)可以對應出一部分內容了，接著往下看（主要先記住前面3個空間就好，后面會一直用到）：
分代回收機制(Generational collection)
在大部分小說設定里，普通修真者的生命總是短暫的，能脫穎而出的萬中無一。在大部分程序里，對象數(shù)據(jù)的生命也是短暫的，只有少部分數(shù)據(jù)對象會長期存活。所以根據(jù)這種情況，v8引擎設計了分代回收的方式 -- 也就是前面提到的：天劫分一大一小兩類，小天劫發(fā)生頻繁，清掃新生和普通的修真者，只在初始大陸發(fā)生；大天劫間隔更久，清理遠古大陸的修真者，他們分別發(fā)生在不同的空間，共同完成垃圾回收任務。
整體配合機制如下：
在新空間分配新對象，直到空間充滿，就觸發(fā)小型回收機制； 在小型回收機制中存活下2次的對象，就會被移動到舊空間去（根據(jù)數(shù)據(jù)特點分配到舊指針空間或者舊數(shù)據(jù)空間）； 舊數(shù)據(jù)空間內存達到一定值的時候（這個閾值具體的參數(shù)先不用關注），觸發(fā)大型回收機制（major garbage collection）；
（可以再去回頭讀讀前面的故事 是不是基本全對上了！）
接下來我們來分別介紹這兩種機制。
小型回收機制 scavenge
小型回收機制，官方名稱是scavenge， 它發(fā)生概率頻繁，所以要求速度要比較快。基本算法思路源于著名的Cheney算法，思路如下:
把新空間 (new-space)均分為兩部分，命名為from空間和to空間；（這兩個空間不會同時使用）前面說的新對象的分配 是在to空間進行的，直到填滿to空間為止； 此時交換 from空間和to空間，也就是把to空間的所有對象都移動到from空間，這一步執(zhí)行完后，to空間變成空的，from是滿的；在 from空間，從root開始尋找所有可訪問對象（這是上一篇的內容了，忘記了可以去回顧一下），然后把這些對象都移動到to空間或者old空間（某些已經(jīng)挨過兩次的就應該飛升了），這一步其實v8引擎還會順便做一下壓實（compacted）,也就是把存活的對象位置稍微集中一下，增加一下緩存的局部性，保持分配快速而簡單；清空 from空間（篩選剩下的都是可回收的了）；
第一次接觸這個算法的讀者可能稍微有點繞，也會疑惑為什么不直接在to空間滿了的時候就直接清理垃圾，保留live對象(也就是可訪問對象)，反而要移來移去的；其實多看兩遍就很好理解了，這樣設計的好處在于to空間永遠作為實際的內存分配空間，from充當?shù)闹皇且粋€臨時容器，也就是渡劫的空間，兩者不需要同時使用，這樣非常清晰。官方還貼了一份偽代碼:
def scavenge():
swap(fromSpace, toSpace)
allocationPtr = toSpace.bottom
scanPtr = toSpace.bottom
for i = 0..len(roots):
root = roots[i]
if inFromSpace(root):
rootCopy = copyObject(&allocationPtr, root)
setForwardingAddress(root, rootCopy)
roots[i] = rootCopy
while scanPtr < allocationPtr:
obj = object at scanPtr
scanPtr += size(obj)
n = sizeInWords(obj)
for i = 0..n:
if isPointer(obj[i]) and not inOldSpace(obj[i]):
fromNeighbor = obj[i]
if hasForwardingAddress(fromNeighbor):
toNeighbor = getForwardingAddress(fromNeighbor)
else:
toNeighbor = copyObject(&allocationPtr, fromNeighbor)
setForwardingAddress(fromNeighbor, toNeighbor)
obj[i] = toNeighbor
def copyObject(*allocationPtr, object):
copy = *allocationPtr
*allocationPtr += size(object)
memcpy(copy, object, size(object))
return copy
代碼自然看起來枯燥一些，適合有興趣的讀者后面慢慢研究，第一遍閱讀完全可以略過，因為思路都已經(jīng)講完了，缺的只是一些具體的實現(xiàn)。
這里有個小細節(jié)，我們剛剛說到，回收的起始點是root對象，也就是全局對象以及所有它可以訪問到的對象（包括閉包等）。那么如果某個對象只是被已經(jīng)飛升到舊空間的數(shù)據(jù)對象引用了那么辦呢？ 按照我們這種清理方式，如果我們不把舊空間掃描一遍來排查這樣的特殊情況，就會把這個對象給誤清理掉；如果我們真的這么做，那成本就抬高了,因為我們說過小型清理的發(fā)生頻率非常高，所以不可能每次都還去掃描舊空間。
所以，為了解決這個問題，v8引擎在內存里維護了一個緩沖區(qū)，每當新(new-space)空間的對象被舊(old-space)空間的對象引用時， 這個舊空間對象的key將會被記錄下來，例如:
var user1 = {name: 'leo'};
// ...這里省略一些代碼， 假定經(jīng)歷了一段時間并且user1被移動到old空間之后
use1.friend = {name: 'john'};
這個例子中，我們假設use1經(jīng)過一段時間后進入了舊空間，然后{name: 'john'}被新分配到新空間，并且只有user1保留了對它的引用，此時這個key，也就是friend的內存位置會被記錄到緩沖區(qū)里，后面會專門檢測這種情況，防止誤殺。
這個雖然需要額外花費一些代價，但是是為了達到回收效果必須要付出的成本，而且實際這種情景的頻率并沒有想象的高。
大型回收機制
小型回收機制Scavenge比較適合小區(qū)域的清理，因為它需要交換內存空間，有比較多內存開銷，因為新空間比較小，所以這樣做是沒問題的， 對于要大的多的舊空間，就要用大型回收機制。
大型回收機制指的就是我們前文說的標記-清除法，實際上包含分成標記-清除和標記-壓實（壓實的概念前面也說過了）兩種。他們都是分2個階段來運行的：
標記階段：本質上就是一場深度優(yōu)先搜索：有三種顏色的標記（白色-初始狀態(tài)，黑色-已檢查狀態(tài)；灰色-待檢查狀態(tài)）； 首先將所有的對象設置為白色，然后從root對象出發(fā)，將所有可以訪問的對象標記為灰色。并用一個數(shù)組緩存起來； 然后遍歷該數(shù)組，每次都把要遍歷的對象涂成黑色并移出，并且把他的相鄰節(jié)點都涂成灰色，并放入隊列，直到隊列為空 繼續(xù)檢查是否有灰色對象，如果有繼續(xù)放入隊列然后循環(huán), 直到所有的可訪問對象都變成黑色。
這一段看起來雖然有點繞，但是實質上就是深度遍歷有向圖，比較基礎，所以就不畫流程圖了。經(jīng)過標記以后，所有的對象就只剩下黑色和白色了，其中白色的就是可清理垃圾對象。
清除（或壓實）階段：清除算法比較簡單，根據(jù)上一步的查找結果，把對應白色標記對象內存地址轉為自由空間；壓實算法相對復雜一些，核心的思路是把對象從比較分散的內存地址，集體遷移到其他某一塊連續(xù)的內存地址里面，一般是另外選取一個連續(xù)內存塊，然后把對象復制過去，并且在源對象上留下一個轉發(fā)地址，在遷移過程中，記錄下相關的指針位置，在完成整個遷移之后，更新指針指向新位置， 如果遇到某一塊內存地址由于太多對象都要遷移過去，導致無法全部遷移，那么會等到下一個大回收周期再繼續(xù)遷移。
好了 到這里，核心內容基本就介紹完了，可以稍作休息。
v8引擎的優(yōu)化機制-增量標記和延遲清除
遇到大量的實時數(shù)據(jù)處理時，標記清除（或壓實）法會很耗時，所以Google提出了兩項改進方案：增量標記和延遲清除。
增量標記：
這個其實蠻好理解的，因為前文講到的標記清除算法可能一次做完需要很長的時間，這個期間是需要暫停程序的，所以v8允許設定一個閾值，例如每次標記一定數(shù)量（比如100個）的對象，就先回去執(zhí)行程序，然后再回來繼續(xù)標記，也就是在程序運行過程穿插垃圾回收，從而降低最大暫停時間。
但是這個方法有個問題：假如我第一次已經(jīng)把一些對象標記過了，但是返回垃圾回收過程時，有些對象被修改了！
例如前面標記為黑色的對象，在返回執(zhí)行程序過程，增加了一個指向已經(jīng)被標記為白色對象的指針，這就會導致直接繼續(xù)執(zhí)行標記會誤殺這個白色對象（因為后來它實際上變成可訪問的了），怎么辦呢？
很簡單，還記不記得小回收階段，v8引擎在內存里維護了一個緩沖區(qū)，解決new空間的對象被old空間的對象引用的方法？同樣的，他也會記錄這種從黑色對象到白色對象的指針，并且之后把這樣的黑色對象再變成灰色，重新檢查，這樣問題就解決了。
延遲清除：
這個也很簡單，在標記之后，引擎清楚直到哪些是可以清除的對象，但是并不代表需要同時清除掉這些垃圾，所以引擎選擇按需清理，優(yōu)先從需要的頁面開始，逐步清理所有的頁面垃圾，然后就算就完成了一整個垃圾回收周期。
總結
本文在前一節(jié)的基礎上，深入分析了v8引擎的垃圾回收機制，
從大的方面來說，分成小回收周期和大的回收周期 小回收周期發(fā)生在新空間，頻率高，時間短速度快，運用chenny算法 大回收周期發(fā)生在舊空間，頻率低，速度慢，用深度優(yōu)先遍歷和三色標記法（黑白灰） 優(yōu)化方式主要是增量標記和延遲清理，核心思路是碎片化標記階段和優(yōu)先按需清理空間
好了，關于垃圾回收的內容，大概就說到這里， 本文相對前一篇文章稍微枯燥一些，而且沒有畫圖來說明過程（問就是懶得畫-_-），但是多看幾遍還是挺好理解的，而且已經(jīng)去掉了關于內存位圖之類更底層的東西方便理解核心思路，想鉆研更底層內容的同學可以看后面詳細的參考文章。
慣例：如果內容有錯誤的地方歡迎指出（覺得看著不理解不舒服想吐槽也完全沒問題）；如果有幫助，歡迎點贊和收藏，轉載請征得同意后著明出處，如果有問題也歡迎私信交流，主頁有郵箱地址
順便再說下，RingCentral目前在杭州也設置了辦公點，而且可以申請長期遠程辦公，告別996，平衡工作生活，有興趣的同學可以私信或者發(fā)郵件給我，可以免費幫忙內推~
參考文章
http://jayconrod.com/posts/55/a-tour-of-v8-garbage-collection
