一种改进的局部堆碎片压缩机制

吴昊　季振洲

摘 要：在运行时系统中，堆碎片对内存管理以及应用程序运行性能具有十分重要影响。碎片降低了堆空间的利用率并且影响了数据的局部性特性，增加了对象访问的开销。随着程序长时间运行，碎片化严重的时就会由于无法满足应用程序内存分配的需求，而导致提前触发堆空间的垃圾回收，从而导致更多的性能开销。针对以上问题本文首先分析了堆空间碎片产生的原因以及对运行时性能的影响，提出了局部堆碎片消除机制，在此基础上设计了动态调节堆预留空间的大小方案，提高了堆空间利用率。

关键词：堆压缩；堆碎片；垃圾回收

中图分类号：TP314 文献标识号： 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 引 言

内存碎片是影响运行时性能的关键因素之一，在大多数On-the-fly回收算法[1-3]中为了降低垃圾回收对应用线程的暂停时间普遍采取了对象非拷贝策略。然而这种方式最大的缺陷是随着回收的进行，垃圾对象不断从原有的位置清除掉，给堆内存留下很多不连续的空闲空间，堆内存变得碎片化（Fragmentation）。堆碎片化对垃圾回收不会产生影响，但是提高了未来的对象分配开销，而且还会导致无法满足对象分配中对连续空间的需求。针对以上问题，需要设计有效的碎片整理压缩机制，但是频繁使用堆压缩会给系统带来额外的性能开销[4-6]，近年来已有相关研究[7-12]在垃圾回收过程中考虑堆碎片压缩机制。

1 堆碎片与空间消耗

在垃圾回收中，堆对象面临的内存碎片有两种，分别是外部碎片（External fragmentation）和内部碎片（Internal fragmentation）。外部碎片指的是在堆空间中的不连续内存片段，由于这些空间细小分散形成碎片化状态，无法满足对象内存分配中对连续堆空间的需求，碎片的存在是对堆空间的一种浪费。外部碎片是随着程序的运行，在对象的分配回收过程中产生的，比如在堆空间连续分配若干个对象后，如果其中几个变成垃圾对象，被回收器回收后留下几个不连续的空闲空间。内部碎片指在对象内部浪费的内存空间，比如对于按块对齐申请内存的对象，如果对象大小不是块的整数倍，就会造成某些块的浪费，另外也有对象头部浪费，造成同一个对象在存储时空间不连续的情况。基于存储对齐和维护对象头部信息的需求，对象内部碎片通常是无法避免的，但内部碎片对空间的浪费是固定可控的，所以内部碎片对回收器的性能以及未来对象的分配的影响较小。而外部碎片对堆空间的浪费以及相关对象分配的影响要大得多，因此对外部碎片的控制在内存管理中十分重要。

在堆空间中随着程序的运行，碎片是一直存在的，为了比较和度量计算碎片关于对象分配所形成的影响，本文首先给出用于计算堆空间中的碎片度的方法。对于内部碎片，主要来自于对象的内部，通常是在对象分配时为了保证内存对齐导致的块内的空间浪费，假设堆空间分配粒度为BLOCK_BYTES表示堆分配的最小字节数，对于任意活动对象v，其分配的块个数表示为M（v），该对象的内部空间浪费为： ，整体的内部碎片度就是所有活动对象内部的浪费空间占所有活动对象分配消耗的总空间，计算公式如下：

（1）

对于外部碎片主要是由于堆空间无法提供连续的块以用于大对象分配，假设堆空间中存在16块的连续空闲空间，大对象分配需要连续9块空间，最小对象仅需1块空间，如果小对象存储在第8块中，就会将连续的块划分为大小为7和8的两部分，对于大对象虽然堆中总的空闲空间足够但是因为无法提供连续的块则会导致分配失败。只有当无法满足大对象分配时才能称为碎片，因此外部碎片取决于堆中需要分配的大对象的情况。假设堆空间中最大连续块为max_free，则外部碎片程度可按如下公式计算：

（2）

式中，当Fexternal≥1时表示堆中的空闲空间可以满足大对象分配，当0

在不同的内存分配和垃圾回收策略中，外部碎片对堆的浪费程度有很大不同，在某些分配策略下，甚至可以完全避免外部碎片。比如把所有的对象的分配都限制为固定的大小，即使回收器把一部分对象清除，留下的空位也能满足其他对象的分配，但这种极端的方式其实是把外部碎片转移到对象的内部碎片中。在对象的大小不受限制时，已有的研究表明理论上在Mark-sweep垃圾回收中，最坏情况下堆碎片造成堆空间的浪费情况为：

式中，V表示堆中的全部的对象，公式表示碎片会造成f倍的堆空间浪费。而在实际的Mark-sweep垃圾回收中很难精确地计算出堆浪费的多少，并且因受应用程序和回收策略的影响而具有相当的不确定性。而在Semi-space回收算法中，在堆中任意时刻只有一半的空间允许分配对象，因此可以确定该算法需要消耗2倍的堆空间。表1简单总结并比较了堆碎片对两种追踪类回收算法的影响。

在追踪类的垃圾回收算法中，垃圾回收器从一组根结点开始，依次遍历所有对象，并识别出哪些是活动的对象，哪些是垃圾对象，非活动的对象所占的内存由回收器收回。标记清除（Mark-sweep）将垃圾回收工作分为两个阶段：第一阶段在遍历过程中定位并标记所有的活动对象；第二阶段清除回收所有未被标记的对象，为了避免因此带来内存碎片，回收过程也会采取对内存进行压缩的策略。半空间（Semi-space）回收与标记清除回收有所不同的是：半空间算法将内存划分为两个大小相等的空间，分别称为起始空间（from-space）和到达空间（to-space）。回收开始前，所有对象都存放在起始空间，一旦回收工作启动，在遍历过程中将发现的活动对象依次移动至到达空间，当回收工作完成时，所有的活动对象都已移动至到达空间，起始空间的内存整体回收，下次回收启动时再将两个空间的角色互换。

在垃圾回收算法中，将堆中的空闲空间表示为：

式中，SFree和SHeap分别表示空闲空间和全部的堆空间，ω表示最坏情况下对象分配空间消耗函数，对于大小为n的对象，消耗的堆空间大小为ω（n），ω的确定取决于堆碎片的影响和垃圾回收算法的特性。对于任意对象v，如果回收算法确保该对象在堆上成功分配，必须保证有足够的空闲空间，即ω（n）≤SHeap。ω（n）反映了在不同的回收算法下，堆空间浪费情况。对于Semi-space回收，ω（n）=2（n），消耗函数是常量，而在Mark-sweep算法下，ω（n）= nlogSHeap。可以看出，在堆空间浪费方面两种算法具有较大的差别，堆碎片对Mark-sweep回收的影响要比Semi-space严重。

2 动态调节堆压缩预留空间

本节针对局部堆进行建模，介绍根据局部堆对象分布特点动态调节压缩预留空间的方案，该方案克服了固定设置预留空间的缺陷，减少了堆空间的浪费。

图1 局部堆空间分布示意图

Fig.1 Illustration of partial heap space

如图1所示，将需要压缩整理的局部堆称为压缩区（Compaction Space，用Scompaction表示），在堆中预留区域（Reserved Space）用Sreserved表示，Sreserved的大小主要取决于Scompaction中所有活动的对象的数量和大小，另外还需要加上在堆拷贝过程中应用程序新分配的对象。本文引入局部活动对象率（Live Object Ratio）参数表示在某块堆空间中所有活动对象所占的空间比例的大小，用Rlive表示。活動对象率满足0≤Rlive≤1，当Rlive=0说明该空间没有活动对象，Rlive=1表示该空间存储的全部是活动对象，当Rlive满足以上两种条件时都不需要进行压缩，因此压缩只针对0

（5）

当压缩整理完成后，Scompaction空间被清空，该空间可以作为下一次压缩的预留空间，满足Scompaction≥Sreserved，结合公式（5）得出如下关系：

（6）

如果将预留区和压缩区看成是整个堆空间，Sheap=Scompaction+Sreserved，用Slive_up表示堆空间中活动对象所占空间的上限，结合公式（6）可得出堆空间与最大活动对象空间以及活动对象率之间满足以下关系：

（7）

从公式（7）可以看出假设堆大小是固定的，在给定Slive_up和Sallocation条件下，活动对象率越高则所需的预留空间越大，反之则越小，如图2所示。因此可以在垃圾回收及堆压缩过程中通过监视压缩空间中的Rlive，根据堆使用的情况及时调整预留空间的大小，并且也可以作为回收器触发堆压缩的条件，本文采取最低活动对象率优先的策略，在多个压缩空间的选择上优先压缩活动对象率最低的空间，这样做的好处是可以较小的预留空间完成同样大小压缩空间的碎片整理，同时整理出来的空间又可以作为下一个空间的预留空间，由低向高逐步完成整个堆的碎片整理。

图2 根据Rlive动态调节预留空间大小

Fig.2 Adjustment of reserved space with Rlive

根据公式（7）求导可知Sheap取最小值的条件是活动对象率Rlive满足公式（8），同时该计算结果也是可压缩堆空间的活动对象率的上限：

（8）

公式（8）反映了对于指定大小的堆空间其局部活动对象所占空间比例的上界，如果堆中的活动对象所占空间比例超过该值，那么将无法完成对该堆空间的压缩整理。结合公式（6）可得出，在给定局部堆空间下，所需的最小预留空间满足以下关系：

（9）

令Sallocation=αSlive_up，该参数反映了在堆碎片整理过程中回收器与应用线程并发执行的情况，α越大表明在堆压缩过程中需要在预留空间满足更多的新对象的分配。选取α=0.05根据公式（7），Rlive-up和Sheap_min/Slive_up的关系如图3所示，从图中看出当Rlive在0.7～0.8区间时，堆空间最小，仅需要最大活动对象所占的空间上限的1.5倍。当Rlive > 0.9时堆空间需求剧增，这是因为此时整个堆空间的活动对象已经接近饱和，如果进行压缩则需要设置更大的预留区，从而导致堆空间需求增大，不过此时执行堆压缩也是没有意义的，因为Rlive已经接近1，就使得不再可能通过压缩提高空间的利用率。

图3 对象活动率与堆大小关系

Fig.3 Relationship of live ratio and heap size

3 实验结果

本文使用虚拟机平台是JikesRVM 3.1.0，在该平台上设计了本文提出堆碎片压缩以及堆压缩预留空间的优化方案。在实验中使用SPECjvm2008[13]和Dacapo[14]两种基准测试程序。

本文在JikesRVM平台上实现了这两种预留区选取方案，分别将预留区比例设置为半空间的10%，20%，35%，50%，测试结果如表2所示。从表2的测试结果中可以看出当R=35%和R=20%时增加的开销几乎可以忽略，当R=10%时压缩仅增加了约4%-6%的暂停时间。

4 结束语

本文研究了内存垃圾回收中的堆碎片消除问题，分析了堆碎片产生的原因以及对运行时系统的影响，在半空间拷贝垃圾回收基础上提出了局部堆空间碎片整理压缩的方案。局部堆压缩预留空间大小的选取中则充分考虑了压缩空间活动对象率的情况，在压缩拷贝过程中通过活动对象率变化，根据堆使用的情况及时调整预留空间的大小，并进一步作为回收器触发堆压缩的条件之一。同时本文提出了降低堆压缩预留空间的改进方案，给出了当预留空间无法满足压缩时的解决方案，本文的设计以较小的预留空间完成同样大小压缩空间的碎片整理。通过实验结果可以看出本文提出的方案有效地降低了在堆压缩中预留空间设置的大小，提高了堆空间的利用率，降低了垃圾回收的次数。

参考文献：

[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.