垃圾回收器的相關知識點總結

垃圾回收器是一把十足的雙刃劍。其好處是可以大幅簡化程序的內存管理代碼，因為內存管理無需程序員來操作，由此也減少了（但沒有根除）長時間運轉的程序的內存泄漏。對于某些程序員來說，它甚至能夠提升代碼的性能。

另一方面，選擇垃圾回收器也就意味著程序當中無法完全掌控內存，而這正是移動終端開發(fā)的癥結。對于JavaScript，程序中沒有任何內存管理的可能——ECMAScript標準中沒有暴露任何垃圾回收器的接口。網頁應用既沒有辦法管理內存，也沒辦法給垃圾回收器進行提示。

嚴格來講，使用垃圾回收器的語言在性能上并不一定比不使用垃圾回收器的語言好或者差。在C語言中，分配和釋放內存有可能是非常昂貴的操作，為了使分配的內存能夠在將來釋放，堆的管理會趨于復雜。而在托管內存的語言中，分配內存往往只是增加一個指針。但隨后我們就會看到，當內存耗盡時，垃圾回收器介入回收所產生的巨大代價。一個未經琢磨的垃圾回收器，會致使程序在運行中出現長時間、無法預期的停頓，這直接影響到交互系統（特別是帶有動畫效果的）在使用上的體驗。引用計數系統時常被吹捧為垃圾回收機制的替代品，但當大型子圖中的最后一個對象的引用解除后，同樣也會有無法預期的停頓。而且引用計數系統在頻繁執(zhí)行讀取、改寫、存儲操作時，也會有可觀的性能負擔。

或好或壞，JavaScript需要一個垃圾回收器。V8的垃圾回收器實現現在已經成熟，其性能優(yōu)異，停頓短暫，性能負擔也非常可控。

基本概念

垃圾回收器要解決的最基本問題就是，辨別需要回收的內存。一旦辨別完畢，這些內存區(qū)域即可在未來的分配中重用，或者是返還給操作系統。一個對象當它不是處于活躍狀態(tài)的時候它就死了（廢話）。一個對象處于活躍狀態(tài)，當且僅當它被一個根對象或另一個活躍對象指向。根對象被定義為處于活躍狀態(tài)，是瀏覽器或V8所引用的對象。比如說，被局部變量所指向的對象屬于根對象，因為它們的棧被視為根對象；全局對象屬于根對象，因為它們始終可被訪問；瀏覽器對象，如DOM元素，也屬于根對象，盡管在某些場合下它們只是弱引用。

從側面來說，上面的定義非常寬松。實際上我們可以說，當一個對象可被程序引用時，它就是活躍的。比如：

function f() {
	 var obj = {x: 12};
	 g(); // 可能包含一個死循環(huán)
	 return obj.x;
	}

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

在這個算法的執(zhí)行過程中，我們始終維護兩個出區(qū)中的指針：allocationPtr指向我們即將為新對象分配內存的地方，scanPtr指向我們即將進行活躍檢查的下一個對象。scanPtr所指向地址之前的對象是處理過的對象，它們及其鄰接都在出區(qū)，其指針都是更新過的，位于scanPtr和allocationPtr之間的對象，會被復制至出區(qū)，但這些對象內部所包含的指針如果指向入區(qū)中的對象，則這些入區(qū)中的對象不會被復制。邏輯上，你可以將scanPtr和allocationPtr之間的對象想象為一個廣度優(yōu)先搜索用到的對象隊列。

譯注：廣度優(yōu)先搜索中，通常會將節(jié)點從隊列頭部取出并展開，將展開得到的子節(jié)點存入隊列末端，周而復始進行。這一過程與更新兩個指針間對象的過程相似。

我們在算法的初始時，復制新區(qū)所有可從根對象達到的對象，之后進入一個大的循環(huán)。在循環(huán)的每一輪，我們都會從隊列中刪除一個對象，也就是對scanPtr增量，然后跟蹤訪問對象內部的指針。如果指針并不指向入區(qū)，則不管它，因為它必然指向老生區(qū)，而這就不是我們的目標了。而如果指針指向入區(qū)中某個對象，但我們還沒有復制（未設置轉發(fā)地址），則將這個對象復制至出區(qū)，即增加到我們隊列的末端，同時也就是對allocationPtr增量。這時我們還會將一個轉發(fā)地址存至出區(qū)對象的首字，替換掉Map指針。這個轉發(fā)地址就是對象復制后所存放的地址。垃圾回收器可以輕易將轉發(fā)地址與Map指針分清，因為Map指針經過了標記，而這個地址則未標記。如果我們發(fā)現一個指針，而其指向的對象已經復制過了（設置過轉發(fā)地址），我們就把這個指針更新為轉發(fā)地址，然后打上標記。

算法在所有對象都處理完畢時終止（即scanPtr和allocationPtr相遇）。這時入區(qū)的內容都可視為垃圾，可能會在未來釋放或重用。

秘密武器：寫屏障

上面有一個細節(jié)被忽略了：如果新生區(qū)中某個對象，只有一個指向它的指針，而這個指針恰好是在老生區(qū)的對象當中，我們如何才能知道新生區(qū)中那個對象是活躍的呢？顯然我們并不希望將老生區(qū)再遍歷一次，因為老生區(qū)中的對象很多，這樣做一次消耗太大。

為了解決這個問題，實際上在寫緩沖區(qū)中有一個列表，列表中記錄了所有老生區(qū)對象指向新生區(qū)的情況。新對象誕生的時候，并不會有指向它的指針，而當有老生區(qū)中的對象出現指向新生區(qū)對象的指針時，我們便記錄下來這樣的跨區(qū)指向。由于這種記錄行為總是發(fā)生在寫操作時，它被稱為寫屏障——因為每個寫操作都要經歷這樣一關。

你可能好奇，如果每次進行寫操作都要經過寫屏障，豈不是會多出大量的代碼么？沒錯，這就是我們這種垃圾回收機制的代價之一。但情況沒你想象的那么嚴重，寫操作畢竟比讀操作要少。某些垃圾回收算法（不是V8的）會采用讀屏障，而這需要硬件來輔助才能保證一個較低的消耗。V8也有一些優(yōu)化來降低寫屏障帶來的消耗：

大多數的腳本執(zhí)行時間都是發(fā)生在Crankshaft當中的，而Crankshaft常常能靜態(tài)地判斷出某個對象是否處于新生區(qū)。對于指向這些對象的寫操作，可以無需寫屏障。

Crankshaft中新出現了一種優(yōu)化，即在對象不存在指向它的非局部引用時，該對象會被分配在棧上。而一個棧上對象的相關寫操作顯然無需寫屏障。（譯注：新生區(qū)和老生區(qū)在堆上。）

“老→新”這樣的情況相對較為少見，因此通過將“新→新”和“老→老”兩種常見情況的代碼做優(yōu)化，可以相對提升多數情形下的性能。每個頁都以1MB對齊，因此給定一個對象的內存地址，通過將低20bit濾除來快速定位其所在的頁；而頁頭有相關的標識來表明其屬于新生區(qū)還是老生區(qū)，因此通過判斷兩個對象所屬的區(qū)域，也可以快速確定是否是“老→新”。

一旦我們找到“老→新”的指針，我們就可以將其記錄在寫緩沖區(qū)的末端。經過一定的時間（寫緩沖區(qū)滿的時候），我們將其排序，合并相同的項目，然后再除去已經不符合“老→新”這一情形的指針。（譯注：這樣指針的數目就會減少，寫屏障的時間相應也會縮短）

“標記－清除”算法與“標記－緊縮”算法

Scavenge算法對于快速回收、緊縮小片內存效果很好，但對于大片內存則消耗過大。因為Scavenge算法需要出區(qū)和入區(qū)兩個區(qū)域，這對于小片內存尚可，而對于超過數MB的內存就開始變得不切實際了。老生區(qū)包含有上百MB的數據，對于這么大的區(qū)域，我們采取另外兩種相互較為接近的算法：“標記－清除”算法與“標記－緊縮”算法。

這兩種算法都包括兩個階段：標記階段，清除或緊縮階段。

在標記階段，所有堆上的活躍對象都會被標記。每個頁都會包含一個用來標記的位圖，位圖中的每一位對應頁中的一字（譯注：一個指針就是一字大小）。這個標記非常有必要，因為指針可能會在任何字對齊的地方出現。顯然，這樣的位圖要占據一定的空間（32位系統上占據3.1%，64位系統上占據1.6%），但所有的內存管理機制都需要這樣占用，因此這種做法并不過分。除此之外，另有2位來表示標記對象的狀態(tài)。由于對象至少有2字長，因此這些位不會重疊。狀態(tài)一共有三種：如果一個對象的狀態(tài)為白，那么它尚未被垃圾回收器發(fā)現；如果一個對象的狀態(tài)為灰，那么它已被垃圾回收器發(fā)現，但它的鄰接對象仍未全部處理完畢；如果一個對象的狀態(tài)為黑，則它不僅被垃圾回收器發(fā)現，而且其所有鄰接對象也都處理完畢。

如果將堆中的對象看作由指針相互聯系的有向圖，標記算法的核心實際是深度優(yōu)先搜索。在標記的初期，位圖是空的，所有對象也都是白的。從根可達的對象會被染色為灰色，并被放入標記用的一個單獨分配的雙端隊列。標記階段的每次循環(huán)，GC會將一個對象從雙端隊列中取出，染色為黑，然后將它的鄰接對象染色為灰，并把鄰接對象放入雙端隊列。這一過程在雙端隊列為空且所有對象都變黑時結束。特別大的對象，如長數組，可能會在處理時分片，以防溢出雙端隊列。如果雙端隊列溢出了，則對象仍然會被染為灰色，但不會再被放入隊列（這樣他們的鄰接對象就沒有機會再染色了）。因此當雙端隊列為空時，GC仍然需要掃描一次，確保所有的灰對象都成為了黑對象。對于未被染黑的灰對象，GC會將其再次放入隊列，再度處理。

以下是標記算法的偽碼：

markingDeque = []
	overflow = false

	def markHeap():
	 for root in roots:
	 mark(root)

	 do:
	 if overflow:
	 overflow = false
	 refillMarkingDeque()

	 while !markingDeque.isEmpty():
	 obj = markingDeque.pop()
	 setMarkBits(obj, BLACK)
	 for neighbor in neighbors(obj):
	 mark(neighbor)
	 while overflow
	 

	def mark(obj):
	 if markBits(obj) == WHITE:
	 setMarkBits(obj, GREY)
	 if markingDeque.isFull():
	 overflow = true
	 else:
	 markingDeque.push(obj)

	def refillMarkingDeque():
	 for each obj on heap:
	 if markBits(obj) == GREY:
	 markingDeque.push(obj)
	 if markingDeque.isFull():
	 overflow = true
	 return

標記算法結束時，所有的活躍對象都被染為了黑色，而所有的死對象則仍是白的。這一結果正是清理和緊縮兩個階段所期望的。

標記算法執(zhí)行完畢后，我們可以選擇清理或是緊縮，這兩個算法都可以收回內存，而且兩者都作用于頁級（注意，V8的內存頁是1MB的連續(xù)內存塊，與虛擬內存頁不同）。

清理算法掃描連續(xù)存放的死對象，將其變?yōu)榭臻e空間，并將其添加到空閑內存鏈表中。每一頁都包含數個空閑內存鏈表，其分別代表小內存區(qū)（<256字）、中內存區(qū)（<2048字）、大內存區(qū)（<16384字）和超大內存區(qū)（其它更大的內存）。清理算法非常簡單，只需遍歷頁的位圖，搜索連續(xù)的白對象。空閑內存鏈表大量被scavenge算法用于分配存活下來的活躍對象，但也被緊縮算法用于移動對象。有些類型的對象只能被分配在老生區(qū)，因此空閑內存鏈表也被它們使用。

緊縮算法會嘗試將對象從碎片頁（包含大量小空閑內存的頁）中遷移整合在一起，來釋放內存。這些對象會被遷移到另外的頁上，因此也可能會新分配一些頁。而遷出后的碎片頁就可以返還給操作系統了。遷移整合的過程非常復雜，因此我只提及一些細節(jié)而不全面講解。大概過程是這樣的。對目標碎片頁中的每個活躍對象，在空閑內存鏈表中分配一塊其它頁的區(qū)域，將該對象復制至新頁，并在碎片頁中的該對象上寫上轉發(fā)地址。遷出過程中，對象中的舊地址會被記錄下來，這樣在遷出結束后V8會遍歷它所記錄的地址，將其更新為新的地址。由于標記過程中也記錄了不同頁之間的指針，此時也會更新這些指針的指向。注意，如果一個頁非常“活躍”，比如其中有過多需要記錄的指針，則地址記錄會跳過它，等到下一輪垃圾回收再進行處理。

增量標記與惰性清理

你應該想到了，當一個堆很大而且有很多活躍對象時，標記-清除和標記-緊縮算法會執(zhí)行的很慢。起初我研究V8時，垃圾回收所引發(fā)的500-1000毫秒的停頓并不少見。這種情況顯然很難接受，即使是對于移動設備。

2012年年中，Google引入了兩項改進來減少垃圾回收所引起的停頓，并且效果顯著：增量標記和惰性清理。

增量標記允許堆的標記發(fā)生在幾次5-10毫秒（移動設備）的小停頓中。增量標記在堆的大小達到一定的閾值時啟用，啟用之后每當一定量的內存分配后，腳本的執(zhí)行就會停頓并進行一次增量標記。就像普通的標記一樣，增量標記也是一個深度優(yōu)先搜索，并同樣采用白灰黑機制來分類對象。

但增量標記和普通標記不同的是，對象的圖譜關系可能發(fā)生變化！我們需要特別注意的是，那些從黑對象指向白對象的新指針。回憶一下，黑對象表示其已完全被垃圾回收器掃描，并不會再進行二次掃描。因此如果有“黑→白”這樣的指針出現，我們就有可能將那個白對象漏掉，錯當死對象處理掉。（譯注：標記過程結束后剩余的白對象都被認為是死對象。）于是我們不得不再度啟用寫屏障。現在寫屏障不僅記錄“老→新”指針，同時還要記錄“黑→白”指針。一旦發(fā)現這樣的指針，黑對象會被重新染色為灰對象，重新放回到雙端隊列中。當算法將該對象取出時，其包含的指針會被重新掃描，這樣活躍的白對象就不會漏掉。

增量標記完成后，惰性清理就開始了。所有的對象已被處理，因此非死即活，堆上多少空間可以變?yōu)榭臻e已經成為定局。此時我們可以不急著釋放那些空間，而將清理的過程延遲一下也并無大礙。因此無需一次清理所有的頁，垃圾回收器會視需要逐一進行清理，直到所有的頁都清理完畢。這時增量標記又蓄勢待發(fā)了。

Google近期還新增了并行清理支持。由于腳本的執(zhí)行線程不會再觸及死對象，頁的清理任務可以放在另一個單獨的線程中進行并只需極少的同步工作。同樣的支持工作也正在并行標記上開展著，但目前還處于早期試驗階段。

總結

垃圾回收真的很復雜。我在文章中已經略過了大量的細節(jié)，而文章仍然變得很長。我一個同事說他覺得研究垃圾回收器比寄存器分配還要可怕，我表示確實如此。也就是說，我寧可將這些繁瑣的細節(jié)交給運行時來處理，也不想將其交給所有的應用開發(fā)者來做。盡管垃圾回收存在一些性能問題而且偶爾會出現靈異現象，它還是將我們從大量的細節(jié)中解放了出來，以便讓我們集中精力于更重要的事情上。

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com