Rubyにおけるライトバリアのないオブジェクトを考慮した
世代別インクリメンタルGCの実装
笹田 耕一, 松本 行弘(Heroku, Inc.)1

この発表を3行でまとめると• Ruby処理系にはライトバリア（WB）が入っていないし、実装大変• 世代別GC、インクリメンタルGCはWBが無いと実装できない• 完璧にWBが入って無くても出来るアルゴリズムを考えました

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)2

Programming language Ruby
• Object oriented programming language Ruby
• Ruby is widely used in world-wide.

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)3

Rubyが使われている例• アンダースタンディング コンピュ
テーション（オライリー）• Tom Stuart著、笹田 耕一監訳、
笹井 崇司訳• Ruby で意味論、オートマトン、
チューリング機械、ラムダ計算、
その他の万能機械、停止性問
題、型推論を解説

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処
理学会 第101回プログラミング研究発表会 (2014/11)

4Programming language Ruby
• Object oriented programming language Ruby
• Ruby is widely used in world-wide.
• Web application development, such as Twitter (early days), github,and so on.

• Performance of Ruby interpreter is a matter.

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

5

One of performance bottleneck
Ruby’s GC• Conservative mark and sweep GC (from 1993)• Issues:
1. Low throughput
2. Long pause time

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

6

Traditional solution: well-known GC algorithms• Generational GC (GenGC) to improve throughput by
separating heaps per generations.
• Incremental GC (IncGC) to reduce pause time by doing
GC steps incremental• They needs “Write Barriers” (WB) to work correctly

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

7

Challenge• Inserting perfect WBs is very difficult• Unfortunately, Ruby interpreter does not support WBs• High implementation cost for perfect WBs• API change becomes compatibility issue for existing
extension libraries• Allowing GenGC and IncGC with “Incomplete” WB insertions→ RGenGC: Restricted Generational GC algorithm→ RincGC: Restricted Incremental GC algorithm

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

8

RGenGC: Restricted Generational
GC algorithms
RGenGC algorithm is implemented at Ruby 2.1
which is already shipped.

9

Simple Mark & Sweep
Root objects
traverse
freemarkedtraverse

traverse

markedtraverse

markedmarkedtraversefree

1. Mark reachable
objects from rootobjects
2. Sweep unmarked
objects (collection
and de-allocation)

Collect unreachable
objects

markedfree
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

10

Generational GC (GenGC)• Weak generational hypothesis:“Most objects die young”

http://www.flickr.com/photos/ell-r-brown/5026593710→ Concentrate reclamation effort
only on the young objects
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

11

Generational hypothesis
Object lifetime in RDoc
(How many GCs surviving?)

Percentage of dead object#

100
90

95% of objects die at the first GC

80
70
60
50
40
30
20
10
0
0

3

6

9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 102

Lifetime (Survibing GC count)
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

12

Generational hypothesis
Percentage of dead object#

Object lifetime in RDoc
(How many GCs survive?)
100
90

Some type of objects (like Class)has long lifetime

80
70
60
50
40
30
20
10
0
0

3

6

9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 102

Lifetime (Survibing GC count)
T_OBJECT

T_CLASS

T_MODULE

T_STRING

T_REGEXP

T_ARRAY

T_HASH

T_STRUCT

T_BIGNUM

T_FILE

T_DATA

T_MATCH

T_NODE

T_ICLASS

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

13

Generational GC (GenGC)• Separate young generations and old generations• Create objects as youngest generation• Promote to old generations after surviving GCs• Usually, GC on young space (minor GC)• GC on both spaces if no memory (major/full GC)• We can choose different GC algorithms on Minor GC and Major GC• In this presentation, we choose M&S for both GCs (because we choose M&S)

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

14

[Minor M&S GC]
1st MinorGC• Mark reachable objects fromroot objects.

Root objects
traverse
new/
free

new
old
traverse

traversenew/freecollectnewoldtraverse
new
old

new
old
traverse
newold• Mark and promote to oldgeneration• Stop traversing after old
objects→ Reduce mark overhead• Sweep not (marked or old)
objects• Can’t collect Some
unreachable objects
Don’t collect old object
•
old/
free

even if it is unreachable.
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装,
情報処理学会 第101回プログラミング研究発表会(2014/11)

15

RGenGC: Background: GenGC[Minor M&S GC]
2nd MinorGC• Mark reachable objects fromroot objects.

Root objects
traverse
new/
free

old
ignoreignorenew/freecollectoldignoreold

oldignoreold• Mark and promote to oldgeneration• Stop traversing after old
objects→ Reduce mark overhead• Sweep not (marked or old)
objects• Can’t collect Some
unreachable objects
Don’t collect old object
•
old/
free

even if it is unreachable.
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装,
情報処理学会 第101回プログラミング研究発表会(2014/11)

16

RGenGC: Background: GenGC[Major M&S GC]• Normal M&S• Mark reachable objects fromroot objects

Root objects
traverse

new/
free

new
traverse

traverse

new/
free

• Mark and promote to old gen• Sweep unmarked objects

collectoldtraverseoldnewtraverseold• Sweep all unreachable(unused) objects

old/
free
collect

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

17

RGenGC: Background: GenGC
Problem: mark missRoot objects
traverse
new
traverse• Because minor GC ignoresreferenced objects by old
objectsoldignore• Old objects refer young objects→ Ignore traversal of old object→ Minor GC causes
marking leak!!

ignoreCan’t mark new object!
old

old
old

ignore→ Sweeping living object!
(Critical BUG)

new

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

18

RGenGC: Background: GenGC
Introduce Remember set (Rset)
Root objects
traverse
new
traverse
oldignoreignore

old

old
old

Rememberset (RSet)

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

new笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

19

RGenGC: Background: GenGC[Minor M&S GC] w/ RSet
Rememberset (RSet)

Root objects

1. Mark reachable
objects from rootobjects

traverse
new
traverse
oldignoreignore

old

old
old

traverse

collect
new/
new/
free
free

• Remembered objects arealso root objects

2. Sweep not (marked orold) objects
traversenew

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

20

Write barriers in Ruby
• Write barrier (WB) example in Ruby world• (Ruby) old_ary[0] = new0 # [old_ary → new0]• (Ruby) old_obj.foo = new1 # [old_obj → new1]
old_ary0

old_obj
new0

1

foo

2

bar

new1

3
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)21

Difficulty of inserting write barriers• To introduce generational garbage collector, WBs are necessary todetect [old→new] type reference• “Write-barrier miss” causes terrible failure
1.
2.
3.
4.

WB miss
Remember-set registration miss(minor GC) marking-missCollect live object → Terrible GC BUG!!

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)22

Problem: Inserting WBs into C-extensions (C-exts)• All of C-extensions need perfect Write-barriers• C-exts manipulate objects with Ruby’s C API• C-level WBs are needed• Problem: How to insert WBs into C-exts?
• There are many WB required programs in C-exts• Example (C): RARRAY_PTR(old0)[0] = new1
• Ruby C-API doesn’t require WB before• CRuby interpreter itself also uses C-APIs• How to deal with?
• We can rewrite all of source code of CRuby interpreter to add WB, with huge
debugging effort!!
• We can’t rewrite all of C-exts which are written by 3rd party
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)23

Problem: Inserting WBs into C-extensions (C-exts)
Two options
Performance

Compatibility

Ruby 2.0
and earlier
conservative

1

Give up GenGC

Poor

Good
(No problem)

2

GenGC with rewriting all of C exts

Good

Most of C-exts
doesn’t work

choiceTrade-off of Speed and Compatibility
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)24

rdInvent 3 option

1

Give up GenGCGenGC with re2
writing all of C codes3

Use new RGenGC

Performance

Compatibility

Poor

Good
(No problem)

Good

Most of C-exts
doesn’t work

Good

Most of C-exts
works!!

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)25

RGenGC:
Key idea• Introduce WB unprotected objects

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)26

RGenGC:
Key idea• Separate objects into two types• WB protected objects• WB unprotected objects• We are not sure that a WB unprotected objects point to new
objects or not• Decide this type at creation time
• A class care about WB → WB protected object• A class don’t care about WB → WB unprotected object
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)27

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• ptr = RARRAY_PTR(ary)• In this case, we can’t insert WB for ptr
operation, so VM shade “ary”

VM
CreateUnprotect

WB p.
obj

WB
unp.
obj

Now, WB unprotected object
can’t change into WB p. object
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)28

RGenGC
Rule• 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

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)29

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 andremembertraverseold• Mark reachable objects
from root objects• Mark WB unprotected
objects, and *don’t
promote* them to old 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!!

new笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装,
情報処理学会 第101回プログラミング研究発表会(2014/11)30

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

Root objects

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

ignoreoldignoreoldignoretraverse

WB
unp.

traverse

traverseoldold• Mark reachable objects
from root objects• Mark WB unprotected
objects, and *don’t
promote* them to old 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!!

new笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装,
情報処理学会 第101回プログラミング研究発表会(2014/11)

31

RGenGC[Unprotect operation]
Rememberset (RSet)
old

old

WB
old
unp.

• 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

new
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)32

RGenGC
Discussion: Pros. and Cons.
• Pros.
• Allow WB unprotected objects• 100% compatible w/ existing extensions which don’t care about WB• A part of CRuby interpreter which doesn’t care about WB• Inserting WBs step by step, and increase performance gradually• We don’t need to insert all WBs into interpreter core at a time
• We can concentrate into popular (effective) classes/methods.
• We can ignore minor classes/methods.

• Simple algorithm, easy to develop
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)33

RGenGC
Discussion: Pros. and Cons.
• Cons.
• Increasing “unused, but not collected objects until full/major GC• Remembered normal objects (caused by traditional GenGC algorithm)• Remembered WB unprotected objects (caused by RGenGC algorithm)• WB insertion bugs (GC development issue)• WB protected objects need correct/perfect WBs. However, inserting
correct/perfect WBs is difficult.
• This issue is out of scope

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)34

Issue of RGenGC: Long pause time
• Good: RGenGC achieves high throughput• Good: Minor GC stops only short pause time
• Bad: Major GC still stops long pause time
→ Introducing Incremental GC for major GC
Throughput
Pause time

Generational GC Incremental GC Gen+Inc GC
High
Low (a bit slow)
High
Long
Short
Small

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

35

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

36

Incremental GC• GC steps incrementally• Interleaving with mutators and GC process.
Mutaor• Using 3 colors

GC• White objects is not traversed objects• Grey objects can point white objects• Black objects only point grey or black objects

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)37

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
reachable white objects, andblack the chosen object
4. Finish marking when no grey
objects
5. Sweep white objects asunmarked objects

Do step 3
incrementally

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)38

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

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)39

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

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

40

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, so black such
white objects without interleaving any mutators

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

41

RincGC
Root objects
traverse

traverse

traverse

WB unp.

traverse

traverse

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

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

42

RincGC: Discussion• Long pause time
• This technique can introduce long pause time, relative to thenumber of WB unprotected objects at last. This is why thisalgorithm is named “Restricted”• Shorter pause time than “Minor GC” of RGenGC.

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

43

Implementation

44

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

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)45

Ruby’s implementation
Data structure• Introduce 2 bits age information to represent young and old objects• Age 0 to 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 the latter is used
only at major GC (incremental GC)

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)46

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)
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)47

Evaluation• RGenGC• Micro-benchmark• Application benchmark• RincGC• Micro-benchmark• Application benchmark• Environment• Intel(R) Core(TM) i7-4930K CPU @ 3.40GHz (Thanks Prof. Sugaya, Shibaura-IT)• Ubuntu 14.04.1 LTS (GNU/Linux 3.13.0-37-generic x86_64)• ruby 2.2.0dev (2014-11-09 trunk 48334) [x86_64-linux]
笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)48

RGenGC: Micro-benchmark# Make 1M objects (long lived)
ary = (1..1_000_000).map{|e| Object.new}# Make short-lived 100M objects
100_000_000.times{Object.new}

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)49

RGenGC: Micro-benchmark
25Time (ms)

20
15
10
5

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

0

n-th GC
mark time/nosweep time/nomark time/RGenGC

sweep time/RGenGC

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)50

RGenGC: Micro-benchmark
3000

Time (ms)

2500

2000

704.843669

1500
1000

1699.805974

500

867.740319

087.230735
RGenGCnototal marktotal sweep

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)51

RGenGC: Rdoc application
200
180
160

Time (ms)

140
120
100
80
60
40
20

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
nth-GC
mark time/nosweep time/nomark time/RGenGC

sweep time/RGenGC

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)52

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

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)53

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

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)54

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

remembered unprotected objects

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)55

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

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

56

RincGC: Micro-benchmark
Top 2048 of pause time
0.035
0.03

Time (sec)

0.025

0.02
0.015
0.01
0.005

1
49
97
145
193
241
289
337
385
433
481
529
577
625
673
721
769
817
865
913
961
1009
1057
1105
1153
1201
1249
1297
1345
1393
1441
1489
1537
1585
1633
1681
1729
1777
1825
1873
1921
1969
2017

0

pause time (lazy sweep)

pause time (rincgc)

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)

57

RincGC: Rdoc application
Pause time top 256
0.25

Time (sec)

0.2
0.15
0.1
0.05

1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145
151
157
163
169
175
181
187
193
199
205
211
217
223
229
235
241
247
253

0
pause time (rgengc+lazy sweep)

pause time (rgengc+rincgc)

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)58

Related work
• Unexpectedly, only a few work. Maybe most of interpreters are
initially developed using write barriers.
• Memory protection is widely used for card marking instead of finegrain write barriers.
• Hanai, et.al. proposed auto WB insertion technique by analyzing
interpreter source code.
• Aikawa, et.al. proposed WB location detection using memory
protection technique.

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)59

Future work
• Improve performance of sweep-phase• Tuning RincGC to reduce pause time

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)60

Summary• 背景• Ruby処理系にはライトバリア（WB）が入っていないし、実装大変• 世代別GC、インクリメンタルGCはWBが無いと実装できない• 本研究の貢献• 完璧にWBが入って無くても出来るアルゴリズムを考えました• 実世界への貢献• この世代別GCが入ったRuby 2.1は2013年12月にリリース済み• このインクリメンタルGCを追加したRuby 2.2を2014年12月にリリース予定

笹田 耕一, 松本 行弘: Rubyにおけるライトバリアのないオブジェクトを考慮した世代別インクリメンタルGCの実装, 情報処理学会 第101回プログラミング研究発表会(2014/11)61