垃圾回收器的相關(guān)知識點(diǎn)總結(jié)

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

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

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

或好或壞，JavaScript需要一個(gè)垃圾回收器。V8的垃圾回收器實(shí)現(xiàn)現(xiàn)在已經(jīng)成熟，其性能優(yōu)異，停頓短暫，性能負(fù)擔(dān)也非常可控。

基本概念

垃圾回收器要解決的最基本問題就是，辨別需要回收的內(nèi)存。一旦辨別完畢，這些內(nèi)存區(qū)域即可在未來的分配中重用，或者是返還給操作系統(tǒng)。一個(gè)對象當(dāng)它不是處于活躍狀態(tài)的時(shí)候它就死了（廢話）。一個(gè)對象處于活躍狀態(tài)，當(dāng)且僅當(dāng)它被一個(gè)根對象或另一個(gè)活躍對象指向。根對象被定義為處于活躍狀態(tài)，是瀏覽器或V8所引用的對象。比如說，被局部變量所指向的對象屬于根對象，因?yàn)樗鼈兊臈１灰暈楦鶎ο螅蝗謱ο髮儆诟鶎ο螅驗(yàn)樗鼈兪冀K可被訪問；瀏覽器對象，如DOM元素，也屬于根對象，盡管在某些場合下它們只是弱引用。

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

function f() {
	 var obj = {x: 12};
	 g(); // 可能包含一個(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

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

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

我們在算法的初始時(shí)，復(fù)制新區(qū)所有可從根對象達(dá)到的對象，之后進(jìn)入一個(gè)大的循環(huán)。在循環(huán)的每一輪，我們都會(huì)從隊(duì)列中刪除一個(gè)對象，也就是對scanPtr增量，然后跟蹤訪問對象內(nèi)部的指針。如果指針并不指向入?yún)^(qū)，則不管它，因?yàn)樗厝恢赶蚶仙鷧^(qū)，而這就不是我們的目標(biāo)了。而如果指針指向入?yún)^(qū)中某個(gè)對象，但我們還沒有復(fù)制（未設(shè)置轉(zhuǎn)發(fā)地址），則將這個(gè)對象復(fù)制至出區(qū)，即增加到我們隊(duì)列的末端，同時(shí)也就是對allocationPtr增量。這時(shí)我們還會(huì)將一個(gè)轉(zhuǎn)發(fā)地址存至出區(qū)對象的首字，替換掉Map指針。這個(gè)轉(zhuǎn)發(fā)地址就是對象復(fù)制后所存放的地址。垃圾回收器可以輕易將轉(zhuǎn)發(fā)地址與Map指針分清，因?yàn)镸ap指針經(jīng)過了標(biāo)記，而這個(gè)地址則未標(biāo)記。如果我們發(fā)現(xiàn)一個(gè)指針，而其指向的對象已經(jīng)復(fù)制過了（設(shè)置過轉(zhuǎn)發(fā)地址），我們就把這個(gè)指針更新為轉(zhuǎn)發(fā)地址，然后打上標(biāo)記。

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

秘密武器：寫屏障

上面有一個(gè)細(xì)節(jié)被忽略了：如果新生區(qū)中某個(gè)對象，只有一個(gè)指向它的指針，而這個(gè)指針恰好是在老生區(qū)的對象當(dāng)中，我們?nèi)绾尾拍苤佬律鷧^(qū)中那個(gè)對象是活躍的呢？顯然我們并不希望將老生區(qū)再遍歷一次，因?yàn)槔仙鷧^(qū)中的對象很多，這樣做一次消耗太大。

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

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

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

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

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

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

“標(biāo)記－清除”算法與“標(biāo)記－緊縮”算法

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

這兩種算法都包括兩個(gè)階段：標(biāo)記階段，清除或緊縮階段。

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

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

以下是標(biāo)記算法的偽碼：

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

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

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

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

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

增量標(biāo)記與惰性清理

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

2012年年中，Google引入了兩項(xiàng)改進(jìn)來減少垃圾回收所引起的停頓，并且效果顯著：增量標(biāo)記和惰性清理。

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

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

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

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

總結(jié)

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

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