Evolution of
Keyword parameters
Koichi Sasada<ko1@heroku.com>

Rubyconf Portugal’15

Background“Keyword parameters” from Ruby 2.0# From Ruby 2.0 feature
def foo(k1: 1, k2: 2)
p [k1, k2] #=> [345, 2]
endfoo(k1: 345)

Execution time (sec)Background“Keyword parameters” was slow!!
Evaluation on Ruby 2.1
16
14
12
10
8
6
4
2
0

x30 slower

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

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

Repeat 10M times

Summary

Execution time (sec)

Ruby 2.2 optimized“keyword parameters”
20
15
10

x14 faster!!

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

foo_kw6(k1: 1, k2: 2, k3: 3, k4: 4,
k5: 5, k6: 6)
Repeat 10M times But still x2 times slower

compare with normal dispatch

Ruby 2.1

Ruby 2.2

Why was slow?
How to solve it?

Koichi Sasada 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 andlater• Generational/incremental GC for 2.x

Koichi Sasada from Japan

Japanese lesson

EnglishThank you
Portuguese Obrigado
Japanese
Arigatoありがとう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 coredevelopers in Japan named “Matz team”

Heroku Matz team
Matz

Nobu
Ko1

Designer/director of
Ruby
Quite active committer
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 introduced• 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
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 Back to the main topic

Ruby has many

Let’s play hangman game

Ruby has many

Ruby has many

Ruby has many

RubyConf 2008 Keynote
by Dave Thomas (Pragmatic programmer)

Quoted from Dave Thomas Keynote

RubyConf 2008
Keynote by Dave Thomas

Quoted from Dave Thomas Keynote

RubyConf 2008
Keynote by Dave Thomas

Quoted from Dave Thomas Keynote

Ruby has many

RubyConf Portgual 2015
Koichi Sasada

Ruby has many

Or Methods

Optimizing Func(tion)s or Methods
is important for Ruby
• Syntax optimization (readable/writable)• Call without parenthesis• Passing blocks with braces or do/end• Splat/block arguments (*args, &block)• Optional/rest/post/block parameters by def• def foo(m1, m2, o1=1, o2=2, *rest, p1, p2, &block)• Keyword arguments/parameters• Performance optimization• By virtual machine implementation. My task Tough work to pass manyarguments# Quoted from my Ruby code
scinsn = Instruction.new(
name, opes, pops, rets, comm,orig_insn.body, orig_insn.tvars, orig_insn.sp_inc,
orig_insn, orig_insn.defopes, :sc, nextsc, pushs)

12 arguments.
Can’t understand what parameter mean.

Tough work to pass manyarguments# Difficult to understand what we specify
GC::Tracer.start_logging(filename, false, false, false)

Only 4 arugments,
but also it’s difficult to read

Keyword parameter helps you# quoted from my Ruby code
GC::Tracer.start_logging(
filename,
gc_stat: false,
gc_latest_gc_info: false,
rusage: false
Easytounderstand!
)The History of
Keyword parameter

Hash notation at the last argumentfrom beginning of Ruby

Create a
Hash object

foo(1, 2, :key1 => v1, :key2 => v2 )3 arguments# Same as# foo(1, 2, {:key1 => v1, :key2 => v2})

Symbol hash notationfrom Ruby 1.9.3
foo(1, 2, key1: v1, key2: v2)# Same as# foo(1, 2, :key1 => v1, :key2 => v2)# foo(1, 2, {:key1 => v1, :key2 => v2})

Keyword parameters processing
before Ruby 2.0
def foo(a, b, kw={}) # kw is Hash
key1 = kw.fetch(:key1, 1)
key2 = kw.fetch(:key2, 2)# check unknown kws…
Default values
endKeyword parametersfrom Ruby 2.0 (1)def foo(a, b, key1: 1, key2: 2)…
end
Default values(any Ruby’s expression)

We don’t need to write
Hash access any more!

Keyword parametersfrom Ruby 2.0 (2)• Raise an exception when unknown keywords are passed• Rest keyword parameter (**kw) can receive nonspecified keyword parameters
def foo(k1: v1, **kw)
p kw #=> {k2: 2, k3: 3}
endfoo(k1: 1, k2: 2, k3: 3)• Blocks also can accept keyword parameters
foo{|k1: 1, k2: 2| …}

Required keyword parameterfrom Ruby 2.1
def foo(a, b, key1: 1, key2:)…
end
No default value
Need to specify by caller# Similar todef foo(a, b, key1: 1, key2: raise(“err”))…
endThe Implementation of
Keyword parameterImplementation of keyword parameter
Ruby 2.0 and Ruby 2.1• Caller: make a Hash object and pass it normally• Same as Ruby 2.0 and before• Callee: decompose a Hash object and assign tolocal variables correctly• Mostly same code of decomposing code in Ruby
• Need some more error checking

Implementation of keyword parameter
Ruby 2.0 and Ruby 2.1
def foo(k1: v1, k2: v2)…
end
Compiler translate todef foo(h={})k1 = h.fetch(:k1, v1)
k2 = h.fetch(:k2, v2)#(and error check code)…
endExecution time (sec)

Bad NEWS
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” instead of a Hash object

Preparation: Make “keyword list” and“default value list” at compile time
• We can see all source code at compile time
• Collect keywords in a list for each method call
• ex: “foo(k1: x, k2: y)” #=> kwlist is [:k1, :k2]
• Collect “Receive keyword list (Rkwlist)” and “Default
values list (dvlist)” in each method definition• ex: “def foo(k1: 1, k2: 2)” #=> Rkwlist is [:k1, :k2],
dvlist is [1, 2]• ex: “def foo(k1: 1, k2: f2()) #=> dvlist is [1, Qundef]
NOTE: Qundef is internal special value
which should not expose Ruby world

Call with keyword parameter [Sender]
Pass “kwlist” instead of making a Hash
• Pass values as a “keyword list”
foo(k1: 1, k2: 2)

foo(1, 2, kwlist)
NOTE: This is pseudo code.
kwlist is not passed as an argument,
but passed as calling information.

Call with keyword parameter [Receiver]
Manipulate passed kwlist• Assign local variables with passed keyword list
def foo(k1: 1, k2: 2, k3: 3)

Pseudo code

kvs = [1, 2]; kwlist=[:k1, :k2]
Rkwlist = [:k1, :k2, :k3]
dvlist = [1, 2, 3]

def foo(*kvs, kwlist)
Rkwlist.each.with_index{|k, i|
ki = kwlist.index(k)assign(k, ki ? kvs[ki] : dvlist[i])}Call with keyword parameter [Receiver]
Treat with default values with expressions
def foo(k1: 1, k2: f2(), k3: f3())
Pseudo codedef foo(*kvs, kwlist)
unset_bits = 0
Rkwlist.each.with_index{|k, i|
if ki = kwlist.index(k)v = kvs[ki]else if (v = dvlist[i]) == Qundef
v = nilunset_bits[i] = 1
end
assign(k, v)} # cont to right

Rkwlist = [:k1, :k2, :k3]
dvlist = [1, Qundef, Qundef]# k1 is already initialized
k2 = f2() unless unset_bits[1]k3 = f3() unless unset_bits[2]… # start of method body
end

Using BITMAP to remember
unspecified keywords
NOTE: Qundef is internal special value
which should not expose Ruby world

ADVANCED

Q. Why not assign Qundef
directly? (instead of using bitmap)
def foo(k1: 1, k2: f2(), k3: f3())
Pseudo codedef foo(*kvs, kwlist)
unset_bits = 0
Rkwlist.each.with_index{|k, i|
ki = kwlist.index(k)v = ki ? kvs[i] : dvlist[i]assign(k, v)}
k2 = f2() unless k2 == Qundef
k3 = f3() unless k3 == Qundef… # start of method bodyend

Rkwlist = [:k1, :k2, :k3]
dvlist = [1, Qundef, Qundef]

ADVANCED

A. We can access initializing
keyword variables with eval()

def foo(k1: 1,
k2: eval(“k3”), # should be nil
k3: f3())

Evaluation result
Compare 3 types methods
1. def foo6(a, b, c, d, e, f); end• Normal method dispatch with 6 parameters

2. def foo_kw6(k1: 1, k2: 2, k3: 3, k4: 4, k5:
5, k6: 6); end• Default values are immediate values

3. def foo_complex_kw6(k1: 1+1, k2: 2+1,
k3: 3+1, k4: 4+1, k5: 5+1, k6: 6+1); end• Default values are expressions (notimmediate values)

Result: Fast keyword parameters
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

Execution time (sec)Result: Ruby 2.1 vs. Ruby 2.2
20

Removing Hash creation is dramatically effective.

15
10
5
0

Ruby 2.1

Ruby 2.2

Execution time (sec)Result: Ruby 2.2
2

Using immediate default values is effective
Using immediate values

Using non-immediate values

1.5
1
0.5
0

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

foo_kw6

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

Challenge:
Improve computational complexity• Computational complexity of current impl. is O(mn)• Now, m and n is enough small (only a few keywords), but…
n = kwlist.lengthm = Rkwlist.length
Pseudo code

Total computationan complexity: O(mn)def foo(*kvs, kwlist)
Rkwlist.each.with_index{|k, i| # m times
ki = kwlist.index(k)→ O(m)O(n)…

Execution time (sec)Summary
20

Ruby 2.2 optimized“keyword parameters”

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

Ruby 2.2
But still x2 times slower
compare with normal dispatchThank you for your attention
Arigato!
Koichi Sasada<ko1@heroku.com>