Starvation-Free Heap Size for
Replication-Based Incremental
Compacting Garbage Collection
Tomoharu Ugawa (The University of Electro-Communications)
Hideya Iwasaki (The University of Electro-Communications)Taiichi Yuasa (Kyoto University)

Starvation-Free Heap Size for
Replication-Based Incremental
Compacting Garbage Collection
Tomoharu Ugawa (The University of Electro-Communications)
Hideya Iwasaki (The University of Electro-Communications)Taiichi Yuasa (Kyoto University)

Motivation• Real-time GC is indispensable for real-time
applications• Real-time GC requires much memory if theapplication allocates objects of various sizes• Real-time mark-sweep GC→ suffer from fragmentation• Real-time semi-space copying GC→ twice as much memory as live objects• Real-time mark-compact GC→ large overhead (execution time)Partial Compaction
We developed a “partial compaction” by evacuation• To be combined with mark-sweep GC• Evacuate only a part of the heap
• to create a large contiguous free area
• to eliminate fragmentation

Partial Compaction
after mark-sweep GC,
1. Choose an area as the evacuation area (EA)
2. Relocate objects in the EA
3. Reclaim the EA as a large contiguous free areaevacuation area

heapobjectAB

Partial Compaction
after mark-sweep GC,
1. Choose an area as the evacuation area (EA)
2. Relocate objects in the EA
3. Reclaim the EA as a large contiguous free area

AʼAB

Bʼ

Partial Compaction
after mark-sweep GC,
1. Choose an area as the evacuation area (EA)
2. Relocate objects in the EA
3. Reclaim the EA as a large contiguous free area

AB

Required Memory
EA is only a part of the heap
→ space for copies can besmaller than semi-space copying GC
Smaller EA• smaller space for copies• less effective for eliminating fragmentation

AʼABBʼ

Problems• How large the EA should be?
• Where in the heap should the GC choose the EA?
• How large the heap should be to avoid starvation?
starvation:
failure of allocation due to lack of memory orlack of contiguous memory

Aʼ

A

BBʼ

Outline• Related work
• Model of application, allocator, and GC• Basic Idea
• Strategy• Analysis• Practical setting• Future work and summaryRelated Work
Real-time mark-sweep GC• incremental update [Steele ’75]• on-the-fly [Dijkstra et al. ’78]
• snapshot-at-the-beginning [Yuasa ’90]
cannot bound heap size in cases
where objects of various sizes are allocatedRelated Work
Real-time semi-space copying GC• with read barrier [Baker ’78]
• replication-based [Nettles and O’Toole ’93]
• in multi-processor settings [Cheng et al. ’01]
require more than twice as much memory as theamount of live objects

Related Work
Partial compaction by evacuation (1/3)• Metronome [Bacon ’03]
• Immix [Blackburn and McKinley ’08]
choose several discontiguous areas as the EA→ cannot allocate large memory chunkRelated Work
Partial compaction by evacuation (2/3)• Sapphire [Hudson and Moss ’01]
• Open VM [Kalibera ’09]
do not have any idea about where to choose the EA?

Related Work
Partial compaction by evacuation (3/3)• Replication-based compaction [Ugawa et al. ’10]
chooses the EA that is effective for defragmentation
Cannot bound the heap size?

Outline• Related work
• Model of application, allocator, and GC• Basic Idea
• Strategy• Analysis• Practical setting• Future work and summary

Application Model• Application creates objects of different sizes• All objects can be relocated• No ambiguous pointers• No pinned objects• Max(amount of reachable (i.e. live) objects) ≤ R

Allocator Model• A single “unstructured” heap
• Not divided into pages or segments(page boundaries do not have significant meaning)• Objects can be allocated anywhere in the heap

• Every object occupies a contiguous memory area
regardless of its sizeCollector Model• Compaction after mark-sweep GC
1. Mark phase
2. Sweep phase
3. Compaction phase• Incremental GC• Perform GC little by little each time an object isallocated• Amount of allocation during a single GC cycle ≤ a

Before Compaction• Mark and sweep phases collect garbage• Independent of barriers for incremental marking

Compaction Steps
Step 1: Choose the EA (location and size)Compaction Steps
Step 1: Choose the EA (location and size)
Step 2: Relocate objects in the EA• Independent of barrier for relocating incrementally

Compaction Steps
Step 1: Choose the EA (location and size)
Step 2: Relocate objects in the EA• Independent of barrier for relocating incrementally
Step 3: Reclaim the EA as a large contiguous free area

Goal
• Give a strategy for choosing the EA• Estimate the required heap size to avoid starvation

Outline• Related work
• Model of our GC• Basic Idea
• Strategy• Analysis• Practical setting• Future work and summary

Reserved Free Area
• Reserve a contiguous free area for the next
GC cycle• Allocation in the area is prohibited until thenext GC cycle is triggered

Areservedarea

Reserved Free Area
• Reserve a contiguous free area for the nextGC cycle• Allocation in the area is prohibited until thenext GC cycle is triggeredAB

reservedarea

Trigger GC cycle• When an allocation of an object, x, is failed• Allocate the object x in the reserved free area
• Trigger the GC cycle

XAB

reservedarea

Trigger GC cycle• When an allocation of an object, x, is failed• Allocate the object x in the reserved free area
• Trigger the GC cycle

ABX

GC cycle• The reserved free area behaves as the to-space• copying objects in the evacuation area
• Aʼ, Bʼ• allocation by the application• X, YEAABX Y Aʼ Bʼ

Next Reserved Area
• Use the EA as the next reserved free area
• Reserved free area has the same size as theprevious EA

ABX Y Aʼ Bʼ

X Y Aʼ BʼSize of Evacuation Area
• Always choose the EA of a fixed size
• sizeof(from space) == sizeof(to space)AB

X Y Aʼ Bʼ

Overflow
If we chose the EA full of live objects,
the reserved free area would be exhausted• Because application also allocates objects
in the area

YXABCABC

Live Ratio
Define live ratio :fraction of the area occupied by live objects
Limit the live ratio of the EA by l

• We can guarantee that there is an area whose

live ratio is less than l by adjusting the heap size
(because we know the amount of live objects ≤ R)
live ratio ≤ l
Alive ratio ≤ l

BX Y Aʼ Bʼ

Estimation
We will estimate• H –– heap size
• E –– size of the EA• l –– upper bound of the live ratio of the heap
We are given• R –– maximum amount of live objects
bound of the amount of objects• a –– upper
allocated during a single GC cycle

Size of Reserved Free Area
Memory consumption during GC ≤ a + lE

• a: Allocation by the application• lE: Objects in the EA(to be copied to the reserved area)

Size of the reserved free area: FF ≥ a + lE

live ratio ≤ laE A≥ B
1−lE
E=F(1)lEa(2)X Y Aʼ Bʼ

F(3)Size of EA
Size of the EA, E, shouldF ≤ bea +aslElarge as
the size of the reserved free area, F•(1)a(2)
Because the EAEis≤used as the next reserved
1−lfree area

E=F(3)

By F ≥ a + lE ,F ≥ (1)a + lE(1)aE≥
1−laE ≥(2)
1−l(2)

E=F

E=(3)F(3)E=F(3)

HeapRSize
Required heap size H is(4)

lR
a
H= +l
1−l(5)

amount of live objects ≤ R
live ratio ≤ lR/l

FH

Rl

Adjusting Live Ratio
too low:

appropriate:

too high:

Ra
H= +l
1−l

E≥

1−l

Rl
Appropriate LiveE Ratio
=F54R
a
H= +l
1−l(5)Rl=√√
R+ a(6)√321000.2(3)R Ra (4)Hl = +l
1−lNormalized heap size
when a/R = 1%

H/R(2)

0.40.6

live ratio

0.81RRl = √l √R +l aResult
RR aa RRl

(4)(6) (4)aa +HH== +R(5)H=+(7)
H l=l 1 +(5)−−l l l11−ll1−lWhen the live ratio is appropriate,√√ √ √√
R
H = (R + Ra)R+ (a+ Ra)(8)R√l = l√= √ l√= √√ (6) (6)R +R +a aR + a√
H = R + 2 Ra +Ra(9)aR √a
H = H+= +(7)E = F = al1 + 1 Ra−l l 1 − l (10)

(4)
(5)

(6)
(7)

√√
√√
H+= (R+ + (aRa)(a + (8)Ra)
H = (RRa)+ + Ra)

(8)

√
√
H = RH+ =2 RRa++
2 aRa + a (9)

(9)

1H11

RRl = √l √R +l aResultRR aa RRl(4)(6) (4)

(13)
(4)

√√
aaF =
HH== +R(5)
E=F=
2a + 2(5)2Ra
H=+E=2a+22Ra(14)+(7)
H l=l 1 +(5)−−l l l
11−ll
1−l
When the live ratio is appropriate,√√ √ √√√√√√R + (8)Ra)H = (R + Ra)R+ (a+ R(RRa)
R(a+Ra)R√ √lEl = l√= √ l√==(6)
√ =(6)√lE(15)√ (6)√√R +R +a aR + R a+ a R + a√√√=(9)Ra = (16)H = R + 2 Ra +RaRaaR √a(7)H = H+= +(7)E = F = al1 + 1 Ra−l l 1 − l (10)√√√√H+= (R+ + (aRa)(a + (8)Ra) (8)H = (RRa)+ + Ra)√√
H = RH+ =2 RRa(9)++2 aRa
2 + a1H112(9)Outline• Related work
• Model of our GC• Basic Idea
• Strategy• Analysis• Practical setting• Future work and summary

Practical Settings
We looked over two cases where we cannot choose
the candidate of the EA
case 1: candidate overlaps with the reserved area

case 2: candidate contains a part of an object√√ √√= FRa= a + RaRE = F =Ea+(10)E=F=a+Ra(10)√√l=(11)Revised
Estimation
R + 2a√√√√RR√ (11)l√=√√Rl=
Hl =2Ra(12)√+R2 +√+ 2a(11)=R
2a+R3aR + 2a(13)√√HR ++23a 2Ra +(12)3aH = R +√2 =2RaH = R + 2 2Ra +(12)√3a(13)
E = F = 2a + 2 2Ra(14)(13)√√
2a + 2 2Ra
E = F =E
2a=+F
2 =2Ra(14)√E = F = 2a + 2 2Ra(14)

H(10)

(11)
(12)
(13)
(14)

Required Heap Size
3normalized
heap size
H/R2.5
21.5

normalizedsize of EA
E/R
a/R = 7.5%

1
0.5
00.02

0.04

0.06

0.08

0.1

a/R; upper bound of allocation during a GC cycleFuture Work• Implementation

Summary• Gave a strategy to choose the EA• Estimated the required heap size to avoid starvation• Applicable to any partial compaction by evacuation• Independent of barrier for incremental marking• Independent of barrier for incremental relocation

Thank you

E-mail to: ugawa@cs.uec.ac.jp