最近の Ruby のメモリ管理
Recent Ruby’s memory management
Koichi Sasada
ko1@heroku.com

K.Sasada: 最近の Ruby のメモリ管理, 2014

Summary• Ruby’s new two GC implementation• RGenGC: Restricted Generational GC• RincGC: Restricted incremental GC

K.Sasada: 最近の Ruby のメモリ管理, 2014

Who am I ?
Koichi Sasada from Heroku, Inc.
• CRuby/MRI committer• Virtual machine (YARV) from Ruby 1.9• YARV development since 2004/1/1• Recently, improving GC performance• Matz team at Heroku, Inc.
• Full-time CRuby developer• Working in Japan• Director of Ruby Association
K.Sasada: 最近の Ruby のメモリ管理, 2014• Foundation to encourage Ruby developments andcommunities• Chairman is Matz
• Located at Matsue-city, Shimane, Japan• Activities• Maintenance of Ruby (Cruby) interpreter• Now, it is for Ruby 1.9.3• Ruby 2.0.0 in the future?

• Events, especially RubyWorld Conference• Ruby Prize• Grant project. We have selected 3 proposals in 2013
• Win32Utils Support, Conductor, Smalruby - smalruby-editor• We will make this grant 2014!!

• Donation for Ruby developments and communities
K.Sasada: 最近の Ruby のメモリ管理, 2014• Heroku, Inc. http://www.heroku.com• Heroku supports Ruby development• Many talents for Ruby, and also other languages• Heroku employs 3 Ruby interpreter core developers• Matz• Nobu• Ko1 (me)• We name our group “Matz team”

K.Sasada: 最近の Ruby のメモリ管理, 2014

“Matz team” in Heroku

K.Sasada: 最近の Ruby のメモリ管理, 2014

Matz team in Heroku
in JapanNobu @ Tochigi
Patch monster

Matz @ Shimane
Title collector

K.Sasada: 最近の Ruby のメモリ管理, 2014

ko1 @ Tokyo
EDD developer

Mission of Matz team
• Improve quality of next version of CRuby• Matz decides a spec finally• Nobu fixed huge number of bugs
• Ko1 improves the performance

Current target is Ruby 2.2!!
Now, Ruby 2.1 is old version for us.
K.Sasada: 最近の Ruby のメモリ管理, 2014

http://www.flickr.com/photos/loginesta/5266114104

Ruby 2.1
Current stable
K.Sasada: 最近の Ruby のメモリ管理, 2014

Ruby 2.1
a bit old Ruby
• Ruby 2.1.0 was released at 2013/12/25• New features• Performance improvements• Ruby 2.1.1 was released at 2014/02/24• Includes many bug fixes found after 2.1.0 release• Introduce a new GC tuning parameter to change
generational GC behavior (introduce it later)• Ruby 2.1.2 was released at 2014/05/09• Solves critical bugs (OpenSSL and so on)

K.Sasada: 最近の Ruby のメモリ管理, 2014

Performance improvements• Optimize “string literal”.freeze• Sophisticated inline method cache• Introducing Generational GC: RGenGC

K.Sasada: 最近の Ruby のメモリ管理, 2014

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

Ruby 2.2
Next version
K.Sasada: 最近の Ruby のメモリ管理, 2014

Ruby 2.2
Big features (planned)• New syntax: not available now• New method: no notable methods availablenow• Libraries:• Minitest and test/unit will be removed (provided bybundled gem)

K.Sasada: 最近の Ruby のメモリ管理, 2014

Ruby 2.2
Internal changes• Internal• C APIs• Hide internal structures for Hash, Struct and so on• Remove obsolete APIs

• GC
• Symbol GC (merged recently)• 2age promotion strategy for RGenGC• Incremental GC to reduce major GC pause time

• VM
• More sophisticated method cache
K.Sasada: 最近の Ruby のメモリ管理, 2014

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

Break

K.Sasada: 最近の Ruby のメモリ管理, 2014

Garbage collection
The automatic memory management

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

K.Sasada: 最近の Ruby のメモリ管理, 2014

Automatic memory management
Basic concept• “Object.new” allocate a new object• “foo” (string literal) also allocate a new object• Everything are objects in Ruby!

• We don’t need to “de-allocate” objects manually

K.Sasada: 最近の Ruby のメモリ管理, 2014

Automatic memory management
Basic concept• Garbage collector recycled “unused” objects
automatically

K.Sasada: 最近の Ruby のメモリ管理, 2014

Ruby’s GC• Mark & Sweep (from first release)• Conservative marking (from first release)• Lazy (incremental) sweep (from Ruby 1.9.3)• Bitmap marking (from Ruby 2.0)
• Generational marking (RGenGC, from Ruby 2.1)
• Incremental marking (PLANNED: from Ruby 2.2)

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Restricted
Generational GC

http://www.flickr.com/photos/ell-r-brown/5026593710

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Summary• RGenGC: Restricted Generational GC• New generational GC algorithm allows mixing “Writebarrier protected objects” and “WB unprotected objects”• No (mostly) compatibility issue with C-exts• Inserting WBs gradually• We can concentrate WB insertion efforts for major objects
and major methods• Now, Array, String, Hash, Object, Numeric objects are WB
protected• Array, Hash, Object, String objects are very popular in Ruby
• Array objects using RARRAY_PTR() change to WB unprotected
objects (called as WB-unprotected objects), so existing codes stillworks.
K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Background
Current CRuby’s GC• Mark & Sweep• Conservative• Lazy sweep• Bitmap marking• Non-recursive marking• C-friendly strategy• Don’t need magical macros in C source codes• Many many C-extensions under this strategy

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC
Restriction of CRuby’s GC
1. Because of “C-friendly” strategy:• We can’t know object relation changing timing• We can’t use “Moving GC algorithm” (such as
copying/compacting)
2. Because of “Object data structure”:• We can’t measure exact memory consumption• Based on assumption: “malloc” library may besmarter than our hack
• We rely on “malloc” library for memory allocations• GC only manage “object” allocation/deallocation
K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: BackgroundMark & 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
K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Background
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
K.Sasada: 最近の Ruby のメモリ管理, 2014

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

Percentage of dead object#

100
90

95% of objects dead by 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)
K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Background
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

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Background
Generational GC (GenGC)• Separate young generation and old generation• Create objects as young generation• Promote to old generation after surviving n-th GC• In CRuby, n == 1 (after 1 GC, objects become old)

• Usually, GC on young space (minor GC)• GC on both spaces if no memory (major/full GC)

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Background
Generational GC (GenGC)• Minor GC and Major GC can use different GC
algorithm• Popular combination is:
Minor GC: Copy GC, Major GC: M&S• On the CRuby, we choose:
Minor GC: M&S, Major GC: M&S• Because of CRuby’s restriction (we can’t use moving
algorithm)

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Background: GenGC[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.
K.Sasada: 最近の Ruby のメモリ管理, 2014

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.
K.Sasada: 最近の Ruby のメモリ管理, 2014

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

collectoldtraverse

oldnew• Sweep all unreachable(unused) objects

traverse
old

old/
free
collect
K.Sasada: 最近の Ruby のメモリ管理, 2014

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)

newK.Sasada: 最近の Ruby のメモリ管理, 2014

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

newK.Sasada: 最近の Ruby のメモリ管理, 2014

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
traverse
new
K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Background: GenGC
Write barrier• To detect [old→new] type references, we need toinsert “Write-barrier” into interpreter for all“Write” operation

old

new

“Write barrier”[Old->New] type reference
Detected!
K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC
Back to Ruby’s specific issue

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: CRuby’s caseWrite 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

3
K.Sasada: 最近の Ruby のメモリ管理, 2014

new1

RGenGC: CRuby's caseDifficulty of inserting write barriers• To introduce generational garbage collector, WBs arenecessary to detect [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!!

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: 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

K.Sasada: 最近の Ruby のメモリ管理, 2014

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

Compatibility

2.0 andearlierconservative

1

Give up GenGC

Poor

Good
(No problem)

2

GenGC with rewriting all of C exts

Good

Most of C-exts
doesn’t work

Trade-off of Speed and Compatibility
K.Sasada: 最近の Ruby のメモリ管理, 2014

choiceRGenGC: Challenge• Trade-off of Speed and Compatibility• Can we achieve both speed-up w/ GenGC and keeping
compatibility?

• Several possible approaches• Separate heaps into the WB world and non-WB world• Need to re-write whole of Ruby interpreter• Need huge development effort• WB auto-insertion• Modify C-compiler• Need huge development effort

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Our approach• Create new generational GC algorithm permits WB
protected objects AND WB un-protected object inthe same heap

RGenGC: Restricted Generational
Garbage Collection

K.Sasada: 最近の Ruby のメモリ管理, 2014

rd
RGenGC: Invent 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!!

Breaking the trade off. You can praise us!!
K.Sasada: 最近の Ruby のメモリ管理, 2014

Ruby 2.1
choiceRGenGC:
Key idea• Introduce WB unprotected objects

K.Sasada: 最近の Ruby のメモリ管理, 2014

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
objectK.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC:
Key Idea• Normal objects can bechanged 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: 最近の Ruby のメモリ管理, 2014

RGenGC
Key Idea: 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

K.Sasada: 最近の Ruby のメモリ管理, 2014

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 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!!

K.Sasada: 最近の Ruby のメモリ管理, 2014

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

Root objects

Rememberset (RSet)traverse

oldcollect
new/
new/
free
free

ignoreoldignoreignoretraverse

WB
unp.

traverse

oldtraverse
old

new

old

• 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!!

K.Sasada: 最近の Ruby のメモリ管理, 2014

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

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC
Timing chart
2.0.0 GC (M&S w/lazy sweep)
Ruby

Mark

Sweep

Sweep

Sweep

Sweep

Sweep

Stop the (Ruby)
World

w/RGenGC (Minor GC)
RubyMark Sweep

Stop the(Ruby)
World

Sweep

Sweep

Sweep

Sweep

• Shorter mark time (good)• Same sweep time (not good)• (little) Longer execution time b/c WB (bad)K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC
Number of objects
2.0.0 GC (M&S)# of Living objects

w/RGenGC (Minor GC)# of Living objects# of old
objects(#old)(c)# of Freed objects

(a)

(b)
# of Freed objects# of freed# of newobjects (#new) but rememberedobjects(a) # of unused promoted objects(b) # of unused WB unp. objects
pointed by old(c) # of WB unp. objects

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC
Number of objects(a)w/RGenGC (Minor GC)# of Living objects# of old
object(#old)(c)(b)# of Freed object# of freed# of newobject (#new) but rememberedobjects(a) # of unused promoted objects(b) # of unused WB unp. objects
pointed by old(c) # of WB unp. objects

Marking space

Number of unused,uncollected objs

Sweeping
space

Mark&Swep GC# of Living objects

0

Full heap

Traditional GenGC#new + (a)

(a)

#new

RGenGC#new + (a) + (b) + (c)(a) + (b)Full heap

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC
Discussion: Pros. and Cons.

• Pros.

• Allow WB unprotected objects• 100% compatible w/ existing extensions which don’t careabout 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 atime
• We can concentrate into popular (effective)classes/methods.
• We can ignore minor classes/methods.

• Simple algorithm, easy to develop
K.Sasada: 最近の Ruby のメモリ管理, 2014

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. We have another idea against this problem(out of scope).

• Can’t reduce Sweeping time
• But many (and easy) well-known techniques to reduce sweeping time(out of scope).

• Increase complexity• Additional tuning parameters
K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC
Performance evaluation• Ideal micro-benchmark for RGenGC• Create many old objects at first• Many new objects (many minor GC, no major GC)• RDoc• Same “make doc” task from trunk

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC
Performance evaluation (micro)
600000000• Shorter mark time (good)• Same sweep time (not good)

Execution time by RDTSC

500000000

400000000

mark (RGENGC)
sweep (RGENGC)

300000000

mark
200000000

sweep

Good marktime 
100000000

0
1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

GC count

K.Sasada: 最近の Ruby のメモリ管理, 2014

Same sweep
time 

RGenGC
Performance evaluation (RDoc)
Compare with M&S and RGenGC
250

Major/full
GC peaks

200
150

ms

mark (ms)sweep (ms)100

Faster minor
50
GC

rgengc/mark (ms)rgengc/sweep (ms)

1
10
19
28
37
46
55
64
73
82
91
100
109
118
127
136

0

GC count* Disabled lazy sweep to measure correctly.
K.Sasada: 最近の Ruby のメモリ管理, 2014

Accumulated execution time (sec)

RGenGC
Performance evaluation (RDoc)
14
12
10
8
6

About x15 speedup!

4
20
Total mark time (ms)w/o RGenGC

Total sweep time (sec)
RGenGC* Disabled lazy sweep to measure correctly.

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC
Performance evaluation (RDoc)
Total execution time (sec)

140
120
100

16.04393815

4.946003494

80
60
40

103.7627479

102.3799865

w/o RGenGC

RGenGC20

0other than GC

GC

K.Sasada: 最近の Ruby のメモリ管理, 2014

RGenGC: Summary• RGenGC: Restricted Generational GC• New GC algorithm allow mixing “Write-barrier protected
objects” and “WB unprotected objects”• (mostly) No compatibility issue with C-exts• Inserting WBs gradually• We can concentrate WB insertion efforts for major objects
and major methods

K.Sasada: 最近の Ruby のメモリ管理, 2014

RincGC:
Restricted incremental GC

K.Sasada: 最近の Ruby のメモリ管理, 2014

RincGC
Background and motivation• Ruby 2.1 had introduced generational GC• Short marking time on minor GC• Improve application throughput• Still long pause time on major GC• Long pause time affects user response time

K.Sasada: 最近の Ruby のメモリ管理, 2014

Proposal:
RincGC: Incremental GC for major GC• Introducing incremental GC to reduce pause time
• Can combine with Generational GC

Throughput
Pause time

Generational GC
High
Long

Incremental GC
Low (a bit slow)
Short

K.Sasada: 最近の Ruby のメモリ管理, 2014

Gen+Inc GC
High
Small

RincGC: Base idea
Incremental GC algorithm• Move forward GC processes incrementally• Mark slots incrementally• Sweep slots incrementally• Incremental marking in 3 phase• (1) Mark roots (pause)• (2) Mark objects reachable from roots (incremental)• (3) Mark roots again, and mark remembered objects (pause)• Mark objects with three state (white/grey/black)• White: Untouched objects• Grey: Marked, and prepare to mark directly reachable objects• Black: Marked, and all directly reachable objects are marked• Use write barriers to avoid marking miss from marked objects to live
objects• Detect new reference from black objects to white objects• Remember such source black objects (marked at above (3))
K.Sasada: 最近の Ruby のメモリ管理, 2014

RincGC:
Incremental GC for CRuby/MRI• Incremental marking• (1) mark roots (gc_mark_roots())• (2) Do incremental mark at rb_newobj_of()• (3) Make sure write barrier with WB-protected objects• (4) Take care of WB-unprotected objects (MRI specific)• Incremental sweeping• Modify current lazy sweep implementation

K.Sasada: 最近の Ruby のメモリ管理, 2014

RincGC:
Incremental marking• (1) mark roots (gc_mark_roots())• Push all root objects onto “mark_stack”• (2) Do incremental mark at rb_newobj_of()• Fall back incremental marking process periodically• Consume (pop) some objects from “mark_stack” and makeforward incremental marking• (3) Make sure write barrier with WB-protected objects• Mark and push pointed object onto “mark_stack”• (4) Take care of WB-unprotected objects (MRI specific)• After incremental marking (“mark_stack” is empty), re-scan
all roots and all living non-WB-protected objects• WB-unprotected objects are represented by bitmap(WB_UNPROTECTED_BITS)
K.Sasada: 最近の Ruby のメモリ管理, 2014

RincGC:
Incremental marking
def mark(obj)

def finish_marking

return if obj.mark_bit

root_objects{|o| mark(o)} # re-scan root objects

obj.mark_bit = true

return false unless mark_stack.empty?

obj.marking_bit = true

$marked_wb_unprotected_objects.each{|unprotected_obj|$mark_stack.push(obj)
endunprotected_obj.reachable_objects{|o| mark(o)}}mark(obj) while obj = $mark_stack.pop

def start_marking
GC.state = :markGC.state = :sweep$root_objects{|o| mark(o)}return trueend

end
def incremental_mark(n)n.times{

def write_barrier(a, b)

return if $mark_stack.empty? && finish_marking

if GC.state == :mark && a.mark_bit && !a.marking_bit && !b.mark_bit

obj = mark_stack.pop

a.marking_bit = true

reachable_objects_from(obj){|o| mark(o)}mark(b) and $mark.stack.push(b)obj.marking_bit = false

end

}

end

end

K.Sasada: 最近の Ruby のメモリ管理, 2014

RincGC:
Incremental marking
Traditional GC coloring
terminology
White
Grey
Black

RincGC
mark_bit
marking_bit
FALS
FALSE
TRUE
TRUE
TRUE
FALSE

K.Sasada: 最近の Ruby のメモリ管理, 2014

RincGC:
Incremental sweeping• Current implementation• Iterate until no pages• Sweep 1 page (a set of slots)• Consume 1 page

• After that, no empty pages• Modify implementation• Iterate• Sweep 2 page (a set of slots)• Consume *1* page (1 page remain)• After that, half of pages are left
• We can use this half of pages for incremental marking
K.Sasada: 最近の Ruby のメモリ管理, 2014

RincGC:
DiagramDirect transition

State: marking

garbage_collect()
if (nopages)

Via mutator(clear doing flag)

State: sweeping

marks_start()

sweep_start()

newobj()if (incremental_marking)doing: truemarks_continue()marks_step()

if (sweep_pages)

sweep_step()doing: true

sweep_continue()marks_finish()
if (root scan detect unmarked objects)

K.Sasada: 最近の Ruby のメモリ管理, 2014

sweep_finish()State: noneSummary• Ruby’s new two GC implementation• RGenGC: Restricted Generational GC• RincGC: Restricted incremental GC

K.Sasada: 最近の Ruby のメモリ管理, 2014

Thank you for your attention
Q&A?
Koichi Sasada<ko1@heroku.com>

K.Sasada: 最近の Ruby のメモリ管理, 2014