Incremental GC
for Ruby interpreter
Koichi Sasada
ko1@heroku.net

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

1

2014
Very important year for me
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

2

th
10

Anniversary
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

3

th
10

Anniversary
YARV development (2004/01-)
First presentation at RubyConf 2004
K.Sasada: Incremental GC for Ruby interpreter, RubyConf20144

Garbage Collection
Improvements
Good throughput and short pause time
Ruby 2.2 will be released soon.
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

5

RGenGC: Micro-benchmark
3000

Time (ms)

2500
2000

704.843669

x2.5 faster

1500
1000

1699.805974

500

867.740319

087.230735
RGenGCnototal marktotal sweep

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

6

RGenGC: Pause time

K.Sasada: Incremental GC for Ruby interpreter, RubyConf20147

Today’s topic• Use incremental GC algorithm for major GC to reduce
long pause time
• Ruby 2.2 will have it!!

Goal

BeforeRuby 2.1
Ruby 2.1 RGenGC
Throughput
Pause time

Low
Long

High
Long

Incremental
GC
Low
Short

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

Ruby 2.2
Gen+IncGC

High
Short
8

Achievements: RGenGC+RincGC

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

9

Who am I?
Koichi Sasada as a Programmer• CRuby committer since
2007/01• Original YARV developer
since 2004/01• From Japan

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

10

Who am I?
Koichi Sasada as a Employee

K.Sasada: Incremental GC for Ruby interpreter, RubyConf201411

Who am I?
Koichi Sasada as a Employee• A member of Matz team
• Full-time CRuby developer• Working in Japan• Mission of our team is to improve “QUALITY” of
CRuby interpreter

K.Sasada: Incremental GC for Ruby interpreter, RubyConf201412

Upcoming Ruby 2.2
What’s next?

http://www.flickr.com/photos/adafruit/8483990604

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

13

Ruby 2.2
Syntax• No notable changes (maybe)• Symbol key of Hash literal can be quoted• {“foo-bar”: baz}#=> {:”foo-bar” => baz}#=> not {“foo-bar” => baz} like JSON
TRAP: easy to misunderstandK.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

14

Ruby 2.2
Classes and Methods• Some methods are introduces• Kernel#itself• String#unicode_normalize• Etc.nprocessors•…

K.Sasada: Incremental GC for Ruby interpreter, RubyConf201415

Ruby 2.2
Internal changes• Remove obsolete C-APIs• Hide internal definitions of data type

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

16

Ruby 2.2
Improvements• Improve GC• Symbol GC• 4 ages generational GC• Incremental GC (today’s topic)• Improve the performance of keyword parameters• Use frozen string literals if possible

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

17

Ruby 2.2
Symbol GC
before = Symbol.all_symbols.size
1_000_000.times{|i| i.to_s.to_sym} # Make 1M symbols
after = Symbol.all_symbols.size; p [before, after]# Ruby 2.1#=> [2_378, 1_002_378] # not GCed # Ruby 2.2 (dev)#=> [2_456, 2_456] # GCed! 
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

18

Ruby 2.2
Fast keyword parameters# time of this programdef foo(k1: nil, k2: nil, k3: nil, k4: nil, k5: nil, k6: nil)
10_000_000.times{foo(k1: 1, k2: 2, k3: 3, k4: 4, k5: 5, k6: 6)}
20
15
10
5
0

17.170841

x15 faster!
1.15534
Execution time (sec)
Before opt.

After opt.

K.Sasada: Incremental GC for Ruby interpreter, RubyConf201419

http://www.flickr.com/photos/donkeyhotey/8422065722

Break

K.Sasada: Incremental GC for Ruby interpreter, RubyConf201420

Garbage collection
The automatic memory management

http://www.flickr.com/photos/circasassy/6817999189/

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

21

History of CRuby’s GC• 1993/12 Ruby 0.9: Conservative mark and sweep GC• Simple algorithm• Easy to implement C extensions• 2011/10 Ruby 1.9.3: Lazy sweep• To reduce pause time on sweep• 2013/02 Ruby 2.0: Bitmap marking• To make CoW friendly• 2013/12 Ruby 2.1: RGenGC• To improve throughput
K.Sasada: Incremental GC for Ruby interpreter, RubyConf201422

Since birth of Ruby
Simple Mark & Sweep
Root objects
traverse
freemarkedtraverse

traverse

markedtraverse

markedmarkedtraversefree

1. Mark reachable objects
from root objects
2. Sweep unmarked objects(collection and deallocation)

Collect unreachable
objects

markedfree
K.Sasada: Incremental GC for Ruby interpreter, RubyConf201423

Since Ruby 2.1
RGenGC• Weak generational hypothesis:“Most objects die young”

http://www.flickr.com/photos/ell-r-brown/5026593710→ Concentrate reclamation effort
only on the young objects
K.Sasada: Incremental GC for Ruby interpreter, RubyConf201424

Since Ruby 2.1
RGenGC• Separate young generations and old generations• Create objects as youngest generation• Promote to old generations after surviving GCs• Many minor GC and rare major GC• Usually, GC on only young space (minor GC)• GC on both spaces if no memory (major/full GC)→ Improve total throughput
K.Sasada: Incremental GC for Ruby interpreter, RubyConf201425

Since Ruby 2.1
RGenGC [Minor M&S GC]• Mark reachable objects from rootobjects.
traverse• Mark and promote to old
new/
free
new/
new
generationold
free
traverse
traverse• Stop traversing after old objects
collect→ Reduce mark overhead
new
new
old
old
traverse
traverse• Sweep not (marked or old) objects• Can’t collect Some unreachable
old/
new
new
old
old
free
objects
1st MinorGC

Root objects

Don’t collect old object
even if it is unreachable.
K.Sasada: Incremental GC for Ruby interpreter, RubyConf201426

Since Ruby 2.1
RGenGC [Minor M&S GC]• Mark reachable objects from rootobjects.
traverse• Mark and promote to old generation
new/
free
• Assumption: “Old objects only refer
new/
old
free
old objects”
ignoreignorecollect• Stop traversing after old objects
oldold→ Reduce mark overhead
ignoreignore• Sweep not (marked or old) objects
old/
old
old
• Can’t collect Some unreachable objects
free

2nd MinorGC

Root objects

Don’t collect old object
even if it is unreachable.
K.Sasada: Incremental GC for Ruby interpreter, RubyConf201427

Since Ruby 2.1
RGenGC [Remember set]
• Assumption: “Old objects only refer old
objects”• However old objects can refer young
objects by adding reference from old to
new objects→ Ignore traversal of old object→ Minor GC causes marking leak!!
• Because minor GC ignores referenced
objects by old objects

Root objects
traverse
new
traverse
oldignoreignore

old

old
old

ignorenew

Can’t mark new object!
→ Sweeping living object! (Critical BUG)28

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

Since Ruby 2.1
RGenGC [Remember set]
Rememberset (RSet)

Root objects

1. Detect creation of an[old->new] type reference
2. Add an [old object] into
Remember set (RSet) if
Rememberan old object refer new
objects

traverse
new
traverse
oldignoreignore

old

old
old

new
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

29

Since Ruby 2.1
RGenGC [Remember set]
Rememberset (RSet)

Root objects
traverse
new
traverse
oldignoreignore

old

old
old

traverse

collect
new/
new/
free
free

1. Mark reachable objects fromroot objects• Remembered objects arealso root objects
2. Sweep not (marked or old)
objects

traverse
new
K.Sasada: Incremental GC for Ruby interpreter, RubyConf201430

Since Ruby 2.1
RGenGC [Write barrier]• To detect [old→new] type references, we need to insert“Write-barrier” into interpreter for all “Write” operation

old

new

“Write barrier”[Old->New] type reference detected!
K.Sasada: Incremental GC for Ruby interpreter, RubyConf201431

Since Ruby 2.1
RGenGC: Challenge• Trade-off of Speed and Compatibility• Introducing “Write barriers” completely is very hard
• Can we achieve both speed-up w/ GenGC and keeping
compatibility?

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

32

Since Ruby 2.1
RGenGC: Key idea

Introduce
WB unprotected objects
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

33

Since Ruby 2.1
RGenGC: Key idea
• Separate objects into two types• WB protected objects• WB unprotected objects• Decide this type at creation time
• A class care about WB → WB protected object• A class don’t care about WB → WB unprotected object

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

34

Since Ruby 2.1
RGenGC: Key idea
• Normal objects can be changed
to WB unprotected objects• “WB unprotect operation”• C-exts which don’t care about
WB, objects will be WB
unprotected objects• Example

VM
CreateUnprotect

WB p.
obj

WB
unp.
obj

• ptr = RARRAY_PTR(ary)• In this case, we can’t insert WB
for ptr operation, so VM shade Now, WB unprotected object“ary”
can’t change into WB p. object
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

35

Since Ruby 2.1
RGenGC: Rules• Treat “WB unprotected objects” correctly• At Marking
1. Don’t promote WB unprotected objects to old objects
2. Remember WB unprotected objects pointed from old objects• At WB unprotect operation for old WB protected objects
1. Demote objects
2. Remember this unprotected objects

K.Sasada: Incremental GC for Ruby interpreter, RubyConf201436

Since Ruby 2.1
RGenGC: [Minor M&S GC w/WB unp. objects]
1st MinorGC

Root objects

Rememberset (RSet)traverse
remembernewoldcollect
new/
new/
free
free

traverse
newoldtraverse
new
old

old

traverse
WB
unp.

mark andremembertraverseoldnew• Mark reachable objects from rootobjects• Mark WB unprotected objects,
and *don’t promote* them toold gen objects• If WB unprotected objects
pointed from old objects,
then remember this WB
unprotected objects by RSet.
→ Mark WB unprotected
objects every minor GC!!

K.Sasada: Incremental GC for Ruby interpreter, RubyConf201437

Since Ruby 2.1
RGenGC: [Minor M&S GC w/WB unp. objects]
2nd MinorGC

Rememberset (RSet)

Root objects
traverse

oldcollect
new/
new/
free
free

ignoreoldignoreignoretraverse

WB
unp.

traverse

oldtraverse
old

new

old

• Mark reachable objects from rootobjects• Mark WB unprotected objects,
and *don’t promote* them toold gen objects• If WB unprotected objects
pointed from old objects,
then remember this WB
unprotected objects by RSet.
→ Mark WB unprotected
objects every minor GC!!

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

38

Since Ruby 2.1
RGenGC: [Unprotect operation]
Rememberset (RSet)
old

old

WB
old
unp.

new

• Anytime Object can give up to
keep write barriers→ [Unprotect operation]• Change old WB protected
objects to WB unprotected
objects• Example: RARRAY_PTR(ary)(1) Demote object (old → new)(2) Register it to Remember Set

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

39

RGenGC: Micro-benchmark
25

15
10
5
0

1
6
11
16
21
26
31
36
41
46
51
56
61
66
71
76
81
86
91
96
101
106
111
116
121
126
131
136

Time (ms)20n-th GC
mark time/nosweep time/nomark time/RGenGC

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

sweep time/RGenGC
40

RGenGC: Micro-benchmark
3000

Time (ms)

2500

2000

704.843669

1500
1000

1699.805974

500

867.740319

087.230735
RGenGCnototal marktotal sweep

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

41

RGenGC: Rdoc application
200
180
160
120
100
80
60
40
20
0

1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125
129
133
137
141
145

Time (ms)140

nth-GC
mark time/nosweep time/nomark time/RGenGC

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

sweep time/RGenGC
42

RGenGC: Rdoc application
9000
8000
7000

Time (ms)

6000

5000
4000

3000
2000
1000
0
no
RGenGC

total mark8210.724461
1049.27184

total sweep
3524.425873
3579.584833
noRGenGC

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

43

RGenGC: Rdoc application
120000Time (ms)100000
80000
60000
40000
20000
0
total sweep
total markothers

no3524.425873
8210.724461
100907.4225
othersRGenGC3579.584833
1049.27184
100640.8472
total marktotal sweep

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

44

RGenGC: Rdoc application
3,000,000

2,500,000
2,000,000
1,500,000
1,000,000
500,000

1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125
129
133
137
141
145

0
available slots

live slots

old objects

unprotected objects

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

remembered unprotected objects
45

RGenGC: Rdoc application
70,00060,00050,00040,00030,00020,00010,000

1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125
129
133
137
141
145

0
unprotected objects

remembered unprotected objects

K.Sasada: Incremental GC for Ruby interpreter, RubyConf201446

Since Ruby 2.1
RGenGC timing chart
2.0.0 GC (M&S w/lazy sweep)
Sweep

Mark

Ruby

Sweep

Sweep

Sweep

Sweep

Stop the (Ruby) World

w/RGenGC (Minor GC)
RubyMark Sweep

Sweep

Sweep

Sweep

Sweep

Stop the(Ruby)
World

w/RGenGC (Major GC)
Ruby

Mark

Sweep

Sweep

Sweep

Stop the (Ruby)K.Sasada:World Incremental GC for Ruby interpreter, RubyConf2014

Sweep

Sweep

47

Issue of RGenGC: Long pause time
 RGenGC achieves high throughput
 Minor GC stops only short pause time
 Major GC still stops long pause time

→ Introducing Incremental GC for major GC
Generational GC Incremental GC Gen+Inc GC
Throughput
High
Low
High
Pause time
Long
Short
Short
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

48

RincGC: Restricted Incremental
GC algorithms
RincGC algorithm is implemented for Ruby 2.2.

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

49

Incremental GC
Well-known GC algorithm to reduce pause time
• Do GC steps incrementally• Interleaving with Ruby’s execution (mutator) and GC process.
• Lazy sweep is part of an incremental GC
STW GC

Sweep

Mark

Ruby

Sweep

Sweep

Sweep

Sweep

Sweep

Sweep

Sweep

Stop the (Ruby) WorldInc GC

Ruby

Mark

Mark

Mark

Mark

Mark

Short pause time No total time change

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

50

Terminology: Tri-color GC• Define three colors for objects• White objects is not traversed objects• Grey objects are marking objects• Black objects are marked objects

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

51

Incremental GC
Root objects
traverse

traverse

traverse

traverse

traverse

Collect white
objects

1. Color all objects “white”
2. Grey root objects
3. Choose a grey object and grey
all reachable white objects,
and black the chosen object(incremental marking)
4. Finish marking when no grey
objects
5. Sweep white objects asunmarked objects

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

52

Incremental GC requires WBs
Root objects
traverse

traverse

Mutator can add reference from a Blackobject to a white object!!
→ Mark miss!
No more traversal from black objects

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

53

Incremental GC requires WBs
Root objects
traverse

traverse

Use write barrier to detect an additionof references from black objects towhite objects, and grey black objects

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

54

RincGC: Restricted Incremental GC using WBunprotected objects• Use WB unprotected objects like RGenGC• Introducing a new rule: “Scan all black WB
unprotected objects at the end of incremental GC at
once”• WB unprotected objects can point white objects• Scan from all (“Black” and “WB unprotected objects”) at once
(stop the world marking)

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

55

RincGC

Restricted Incremental GC
using WB-unprotected objects

Root objects

WB unp.

WB unp.

Root

1. Color all objects “white”
2. Grey root objects
3. Choose a grey object and grey
reachable white objects, andblack the chosen object(incremental marking)
4. Finish marking when no grey
objects
5. Scan all black WB
unprotected objects at once
6. Sweep white objects asunmarked objects

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

56

RincGC: Discussion• Long pause time than usual incremental GC step• This technique can introduce long pause time, relative tothe number of WB unprotected objects at last. This is why
this algorithm is named “Restricted”• Similar/shorter pause time than “Minor GC” of
RGenGC.

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

57

Implementation

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

58

Ruby’s implementation
State chart
garbage_collect()
if (no pages)

Ruby program(mutators)

Direct transition
To mutator
State: marking

State: sweeping

marks_start()

sweep_start()

marks_step()sweep_step()marks_finish()sweep_finish()newobj()if (incremental_marking)marks_continue()
if (sweep_pages)

sweep_continue()

State: none

59Ruby’s implementation
WB protected/unprotected• Make popular class instances WB protected• String, Array, Hash, and so on• Implement “unprotect operation” for Array and so on• Remain WB unprotected objects• Difficult to insert WBs: a part of Module, Proc (local
variables) and so on.
• Minor features

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

60

Ruby’s implementation
Data structure• Introduce 2 bits age information to represent young and old objects• Age 0, 1, 2 is young object• Age 3 is old object• Surviving 1 GC increase one age• Add 3 bits information for each objects (we already have mark bit)
• WB unprotected bit• Long lived bit (old objects or remembered WB unprotected objects)• Remembered old object bit / Marking (Grey) bit• They can share 1 bit field because the former is used only at minor GC and thelatter is used only at major GC (incremental GC)
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

61

Ruby’s implementation
Bitmap technique• Each bits are managed by bitmap technique• Easy to mange remember set• Fast traversing• Easy to get a set• Remember set: (Remembered old object bitmap) | (Long lived
bitmap & WB unp. Bitmap)• Living unprotected objects: (mark bitmap & WB unprotected
bitmap)K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

62

RincGC: Evaluation• Measure pause times for<https://github.com/tenderlove/ko1-test-app> by Aaron
Patterson

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

63

Evaluation

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

64

Evaluation
0.018
0.016
0.014
0.012
0.01
0.008
0.006
0.004
0.002
0

Long major marking time of RGenGC
Incremental Major GC of RincGC
Lazy sweep pauses only short time
Same pause time for Minor marking time
1
69
137
205
273
341
409
477
545
613
681
749
817
885
953
1021
1089
1157
1225
1293
1361
1429
1497
1565
1633
1701
1769
1837
1905
1973
2041
2109
2177
2245
2313
2381
2449

GC pause time (sec)

2,500 GC's pause time since one major GC

pause time (rgengc)

pause time (rincgc)

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

65

Evaluation
maximum pause time
0.02
0.015

0.01
0.005
0
max

rgengc0.015923438
K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

rincgc0.004662491
66

NOTE: Incremental GC is not silver bullet• Incremental GC does not guarantee improving yourapplication’s response time
• Incremental GC does not reduce total GC time, sothat a big task includes several major GC doesn’t
improve its response time.
• Check GC counts with GC.stat(:major_gc_count)and GC.stat(:minor_gc_count) for each request.
K.Sasada: Incremental GC for Ruby interpreter, RubyConf201467

Summary• Introducing incremental GC algorithm into major GC
to reduce long pause time
• Ruby 2.2 will have it!!

Goal

BeforeRuby 2.1
Ruby 2.1 RGenGC
Throughput
Pause time

Low
Long

High
Long

Incremental
GC
Low
Short

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

Ruby 2.2
Gen+IncGC

High
Small
68

Thank you for your attention
Koichi Sasada<ko1@heroku.com>

K.Sasada: Incremental GC for Ruby interpreter, RubyConf2014

69