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

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

? ? ?

一、什么是GC？

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

1. 引用計數(shù)

我們通過一個示例來了解什么是引用計數(shù)：

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

? ?

●?優(yōu)點：

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

?

●?缺點：

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

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

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

（左右滑動，查看更多）

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

2. 對象追蹤

為了方便大家理解對象追蹤算法，我們通過一個圖來進行介紹：

如圖1所示，從根對象開始遍歷對象以及對象的域，所有可達的對象打上標記（黑色），即為活對象，剩下的不可達對象（白色）即為垃圾。

圖1 對象追蹤

? ? ?

●?優(yōu)點：

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

?

●?缺點：

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

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

? ? ?

二、Tracing GC介紹

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

1. 標記-清掃回收

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

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

圖2 標記-清掃回收

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

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

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

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

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

3. 標記-整理回收

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

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

圖4 標記-整理回收

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

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

? ? ?

三、HPP GC詳解

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

1. 分代模型

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

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

圖5 分代模型

2. 混合算法

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

(1) 部分復(fù)制

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

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

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

具體的回收策略如下：

? ? ?

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

（注：存活率=存活對象大小/區(qū)域大?。?/span>

?

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

?

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

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

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

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

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

圖6 HPP GC流程

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

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

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

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

圖7 對象標記出錯

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

圖8 增加標記屏障

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

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

圖9 全局工作隊列

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

圖10 增加本地工作隊列

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

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

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

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

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

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

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

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

(4)?并行回改

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

圖12 地址回改

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

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

四、結(jié)束語

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

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

?

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

?

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

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