nia, Santa Barbara
Santa Barbara, CA 93106
ckrintz@cs.ucsb.edu
David F. Bacon
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598
dfb@watson.ibm.com
ABSTRACT
In this paper, we describe a novel execution environment that can
dynamically switch between garbage collection (GC) systems. As
such, it enables application-specic GC selection. In addition, the
system can switch between different GC systems while the program
is executing. Our system is novel in that it is able to switch between
a wide range of diverse collection systems. To empirically evalu-
ate our system, we implemented annotation-guided GC selection
and we show its efcacy for a wide range of benchmarks and heap
sizes. In addition, we implemented a simple heuristic that automat-
ically identies when to switch collectors when program execution
behavior warrants it. Our system introduces an average overhead
of 4% for both annotation-guided and automatic switching. Per-
haps more importantly however, we signicantly improve perfor-
mance over selecting the wrong collection system (by 19% using
annotation-guided selection and by 16% using automatic switch-
ing, on average).
1.
INTRODUCTION
Garbage collection is a mechanism for automatic reclamation of
dynamically allocated memory. It simplies the program devel-
opment cycle by eliminating the burden of explicit memory de-
allocation. However, garbage collection imposes a performance
overhead since it must identify and reuse memory that is no longer
accessible by the program, while the program is executing.
The performance of heap allocation and collection techniques
has been the focus of much research [10, 11, 9, 16, 1, 12, 30, 6].
The goal of most of this prior work has been to provide general-
purpose mechanisms that enable high-performance execution across
all applications. However, other prior research [5, 14, 31, 27], has
shown that the efcacy of a memory management system (the al-
locator and the garbage collector) is dependent upon application
behavior and available resources. That is, no single collection sys-
tem enables the best performance for all applications and all heap
sizes. Our empirical experimentation conrms these ndings. Over
a wide-range of heap sizes and the 10 benchmarks studied, we
found that every collector enabled the best performance at least
once; including a mark-and-sweep and non-generational copying
collector, two collectors that are commonly thought of as imple-
menting obsolete technology. As such, we believe that to achieve
the best performance, the collection and allocation algorithms used
should be specic to both application behavior and heap size.
Existing execution environments enable application- and heap-
specic garbage collection, through the use of different congura-
tions (via separate builds or command-line options) of the execu-
tion environment. However, such systems do not lend themselves
well to next-generation, high-performance server systems in which
a single execution environment executes continuously while multi-
ple applications and code components are uploaded by users [20,
15, 25] For these systems, a single collector and allocator must be
used for a wide range of available heap sizes and applications, e.g.,
e-commerce, agent-based, distributed, collaborative, etc. As such,
it may not be possible to achieve high-performance in all cases and
selection of the wrong GC system may result in signicant perfor-
mance degradation.
In this work, we present the design, implementation, and eval-
uation of a dynamic GC switching system for JikesRVM, a per-
formance-oriented, server-based, Java virtual machine [2] from the
IBM T.J. Watson Research Center. Our switching system facili-
tates the use of the garbage collector and memory allocator that
will enable the best performance for the executing application and
the underlying resource availability. The system we present is ex-
tensible and general; it can switch between many different types of
collectors, e.g., semi-space, mark-and-sweep, copying-marksweep,
and many variants of generational collection.
To evaluate our system, we implemented two mechanisms: anno-
tation-guided GC selection, and automatic switching. For the for-
mer, we identied the best-performing GC for a range of heap sizes
for each program, across inputs. We then annotated the programs to
identify the collection system to use given different resource con-
straints. Upon dynamic loading of each application the VM uses
the annotation to switch to the appropriate GC given the current
maximum available heap size. To implement automatic switching,
we employ a simple heuristic that uses maximum heap size and a
heap residency threshold to switch during program execution.
Our results show that the cost of switching is equivalent to a
garbage collection. In addition, the overhead that our system im-
poses on application execution performance is 4% on average, for
the programs studied. Perhaps more importantly, our system signif-
icantly reduces the negative impact of selecting the wrong collector
(by 19% using annotation-guided selection and over 16% using au-
tomatic switching, on average).
This paper makes the following contributions:
�
It provides a JVM implementation that is able to dynamically
switch between a diverse set of garbage collection systems,
�
It shows how dynamic switching can be successfully guided
1 100
200
300
400
Heap Size (MB)
120
140
160
180
10^6/throughput(ops/sec)
SPECjbb
SS
MS
GMS
GSS
20
40
60
80
100
Heap Size (MB)
60
70
80
90
Execution Time (sec)
JavaGrande
SS
MS
GMS
GSS
Figure 1: Application performance for different GC systems
and heap sizes (lower is better).
by ofine, cross-input, as well as online, program and under-
lying resource characteristics,
�
It provides an empirical evaluation of the efcacy of dy-
namic, application-specic GC selection.
In the following section, we motivate our work and present an
overview of our dynamic GC switching framework. Section 3 de-
scribes the different approaches we employ to dynamically switch
between collectors. Section 4 presents and discusses our experi-
mental results. Section 5 discusses some related work and Section 6
presents our conclusions.
2.
APPLICATION-SPECIFIC GC
The next-generation of high-performance server systems must
enable continuous availability and high-performance to gain wide-
spread use and acceptance. Due to the portability, exibility, and
security features enabled by the Java programming language and its
execution environments, a number of high-end server systems now
employ Java as the implementation language for application and
execution servers [20, 15, 25]. These systems run a single virtual
machine (VM) image continuously so that applications and code
components can be uploaded and executed as needed by customers
(for customization, collaboration, distributed execution, etc.).
Given this model (single VM and continuous execution) and ex-
isting JVM technology, a single, general-purpose collector and al-
location policy must be used for all applications. However, many
researchers have shown that there is no single combination of a
collector and an allocator that enables the best performance for all
applications on all hardware and given all resource constraints [5,
14, 31]. Figure 1 conrms these ndings. The graphs show perfor-
mance (lower is better) over heap size for the SPECjbb [28] and the
JavaGrande [21] benchmarks, executing within the JikesRVM [2].
Figure 1(a) shows that for SPECjbb, the semispace (SS) collec-
tor, performs best for all heap sizes larger than 200MB, the gener-
ational/semispace hybrid (GSS) performs best for heap sizes 120-
200MB, and the generational/mark-sweep hybrid (GMS) performs
best for heaps smaller than 120MB. In Figure 1(b), GMS is the best
for small sized heaps, SS performs well for heap sizes 40-53MB,
and GSS performs best for heap sizes larger than 53MB. We refer
to the point at which the best-performing GC system changes as the
switch point.
To exploit this execution behavior that is application-specic and
dependent upon the underlying resource availability, we extended
the JikesRVM adaptive optimization system for Java, to enable dy-
namic switching between GC systems. The goal of our work is
to improve performance of applications for which there exists GC
switch points, without imposing signicant overhead.
2.1
The JikesRVM and the JMTk
The JikesRVM [2] is an open-source, dynamic and adaptive opti-
mization system for Java that was designed and continues to evolve
with the goal of enabling high-performance in server systems. The
JikesRVM (version 2.2.0+) implements the Java Memory Manage-
ment Toolkit (JMTk) that enables garbage collection and allocation
algorithms to be written and plugged into the JikesRVM. The
framework offers a high-level, uniform interface to the JikesRVM
that is used by all algorithm implementations. We refer to the com-
bination of an allocation policy and a collection technique as a
GC system. This corresponds to a Plan in the JMTk terminology.
The JMTk allows users to implement their own GC systems eas-
ily within the JikesRVM and to perform an empirical comparison
with other existing collectors and allocators. When a user builds a
conguration of the JikesRVM, she is able to select a particular GC
system for incorporation into the JikesRVM image.
Each GC system in the JikesRVM is implemented via a Plan
and Policy class. Each GC system is linked to a virtual mem-
ory resource (VM Resource) which binds the allocation region to
particular virtual address ranges. In addition, the syste