Performance in the details:
A way to make faster Ruby
Koichi Sasada<ko1@heroku.com>

RailsClub 2015

A way to make faster Ruby

The only way I can find is:

Repeating a process.

A way to make faster Ruby: A process
1. Observe Ruby interpreter
2. Make assumption the reason of slowness
3. Consider ideas to overcome
4. Implement ideas
5. Measure the result• Bad/same performance → Goto 4, 3, 2 or 1
• Good performance! → Commit it.

Koichi Sasada
A programmer from Japan

Koichi is a Programmer• MRI committer since 2007/01• Original YARV developer since 2004/01• YARV: Yet Another RubyVM• Introduced into Ruby (MRI) 1.9.0 and later• Generational/incremental GC for 2.x

Koichi is an Employee

Koichi is a member of Heroku Matz team
MissionDesign Ruby language
and improve quality of MRI
Heroku employs three full time Ruby core developers in Japan
named “Matz team”

Heroku Matz team
Matz

Designer/director of Ruby

Nobu

Quite active committer

Ko1

Internal Hacker

Matz
Title collector• He has so many (job) title• Chairman - Ruby Association• Fellow - NaCl
• Chief architect, Ruby - Heroku• Research institute fellow – Rakuten• Chairman – NPO mruby Forum• Senior researcher – Kadokawa Ascii Research Lab• Visiting professor – Shimane University• Honorable citizen (living) – Matsue city
• Honorable member – Nihon Ruby no Kai• …

• This margin is too narrow to contain

Nobu
Great Patch monster

Ruby’s bug|> Fix Ruby|> Break Ruby|> And Fix Ruby

Nobu
Patch monster
COMMITRATIOIN LAST 5 YEARS
charliesom
shirosaki
sorah
tarui
xibbarryan
eregonwanabenagai
luislavena
ngoto
takano32
davidflanag
kanemotoa_matsuda
technoram
duerstiwamatsu
azav
keiju
murakensuke
kouji
gotokenheadius
arton
tmm1
jeg2
hsbt
okkez
eban
seki
evan
ayumin
nahi
ktsj
glass
nari
shyouheiembossmrkn
koue0%
yugui
nagachika
0%
0%
0%
0%
0%
0%
0%
0%
0%
0%
0%
0%
0%
an
a
0%
0%
0%
shugo
1%
1%
1%0%
knu
1%
nobu
1%
0%
tadf
1%
1%
mame
29%
2%
marcandre
2%
matz
2%
tenderlove
2%zzak
2%kazu2%
kosaki2%3%drbrain
3% ko1akr
naruse
svn
12%
4%usa
4% 8%
9%

Commit count of MRI

Nobu
The Ruby Hero

EDD: Event Driven Development
2013/11/8

2013/9/8

2013/7/8

2013/5/8

2013/3/8

2013/1/8

2012/11/8

2012/9/8

2012/7/8

2012/5/8

15

2012/3/8

20

2012/1/8

25

2011/11/8

2011/9/8

2011/7/8

2011/5/8

2011/3/8

2011/1/8

2010/11/8

Ko1
EDD developer
EurukoCommit number of ko1 (last 3 years)
2013
RubyKaigi
2013
RubyConf
RubyConf
2012
2013
Ruby 2.01050Heroku Matz team and Ruby core team
Recent achievement

Ruby 2.2
Current stable

Ruby 2.2
Syntax• Symbol key of Hash literal can be quoted{“foo-bar”: baz}#=> {:“foo-bar” => baz}#=> not {“foo-bar” => baz} like JSON

TRAP!!
Easy to misunderstand(I wrote a wrong code, already…)

Ruby 2.2
Classes and Methods• Some methods are introduces• Kernel#itself• String#unicode_normalize• Method#curry• Binding#receiver• Enumerable#slice_after, slice_before• File.birthtime• Etc.nprocessors•…

Ruby 2.2
Improvements• Improve GC• Symbol GC• Incremental GC• Improved promotion algorithm• Young objects promote after 4 GCs• Fast keyword parameters• Use frozen string literals if possible

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#=> [2_456, 2_456] # GCed! Ruby 2.2
Symbol GC Issues history• Ruby 2.2.0 has memory (object) leak problem• Symbols has corresponding String objects• Symbols are collected, but Strings are not collected! (leak)• Ruby 2.2.1 solved this problem!!
• However, 2.2.1 also has problem (rarely you encounter BUG at the end of process[Bug #10933] ← not big issue, I want to believe)• Ruby 2.2.2 had solved [Bug #10933]!!
• However, patch was forgot to introduce!!

• Finally, Ruby 2.2.3 solved it!!

• Please use newest version!!

Ruby 2.2
Fast keyword parameters
Execution time (sec)“Keyword parameters” introduced in Ruby 2.0 is useful, but slow!!
20

Evaluation on Ruby 2.1

15x30 slower

1050foo6(1, 2, 3, 4, 5, 6)

foo_kw6(k1: 1, k2: 2, k3: 3, k4: 4, k5: 5, k6: 6)

Repeat 10M times

Ruby 2.2
Fast keyword parameters
Execution time (sec)

Ruby 2.2 optimizes method dispatch with keyword parameters
20
15

x14 faster!!

10
50foo6(1, 2, 3, 4, 5, 6)

foo_kw6(k1: 1, k2: 2, k3: 3, k4: 4, k5: 5, k6: 6)

Repeat 10M times

Ruby 2.1

But still x2 times slower

Ruby 2.2 compare with normal dispatch

Ruby 2.2
Incremental GC

Goal
Before Ruby 2.1
Ruby 2.1 RGenGC
Throughput
Pause time

Low
Long

High
Long

Incremental Ruby 2.2
Gen+IncGC
GC
Low
Short

High
Short

RGenGC from Ruby 2.1:
Micro-benchmark
3000

Time (ms)

2500
2000

704.843669

x2.5 faster

1500
1000

1699.805974

500

867.740319

087.230735
RGenGCnototal marktotal sweep

RGenGC from Ruby 2.1:
Pause time
Most of cases, FASTER (w/o rgengc)

RGenGC from Ruby 2.1:
Pause time

Several peaks (w/o rgengc)

Ruby 2.2 Incremental GC
Short pause time Heroku Matz team and Ruby core team
Next target is

Ruby 2.3

Heroku Matz team and Ruby core team
Next target is

Ruby 2.3
No time to talk about it.
Please ask me later Performance in the details:
A way to make faster Ruby

Ruby’s components for users
Ruby (Rails) app

i gigantum umeris insidentes
Standing on the shoulders of giants

So many gems
such as Rails, pry, thin, … and so on.
RubyGems/Bundler

Ruby interpreterRuby’s components
from core developer’s perspective
Ruby
scriptBundledLibraries

Gem
Libraries

Embeddedclasses and methods(Array, String, …)

Parse

CompileThreading

Evaluator

Ruby
Bytecode

Objectmanagement(GC)Ko1’s area

Interpret on RubyVM

Basic flow to make faster Ruby
1. Observe Ruby interpreter
2. Make assumption the reason of slowness
3. Consider ideas to overcome
4. Implement ideas
5. Measure the result• Bad/same performance → Goto 4, 3, 2 or 1
• Good performance! → Commit it.

Basic weapons to overcome issues• Knowledge of computer science• Computer system, Programming techniques, and manyothers• From:• Textbook• Academic papers• Other implementation• Feedback from users

Basic technique to improve performance• Change the algorithm to reduce computation complexity• e.g.: Selection sort (O(n^2)) v.s. Quick sort (O(n log(n))• Chang the data structure to improve data locality• e.g.: “list” and “array”• Remove redundant process• e.g.: Using cache (utilize time locality)• Considering trade-off• Speed-up major cases and slow-down minor cases• e.g.: speed-up non-exception flow (and slow-down exception cases)• Machine dependent technique• e.g.: Using assembler / CPU register directly•…

Case studies

Ruby has many

Let’s play hangman game

Ruby has many

Ruby has many

Ruby has many

Ruby has many

Ruby has many

Or Methods

Case study:
Optimize method dispatch

Ruby’s components
from core developer’s perspective
Ruby
scriptBundledLibraries

Gem
Libraries

Embeddedclasses and methods(Array, String, …)

Parse

CompileThreading

Evaluator

Ruby
Bytecode

Objectmanagement(GC)Ko1’s area

Interpret on RubyVM

Method dispatch# Example
recv.selector(arg1, arg2)•recv: receiver•selector: method id•arg1, arg2: arguments

Method dispatch
Overview
1. Get class of `recv’ (`klass’)
2. Search method `body’ named `selector’ from `klass’••Method is not fixed at compile time
“Dynamic” method dispatch

3. Dispatch method with `body’
1.
2.
3.
4.
5.

Check visibility
Check arity (expected args # and given args #)Store `PC’ and `SP’ to continue after method returning
Build `local environment’
Set program counter

4. And continue VM execution

Overview
Method search• Search method from `klass’

BasicObject

1. Search method table of `klass’
1.
2.

if method `body’ is found, return `body’`klass’ = super class of `klass’ and repeat it

Kernel

2. If no method is given, exceptional flow•

In Ruby language, `method_missing’ will be called

selector: body...
Each Class has
method table

Object
C1
C2

Overview
Checking arity and visibility• Checking arity• Compare with given argument number and expected argument number• Checking visibility• In Ruby language, there are three visibilities• can you explain each of them ?:-p
• public• private• protectedOverview
Building `local environment’• How to maintain local variables?
→ Prepare `local variables space’ in stack→ `local environment’ (short `env’)• Parameters are also in `env’Method dispatch
Overview (again)
1. Get class of `recv’ (`klass’)
2. Search method `body’ `selector’ from `klass’• Method is not fixed at compile time
• “Dynamic” method dispatch

3. Dispatch method with `body’
1.
2.
3.
4.
5.

Check visibility
Check arity (expected args # and given args #)Store `PC’ and `SP’ to continue after method returning
Build `local environment’
Set program counter

4. And continue VM execution

It seems very easyand simple!
and slow...

Method dispatch• Quiz: How many steps in Ruby’s method dispatch?
• Hint: More complex than I explained overview① 8 steps② 12 steps
Answer is③ 16 steps
About ④ 20 steps④ 20 steps

Method dispatch
Ruby’s case1.

Check caller’s arguments
1.
2.

Check splat (*args)
Check block (given by compile time or block parameter (&block))2.

Get class of `recv’ (`klass’)3.

Search method `body’ `selector’ from `klass’••

4.

Method is not fixed at compile time
“Dynamic” method dispatch

Dispatch method with `body’1.
2.

Check visibility
Check arity (expected args # and given args #) and process
1.
2.
3.
4.
5.

3.

Push new control frame
1.
2.
3.
4.
5.

4.
5.
6.

5.

Post arguments
Optional arguments
Rest argument
Keyword arguments
Block argument
Store `PC’ and `SP’ to continue after method returning
Store `block information’Store `defined class’Store bytecode info (iseq)
Store recv as self... simple?

Build `local environment’
Initialize local variables by `nil’
Set program counter

And continue VM execution(*) Underlined items are additonal process

Ruby’s caseComplex parameter checking• “def foo(m1, m2, o1=..., o2=...,
p1, p2, *rest, &block)”• m1, m2: mandatory parameter• o1, o2: optional parameter• p1, p2: post parameter• rest: rest parameter• block: block parameter• From Ruby 2.0, keyword parameter is supported

Method dispatch
1.

CHeck caller’s arguments
1.
2.

Check splat (*args)
Check block (given by compile time or block parameter (&block))2.

Get class of `recv’ (`klass’)3.

Search method `body’ `selector’ from `klass’••

4.

Method is not fixed at compile time
“Dynamic” method dispatch

Dispatch method with `body’1.
2.

Check visibility
Check arity (expected args # and given args #) and process
1.
2.
3.
4.
5.

3.

Push new control frame
1.
2.
3.
4.
5.

4.
5.
6.

5.

Post arguments
Optional arguments
Rest argument
Keyword arguments
Block argument
Store `PC’ and `SP’ to continue after method returning
Store `block information’Store `defined class’Store bytecode info (iseq)
Store recv as self

Build `local environment’
Initialize local variables by `nil’
Set program counter

And continue VM execution

ComplexandSlow!!!

Method dispatch
Overhead

Method dispatch overhead is big
especially on micro-benchmarks FibPentomino

OthersOthers
NotRuby

NotRuby

Others
Cfunc
Cfunc
MM
GC
CompileOthersBlock

Others
Insn

Obj
Insn

Method

VM

MM

Obj

VM

GC
CompileInst
Block

OS: Linux 2.6.31 32-bit
CPU: IntelCore2Quad 2.66GHz
Mem: 4GB
C Compiler: GCC 4.4.1, -O3
Profiled by Oprofileruby 1.9.3dev (2010-05-26)
Profiled by Mr. Shiba

MethodSpeedup techniques
for method dispatch
1. Specialized instructions
2. Method caching
3. Caching checking results
4. Special path for `send’ and `method_missing’Optimization
Specialized instruction (from Ruby 1.9.0)• Make special VM instruction for several methods• +, -, *, /, ...
def opt_plus(recv, obj)
if recv.is_a(Fixnum) and obj.is_a(Fixnum) andFixnum#+ is not redefined
return Fixnum.plus(recv, obj)
else
return recv.send(:+, obj) # not prepared
end
end

Optimization
Method caching (from Ruby 1.9.0)• Eliminate method search overhead• Reuse search result• Invalidate cache entry with VM stat

BasicObject• Two level method caching

Kernel• Inline method caching• Global method caching

Objectmethod search

returnclass =>
body

miss

Inline cache
1 element per call-siteclass, id => bodyclass, id => body....
class, id => body

C1
miss

fill

fill

Global cachehash table

C2
naive searchOptimization
Caching checking results (from 2.0.0)• Idea: Visibility and arity check can be skipped after first checking

First time

Second time

• Store result in inline method cache
1. Check caller’s arguments
2. Search method `body’ `selector’ from `klass’

3. Dispatch method with `body’
1.

Check visibility and arity
1.

Cache result into inline method cache

2. Push new control frame
3. Build `local environment’
4. Initialize local variables by `nil’

Evaluation result
Microbenchmarks
Faster than first date2

Speedup ratio

vm1_attr_ivar*

1.5

vm1_attr_ivar_set*
vm1_block*
vm1_simplereturn*
vm1_yield*

1vm2_defined_method*
vm2_method*
vm2_method_missing*

0.5

vm2_method_with_block*
vm2_poly_method*vm2_send*0

vm2_super*

vm2_zsuper*

trunk 2012/10/13

trunk 2012/10/31

Case study
Faster keyword parameters

Keyword parameters from Ruby 2.0# def with keywords
def foo(a, b, key1: 1, key2: 2)…
end# call with keywords
foo(1, 2, key1: 123, key2: 456)

Execution time (sec)

Slow keyword parameters

20
15

Evaluation on Ruby 2.1
x30 slower

1050foo6(1, 2, 3, 4, 5, 6)

foo_kw6(k1: 1, k2: 2, k3: 3, k4: 4,
k5: 5, k6: 6)

Repeat 10M times

Why slow, compare with normal parameters?
1. Hash creation
2. Hash accessdef foo(k1: v1, k2: v2)…
endfoo(k1: 1, k2: 2)

def foo(h = {})k1 = h.fetch(:k1, v1)
k2 = h.fetch(:k2, v2)…
2. Hash accessendfoo( {k1: 1, k2: 2} )1. Hash creation

Optimization technique of keyword
parameters from Ruby 2.2• Key technique→ Pass “a keyword list”
nstead of a Hash object

Check “Evolution of Keyword parameters” at Rubyconf portugal'15
http://www.atdot.net/~ko1/activities/2015_RubyConfPortgual.pdf

Result: Fast keyword parameters (Ruby 2.2.0)
Execution time (sec)

Ruby 2.2 optimizes method dispatch with keyword parametersx14 faster!!

20
15
10
5
0

(best case)foo6(1, 2, 3, 4, 5, 6)

foo_kw6(k1: 1, k2: 2, k3: 3, k4: 4, k5:
5, k6: 6)

Repeat 10M times

Ruby 2.1

Ruby 2.2
But still x2 times slower
compare with normal dispatch

Case study
Garbage collection

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

Ruby’s components
from core developer’s perspective
Ruby
scriptBundledLibraries

Gem
Libraries

Embeddedclasses and methods(Array, String, …)

Parse

CompileThreading

Evaluator

Ruby
Bytecode

Objectmanagement(GC)Ko1’s area

Interpret on RubyVM

Automatic memory management
Basic concept• Garbage collector recycled “unused” objects automaticallyMark & Sweep algorithm
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Generational GC (GenGC) from Ruby 2.1.0• Weak generational hypothesis:“Most objects die young”

http://www.flickr.com/photos/ell-r-brown/5026593710→ Concentrate reclamation effort
only on the young objects

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)Generational GC (GenGC)• Separate young generation and old generation• Create objects as young generation• Promote to old generation after surviving n-th GC• Usually, GC on young space (minor GC)• GC on both spaces if no memory (major/full GC)

GenGC [Minor M&S GC] (1/2)
1st MinorGC• Mark reachable objects fromroot objects.

Root objects• Mark and promote to oldgeneration• Stop traversing after old
objects

traverse
new/
free

new
old
traverse

traverse

new/
free

collectnewoldtraverse
new
old

new
old
traverse
newold→ 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.

GenGC [Minor M&S GC] (2/2)
2nd MinorGC• Mark reachable objects fromroot objects.

Root objects• Mark and promote to oldgeneration• Stop traversing after old
objects

traverse
new/
free

old
ignoreignorenew/freecollectoldignoreold

oldignoreold→ 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.

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

collectoldtraverseoldnewtraverse
old

old/
free
collect• Sweep all unreachable(unused) objects

Accumulated execution time (sec)

RGenGC from Ruby 2.1.0
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.

RGenGC from Ruby 2.1.0
Performance evaluation (RDoc)
Total execution time (sec)

140
120

16.04393815
4.946003494

100
80
60
40

103.7627479

102.3799865

w/o RGenGC

RGenGC20
0other than GC

GC* 12% improvements compare with w/ and w/o RGenGC* Disabled lazy sweep to measure correctly.

SummarySummary
Repeating “Basic flow” is my daily job
1. Observe Ruby interpreter
2. Make assumption the reason of slowness
3. Consider ideas to overcome
4. Implement ideas
5. Measure the result• Bad/same performance → Goto 4, 3, 2 or 1
• Good performance! → Commit it.

Summary

Ruby/MRI is getting
better and better.

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