深入剖析高性能內(nèi)存回收技術(shù)

作者：yingguofeng，軟件開(kāi)發(fā)工程師

眾所周知，內(nèi)存是操作系統(tǒng)的一項(xiàng)重要資源，直接影響系統(tǒng)性能。而在應(yīng)用蓬勃發(fā)展的今天，系統(tǒng)中運(yùn)行的應(yīng)用越來(lái)越多，這讓內(nèi)存資源變得越來(lái)越緊張。在此背景下，方舟JS運(yùn)行時(shí)在內(nèi)存回收方面發(fā)力，推出了高性能內(nèi)存回收技術(shù)——HPP GC（High Performance Partial Garbage Collection）。本文我們將從GC的基礎(chǔ)入手，由淺入深地為大家介紹HPP GC。

? ? ?

一、什么是GC？

GC（全稱(chēng)Garbage Collection），字面意思是垃圾回收。在計(jì)算機(jī)領(lǐng)域，GC就是找到內(nèi)存中的垃圾，釋放和回收內(nèi)存空間。目前主流編程語(yǔ)言實(shí)現(xiàn)的GC算法主要分為兩大類(lèi)：引用計(jì)數(shù)和對(duì)象追蹤（即Tracing GC）。

1. 引用計(jì)數(shù)

我們通過(guò)一個(gè)示例來(lái)了解什么是引用計(jì)數(shù)：

當(dāng)一個(gè)對(duì)象A被另一個(gè)對(duì)象B指向時(shí)，A引用計(jì)數(shù)+1；反之當(dāng)該指向斷開(kāi)時(shí)，A引用計(jì)數(shù)-1。當(dāng)A引用計(jì)數(shù)為0時(shí)，回收對(duì)象A。

? ?

●?優(yōu)點(diǎn)：

引用計(jì)數(shù)算法設(shè)計(jì)簡(jiǎn)單，并且內(nèi)存回收及時(shí)，在對(duì)象成為垃圾的第一時(shí)間就會(huì)被回收，所以沒(méi)有單獨(dú)的暫停業(yè)務(wù)代碼(Stop The World，STW)階段。

?

●?缺點(diǎn)：

在對(duì)對(duì)象操作的過(guò)程中額外插入了計(jì)數(shù)環(huán)節(jié)，增加了內(nèi)存分配和內(nèi)存賦值的開(kāi)銷(xiāo)，對(duì)程序性能必然會(huì)有影響。最致命的一點(diǎn)是存在循環(huán)引用問(wèn)題。

• ?
• ?
• ?
• ?
• ?
• ?

function main() {var parent = {};var child = {};parent.child = child;child.parent = parent; }

（左右滑動(dòng)，查看更多）

比如以上代碼中，對(duì)象parent被另一個(gè)對(duì)象child持有，對(duì)象parent引用計(jì)數(shù)加1，同時(shí)child也被parent持有，對(duì)象child引用計(jì)數(shù)也加1，這就是循環(huán)引用。一直到main函數(shù)結(jié)束后，對(duì)象parent和child依然無(wú)法釋放，導(dǎo)致內(nèi)存泄漏。

2. 對(duì)象追蹤

為了方便大家理解對(duì)象追蹤算法，我們通過(guò)一個(gè)圖來(lái)進(jìn)行介紹：

如圖1所示，從根對(duì)象開(kāi)始遍歷對(duì)象以及對(duì)象的域，所有可達(dá)的對(duì)象打上標(biāo)記（黑色），即為活對(duì)象，剩下的不可達(dá)對(duì)象（白色）即為垃圾。

圖1 對(duì)象追蹤

? ? ?

●?優(yōu)點(diǎn)：

對(duì)象追蹤算法可以解決循環(huán)引用的問(wèn)題，且對(duì)內(nèi)存的分配和賦值沒(méi)有額外的開(kāi)銷(xiāo)。

?

●?缺點(diǎn)：

和引用計(jì)數(shù)算法相反，對(duì)象追蹤算法較為復(fù)雜，且有短暫的STW階段。此外，回收會(huì)有延遲，導(dǎo)致比較多的浮動(dòng)垃圾。

引用計(jì)數(shù)和對(duì)象追蹤算法各有優(yōu)劣，但考慮到引用計(jì)數(shù)存在循環(huán)引用的致命性能問(wèn)題，方舟JS運(yùn)行時(shí)選擇基于對(duì)象追蹤（即Tracing GC）算法來(lái)設(shè)計(jì)自己的GC算法。

? ? ?

二、Tracing GC介紹

在介紹HPP GC之前，我們先來(lái)了解一下Tracing GC。從前面的介紹可知，Tracing GC算法通過(guò)遍歷對(duì)象圖標(biāo)記出垃圾。而根據(jù)垃圾回收方式的不同，Tracing GC可以分為三種基本類(lèi)型：標(biāo)記-清掃回收、標(biāo)記-復(fù)制回收、標(biāo)記-整理回收。

1. 標(biāo)記-清掃回收

此算法的回收方式是：完成對(duì)象圖遍歷后，將不可達(dá)對(duì)象內(nèi)容擦除，并放入一個(gè)空閑隊(duì)列，用于下次對(duì)象的再分配。

該種回收方式不需要搬移對(duì)象，所以回收效率非常高。但由于回收的對(duì)象內(nèi)存地址不一定連續(xù)，所以該回收方式最大的缺點(diǎn)是會(huì)導(dǎo)致內(nèi)存空間碎片化，降低內(nèi)存分配效率，極端情況下甚至?xí)霈F(xiàn)還有大量?jī)?nèi)存的情況下分配不出一個(gè)比較大的對(duì)象的情況。

圖2 標(biāo)記-清掃回收

（注：灰色塊表示可達(dá)對(duì)象的內(nèi)存空間，白色塊表示不可達(dá)對(duì)象的內(nèi)存空間。）

2. 標(biāo)記-復(fù)制回收

此算法的回收方式是：在對(duì)象圖的遍歷過(guò)程中，將找到的可達(dá)對(duì)象直接復(fù)制到一個(gè)全新的內(nèi)存空間中。遍歷完成后，一次將舊的內(nèi)存空間全部回收。

顯然，這種方式可以解決內(nèi)存碎片的問(wèn)題，且通過(guò)一次遍歷便完成整個(gè)GC過(guò)程，效率較高。但同時(shí)在極端情況下，這種回收方式需要預(yù)留一半的內(nèi)存空間，以確保所有活的對(duì)象能被拷貝，空間利用率較低。

圖3 標(biāo)記-復(fù)制回收

3. 標(biāo)記-整理回收

此算法的回收方式是：完成對(duì)象圖遍歷后，將可達(dá)對(duì)象（紅色）往本區(qū)域（或指定區(qū)域）的頭部空閑位置復(fù)制，然后將已經(jīng)完成復(fù)制的對(duì)象回收整理到空閑隊(duì)列中。

這種回收方式既解決了“標(biāo)記-清掃回收”引入的大量?jī)?nèi)存空間碎片的問(wèn)題，又不需要像“標(biāo)記-復(fù)制回收”那樣浪費(fèi)一半的內(nèi)存空間，但是性能上開(kāi)銷(xiāo)比“標(biāo)記-復(fù)制回收”稍大一些。

圖4 標(biāo)記-整理回收

綜上所述，Tracing GC的三種基本類(lèi)型各有優(yōu)缺點(diǎn)，那么方舟JS運(yùn)行時(shí)的HPP GC是基于哪種類(lèi)型實(shí)現(xiàn)的呢？

HPP GC同時(shí)實(shí)現(xiàn)了這三種Tracing GC算法！沒(méi)想到吧？HPP GC綜合了這三種算法的優(yōu)點(diǎn)，且支持根據(jù)不同對(duì)象區(qū)域、采取不同的回收方式。下面就為大家詳細(xì)解析HPP GC。

? ? ?

三、HPP GC詳解

前面我們提到了，HPP GC支持根據(jù)不同對(duì)象區(qū)域，采取不同的回收方式。這是基于分代模型和混合算法來(lái)實(shí)現(xiàn)的。另外，為了實(shí)現(xiàn)HPP GC（High Performance Partial Garbage Collection）中的“High Performance”（高性能），HPP GC對(duì)GC流程做了大量?jī)?yōu)化。所以下面我們就從分代模型、混合算法和GC流程優(yōu)化三個(gè)方面來(lái)為大家介紹HPP GC。

1. 分代模型

方舟JS運(yùn)行時(shí)采用傳統(tǒng)的分代模型，將對(duì)象進(jìn)行分類(lèi)?？紤]到大多數(shù)新分配的對(duì)象都會(huì)在一次GC之后被回收，而大多數(shù)經(jīng)過(guò)多次GC之后依然存活的對(duì)象會(huì)繼續(xù)存活，方舟JS運(yùn)行時(shí)將對(duì)象劃分為年輕代對(duì)象和老年代對(duì)象，并將對(duì)象分配到不同的空間。

如圖5所示，方舟JS運(yùn)行時(shí)將新分配的對(duì)象直接分配到年輕代（Young Generation）的From空間。經(jīng)過(guò)一次GC后依然存活的對(duì)象，會(huì)進(jìn)入To空間。而經(jīng)過(guò)再次GC后依然存活的對(duì)象，會(huì)被復(fù)制到老年代（Old?Generation）。

圖5 分代模型

2. 混合算法

通過(guò)前面的介紹，我們已經(jīng)知道：HPP GC同時(shí)實(shí)現(xiàn)了“標(biāo)記-清掃回收”、“標(biāo)記-復(fù)制回收”和“標(biāo)記-整理回收”這三種Tracing GC算法。也就是說(shuō)，HPP GC是一種“部分復(fù)制+部分整理+部分清掃”的混合算法，支持根據(jù)年輕代對(duì)象和老年代對(duì)象的不同特點(diǎn)，分別采取不同的回收方式。

(1) 部分復(fù)制

考慮到年輕代對(duì)象生命周期較短，回收較為頻繁，且年輕代對(duì)象大小有限的特點(diǎn)，方舟JS運(yùn)行時(shí)對(duì)年輕代對(duì)象采用“標(biāo)記-復(fù)制回收”算法。

(2) 部分整理+部分清掃

方舟JS運(yùn)行時(shí)根據(jù)老年代對(duì)象的特點(diǎn)，引入啟發(fā)式Collection Set（簡(jiǎn)稱(chēng)CSet）選擇算法。此選擇算法的基本原理是：在標(biāo)記階段對(duì)每個(gè)區(qū)域的存活對(duì)象進(jìn)行大小統(tǒng)計(jì)，然后在回收階段優(yōu)先選出存活對(duì)象少、回收代價(jià)小的區(qū)域進(jìn)行對(duì)象整理回收，再對(duì)剩下的區(qū)域進(jìn)行清掃回收。

具體的回收策略如下：

? ? ?

(a) 根據(jù)設(shè)定的區(qū)域存活對(duì)象大小閾值，將滿(mǎn)足條件的區(qū)域納入初步的CSet隊(duì)列，并根據(jù)存活率進(jìn)行從低到高的排序。

（注：存活率=存活對(duì)象大小/區(qū)域大小）

?

(b) 根據(jù)設(shè)定的釋放區(qū)域個(gè)數(shù)閾值，選出最終的CSet隊(duì)列，進(jìn)行整理回收。

?

(c) 對(duì)未被選入CSet隊(duì)列的區(qū)域進(jìn)行清掃回收。

由上可知，啟發(fā)式CSet選擇算法同時(shí)兼顧了 “標(biāo)記-整理回收”和“標(biāo)記-清掃回收”這兩種算法的優(yōu)點(diǎn)，既避免了內(nèi)存碎片問(wèn)題，也兼顧了性能。

3. GC流程優(yōu)化

在內(nèi)存回收時(shí)，雖然釋放和回收了內(nèi)存空間，讓系統(tǒng)有了更多可用的內(nèi)存資源，但內(nèi)存回收過(guò)程本身需要暫停應(yīng)用業(yè)務(wù)代碼執(zhí)行，影響用戶(hù)使用應(yīng)用的體驗(yàn)?；厥諆?nèi)存時(shí)，如何盡可能的減小對(duì)應(yīng)用性能的影響呢？

為此，我們?cè)贖PP GC流程中引入了大量的并發(fā)和并行優(yōu)化，以減少對(duì)應(yīng)用性能的影響。如圖6所示，HPP GC流程中采用了并發(fā)+并行標(biāo)記（Marking）、并發(fā)+并行清掃（Sweep）、并行復(fù)制/整理（Evacuation）、并行回改（Update）和并發(fā)清理（Clear）。

圖6 HPP GC流程

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

在JS線程執(zhí)行業(yè)務(wù)代碼的同時(shí)，另外啟動(dòng)線程執(zhí)行標(biāo)記，即為“并發(fā)標(biāo)記”。如果另外啟動(dòng)多個(gè)線程執(zhí)行標(biāo)記，即為“并發(fā)+并行標(biāo)記”。 ?在并發(fā)+并行標(biāo)記過(guò)程中，為確保標(biāo)記的正確性和高性能，HPP GC采取了兩項(xiàng)優(yōu)化措施：

措施一：在新增引用關(guān)系時(shí)增加標(biāo)記屏障(Marking Barrier)，以確保標(biāo)記結(jié)果的正確性。

并發(fā)標(biāo)記過(guò)程中，JS線程有可能會(huì)更改對(duì)象之間的引用關(guān)系，從而導(dǎo)致對(duì)象標(biāo)記結(jié)果出錯(cuò)。如圖7所示，在marking線程完成對(duì)象1的標(biāo)記、準(zhǔn)備標(biāo)記對(duì)象2的過(guò)程中，JS線程更改了對(duì)象3的引用關(guān)系。那么marking線程完成對(duì)象2的標(biāo)記后，對(duì)象3不會(huì)被標(biāo)記，回收器會(huì)判定對(duì)象3為垃圾，進(jìn)行回收。此后，如果JS線程讀取對(duì)象1的字段，將會(huì)發(fā)生不可預(yù)知的錯(cuò)誤。

圖7 對(duì)象標(biāo)記出錯(cuò)

為確保標(biāo)記結(jié)果的正確性，HPP GC在新增引用關(guān)系時(shí)增加標(biāo)記屏障。如圖8所示，在marking線程完成對(duì)象1的標(biāo)記、準(zhǔn)備標(biāo)記對(duì)象2的過(guò)程中，JS線程更改了對(duì)象3的引用關(guān)系。此時(shí)，JS線程會(huì)將對(duì)象3加入等待標(biāo)記隊(duì)列，等marking線程完成對(duì)象2的標(biāo)記后，繼續(xù)對(duì)象3的標(biāo)記，從而確保對(duì)象3不會(huì)被回收。

圖8 增加標(biāo)記屏障

措施二：在共享全局工作隊(duì)列的基礎(chǔ)上，增加了本地工作隊(duì)列(Local Work List)，以提高讀取對(duì)象的性能。

如圖9所示，并行標(biāo)記時(shí)，每個(gè)Marking線程都要執(zhí)行以下操作：從全局工作隊(duì)列(Global Work List)獲取一個(gè)對(duì)象，然后設(shè)置標(biāo)記位，最后遍歷該對(duì)象的每個(gè)域，將子對(duì)象放入全局工作隊(duì)列中?？紤]到線程之間讀取數(shù)據(jù)安全，必須在每個(gè)對(duì)象的Push/Pop操作時(shí)增加原子化或者鎖，這對(duì)對(duì)象的讀取性能有較大的影響。

圖9 全局工作隊(duì)列

為提高讀取對(duì)象的性能，HPP GC增加了本地工作隊(duì)列。每個(gè)線程持有一個(gè)獨(dú)立的本地工作隊(duì)列，優(yōu)先從本地工作隊(duì)列獲取/放入對(duì)象。當(dāng)本地工作隊(duì)列滿(mǎn)時(shí)，將本地工作隊(duì)列的部分隊(duì)列一次發(fā)布到全局工作隊(duì)列中；當(dāng)本地工作隊(duì)列空時(shí)，一次從全局工作隊(duì)列獲取若干對(duì)象到本地工作隊(duì)列。這樣，只有從全局工作隊(duì)列發(fā)布/獲取對(duì)象那一次需要增加原子化或者鎖，兼顧了多線程的并發(fā)效率和任務(wù)均衡，大大提高了并發(fā)標(biāo)記的效率。

圖10 增加本地工作隊(duì)列

(2) 并發(fā)+并行清掃

在JS線程執(zhí)行業(yè)務(wù)代碼的同時(shí)，另外啟動(dòng)線程執(zhí)行清掃，即為“并發(fā)清掃”。如果另外啟動(dòng)多個(gè)線程執(zhí)行清掃，即為“并發(fā)+并行清掃”。

在并發(fā)+并行清掃過(guò)程中，HPP GC采取增加區(qū)域空閑隊(duì)列(Region Free List)的優(yōu)化措施，用于提高多線程并發(fā)清掃的效率。

并發(fā)+并行清掃過(guò)程中，Sweeping線程發(fā)現(xiàn)不可達(dá)對(duì)象后，需要將對(duì)象放入全局的空閑隊(duì)列，同時(shí)JS線程執(zhí)行的業(yè)務(wù)代碼可能需要從空閑隊(duì)列分配對(duì)象。為了確保數(shù)據(jù)安全，這個(gè)過(guò)程需要增加原子化或者鎖，但會(huì)影響到分配和清掃的效率。

為了提升效率，HPP GC增加區(qū)域空閑隊(duì)列。將所有需要清掃的內(nèi)存按內(nèi)存地址分成若干個(gè)區(qū)域，每個(gè)區(qū)域擁有獨(dú)立的空閑隊(duì)列，且每個(gè)區(qū)域同時(shí)只有一個(gè)線程進(jìn)行清掃。在并發(fā)清掃過(guò)程中，Sweeping線程會(huì)首先將不可達(dá)對(duì)象放入本區(qū)域的空閑隊(duì)列。當(dāng)JS線程需要從空閑隊(duì)列分配對(duì)象時(shí)，先獲取已經(jīng)完成清掃的區(qū)域，再將這些區(qū)域的空閑隊(duì)列發(fā)布到全局空閑隊(duì)列中，用于對(duì)象分配，如圖11所示。由于發(fā)布的任務(wù)由JS線程單獨(dú)完成，所以整個(gè)并行清掃的過(guò)程都不需要加鎖，大大提高了并發(fā)+并行清掃的效率。

圖11 增加區(qū)域空閑隊(duì)列

(3) 并行復(fù)制/整理

在JS線程暫停業(yè)務(wù)代碼(STW)對(duì)可達(dá)對(duì)象進(jìn)行復(fù)制/整理時(shí)，另外啟動(dòng)多個(gè)線程一起進(jìn)行復(fù)制/整理，即為“并行復(fù)制/整理”。和并發(fā)+并行清掃相似，并行復(fù)制/整理的瓶頸點(diǎn)在于多個(gè)線程同時(shí)從全局空閑隊(duì)列/全局線性分配器分配對(duì)象時(shí)，需要增加原子化或者鎖。為了提高多線程分配性能，在并行復(fù)制/整理過(guò)程中引入了TLAB Allocator。TLAB英文全稱(chēng)為T(mén)hread Local Allocation Buffer。顧名思義，TLAB Allocator就是每個(gè)線程擁有一個(gè)獨(dú)立的本地分配器，該分配器會(huì)從全局內(nèi)存分配器一次分配一塊較大的內(nèi)存，然后在線程內(nèi)部再分配。這樣只需從全局分配器分配時(shí)保證多線程安全，即可完成高性能且安全的并行復(fù)制/整理功能。

(4)?并行回改

在GC完成標(biāo)記和復(fù)制/整理后，需要將可達(dá)對(duì)象中指向舊對(duì)象地址的域改成新對(duì)象地址，這個(gè)過(guò)程就是“地址回改”，如圖12所示。為了提升地址回改的效率，HPP GC引入了“并行回改”，同時(shí)啟動(dòng)多個(gè)線程進(jìn)行地址回改，每個(gè)線程負(fù)責(zé)其中一塊內(nèi)存區(qū)域?qū)ο蟮刂返幕馗?/span>。

圖12 地址回改

(5)?并發(fā)清理

在GC復(fù)制/整理結(jié)束后，JS線程將不再讀寫(xiě)遍歷出來(lái)的不可達(dá)對(duì)象和已經(jīng)完成復(fù)制的可達(dá)對(duì)象，因此需要清理和回收對(duì)應(yīng)的物理內(nèi)存。為了減少STW時(shí)間，HPP GC引入“并發(fā)清理”，另外啟動(dòng)一個(gè)工作線程進(jìn)行并發(fā)的物理內(nèi)存回收，這樣JS線程就可以繼續(xù)執(zhí)行業(yè)務(wù)代碼。 ? ? ? ?

四、結(jié)束語(yǔ)

本期就為大家介紹到這里了，最后我們總結(jié)一下： ? ?

●??HPP GC基于分代模型將對(duì)象分為年輕代和老年代對(duì)象。

?

●? HPP GC基于Tracing GC的三種基本類(lèi)型，實(shí)現(xiàn)了“部分復(fù)制+部分整理+部分清掃”的混合算法，從而實(shí)現(xiàn)根據(jù)不同對(duì)象區(qū)域、采取不同的回收方式。

?

●? HPP GC通過(guò)在GC流程中引入了大量的并發(fā)和并行優(yōu)化，實(shí)現(xiàn)高性能。

HPP GC仍有很大的探索空間，我們還將繼續(xù)努力，為大家提供更高性能的內(nèi)存回收能力！