GarbageCollectionHints
Dries Buytaert, Kris Venstermans, Lieven Eeckhout, and Koen De Bosschere
ELIS Department, GhentUniversity – HiPEAC Member,
St.-Pietersnieuwstraat 41, B-9000 Gent, Belgium
{dbuytaer, kvenster, leeckhou, kdb}@elis.UGent.be
Abstract. This paper shows that Appel-style garbage collectors often
make suboptimal decisions both in terms of when and how to collect.
We argue that garbage collection should be done when the amount of
live bytes is low (in order to minimize the collection cost) and when
the amount of dead objects is high (in order to maximize the available
heap size after collection). In addition, we observe that Appel-style col-
lectors sometimes trigger a nursery collection in cases where a full-heap
collection would have been better.
Based on these observations, we propose garbage collection hints
(GCH) which is a profile-directed method for guiding garbage collec-
tion. Offline profilingisused to identify favorable collection pointsinthe
program code. In those favorable collection points, the VM dynamically
chooses between nursery and full-heap collections based onan analytical
garbage collector cost-benefit model. By doing so, GCH guides the col-
lectorintermsofwhenandhowtocollect. Experimental resultsusingthe
SPECjvm98 benchmarks and two generational garbage collectors show
that substantial reductions can be obtained in garbage collection time
(up to 30X)and thatthe overall executiontime canbe reduced by more
than 10%.
1 Introduction
Garbage collection (GC) is an important subject of research as many of todays
programming language systems employ automated memory management. Pop-
ular examples are Java, C# and .NET. Before discussing the contributions of
this paper, we revisit some garbage collection background and terminology.
1.1 Garbage Collection
An Appel-style generational copying collector divides the heap into two genera-
tions [2], a variable-size nursery and a mature generation. Objects are allocated
from the nursery.When thenurseryfills up,a nursery collection is triggeredand
the surviving objects are copied into the mature generation. When the objects
are copied, the size of the mature generation is grown and the size of the nurs-
ery is reduced accordingly.Because the nursery size decreases, the time between
consecutive collections also decreases and objects have less time to die. When
T. Conte etal.(Eds.):HiPEAC 2005, LNCS3793, pp.233–248, 2005.
c Springer-Verlag BerlinHeidelberg2005
Pdf to powerpoint converter online - control application system:C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
www.rasteredge.com
Pdf to powerpoint converter online - control application system:VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
www.rasteredge.com
234
D. Buytaert et al.
the nursery size drops below a given threshold,a full-heap collection is triggered.
After a full-heap collection all free space is returned to the nursery.
In this paper we consider two flavors of generational copying collectors,
namely GenMS and GenCopy from JMTk[3]. GenMS collects thematuregener-
ation using the mark-sweep garbage collection strategy. The GenCopy collector
on the other hand, employs a semi-space strategy to manage its mature genera-
tion. The semi-space collector copies scanned objects, whereas the mark-sweep
collector does not.
To partition the heap into generations, the collector has to keep track of
references between different generations. Whenever an object in the nursery is
assigned to an object in the maturegeneration—i.e.there is a reference from an
object in the mature generation to an object in the nursery—this information
is tracked by using a so-called remembered set. When a nursery collection is
triggered the remembered set must be processed to avoid erroneously collecting
nursery objects that are referenced only from the mature generation.
1.2 Paper Contributions
While garbagecollection offersmanybenefits,thetimespent reclaiming memory
can account for a significant portion of the total execution time [1]. Although
garbage collection research has been a hot research topic for many years, little
researchhas been doneto decidewhen and how garbagecollectors should collect.
Garbage is typically collected when either the heap, or a generation is full.
Ideally, the heap should be collected when the live ratio is low: the fewer live
objects, the fewer objects need to be scanned and/or copied, the more memory
there is to be reclaimed, and the longer we can postpone the next garbage
collection run. In this paper, we show that collecting prior to a full heap, at
points where the live ratio is low, can yield substantial reductions in GC time.
In addition, when using an Appel-style collector with two generations, a
decision needs to be made whether to trigger a full-heap or nursery collection.
We found that triggering nursery collections untilthenursery size drops below a
certain threshold is sometimes suboptimal. In this paper, we show how to trade
off full-heap collections and nursery collections so that performance improves
substantially.
The approach presented in this paper to decide when and how to collect, is
calledgarbage collection hints (GCH) and worksasfollows.GCH firstdetermines
favorable collection points (FCPs) for a given application through offline profil-
ing. A favorable collection point is a location in the application code where the
cost of a collection is relatively cheap.During programexecution a cost function
is then computed in each FCP to determinethe best GC strategy:postponeGC,
perform a nursery GC, or perform a full-heap GC. Our experimental results us-
ing theSPECjvm98 benchmarks and two generationalcollectors show that GCH
can reduce the garbagecollector time by up to 30X and can improvethe overall
execution time by more than 10%.
Figure 1 perfectly illustrates why garbage collection hints actually work for
the
213
javac benchmark. This graph shows the number of live bytes as a
control application system:Online Convert PowerPoint to PDF file. Best free online export
Online Powerpoint to PDF Converter. Download Free Trial. Convert a PPTX/PPT File to PDF. Just upload your file by clicking on the blue
www.rasteredge.com
control application system:XDoc.Converter for .NET, Support Documents and Images Conversion
Convert PowerPoint to ODP. Convert to Tiff. Convert Word, Excel and PDF to image. Next Steps. Download and try Converter for .NET with online support. See Pricing
www.rasteredge.com
Garbage Collection Hints
235
6
8
10
12
14
16
18
0
100
200
300
400
500
600
700
800
900
live data in MB
time in allocated MB
_213_javac, -s100, -m4 -M4 with 156 MB heap, GenCopy
full-heap collections without GCH 
nursery collections without GCH 
nursery collections with GCH 
Fig.1. Garbage collection points with andwithout GCH
function of the number of allocated bytes. The empty circles denote nursery
collections andthesquaresdenotefull-heapcollectionswhen GCHis notenabled.
Without GCH, GC is triggered at points where the number of live bytes is not
necessarilylow.In fact,the maximum GC timethat weobserved onour platform
for these GC points is 225ms; and 12MB needs to be copied from the nursery
to the mature generation. The GC time for a full-heap collection takes 330ms.
When GCH is enabled (see the filled circles in Figure 1), garbage gets collected
when theamount of live bytes reaches a minimum, i.e. at an FCP.The GC time
at an FCP takes at most 4.5ms since only 126KB needs to be copied. From
this example, we observe two key features why GCH actually works: (i) GCH
preferably collects when the amount of live data on the heap is low, and (ii)
GCH eliminates a number of full-heap collections by trading them for (cheaper)
nursery collections.
The main contributions of this paper are as follows.
– We show that GC is usually not triggered when the amount of live data is
low, i.e. when the amount of garbage collection work is minimal.
– We show that the collector does not always make the best decision when
choosing between a nursery and a full-heap collection.
– We propose GCH which is a feedback-directed technique based on profile
information that provides hints to the collector about when and how to
collect.GCHtries to collect at FCPswhen theamountoflivedata is minimal
and dynamically chooses between nursery and full-heap collections.The end
resultissignificant reductions in GCtime andimprovedoverallperformance.
GCH is especially beneficial for applications that exhibit a recurring phase
behavior in the amount of live data allocated during program execution.
2 Experimental Setup
2.1 Java Virtual Machine
We use the Jikes Research Virtual Machine 2.3.2 (RVM) [4]on an AMD Athlon
XP 1500+ at 1.3 GHz with a 256KB L2-cache, running Linux 2.6. Jikes RVM
is a Java virtual machine written almost entirely in Java. Jikes RVM uses a
compilation-only scheme for translating Java bytecodes to native machine in-
structions.For our experiments we use the FastAdaptive profile: all methods are
control application system:C#: How to Use SDK to Convert Document and Image Using XDoc.
You may use our converter SDK to easily convert PDF, Word, Excel, PowerPoint, Tiff, and Dicom files to raster images like Jpeg, Png, Bmp and Gif.
www.rasteredge.com
control application system:RasterEdge XDoc.PowerPoint for .NET - SDK for PowerPoint Document
Add image to specified position on PowerPoint page. Next Steps. Download Free Trial Download and try PDF for .NET with online support. See Pricing
www.rasteredge.com
236
D. Buytaert et al.
initially compiled using a baseline compiler, but sampling is used to determine
which methods to recompile using an optimizing compiler.
Because Jikes RVM is written almost entirely in Java, internal objects such
as those created during class loading or those created by the runtime compilers
are allocated from the Java heap. Thus, unlike with conventional Java virtual
machinesthe heap contains both application data as wellas VM data.We found
that there is at least 8MB of VM data that is quasi-immortal. The presence of
VM data has to be taken into account when interpreting the results presented
in the remainder of this work.
Jikes RVM’s memory management toolkit (JMTk) [3] offers several GC
schemes.While the techniques presented in this paper aregenerallyapplicableto
variousgarbagecollectors,wefocus on the GenMS and GenCopy collectors.Both
been used in Jikes RVM’s production builds that areoptimized for performance.
To getaround a bug in JikesRVM 2.3.2weincreasedthemaximum sizeofthe
remembered set to 256MB. In order to be able to model the shrinking/growing
behavior of the heap accurately, we made onemodification to the originalRVM.
We placed the remembered set outside the heap.
Performance is measured using the Hardware Performance Monitor (HPM)
subsystem of Jikes RVM. HPM uses (i) the perfctr
1
Linux kernelpatch,which
providesa kernelmoduleto accesstheprocessor hardware,and (ii) PAPI[5],a li-
brarytocapturetheprocessor’sperformancecounters.Thehardwareperformance
counterskeeptrackofthenumberofretiredinstructions,elapsedclockcycles,etc.
2.2 Benchmarks
To evaluate our mechanism, we use the SPECjvm98
2
benchmark suite. The
SPECjvm98 benchmark suite is a client-side Java benchmark suite consisting of
seven benchmarks, each with three input sets: -s1, -s10 and -s100. With the
-m and -M parameters the benchmark can be configured to run multiple times
without stopping the VM. Garbage collection hints work well for long running
applications that show some recurring phase behavior in the amount of live
data.To mimic such workloads with SPECjvm98,we use the-s100input set in
conjunction with running the benchmarks four times (-m4 -M4).
We used all SPECjvm98 benchmarks except one, namely
222
mpegaudio,
because it merely allocates 15MB each run and triggers few GCs. The other
benchmarks on the other hand, allocate a lot more.
All SPECjvm98 bencharmks are single-threaded except for
227
mtrt which
is a multi-threaded raytracer. Note that because both Jikes RVM’s sampling
mechanismand the optimizing compilerrun in separate threads the otherbench-
marks are not deterministic.
We ran allexperiments with a range of different heapsizes.We varytheheap
sizebetweentheminimumfeasibleheapsizeandtheheapsizeat whichour mech-
anism stops triggering or shows constant behavior.The larger the heap size,the
lessfrequentgarbageneeds to be collectedand the moretimeobjectshaveto die.
1
http://user.it.uu.se/mikpe/linux/perfctr/
2
http://www.spec.org/jvm98/
control application system:VB.NET PDF - Convert PDF Online with VB.NET HTML5 PDF Viewer
All Formats. XDoc.HTML5 Viewer. XDoc.Windows Viewer. XDoc.Converter. View & Process. Adobe PDF. XDoc.PDF. Scanning. XDoc.Word. XDoc.Excel. XDoc.PowerPoint. Barcoding
www.rasteredge.com
control application system:VB.NET PDF- View PDF Online with VB.NET HTML5 PDF Viewer
All Formats. XDoc.HTML5 Viewer. XDoc.Windows Viewer. XDoc.Converter. View & Process. Adobe PDF. XDoc.PDF. Scanning. XDoc.Word. XDoc.Excel. XDoc.PowerPoint. Barcoding
www.rasteredge.com
Garbage Collection Hints
237
Some benchmarks like
213
javac use forced garbage collections triggered
through calls to java.lang.System.gc(). For our experiments we disabled
forced garbage collections unless stated otherwise.
3 Garbage Collection Hints
Our garbage collection hints approach consists of an offline and an online step,
see Figure 2. The offline step breaks down into two parts:offline profiling of the
application and garbage collector analysis. The offline profiling computes the
live/time function of the application, i.e. the amount of live bytes as a function
of the amount of bytes allocated. Based on this live/time function, favorable
collection points (FCPs) can bedetermined.Determining the FCPsis a one-time
cost per application. The garbage collector analysis characterizes the collection
cost for a particular GC and application, i.e. the amount of time needed to
process a given amount of live bytes. This is dependent on the collector and
the platform on which the measurements are done. In the online part of GCH,
the methods that have been identified as FCPs are instrumented to invoke a
cost-benefit model that helps the garbage collector make decisions about when
and how to collect. This decision making is based on the amount of heap space
available, the live/timefunction of the application and thecharacteristics of the
GC. The following subsections discuss GCH in more detail.
Guide garbage
collection
offline
online
Analyse collector
Profile application
- Identify FCPs
- Capture live/time function
Fig.2. An overview of the GCH methodology
3.1 Program Analysis
Live/Dead Ratio Behavior. The first step of the offline profiling is to collect
the live/time function which quantifies the number of live bytes as a function of
the bytes allocated so far. Moreover, we are interested in linking the live/time
function to methods calls. We modified Jikes RVM to timestamp and report all
method entries and exits. For each method invocation, we want to know how
many objects/bytes died and how many objects are live. Therefore, a lifetime
analysis is required at every point an object could have died. There are two
reasons for an object to die: (i) an object’s last reference is overwritten as a
result of an assignment operation, or (ii) an object’s last reference is on a stack
frame and the stack frame gets popped because the frame’s method returns or
because an exception is thrown. To avoid having to do a lifetime analysis for
control application system:C# HTML5 PDF Viewer SDK to convert and export PDF document to
All Formats. XDoc.HTML5 Viewer. XDoc.Windows Viewer. XDoc.Converter. View & Process. Adobe PDF. XDoc.PDF. Scanning. XDoc.Word. XDoc.Excel. XDoc.PowerPoint. Barcoding
www.rasteredge.com
control application system:DocImage SDK for .NET: Web Document Image Viewer Online Demo
Try Online Demo Now. Please click Browse to upload a file to display in web viewer. Suppported files are Word, Excel, PowerPoint, PDF, Tiff, Dicom and main
www.rasteredge.com
238
D. Buytaert et al.
0
2
4
6
8
10
12
14
16
0
50
100
150
200
250
300
350
400
450
500
live data in MB
time in allocated MB
_201_compress -m4 -M4 -s100
0
2
4
6
8
10
12
0
200
400
600
800
1000
1200
live data in MB
time in allocated MB
_202_jess -m4 -M4 -s100
0
2
4
6
8
10
12
14
16
18
0
50
100
150
200
250
300
350
live data in MB
time in allocated MB
_209_db -m4 -M4 -s100
0
2
4
6
8
10
12
14
16
18
20
0
100
200
300
400
500
600
700
800
900
live data in MB
time in allocated MB
_213_javac -m4 -M4 -s100
0
5
10
15
20
25
0
100
200
300
400
500
600
700
live data in MB
time in allocated MB
_227_mtrt -m4 -M4 -s100
0
2
4
6
8
10
12
14
0
200
400
600
800
1000
1200
live data in MB
time in allocated MB
_228_jack -m4 -M4 -s100
Fig.3. The live/time function for the various benchmarks: number of live bytes as a
function of the number of bytes allocated
every assignment operation, method return and exception, we used a modified
version of the Merlin trace generator [6] that is part of Jikes RVM. Merlin is
atool that precisely computes every object’s last reachable time. It has been
modified to use our alternative timestamping method to correlate object death
with method invocations.
Figure 3 shows the live/timefunction for the various benchmarks.As can be
seen from these graphs, the live/time function shows recurring phase behavior.
This recurring phase behavior will be exploited through GCH.Applications that
do not exhibit a phased live/time function are not likely to benefit from GCH.
Next, the live/time function is used to select FCPs and to compute the FCP
live/time patterns.
FavorableCollection Points. For a method to representa favorablecollection
point (FCP), it needs to satisfy three criteria:
1. An FCP’s invocation should correspond to a local minimum in terms of the
number of live bytes. In other words, we need to select methods that are
executed in the minima of the live/time function. This will allow GCH to
collect garbage with minimal effort.
2. An FCP should not be executed frequently.To minimize the overhead ofthe
instrumentation code, FCPs that represent cold methods are preferred. A
method that gets executed only in local minima is an ideal FCP.
3. The live/time pattern following the execution of the FCP should be fairly
predictable, i.e. each time the FCP gets executed, the live/time function
should have a more or less similar shape for some range after the FCP.
Given the live/timefunction,selecting FCPsisfairlystraightforward.Table1
shows theselected FCPsthat we selected for the SPECjvm98 benchmarks.Some
Garbage Collection Hints
239
Table 1. The selected FCPs for eachof the benchmark applications
Benchmark
Favorablecollectionpoints
201
compress
spec.io.FileInputStream.getContentLength()I
202
jess
spec.benchmarks.
202
jess.jess.
undefrule.<init>()V
spec.harness.BenchmarkTime.toString()Ljava/lang/String;
209
db
spec.harness.Context.setBenchmarkRelPath(Ljava/lang/String;)V
spec.io.FileInputStream.getCachingtime()J
213
javac
spec.benchmarks.
213
javac.ClassPath.<init>(Ljava/lang/String;)V
227
mtrt
spec.io.TableOfExistingFiles.<init>()V
spec.harness.Context.clearIOtime()V
spec.io.FileInputStream.getCachingtime()J
228
jack
spec.benchmarks.
228
jack.Jack
the
Parser
Generator
Internals.-
compare(Ljava/lang/String;Ljava/lang/String;)V
0
50
100
150
200
250
20
40
60
80
100
120
140
160
maximum collection time in ms
heap size in MB
B
_201_compress, GenMS
0
50
100
150
200
250
15
20
25
30
35
40
45
50
55
60
maximum collection time in ms
heap size in MB
_202_jess, GenMS
0
500
1000
1500
2000
2500
3000
3500
0
50
100
150
200
250
300
350
maximum collection time in ms
heap size in MB
B
_209_db, GenMS
0
50
100
150
200
250
300
350
400
40
60
80
100
120
140
160
180
200
maximum collection time in ms
heap size in MB
_213_javac, GenMS
0
50
100
150
200
250
300
350
20
40
60
80
100
120
140
160
180
200
maximum collection time in ms
heap size in MB
_227_mtrt, GenMS
full-heap collections at non-FCPs
full-heap collections at FCPs
nursery collections at non-FCPs
nursery collections at FCPs
s
0
50
100
150
200
250
300
10
20
30
40
50
60
70
80
90
100
maximum collection time in ms
heap size in MB
_228_jack, GenMS
full-heap collections at non-FCPs
full-heap collections at FCPs
nursery collections at non-FCPs
nursery collections at FCPs
Fig.4. The maximum garbage collection times across different heap sizes for each of
the differentscenarios
benchmarkshaveonlyoneFCP (seeforexampleFigure1for
213
javac);others
such as
227
mtrt have three FCPs.
To illustrate the potentialbenefit of FCPs,Figure 4 plots the maximum time
spent in GC when triggered at an FCP and when triggered in a non-FCP. We
make a distinction between full-heap and nursery collections, and plot data for
arange of heap sizes. For most benchmarks we observe that the maximum GC
timespentatanFCP is substantiallylowerthantheGC timein a non-FCP.This
240
D. Buytaert et al.
reinforces ourassumption that collecting at an FCP is cheaperthancollecting in
anon-FCP. However, there are two exceptions,
201
compress and
228
jack,
for which GC time is insensitive to FCPs. For
201
compress, this is explained
by the fact that the live/timefunction shown in Figure3 is due to a few objects
that are allocated in the Large Object Space (LOS). Because objects in LOS
never get copied, GCH cannot reducethe copy cost.Furthermore, becausethere
areonly a few such objects it will not affect the scan cost either. For
228
jack,
the height of the live/time function’s peaks is very low, see Figure 3. Because
201
compressand
228
jackareinsensitive to FCPs we exclude them fromthe
other results that will be presented in this paper. (In fact, we applied GCH to
these benchmarks but the result was a neutral impact of overall performance.
Due to space constraints, we do not to include these benchmarks in the rest of
this paper.)
It isalso interesting to notethatfor
209
db,a nurserycollection canbemore
costly than a full-heap collection. This is due to the fact that the remembered
set needs to be scanned on a nursery collection. As such, for
209
db a full-
heap collection can be more efficient than a nursery collection. This is exploited
through GCH.
FCP’s Live/Time Pattern. For each unique FCP we have to capture the
live/time pattern following the FCP. This is a slice of the live/time function
following the FCP that recurs throughout the complete program execution. We
sample the FCP’s live/time pattern at a frequency of one sample per 0.5MB
of allocated memory and use it as input for the cost-benefit model. An FCP’s
live/time pattern is independent of the heap size (the same information is used
for all heap sizes) and is independent of the collection scheme (the same infor-
mation is used for both GenMS and GenCopy). It only needs to be computed
oncefor each benchmark.For completeness,we add that in order to be indepen-
dant ofthe collection scheme,we differentiate between data that is eligible to be
copied and data that cannot be copied.
3.2 Collector Analysis
So far,wediscussed the offlineprofiling thatis required for GCH.Wenow discuss
the characterization of the garbage collector. This characterization will be used
in the cost model that will drive the decision making in GCH during program
execution. The characterization of the garbage collector quantifies the cost of
acollection. We identify three cost sources: the cost of a full-heap collection,
the cost of a nursery collection and the cost of processing the remembered set.
The cost functions take as input the amount of live data and output the esti-
mated collection time. These cost functions are dependent on the application,
the collector and the given platform (VM, microprocessor, etc.).
Figure 5 shows how the cost functions are to be determined for the GenMS
and GenCopy collectors. The graphs are obtained by running the benchmarks
multiple times with different heap sizes using instrumented collectors. In these
graphs we make a distinction between nursery collections, full-heap collections
Garbage Collection Hints
241
0
50
100
150
200
250
300
350
400
0
5
10
15
20
average processing time in ms
live data in nursery, expressed in MB
MB
GenMS, nursery collections
_202_jess
_209_db
_213_javac
_227_mtrt
0
50
100
150
200
250
300
350
400
0
5
10
15
20
average processing time in ms
live data in nursery, expressed in MB
GenCopy, nursery collections
_202_jess
_209_db
_213_javac
_227_mtrt
0
50
100
150
200
250
300
350
400
0
2
4
6
8
10
12
14
16
18
20
average processing time in ms
live data in nursery and mature generation, expressed in MB
MB
GenMS, full-heap collections
_202_jess
_209_db
_213_javac
_227_mtrt
0
50
100
150
200
250
300
350
400
0
2
4
6
8
10
12
14
16
18
20
average processing time in ms
live data in nursery and mature generation, expressed in MB
GenCopy, full-heap collections
_202_jess
_209_db
_213_javac
_227_mtrt
1
10
100
1000
10000
0.1
1
10
100
1000
average processing time in ms
size of remembered set, expressed in MB
B
GenMS, remembered sets
_202_jess
_209_db
_213_javac
_227_mtrt
1
10
100
1000
10000
0.1
1
10
100
1000
average processing time in ms
size of remembered set, expressed in MB
GenCopy, remembered sets
_202_jess
_209_db
_213_javac
_227_mtrt
Fig.5. The cost of a nursery and full-heap collection in terms of the amount of
copied/live data
andprocessing oftherememberedset.Hence,theprocessingtimeson thenursery
collectiongraphsdonotincludethetimerequiredtoprocesstherememberedsets.
GC time appears to be a linear function of the amount of live data for both
collectors. In other words, the scanning and copying cost is proportional to the
amountof livebytes.Likewise,theprocessingcostoftheremembered setappears
to be a linear function of its size. In summary,we can compute linear functions
that quantify the cost of a nursery collection,full-heap collection and processing
of the remembered set.
In this paper we employ application-specific cost functions, i.e. we compute
cost functions per application. In fact, on a specialized system with dedicated
long running applications, it is appropriate to consider a cost function that is
specificallytuned for the given application. Nevertheless, given the fact that the
costfunctions appear to befairlysimilar acrossthe variousapplications,seeFig-
ure 5, choosing application-independent costfunctions could bea viablescenario
forgeneral-purposeenvironments.Sucha scenarioislikelyto produceresultsthat
are only slightly worse compared to the ones presented in this paper.
3.3 GCH at Work
The information that is collected through our offline analysis is now communi-
cated to the VM to be used at runtime. Jikes RVM reads all profile information
242
D. Buytaert et al.
at startup. This contains (i) a list of methods that represent the FCPs, (ii) the
live/time pattern per FCP, and (iii) the cost functions for the given garbage
collector.Jikes RVM is also modified to dynamically instrument the FCPs. The
instrumentation code added to the FCPs examines whether the current FCP
should trigger a GC. The decision to collect or not is a difficult one as there ex-
ists a trade-off between reducing the amount of work per collection and having
to collect more frequently. Clearly, triggering a collection will have an effect on
subsequent collections. Because GC is invoked sooner dueto GCH than without
GCH,additionalcollections might get introduced.On the other hand, triggering
acollection at an FCP can help reduce the GC overhead. A collection at an
FCP will generally introduce modest pause times compared to collections at a
non-FCPs.Moreover,triggering a full-heap collection grows thenurserysize and
gives objects more time to die, while triggering a nursery collection when few
objects are live will result in the mature generation filling up slower, reducing
the need for more expensive full-heap collections.
To make this complex trade-off, the instrumentation code in the FCPs im-
plements an analytical cost-benefit model. The cost-benefit model estimates the
totalGC time for getting from the currentFCP to theend of its FCP’s live/time
pattern. The cost-benefit model considers the following three scenarios: (i) do
not trigger a GC in thecurrent FCP,(ii) trigger a full-heap GC,or (iii) trigger a
nursery GC. For each of these three scenarios, the cost-benefit model computes
the total GC time by analytically simulating how the heap will evolve through
theFCP’s live/timepattern.Thisis doneasfollows.First,thecost-benefitmodel
computes the GC cost in the current FCP under the three scenarios:
(i) The cost for not triggering a GC is obviously zero. The available heap size
remains unchanged.
(ii) For computing the cost for triggering a full-heap collection in the current
FCP, we first calculate the number of live bytes at the current FCP. We
get this information from the live/time pattern. We subsequently use the
full-heap GC cost function to compute the GC time given the amount of
live data in the current FCP. The available heap size after the current (hy-
pothetical) full-heap collection then equals the maximum heap size minus
the amount of live data in the current FCP.
(iii) To compute the cost for triggering a nursery GC in the current FCP, we
assumethat the amount of live bytes in the nursery at that FCP is close to
zero.TheGC cost is then computedbasedon thenursery-GCcostfunction.
This GC cost is incremented by an extra cost due to processing theremem-
bered set. This extra cost is proportionalto the sizeof the remembered set,
which is known at runtime at an FCP. The heap size that was occupied by
the nursery becomes available again for allocation.
In the second step of the cost-benefit model we compute the cost of addi-
tional collections over the FCP’s live/time pattern for each of the three sce-
narios. In fact, for each scenario, the cost-benefit model analytically simulates
how the heap will evolveover time when going through an FCP’s live/time pat-
tern. Therefore, we compute when the (nursery) heap will be full—when the
Documents you may be interested
Documents you may be interested