Introduction

Java applications do not have memory management issues, because the garbage collector of the Java Virtual Machine (JVM) takes care of all the storage issues. The garbage collector in the IBM JVM is based on the mark-sweep-compact (MSC) algorithm, where garbage collection (GC) takes place in three phases. At the end of the mark and sweep phases, free space is available, but there is a possibility of heap fragmentation. The compact phase alleviates the fragmentation problem by moving chunks of allocated space towards the lower end of the heap, helping create contiguous free memory at the other end.

Since the advent of 64-bit operating systems, applications have had the liberty to use large heaps. With Java applications using large heaps, compaction of the heap takes quite a lot of time, during which the application will not be able to do anything else. This period of time is called pause time. Pause times of 40 seconds are quite possible for compaction of a 1 GB heap. Such long pause times are often unacceptable for real-time applications. Incremental compaction (IC) is a way of reducing pause times. IC also reduces the "dark matter" in a heap, which we'll discuss in the next section.

Back to top

Incremental compaction

Incremental compaction decreases the pause times during compaction by distributing compaction work across different GC cycles. IC also removes dark matter from the heap. Any piece of storage that is more than 512 bytes is treated as free space and is available to mutators or object allocators. Other chunks that are less than 512 bytes are termed dark matter, and are not available as free space.

The amount of dark matter in the heap will directly affect the application throughput, because more dark matter means less free space on the heap for object allocation. This, in turn, will mean more GC cycles seriously affecting the application performance. Incremental compaction aims to minimize pause times, as well as free the heap from dark matter.

The fundamental idea behind incremental compaction is to split the heap up into sections and compact each section just as during a full compaction. IC moves all the moveable objects down the heap, which retrieves all the dark matter and leaves large areas of free space. Individual sections on which IC runs are of fixed size, thereby binding the pause time.

In the top part of Figure 1 above, marked portions are live objects, and unmarked portions represent free space. There might be dark matter among the free spaces depending on the size of the free chunk, as shown in the diagram. The bottom part of Figure 1 shows the situation after IC. Live objects are moved to one end of the section, freeing up space on the other end.

Incremental compaction is done only if the heap size is at least a constant value, currently 128 MB. If the heap size is less than this, IC fails to provide significant improvement in pause time compared to full compaction. The value of 128 MB has been suggested by performance teams for current conditions.

Incremental compaction cycle

An incremental compaction cycle is successive garbage collection cycles that will incrementally compact the entire heap, a region at a time. There are two main steps to IC:

• Identify and remember all references that point into the compaction region, which is done during the mark phase. At the end of this stage all free space within the sections can be identified.
• Compute the new locations of objects and move them within the compaction region, then fix up pointers to those objects.

This section explains the detailed process of incremental compaction.

Regions and sections

A region is a portion of the heap that's subjected to incremental compaction in one cycle. The heap is divided into several regions, and IC runs on one of these regions each time it runs. The whole heap is thus covered in a few GC cycles. Each region is further divided into sections, and IC on each section is handled by one GC helper thread.

Incremental compaction divides each region into (Number of GC helper threads +1) or 8 sections, whichever is less. There is currently a limitation of 16 MB on the size of each section, which limits the size of each region to a maximum of 16 x 8 = 128 MB. IC then makes as many such regions as required to cover the entire heap. Size of each region thus varies with the number of sections, as follows. For:

• 1 section, region is 16 MB.
• 2 or 3 sections, region is 32 MB
• 4, 5, 6, or 7 sections, region is 64 MB
• 8 sections, region is 128 MB.

Figure 2 below shows the regions in a 256 MB memory running on a 4-CPU machine. In this example, we have four sections per region, and the region size is 64 MB. To divide the heap into regions, IC starts from the lower end of the heap and reaches the higher end. The first and last regions might be less than 64 MB because of rounding to nearest 64 MB boundaries.

Remembering references into the compaction region

Once IC has chosen the region to compact, the rest of the process resembles regular compaction. IC must first remember all references for objects in the compaction region, then fix up those references so they point to proper places after objects are moved. Finally, IC moves the objects within the region.

To remember the references into the compaction region, IC uses a new bit vector called FR_bits (Fixup References bits). This is implemented as a bitmap, having one bit for each reference (valid address) inside the heap. Because references are 4 bytes on 32-bit platforms and 8 bytes in 64, there is one bit in FR_bits for 4 bytes on 32-bit platforms and 1 bit for 8 bytes on 64-bit platforms. While marking references in the mark phase, if IC notices any reference into the compaction region, it sets the corresponding bit in the FR bitmap, because these references will change when IC moves objects within the compaction region.

Break tables

As mentioned earlier, moving objects takes place within sections of the region. For example, each GC helper thread takes care of moving objects within the section given to it. IC uses break tables inside each section to decide how much, and where, to move live objects. See Resources for information on break tables.

There is a separate break table for each section in the region, each being built concurrently by a separate thread. IC walks the section looking for free space and live objects; for each block of live objects it writes a break table entry to record how much all the objects in the block will move by. The break table is big enough to hold 100,000 such entries. If it fills up, IC only compacts the part of the section it has walked so far.

Each entry in the break table is a pair of values, offset from the beginning of the first live object in the section, and shows (in bytes) the amount to move.

Fixing up the references

This is the phase just before we actually move the objects. IC fixes up all references to the objects to be moved before it moves them. The FR_bits are used to find where references are in the compaction region. Break tables tell where the objects are to be moved. The main GC thread first triggers the helper threads to start fixing up references in each section. It then scans the loaded classes in system heaps, other heaps, and primitive classes, and fixes references from these roots to moved objects. Ultimately, the main thread also joins the helper threads in fixing up the references. When the main thread has finished, it waits for all helper threads to finish their work.

Moving the objects

Moving the objects is done one section at a time, and each section is processed by a separate helper thread. IC walks the section, looking for movable objects. The break table tells how much each of these objects can be moved. At the end of this phase, IC rebuilds the free space to include all the free space within each section into a chain of free chunks.

Back to top

Interpreting verbosegc output

The most commonly used method to analyze what the garbage collector does is running the JVM with the -verbosegc option. This section shows how to interpret verbosegc output corresponding to IC.

The verbosegc example below shows an incremental compaction.

	
<AF[1]: Allocation Failure. need 528 bytes, 0 ms since last AF>
<AF[1]: managing allocation failure, action=1 (0/131070464) (3145728/3145728)>
  <GC(1): GC cycle started Tue Jun 11 14:33:27 2002
  <GC(1): freed 130223768 bytes, 99% free (133369496/134216192), in 1906 ms>
  <GC(1): mark: 444 ms, sweep: 649 ms, compact: 813 ms>
  <GC(1): refs: soft 0 (age >= 32), weak 0, final 3, phantom 0>
  <GC(1): moved 6461 objects, 363840 bytes, IC reason=13>
<AF[1]: completed in 1936 ms>

The line

shows how many objects have been moved, how many bytes have been moved, and the reason for compaction. The IC reason implies this was an incremental compaction. The possible reasons a.k.a. triggers for a compaction, including IC, are:

1. Following the mark and sweep phase there is insufficient free space for the allocation request.
2. The heap is fragmented and will benefit from an incremental compaction.
3. Less than half the -Xminf value is free space (the default is 30%, which in this case will be less than 15% free space), and the free space plus the dark matter is not less than -Xminf.
4. A System.gc collection.
5. Less than 5% free space available.
6. Less than 128K free space available.
7. The -Xcompactgc parameter has been specified.
8. The transient heap has less than 5% free space available.
10. Incremental compaction is being performed in this GC cycle.
11. Compact to avoid heap shrinkage.
12. An incremental compaction due to excessive dark matter.
13. The -Xpartialcompactgc parameter has been specified.

Back to top

Runtime parameters

There are two runtime parameters available to selectively switch IC on or off:

-Xpartialcompactgc

Run an IC every GC cycle. Default value is false.

-Xnopartialcompactgc

Never run an IC during the life of this JVM. Default value is false.

Back to top

Performance improvements

In tests conducted by the performance team, a significant reduction was observed in the GC pause times with IC as compared to without IC. In Figure 3, which shows the results of SPECjbb runs using a JDK 140 build on Z/OS machine with 16 CPUs, we can clearly conclude that the pause times have come down from a high of 10 seconds with IC off to a maximum of 0.5 seconds with IC on. This is a very significant improvement in the performance of the GC with IC, and is a major factor in improving the response times of large Java applications.

Resources

• Participate in the discussion forum.
  
  
• Garbage Collection - Algorithms for Automatic Dynamic Memory Management by Richard Jones and Rafael Lins covers the topic in great detail.
  
  
• For lots of details about garbage collection, read Sam Borman's articles on the IBM Java Garbage Collector (developerWorks, August 2002)
  
  
• See the article Inside the Java Virtual Machine - Garbage Collection to learn more about garbage collection.
  
  
• Break tables are described in Garbage Collection by Richard Jones and Rafael Lins, ISBN 0-471-94148-4.
  
  

About the authors

Comments (Undergoing maintenance)

Back to top

Trademarks  |  My developerWorks terms and conditions

Table of contents

• Introduction
• Incremental compaction
• Interpreting verbosegc output
• Runtime parameters
• Performance improvements
• Resources
• About the authors
• Comments

Local resources

• IBM Innovation Center - Austin, TX
• IBM Innovation Center - Chicago, IL
• IBM Innovation Center - Dallas, TX
• IBM Innovation Center - San Mateo, CA
• IBM Innovation Center - Waltham, MA
• Technical Briefings in North America

My developerWorks community