Transcript studies.ac.upc.edu

Aspect Enabled Adaptive
Garbage Collection
Darren Ng
David Kaeli
Outline
•
•
•
•
•
Introduction
Problem: Java Performance
Jikes Research Virtual Machine (RVM)
Aspect Oriented Programming (AOP)
Aspectual Framework for Adaptive Garbage
Collection
• SPEC JVM98 Results
• Summary
• Future Work
Thesis Overview
• Goal
To explore the use of aspect oriented
programming (AOP) software engineering to
enhance the run-time performance of the
Java language.
More specifically, an AOP framework was
created to enable adaptive garbage
collection in the Jikes Research Virtual
Machine (RVM).
Thesis Contribution
1. Detailed how aspects in the form of AspectJ can
be integrated into the Jikes RVM for
“environmentally aware” software components.
2. Described an AOP framework for adaptive
Garbage Collection in the Jikes RVM to improve
Java application performance.
3. Explained how the current AOP framework can be
expanded for future software research.
Problem: Java Performance
• Java is an interpreted programming
language.
• A virtual machine (VM) translates Java bytecode into machine code.
• A virtual machine also automatically
manages heap memory.
Java Performance Cont.
• The use of a VM consumes CPU cycles and
slows down the execution of the Java
application.
• New Java technology is continually being
developed to increase the performance of
the language.
– Just-in-time Compilation
– New Garbage Collection Schemes
Garbage Collector Categories
• Stop the World – Application program is paused
while the garbage collector is active.
• Incremental – Interleaves partial garbage
collection with application execution.
• Concurrent – Application and collector may
operate simultaneously
• Real-Time – Garbage collection time is bounded by
a guaranteed small time constant to minimize the
application pause time.
Garbage Collection Terms
• Garbage Collection Cycle (2 phases)
1) Garbage Detection
2) Garbage Reclamation
• Root Set
– Static variables
– Local (stack-allocated) variables
– General-purpose registers.
All objects reachable from the root set are consider
live and cannot be reclaimed. Un-reachable
objects can be freed.
STW: Semi-Space
½ Memory Heap
ROOT SET
½ Memory Heap
D
Directly Reachable
I
Indirectly Reachable
U
Unreachable
G
D
I
U
U
U
D
Contiguous Free
Space
To Space
Bump Pointer
Global
S
Stack
From Space
STW: Semi-Space
½ Memory Heap
½ Memory Heap
ROOT SET
D
Directly Reachable
I
Indirectly Reachable
U
Unreachable
GA
F
F
U
U
U
F
U
U
U
U
U
U
From Space
• Advantages:
D
D
I
Global
SA
Contiguous Free
Space
F Forwarding Pointer
Stack
To Space
Bump Pointer
– Inherently compacts data during copying.
• Disadvantages:
– Requires a lot more heap memory!
STW: Mark-Sweep
ROOT SET
FREE
LIST
GA
GB
Global
SA
SB
Stack
D
D
F
D
F
F
F
F
U
U
I
I
HEAP
D
Directly Reachable
I
Indirectly Reachable
U
Unreachable
F
Free Space
U
U
F
F
STW: Mark-Sweep
ROOT SET
FREE
LIST
GA
GB
Global
SA
SB
Stack
D
D
F
D
F
F
F
F
F
F
I
I
D
Directly Reachable
I
Indirectly Reachable
U
Unreachable
F
Free Space
F
F
F
F
HEAP
• Advantages:
– Simple implementation
– Handles cyclical garbage
• Disadvantages:
– Fragmentation of memory
– Garbage collection time is proportional to heap size
STW: Generational Copy
ROOT SET
U
I
D
U
I
D
U
U
U
Bump Pointer
D
Directly Reachable
I
Indirectly Reachable
U
Unreachable
F
Free Space
D
Global
I
F
Contiguous
Free Space
Stack
To
From
Nursery
Mature Space
Bump Pointer Allocator
Semi-Space Collector
STW: Generational Mark-Sweep
ROOT SET
U
I
D
U
I
D
U
U
U
Global
Contiguous
Free Space
Stack
Nursery
Bump Pointer Allocator
Free List
D
F
F
F
F
F
F
F
F
F
F
F
U
F
F
Mature Space
Mark-Sweep Collector
D
Directly Reachable
I
Indirectly Reachable
U
Unreachable
F
Free Space
STW: Generational
• Advantage
– Reduced garbage collection overhead
• Disadvantage
– More book keeping overhead to keep track of
references from the mature space to the nursery
(Write Barriers)
Garbage Collector Selection
• There is no single garbage collector that will
be optimal in all situations.
• Current VM’s garbage collectors are static
entities that are included at VM compile time
or selected via a user command line switch.
• Lack of “environmental awareness” results in
a non-optimal garbage collector choice.
Aspect Oriented Programming
• AOP can be used to overcome the
performance limitations of a static garbage
collector.
• Aspects allow monolithic program
components to be non-intrusively upgraded
and modified to achieve new functionality.
• Aspects permit the gathering of data
throughout a program’s hierarchy.
AspectJ
Components of Aspect Code
Java Class Code
Aspect
Call-Site A
(Class Static Initialization)
Pointcut A
Advice A
Call-Site B
(Class Method Call)
Pointcut B
Advice B
• Join Point - A well defined location within the primary code
where a concern will crosscut the application.
• Pointcut - A collection of join points that designates where
advice code should be inserted in the program.
• Advice - Code to execute before, after, or around a pointcut
encounter.
Adaptive Garbage Collector
• Adopts a “best-fit” approach to garbage
collection by adjusting itself to better suit the
run-time environment.
• In their paper, Suman et al. showed how
adaptive garbage collection can benefit the
performance of Java applications.
• Adaptive garbage collection can be used for
other purposes besides performance.
Why Use AOP?
1. Aspects minimize the required changes to the
RVM source code though the use of inter-type
declarations and the aspectual introduction.
2. Aspects can crosscut the RVM hierarchy to gather
related VM statistics.
3. Aspects allow for non-intrusive “plugging” and
“unplugging” of VM components to update
functionality.
4. Aspects modularize the adaptive garbage collector
behavior so future upgrades require minimal effort.
Jikes Research Virtual Machine
HEAP
Statistics
User Objects
Compiled
Methods
Thread Stack
Java Memory Toolkit
Class / Methods
Dictionaries
Compilers
Baseline
Runtime
OS (Linux / IA32)
Optimizing
Magic
Java Virtual Memory Toolkit
MM_Interface
• From version 2.2.0+ of the
Jikes RVM, the garbage
collector is contained
within the Java Memory
Tookit
VM System
VM_Interface
• The core VM is isolated
from any memory
management
responsibilities and allows
different garbage
collectors to be compared
on a 1:1 basis.
Java Memory
Toolkit
Jikes Research Virtual Machine
Java Virtual Memory Toolkit
VM_Processor
VM / MM
Interfaces
Plan
StopTheWorldGC
BasePlan
• The garbage collector in the
JMTk is composed from
multiple highly reusable
classes.
• All garbage collectors are of
the Stop the World variety.
• The unique characteristics of a
garbage collector is derived
from its “Plan” and associated
policies classes.
Aspectual Framework
VM / MM
Interfaces
Plan
StopTheWorldGC
BasePlan
Aspectual Refactoring
VM_Processor
Aspectual Introduction
Semi-Space
Mark-Sweep
Generational
Mark-Sweep
Copy
AOP Adaptive Garbage Collection Plan
1. Extract all used garbage collector methods and re-target them with aspects.
2. Introduce new garbage collection schemes into the singular JMTk garbage
collection plan with aspects.
3. Resolve all memory map conflicts between co-existing garbage collectors.
4. Create a heuristic for garbage collector selection.
Aspectual Framework
Garbage
Collector
Roles
Adaptive Garbage Collector Components
Free
List
Mono
tone
Tread
mill
alloc
Free List
alloc
Monotone
alloc
Treadmill
alloc
poll
Free List
poll
Monotone
poll
Treadmill
poll
collect
Free List
collect
Monotone
collect
Treadmill
collect
Component Methods for each Role
RVM Environment
Garbage Collector Functionality
(alloc + poll + collect + etc...)
Functionality
Aspects
(Garbage
Collector
Behavior)
Jikes RVM Virtual Memory Map
Base Plan
Space Name
Start Address
Size
BOOT
0x43000000
256 MB
IMMORTAL
0x53000000
32 MB
META_DATA
0x55000000
64 MB
PLAN
0x59000000
Variable
Semi-Space Plan
Mark-Sweep Plan
Space Name
Start Address
Size
Space Name
Start Address
Size
LOS
0x59000000
214 MB
LOS
0x59000000
494 MB
LOW_SS
0x66600000
716 MB
MS
0x77E00000
1153 MB
HIGH_SS
0x93200000
716 MB
HEAP_END
0xBFF00000
HEAP_END
0xBFE00000
Space Name
Start Address
Size
Space Name
Start Address
Size
LOS
0x59000000
149 MB
LOS
0x59000000
149 MB
MATURE_LO
0x62500000
499 MB
MATURE MS
0x62500000
998 MB
MATURE_HI
0x81800000
499 MB
NURSERY
0xA0B00000
499 MB
NURSERY
0xA0B00000
499 MB
HEAP_END
0xBFE00000
HEAP_END
0xBFE00000
Generational Copy Plan
Generational Mark-Sweep Plan
Universal Virtual Memory Map
• The universal virtual
memory map helps
resolve resource conflicts
between the JMTk
garbage collectors.
• Semi-Space
• Generational Copy
Space Name
Start Address
Size
BOOT
0x43000000
256 MB
IMMORTAL
0x53000000
32 MB
META_DATA
0x55000000
64 MB
LOS
0x59000000
329 MB
LOW_SS
0x6D900000
329 MB
HIGH_SS
0x82200000
329 MB
MS
0x96B00000
329 MB
NURSERY
0xAB400000
329 MB
HEAP_END
0xBFD00000
Adaptive Plan
Limitations/Overhead of AspectJ
• AOP has an inherent overhead associated
with pointcut matching and advice execution.
• In the Jikes RVM, “writeBarriers” are
needlessly called on non-generational
garbage collectors
• Final Variables not targetable.
• Protected Access Types are not supported
• Non Intuitive Pointcuts for abstract methods.
SPEC JVM 98 Benchmarks
• Compress
– Uses a modified Lempel-Ziv method (LZW) to compress data.
• Jess
– Java Expert Shell System that continuously applies a set of if-then
statements, called rules, to a set of data, called the fact list.
• Db
– Performs multiple database functions on a memory resident
database.
• Javac
– Java compiler from the JDK 1.0.2.
SPEC JVM 98 Benchmarks
• Mpegaudio
– Decompresses audio files that conform to the ISO MPEG
Layer-3 audio specification.
• Mtrt
– A raytracer that works on a scene depicting a dinosaur,
where two threads each renders the scene in the input
file time-test model .
• Jack
– A Java parser generator that is based on the Purdue
Compiler Construction Tool Set (PCCTS).
Computer/Experiment Setup
• A computer with the following characteristics
was used to produce the experimental
results.
– 2.0 Ghz Intel Xeon Processor
– 1 GB DDR 266 system memory
– RedHat 9.0 Linux OS (standard installation)
• All JVM98 benchmarks were executed 5
times on a 100% sized dataset for each heap
size. The fastest and slowest times are
discarded and the remaining 3 are averaged.
Jikes RVM Setup
• Fast
– Assertion checking in the RVM is turned o.
– All necessary RVM classes are included in the
boot image.
• Adaptive
– The adaptive optimizing compiler selects "hotspots" during a programs execution via a
statistical sampling model. As such, every run of
the Jikes RVM with the adaptive compiler will
produce slightly differing results.
JVM98 Benchmark Min Heap Sizes
Benchmark / GC
_201_compress
_202_jess
_209_db
_213_javac
_222_mpegaudio
_227_mtrt
_228_jack
SS
MS
GMS
GC
16 MB
13 MB
26 MB
27 MB
10 MB
23 MB
11 MB
18 MB
17 MB
20 MB
28 MB
12 MB
24 MB
17 MB
15 MB
11 MB
17 MB
20 MB
9 MB
16 MB
10 MB
18 MB
16 MB
29 MB
31 MB
14 MB
30 MB
16 MB
• The Generational Mark Sweep collector has the
lowest memory heap requirements of all evaluated
garbage collectors
JVM98 Standardized Heap Sizes
Benchmark
_201_compress
_202_jess
_209_db
_213_javac
_222_mpegaudio
_227_mtrt
_228_jack
Minimum Heap Size
18 MB
17 MB
29 MB
31 MB
14 MB
30 MB
17 MB
• In order to ensure a fair comparison between all
garbage collectors, the minimum heap size was
standardized to be the largest of the minimum
values for the four garbage collectors.
SPEC JVM98 Jess Results
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
50
Total Execution Time (Seconds)
45
40
35
30
25
20
15
10
5
0
17 MB
34 MB
51 MB
68 MB
Heap Size
85 MB
102 MB
0
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
Number of Garbage Collections
Jess Garbage Collection Count
Full Heap
17 MB
34 MB
Nursery
51 MB
68 MB
Heap Size
Forced
400
350
300
250
200
150
100
50
85 MB
102 MB
Jess Results
SPEC JVM98 Db Results
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
35
Total Execution Time (Seconds)
30
25
20
15
10
5
0
29 MB
58 MB
87 MB
116 MB
Heap Size
145 MB
174 MB
0
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
Number of Garbage Collections
Db Garbage Collection Count
Full Heap
29 MB
58 MB
Nursery
87 MB
116 MB
Heap Size
Forced
120
100
80
60
40
20
145 MB
174 MB
Db Garbage Collection Count
SPEC JVM98 Javac Results
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
40
Total Execution Time (Seconds)
35
30
25
20
15
10
5
0
31 MB
62 MB
93 MB
124 MB
Heap Size
155 MB
186 MB
0
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
FASS
FA-SS
FAMS
FA-MS
FAGMS
FA-GMS
FAGC
FA-GC
Number of Garbage Collections
Javac Garbage Collection Count
Full Heap
31 MB
62 MB
Nursery
93 MB
124 MB
Heap Size
Forced
200
180
160
140
120
100
80
60
40
20
155 MB
186 MB
Javac Results
Summary
• Described how to increase the performance
of Java applications with the use of AOP.
• Defined and created an AOP framework to
facilitate an adaptive garbage collector and
implemented it in the Jikes RVM.
• Discovered that our AOP framework
introduces a slight performance overhead but
can increase the JVM98 benchmark
performance on the Jikes RVM significantly.
Future Work
• Our AOP framework does not currently support
“on-the-fly” garbage collector switching. However,
the framework can be upgraded to do so.
Communication Protocol
Library VM-D
Aspects
Library VM-C
Virtual
Machine
Application B
Library VM-E
Application C
Library VM-F
Library B-A
Aspects
Library VM-B
Library A-A
Aspects
Application A
Aspects
Library VM-A
Library C-A
Library A-B
Library B-B
Library C-B