一種改進的局部堆碎片壓縮機制

吳昊　季振洲

摘 要：在運行時系統(tǒng)中，堆碎片對內(nèi)存管理以及應(yīng)用程序運行性能具有十分重要影響。碎片降低了堆空間的利用率并且影響了數(shù)據(jù)的局部性特性，增加了對象訪問的開銷。隨著程序長時間運行，碎片化嚴(yán)重的時就會由于無法滿足應(yīng)用程序內(nèi)存分配的需求，而導(dǎo)致提前觸發(fā)堆空間的垃圾回收，從而導(dǎo)致更多的性能開銷。針對以上問題本文首先分析了堆空間碎片產(chǎn)生的原因以及對運行時性能的影響，提出了局部堆碎片消除機制，在此基礎(chǔ)上設(shè)計了動態(tài)調(diào)節(jié)堆預(yù)留空間的大小方案，提高了堆空間利用率。

關(guān)鍵詞：堆壓縮；堆碎片；垃圾回收

中圖分類號：TP314 文獻標(biāo)識號： A 文章編號：2095-2163（2015）05-

An Improved Partial Heap Compaction Mechanism

WU Hao， JI Zhenzhou

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China ）

Abstract： In programming language runtime systems， heap fragmentation is one of the major performance bottleneck. The heap fragment reduces the heap usage utilization as well as affects the data locality. As the program runs for a long time， the fragmentation becomes seriously， and the heap will be unable to meet the demand of allocations. It also could trigger ahead of schedule， and then bring performance penalty. To solve the aboved problem， this paper first analysed how the heap produced the fragments and then proposes an improved partial heap compaction mechanism， a method of dynamic adjustment for compaction reserve space is also presented to improve the heap usage utilization.

Key words： Heap Compaction； Heap Fragmentation； Garbage Collection

0 引 言

內(nèi)存碎片是影響運行時性能的關(guān)鍵因素之一，在大多數(shù)On-the-fly回收算法[1-3]中為了降低垃圾回收對應(yīng)用線程的暫停時間普遍采取了對象非拷貝策略。然而這種方式最大的缺陷是隨著回收的進行，垃圾對象不斷從原有的位置清除掉，給堆內(nèi)存留下很多不連續(xù)的空閑空間，堆內(nèi)存變得碎片化（Fragmentation）。堆碎片化對垃圾回收不會產(chǎn)生影響，但是提高了未來的對象分配開銷，而且還會導(dǎo)致無法滿足對象分配中對連續(xù)空間的需求。針對以上問題，需要設(shè)計有效的碎片整理壓縮機制，但是頻繁使用堆壓縮會給系統(tǒng)帶來額外的性能開銷[4-6]，近年來已有相關(guān)研究[7-12]在垃圾回收過程中考慮堆碎片壓縮機制。

1 堆碎片與空間消耗

在垃圾回收中，堆對象面臨的內(nèi)存碎片有兩種，分別是外部碎片（External fragmentation）和內(nèi)部碎片（Internal fragmentation）。外部碎片指的是在堆空間中的不連續(xù)內(nèi)存片段，由于這些空間細小分散形成碎片化狀態(tài)，無法滿足對象內(nèi)存分配中對連續(xù)堆空間的需求，碎片的存在是對堆空間的一種浪費。外部碎片是隨著程序的運行，在對象的分配回收過程中產(chǎn)生的，比如在堆空間連續(xù)分配若干個對象后，如果其中幾個變成垃圾對象，被回收器回收后留下幾個不連續(xù)的空閑空間。內(nèi)部碎片指在對象內(nèi)部浪費的內(nèi)存空間，比如對于按塊對齊申請內(nèi)存的對象，如果對象大小不是塊的整數(shù)倍，就會造成某些塊的浪費，另外也有對象頭部浪費，造成同一個對象在存儲時空間不連續(xù)的情況?；诖鎯R和維護對象頭部信息的需求，對象內(nèi)部碎片通常是無法避免的，但內(nèi)部碎片對空間的浪費是固定可控的，所以內(nèi)部碎片對回收器的性能以及未來對象的分配的影響較小。而外部碎片對堆空間的浪費以及相關(guān)對象分配的影響要大得多，因此對外部碎片的控制在內(nèi)存管理中十分重要。

在堆空間中隨著程序的運行，碎片是一直存在的，為了比較和度量計算碎片關(guān)于對象分配所形成的影響，本文首先給出用于計算堆空間中的碎片度的方法。對于內(nèi)部碎片，主要來自于對象的內(nèi)部，通常是在對象分配時為了保證內(nèi)存對齊導(dǎo)致的塊內(nèi)的空間浪費，假設(shè)堆空間分配粒度為BLOCK_BYTES表示堆分配的最小字節(jié)數(shù)，對于任意活動對象v，其分配的塊個數(shù)表示為M（v），該對象的內(nèi)部空間浪費為： ，整體的內(nèi)部碎片度就是所有活動對象內(nèi)部的浪費空間占所有活動對象分配消耗的總空間，計算公式如下：

（1）

對于外部碎片主要是由于堆空間無法提供連續(xù)的塊以用于大對象分配，假設(shè)堆空間中存在16塊的連續(xù)空閑空間，大對象分配需要連續(xù)9塊空間，最小對象僅需1塊空間，如果小對象存儲在第8塊中，就會將連續(xù)的塊劃分為大小為7和8的兩部分，對于大對象雖然堆中總的空閑空間足夠但是因為無法提供連續(xù)的塊則會導(dǎo)致分配失敗。只有當(dāng)無法滿足大對象分配時才能稱為碎片，因此外部碎片取決于堆中需要分配的大對象的情況。假設(shè)堆空間中最大連續(xù)塊為max_free，則外部碎片程度可按如下公式計算：

（2）

式中，當(dāng)Fexternal≥1時表示堆中的空閑空間可以滿足大對象分配，當(dāng)0

在不同的內(nèi)存分配和垃圾回收策略中，外部碎片對堆的浪費程度有很大不同，在某些分配策略下，甚至可以完全避免外部碎片。比如把所有的對象的分配都限制為固定的大小，即使回收器把一部分對象清除，留下的空位也能滿足其他對象的分配，但這種極端的方式其實是把外部碎片轉(zhuǎn)移到對象的內(nèi)部碎片中。在對象的大小不受限制時，已有的研究表明理論上在Mark-sweep垃圾回收中，最壞情況下堆碎片造成堆空間的浪費情況為：

式中，V表示堆中的全部的對象，公式表示碎片會造成f倍的堆空間浪費。而在實際的Mark-sweep垃圾回收中很難精確地計算出堆浪費的多少，并且因受應(yīng)用程序和回收策略的影響而具有相當(dāng)?shù)牟淮_定性。而在Semi-space回收算法中，在堆中任意時刻只有一半的空間允許分配對象，因此可以確定該算法需要消耗2倍的堆空間。表1簡單總結(jié)并比較了堆碎片對兩種追蹤類回收算法的影響。

在追蹤類的垃圾回收算法中，垃圾回收器從一組根結(jié)點開始，依次遍歷所有對象，并識別出哪些是活動的對象，哪些是垃圾對象，非活動的對象所占的內(nèi)存由回收器收回。標(biāo)記清除（Mark-sweep）將垃圾回收工作分為兩個階段：第一階段在遍歷過程中定位并標(biāo)記所有的活動對象；第二階段清除回收所有未被標(biāo)記的對象，為了避免因此帶來內(nèi)存碎片，回收過程也會采取對內(nèi)存進行壓縮的策略。半空間（Semi-space）回收與標(biāo)記清除回收有所不同的是：半空間算法將內(nèi)存劃分為兩個大小相等的空間，分別稱為起始空間（from-space）和到達空間（to-space）?；厥臻_始前，所有對象都存放在起始空間，一旦回收工作啟動，在遍歷過程中將發(fā)現(xiàn)的活動對象依次移動至到達空間，當(dāng)回收工作完成時，所有的活動對象都已移動至到達空間，起始空間的內(nèi)存整體回收，下次回收啟動時再將兩個空間的角色互換。

在垃圾回收算法中，將堆中的空閑空間表示為：

式中，SFree和SHeap分別表示空閑空間和全部的堆空間，ω表示最壞情況下對象分配空間消耗函數(shù)，對于大小為n的對象，消耗的堆空間大小為ω（n），ω的確定取決于堆碎片的影響和垃圾回收算法的特性。對于任意對象v，如果回收算法確保該對象在堆上成功分配，必須保證有足夠的空閑空間，即ω（n）≤SHeap。ω（n）反映了在不同的回收算法下，堆空間浪費情況。對于Semi-space回收，ω（n）=2（n），消耗函數(shù)是常量，而在Mark-sweep算法下，ω（n）= nlogSHeap。可以看出，在堆空間浪費方面兩種算法具有較大的差別，堆碎片對Mark-sweep回收的影響要比Semi-space嚴(yán)重。

2 動態(tài)調(diào)節(jié)堆壓縮預(yù)留空間

本節(jié)針對局部堆進行建模，介紹根據(jù)局部堆對象分布特點動態(tài)調(diào)節(jié)壓縮預(yù)留空間的方案，該方案克服了固定設(shè)置預(yù)留空間的缺陷，減少了堆空間的浪費。

圖1 局部堆空間分布示意圖

Fig.1 Illustration of partial heap space

如圖1所示，將需要壓縮整理的局部堆稱為壓縮區(qū)（Compaction Space，用Scompaction表示），在堆中預(yù)留區(qū)域（Reserved Space）用Sreserved表示，Sreserved的大小主要取決于Scompaction中所有活動的對象的數(shù)量和大小，另外還需要加上在堆拷貝過程中應(yīng)用程序新分配的對象。本文引入局部活動對象率（Live Object Ratio）參數(shù)表示在某塊堆空間中所有活動對象所占的空間比例的大小，用Rlive表示。活動對象率滿足0≤Rlive≤1，當(dāng)Rlive=0說明該空間沒有活動對象，Rlive=1表示該空間存儲的全部是活動對象，當(dāng)Rlive滿足以上兩種條件時都不需要進行壓縮，因此壓縮只針對0

（5）

當(dāng)壓縮整理完成后，Scompaction空間被清空，該空間可以作為下一次壓縮的預(yù)留空間，滿足Scompaction≥Sreserved，結(jié)合公式（5）得出如下關(guān)系：

（6）

如果將預(yù)留區(qū)和壓縮區(qū)看成是整個堆空間，Sheap=Scompaction+Sreserved，用Slive_up表示堆空間中活動對象所占空間的上限，結(jié)合公式（6）可得出堆空間與最大活動對象空間以及活動對象率之間滿足以下關(guān)系：

（7）

從公式（7）可以看出假設(shè)堆大小是固定的，在給定Slive_up和Sallocation條件下，活動對象率越高則所需的預(yù)留空間越大，反之則越小，如圖2所示。因此可以在垃圾回收及堆壓縮過程中通過監(jiān)視壓縮空間中的Rlive，根據(jù)堆使用的情況及時調(diào)整預(yù)留空間的大小，并且也可以作為回收器觸發(fā)堆壓縮的條件，本文采取最低活動對象率優(yōu)先的策略，在多個壓縮空間的選擇上優(yōu)先壓縮活動對象率最低的空間，這樣做的好處是可以較小的預(yù)留空間完成同樣大小壓縮空間的碎片整理，同時整理出來的空間又可以作為下一個空間的預(yù)留空間，由低向高逐步完成整個堆的碎片整理。

圖2 根據(jù)Rlive動態(tài)調(diào)節(jié)預(yù)留空間大小

Fig.2 Adjustment of reserved space with Rlive

根據(jù)公式（7）求導(dǎo)可知Sheap取最小值的條件是活動對象率Rlive滿足公式（8），同時該計算結(jié)果也是可壓縮堆空間的活動對象率的上限：

（8）

公式（8）反映了對于指定大小的堆空間其局部活動對象所占空間比例的上界，如果堆中的活動對象所占空間比例超過該值，那么將無法完成對該堆空間的壓縮整理。結(jié)合公式（6）可得出，在給定局部堆空間下，所需的最小預(yù)留空間滿足以下關(guān)系：

（9）

令Sallocation=αSlive_up，該參數(shù)反映了在堆碎片整理過程中回收器與應(yīng)用線程并發(fā)執(zhí)行的情況，α越大表明在堆壓縮過程中需要在預(yù)留空間滿足更多的新對象的分配。選取α=0.05根據(jù)公式（7），Rlive-up和Sheap_min/Slive_up的關(guān)系如圖3所示，從圖中看出當(dāng)Rlive在0.7～0.8區(qū)間時，堆空間最小，僅需要最大活動對象所占的空間上限的1.5倍。當(dāng)Rlive > 0.9時堆空間需求劇增，這是因為此時整個堆空間的活動對象已經(jīng)接近飽和，如果進行壓縮則需要設(shè)置更大的預(yù)留區(qū)，從而導(dǎo)致堆空間需求增大，不過此時執(zhí)行堆壓縮也是沒有意義的，因為Rlive已經(jīng)接近1，就使得不再可能通過壓縮提高空間的利用率。

圖3 對象活動率與堆大小關(guān)系

Fig.3 Relationship of live ratio and heap size

3 實驗結(jié)果

本文使用虛擬機平臺是JikesRVM 3.1.0，在該平臺上設(shè)計了本文提出堆碎片壓縮以及堆壓縮預(yù)留空間的優(yōu)化方案。在實驗中使用SPECjvm2008[13]和Dacapo[14]兩種基準(zhǔn)測試程序。

本文在JikesRVM平臺上實現(xiàn)了這兩種預(yù)留區(qū)選取方案，分別將預(yù)留區(qū)比例設(shè)置為半空間的10%，20%，35%，50%，測試結(jié)果如表2所示。從表2的測試結(jié)果中可以看出當(dāng)R=35%和R=20%時增加的開銷幾乎可以忽略，當(dāng)R=10%時壓縮僅增加了約4%-6%的暫停時間。

4 結(jié)束語

本文研究了內(nèi)存垃圾回收中的堆碎片消除問題，分析了堆碎片產(chǎn)生的原因以及對運行時系統(tǒng)的影響，在半空間拷貝垃圾回收基礎(chǔ)上提出了局部堆空間碎片整理壓縮的方案。局部堆壓縮預(yù)留空間大小的選取中則充分考慮了壓縮空間活動對象率的情況，在壓縮拷貝過程中通過活動對象率變化，根據(jù)堆使用的情況及時調(diào)整預(yù)留空間的大小，并進一步作為回收器觸發(fā)堆壓縮的條件之一。同時本文提出了降低堆壓縮預(yù)留空間的改進方案，給出了當(dāng)預(yù)留空間無法滿足壓縮時的解決方案，本文的設(shè)計以較小的預(yù)留空間完成同樣大小壓縮空間的碎片整理。通過實驗結(jié)果可以看出本文提出的方案有效地降低了在堆壓縮中預(yù)留空間設(shè)置的大小，提高了堆空間的利用率，降低了垃圾回收的次數(shù)。

參考文獻：

[1]. AZATCHI H， LEVANONI Y， PAZ H， et al. An on-the-fly mark and sweep garbage collector based on sliding views[C]// Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing， systems， languages， and applications， Anaheim， California， USA： ACM ，2003： 269-281.

[2]. DOMANI T， KOLODNER E K， LEWIS E， et al. Implementing an on-the-fly garbage collector for Java[C]//Proceedings of the 2nd international symposium on Memory management， Minneapolis， Minnesota， USA：ACM， 2000：155-166.

[3]. DOMANI T， KOLODNER E K， PETRANK E. A generational on-the-fly garbage collector for Java[C]//Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation， Vancouver， British Columbia， Canada：ACM， 2000：274-284.

[4]. Jones， R.， A. Hosking， E. Moss， The Garbage Collection Handbook： The Art of Automatic Memory Management[M]. London： Chapman & Hall/CRC. 511， 2011.

[5]. KERMANY H， PETRANK E. The compressor： Concurrent， incremental， and parallel compaction[J]. SIGPLAN Not.， 2006. 41（6）： 354-363.

[6]. ABUAIADH D， OSSIA Y， PETRANK E， et al.， An efficient parallel heap compaction algorithm[C]//Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming， systems， languages， and applications， Vancouver， BC， Canada： ACM ， 2004：224-236.

[7]. BACON D F， CHENG P， RAJAN V T. A real-time garbage collector with low vverhead and consistent utilization[C]//Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages， New Orleans， Louisiana， USA：ACM， 2003：285-298.

[8]. BEN-YITZHAK O， GOFT I， KOLODNER E K， et al. An algorithm for parallel incremental compaction[C]//Proceedings of the 3rd international symposium on Memory management， Berlin， Germany：ACM， 2002：100-105.

[9]. UGAWA T， IWASAKI H， YUASA T. Improved replication-based incremental garbage collection for embedded systems[C]// Proceedings of the 2010 international symposium on Memory management， Toronto， Ontario， Canada：ACM，2010： 73-82.

[10]. DETLEFS D， FLOOD C， HELLER S， et al. Garbage-first garbage collection[C]// Proceedings of the 4th international symposium on Memory management， Vancouver， BC， Canada：ACM， 2004：37-48.

[11]. CLICK C， TENE G， WOLF M. The pauseless Gc algorithm[C]//Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments， Chicago， IL， USA：ACM， 2005：46-56.

[12]. PIZLO F， PETRANK E， STEENGAARD B. A study of concurrent real-time garbage collectors[C]//Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation， Tucson， AZ， USA：ACM， 2008：33-44.

[13]. Standard Performance Evaluation Corporation， SPECjvm2008[EB/OL]. http：//www.spec.org/jvm2008.

[14]. DaCapo Project. The DaCapo Benchmarks， beta-2006-08[OL]， 2006. http：//www.dacapobench.org.