電子發(fā)燒友App
眾所周知，內存是操作系統(tǒng)的一項重要資源，直接影響系統(tǒng)性能。而在應用蓬勃發(fā)展的今天，系統(tǒng)中運行的應用越來越多，這讓內存資源變得越來越緊張。在此背景下，方舟JS運行時在內存回收方面發(fā)力，推出了高性能內存回收技術——HPP GC（High Performance Partial Garbage Collection）。本文我們將從GC的基礎入手，由淺入深地為大家介紹HPP GC。
? ? ?一、什么是GC？
GC（全稱Garbage Collection），字面意思是垃圾回收。在計算機領域，GC就是找到內存中的垃圾，釋放和回收內存空間。目前主流編程語言實現(xiàn)的GC算法主要分為兩大類：引用計數(shù)和對象追蹤（即Tracing GC）。
1. 引用計數(shù)
我們通過一個示例來了解什么是引用計數(shù)：當一個對象A被另一個對象B指向時，A引用計數(shù)+1；反之當該指向斷開時，A引用計數(shù)-1。當A引用計數(shù)為0時，回收對象A。
? ?●?優(yōu)點：
引用計數(shù)算法設計簡單，并且內存回收及時，在對象成為垃圾的第一時間就會被回收，所以沒有單獨的暫停業(yè)務代碼(Stop The World，STW)階段。
?●?缺點：
在對對象操作的過程中額外插入了計數(shù)環(huán)節(jié)，增加了內存分配和內存賦值的開銷，對程序性能必然會有影響。最致命的一點是存在循環(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ù)結束后，對象parent和child依然無法釋放，導致內存泄漏。
2. 對象追蹤
為了方便大家理解對象追蹤算法，我們通過一個圖來進行介紹：如圖1所示，從根對象開始遍歷對象以及對象的域，所有可達的對象打上標記（黑色），即為活對象，剩下的不可達對象（白色）即為垃圾。
圖1 對象追蹤
? ? ?●?優(yōu)點：
對象追蹤算法可以解決循環(huán)引用的問題，且對內存的分配和賦值沒有額外的開銷。
?●?缺點：
和引用計數(shù)算法相反，對象追蹤算法較為復雜，且有短暫的STW階段。此外，回收會有延遲，導致比較多的浮動垃圾。
引用計數(shù)和對象追蹤算法各有優(yōu)劣，但考慮到引用計數(shù)存在循環(huán)引用的致命性能問題，方舟JS運行時選擇基于對象追蹤（即Tracing GC）算法來設計自己的GC算法。
? ? ?二、Tracing GC介紹
在介紹HPP GC之前，我們先來了解一下Tracing GC。從前面的介紹可知，Tracing GC算法通過遍歷對象圖標記出垃圾。而根據垃圾回收方式的不同，Tracing GC可以分為三種基本類型：標記-清掃回收、標記-復制回收、標記-整理回收。
1. 標記-清掃回收
此算法的回收方式是：完成對象圖遍歷后，將不可達對象內容擦除，并放入一個空閑隊列，用于下次對象的再分配。該種回收方式不需要搬移對象，所以回收效率非常高。但由于回收的對象內存地址不一定連續(xù)，所以該回收方式最大的缺點是會導致內存空間碎片化，降低內存分配效率，極端情況下甚至會出現(xiàn)還有大量內存的情況下分配不出一個比較大的對象的情況。
圖2 標記-清掃回收
（注：灰色塊表示可達對象的內存空間，白色塊表示不可達對象的內存空間。）
2. 標記-復制回收
此算法的回收方式是：在對象圖的遍歷過程中，將找到的可達對象直接復制到一個全新的內存空間中。遍歷完成后，一次將舊的內存空間全部回收。顯然，這種方式可以解決內存碎片的問題，且通過一次遍歷便完成整個GC過程，效率較高。但同時在極端情況下，這種回收方式需要預留一半的內存空間，以確保所有活的對象能被拷貝，空間利用率較低。
圖3 標記-復制回收
3. 標記-整理回收
此算法的回收方式是：完成對象圖遍歷后，將可達對象（紅色）往本區(qū)域（或指定區(qū)域）的頭部空閑位置復制，然后將已經完成復制的對象回收整理到空閑隊列中。這種回收方式既解決了“標記-清掃回收”引入的大量內存空間碎片的問題，又不需要像“標記-復制回收”那樣浪費一半的內存空間，但是性能上開銷比“標記-復制回收”稍大一些。
圖4 標記-整理回收
綜上所述，Tracing GC的三種基本類型各有優(yōu)缺點，那么方舟JS運行時的HPP GC是基于哪種類型實現(xiàn)的呢？
HPP GC同時實現(xiàn)了這三種Tracing GC算法！沒想到吧？HPP GC綜合了這三種算法的優(yōu)點，且支持根據不同對象區(qū)域、采取不同的回收方式。下面就為大家詳細解析HPP GC。
? ? ?三、HPP GC詳解
前面我們提到了，HPP GC支持根據不同對象區(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ù)經過多次GC之后依然存活的對象會繼續(xù)存活，方舟JS運行時將對象劃分為年輕代對象和老年代對象，并將對象分配到不同的空間。如圖5所示，方舟JS運行時將新分配的對象直接分配到年輕代（Young Generation）的From空間。經過一次GC后依然存活的對象，會進入To空間。而經過再次GC后依然存活的對象，會被復制到老年代（Old?Generation）。
圖5 分代模型
2. 混合算法
通過前面的介紹，我們已經知道：HPP GC同時實現(xiàn)了“標記-清掃回收”、“標記-復制回收”和“標記-整理回收”這三種Tracing GC算法。也就是說，HPP GC是一種“部分復制+部分整理+部分清掃”的混合算法，支持根據年輕代對象和老年代對象的不同特點，分別采取不同的回收方式。(1) 部分復制
考慮到年輕代對象生命周期較短，回收較為頻繁，且年輕代對象大小有限的特點，方舟JS運行時對年輕代對象采用“標記-復制回收”算法。(2) 部分整理+部分清掃
方舟JS運行時根據老年代對象的特點，引入啟發(fā)式Collection Set（簡稱CSet）選擇算法。此選擇算法的基本原理是：在標記階段對每個區(qū)域的存活對象進行大小統(tǒng)計，然后在回收階段優(yōu)先選出存活對象少、回收代價小的區(qū)域進行對象整理回收，再對剩下的區(qū)域進行清掃回收。具體的回收策略如下：
? ? ?(a) 根據設定的區(qū)域存活對象大小閾值，將滿足條件的區(qū)域納入初步的CSet隊列，并根據存活率進行從低到高的排序。
（注：存活率=存活對象大小/區(qū)域大?。?/span>
?(b) 根據設定的釋放區(qū)域個數(shù)閾值，選出最終的CSet隊列，進行整理回收。
?(c) 對未被選入CSet隊列的區(qū)域進行清掃回收。
由上可知，啟發(fā)式CSet選擇算法同時兼顧了 “標記-整理回收”和“標記-清掃回收”這兩種算法的優(yōu)點，既避免了內存碎片問題，也兼顧了性能。
3. GC流程優(yōu)化
在內存回收時，雖然釋放和回收了內存空間，讓系統(tǒng)有了更多可用的內存資源，但內存回收過程本身需要暫停應用業(yè)務代碼執(zhí)行，影響用戶使用應用的體驗?；厥諆却鏁r，如何盡可能的減小對應用性能的影響呢？為此，我們在HPP GC流程中引入了大量的并發(fā)和并行優(yōu)化，以減少對應用性能的影響。如圖6所示，HPP GC流程中采用了并發(fā)+并行標記（Marking）、并發(fā)+并行清掃（Sweep）、并行復制/整理（Evacuation）、并行回改（Update）和并發(fā)清理（Clear）。
圖6 HPP GC流程
(1) 并發(fā)+并行標記
在JS線程執(zhí)行業(yè)務代碼的同時，另外啟動線程執(zhí)行標記，即為“并發(fā)標記”。如果另外啟動多個線程執(zhí)行標記，即為“并發(fā)+并行標記”。 ?在并發(fā)+并行標記過程中，為確保標記的正確性和高性能，HPP GC采取了兩項優(yōu)化措施：措施一：在新增引用關系時增加標記屏障(Marking Barrier)，以確保標記結果的正確性。
并發(fā)標記過程中，JS線程有可能會更改對象之間的引用關系，從而導致對象標記結果出錯。如圖7所示，在marking線程完成對象1的標記、準備標記對象2的過程中，JS線程更改了對象3的引用關系。那么marking線程完成對象2的標記后，對象3不會被標記，回收器會判定對象3為垃圾，進行回收。此后，如果JS線程讀取對象1的字段，將會發(fā)生不可預知的錯誤。
圖7 對象標記出錯
為確保標記結果的正確性，HPP GC在新增引用關系時增加標記屏障。如圖8所示，在marking線程完成對象1的標記、準備標記對象2的過程中，JS線程更改了對象3的引用關系。此時，JS線程會將對象3加入等待標記隊列，等marking線程完成對象2的標記后，繼續(xù)對象3的標記，從而確保對象3不會被回收。
圖8 增加標記屏障
措施二：在共享全局工作隊列的基礎上，增加了本地工作隊列(Local Work List)，以提高讀取對象的性能。
如圖9所示，并行標記時，每個Marking線程都要執(zhí)行以下操作：從全局工作隊列(Global Work List)獲取一個對象，然后設置標記位，最后遍歷該對象的每個域，將子對象放入全局工作隊列中?？紤]到線程之間讀取數(shù)據安全，必須在每個對象的Push/Pop操作時增加原子化或者鎖，這對對象的讀取性能有較大的影響。
圖9 全局工作隊列
為提高讀取對象的性能，HPP GC增加了本地工作隊列。每個線程持有一個獨立的本地工作隊列，優(yōu)先從本地工作隊列獲取/放入對象。當本地工作隊列滿時，將本地工作隊列的部分隊列一次發(fā)布到全局工作隊列中；當本地工作隊列空時，一次從全局工作隊列獲取若干對象到本地工作隊列。這樣，只有從全局工作隊列發(fā)布/獲取對象那一次需要增加原子化或者鎖，兼顧了多線程的并發(fā)效率和任務均衡，大大提高了并發(fā)標記的效率。
圖10 增加本地工作隊列
(2) 并發(fā)+并行清掃
在JS線程執(zhí)行業(yè)務代碼的同時，另外啟動線程執(zhí)行清掃，即為“并發(fā)清掃”。如果另外啟動多個線程執(zhí)行清掃，即為“并發(fā)+并行清掃”。在并發(fā)+并行清掃過程中，HPP GC采取增加區(qū)域空閑隊列(Region Free List)的優(yōu)化措施，用于提高多線程并發(fā)清掃的效率。
并發(fā)+并行清掃過程中，Sweeping線程發(fā)現(xiàn)不可達對象后，需要將對象放入全局的空閑隊列，同時JS線程執(zhí)行的業(yè)務代碼可能需要從空閑隊列分配對象。為了確保數(shù)據安全，這個過程需要增加原子化或者鎖，但會影響到分配和清掃的效率。
為了提升效率，HPP GC增加區(qū)域空閑隊列。將所有需要清掃的內存按內存地址分成若干個區(qū)域，每個區(qū)域擁有獨立的空閑隊列，且每個區(qū)域同時只有一個線程進行清掃。在并發(fā)清掃過程中，Sweeping線程會首先將不可達對象放入本區(qū)域的空閑隊列。當JS線程需要從空閑隊列分配對象時，先獲取已經完成清掃的區(qū)域，再將這些區(qū)域的空閑隊列發(fā)布到全局空閑隊列中，用于對象分配，如圖11所示。由于發(fā)布的任務由JS線程單獨完成，所以整個并行清掃的過程都不需要加鎖，大大提高了并發(fā)+并行清掃的效率。
圖11 增加區(qū)域空閑隊列
(3) 并行復制/整理
在JS線程暫停業(yè)務代碼(STW)對可達對象進行復制/整理時，另外啟動多個線程一起進行復制/整理，即為“并行復制/整理”。和并發(fā)+并行清掃相似，并行復制/整理的瓶頸點在于多個線程同時從全局空閑隊列/全局線性分配器分配對象時，需要增加原子化或者鎖。為了提高多線程分配性能，在并行復制/整理過程中引入了TLAB Allocator。TLAB英文全稱為Thread Local Allocation Buffer。顧名思義，TLAB Allocator就是每個線程擁有一個獨立的本地分配器，該分配器會從全局內存分配器一次分配一塊較大的內存，然后在線程內部再分配。這樣只需從全局分配器分配時保證多線程安全，即可完成高性能且安全的并行復制/整理功能。(4)?并行回改
在GC完成標記和復制/整理后，需要將可達對象中指向舊對象地址的域改成新對象地址，這個過程就是“地址回改”，如圖12所示。為了提升地址回改的效率，HPP GC引入了“并行回改”，同時啟動多個線程進行地址回改，每個線程負責其中一塊內存區(qū)域對象地址的回改。
圖12 地址回改
(5)?并發(fā)清理
在GC復制/整理結束后，JS線程將不再讀寫遍歷出來的不可達對象和已經完成復制的可達對象，因此需要清理和回收對應的物理內存。為了減少STW時間，HPP GC引入“并發(fā)清理”，另外啟動一個工作線程進行并發(fā)的物理內存回收，這樣JS線程就可以繼續(xù)執(zhí)行業(yè)務代碼。 ? ? ? ?四、結束語
本期就為大家介紹到這里了，最后我們總結一下： ? ?●??HPP GC基于分代模型將對象分為年輕代和老年代對象。
?●? HPP GC基于Tracing GC的三種基本類型，實現(xiàn)了“部分復制+部分整理+部分清掃”的混合算法，從而實現(xiàn)根據不同對象區(qū)域、采取不同的回收方式。
?●? HPP GC通過在GC流程中引入了大量的并發(fā)和并行優(yōu)化，實現(xiàn)高性能。
HPP GC仍有很大的探索空間，我們還將繼續(xù)努力，為大家提供更高性能的內存回收能力！
工商網監(jiān)
評論