Implementation Details ofRuby 2.0 VM
Koichi Sasada

1

Disclaimer• (As you can see) I canspeak English little.

http://www.flickr.com/photos/andosteinmetz/2901325908/– It’s my 8th RubyConf– 7th time disclaimer• Ask me an questions in 日本語
Japanese (WELCOME!), Ruby or
SLOW English• All of I want to say is on the screen.
You can read them.
2

Who am I ?
• Koichi Sasada (笹田耕一）– Matz team at Heroku, Inc.
• Full-time CRuby development– CRuby/MRI committer• Virtual machine (YARV) from Ruby 1.9• YARV development since 2004/1/1– 2.0 Release manager assistant• Organizing feature request– 200 tickets → 100 tickets last week!

• Over 150 mails to ruby-core/ruby-dev– Sorry for spamming3

Ruby 2.0

20th Anniversary Releaseof Ruby language

4Ruby 2.0 Release policy• Compatibility (Ruby level)• Compatibility (Ruby level)• Compatibility (Ruby level)• Usability• Performance

ADD (Anniversary Driven Development)
5

Ruby 2.0 Roadmap
2012/Oct
Feature freeze
2012/Aug“Big-feature” freeze(was ignored)

2012/Dec
Preview2
2012/Nov
Now
Preview1

2013/Jan
RC1

2012/Dec
X’mas
Code freeze

2013/2/24
Ruby 2.0 Release(20th anniversary)
2013/Feb
RC2

Only about *2 months*
to introduce new codes“[ruby-core:40301] A rough release schedule for 2.0.0”
6and Endo-san’s (release manager) leak

Introduction of Ruby 2.0 features

What is introduced?

7

# -*- rd -*= NEWSThis document is alist of user visible
feature changes
made between
releases except for
bug fixes.
Note that each entry
is kept so brief thatno reason behind orreference
information is
supplied with. For afull list of changes
with all sufficient
information, see theChangeLog file.
== Changes since the1.9.3 release=== C API updates* NUM2SHORT() andNUM2USHORT()
added. They are
similar to NUM2INT,
but short.
=== Library updates(outstanding ones
only)
* builtin classes* Array* incompatiblechanges:* randomparameter ofArray#shuffle! andArray#sample now
will be calledwith one argument,
maximum value.
* Enumerable* added method:* addedEnumerable#lazy
method for lazy
enumeration.
* ENV* aliased method:* ENV.to_h is a

ENV.to_hash* Hash* added method:* addedHash#to_h as explicit
conversion method,
like Array#to_a.
* extended
method:*Hash#default_proc=
can be passed nil toclear the default proc.
* Kernel* added method:* addedKernel#Hashconversion method
like Array() or Float().
* addedKernel#using, which
imports refinements
into the current
scope.
[experimental]* extended
method:* Kernel#warn
accepts multiple args
in like puts.
* Kernel#caller
accepts second
optional argument `n'which specify
required caller
size.
* incompatiblechanges:* system() andexec() closes nonstandard filedescriptors(The defaultof :close_others
option is changed totrue by default.)* respond_to?
against a protected
method now returns
false unlessthe second
argument is true.
* __callee__ hasreturned to theoriginal behavior, andnow
returns thethe original name inanaliased method.
* Kernel#inspect
does not call #to_s
anymore(it used to call
redefined #to_s).

* LoadError* added method:* addedLoadError#path
method to return thefile name that could
not beloaded.
* Module* added method:* addedModule#prepend
which is similar to
Module#include,
however amethod in theprepended module
overrides thecorresponding
method in theprepending module.
* addedModule#refine, which
extends a class or
module locally.
[experimental]* addedModule#refinements,
which returns
refinements definedin thereceiver.
[experimental]* addedModule#using, which
imports refinements
into the receiver.
[experimental]* extended
method:*Module#define_meth
od accepts a
UnboundMethodfrom a Module.
*
Module#const_get
accepts a qualified
constant string, e.g.

Object.const_get("Foo::Bar::Baz")

Encoding.default_inte
rnal if it is set.

* NilClass* added method:* added nil.to_h
which returns {}* Fiber* incompatiblechanges:* Fiber#resume
cannot resume a fiber
which invokes"Fiber#transfer".

* Signal* incompatiblechanges:* Signal.trap
raises ArgumentError
when :SEGV, :BUS, :IL
L, :FPE, :VTALRM
are specified.

* Thread* added method:* addedThread#thread_varia
ble_get for getting
thread local variables(these aredifferent than Fiberlocal variables).
* addedThread#thread_varia
ble_set for setting
thread local variables.
* addedThread#thread_varia
bles for getting a listof the thread local
variable keys.
* addedThread#thread_varia
ble? for testing to see
if a particular threadvariable has
been set.

* net/http* new features:* Proxies are now
automaticallydetected from the
http_proxyenvironment
variable. See
Net::HTTP::new for
details.
* gzip and deflate
compression are now
requested for all
requests bydefault. See
Net::HTTP for details.
* SSL sessions are
now reused acrossconnections for asingle instance.
This speeds up
connection by using apreviously negotiatedsession.
* new methods:*
Net::HTTP#local_host*
Net::HTTP#local_host=*
Net::HTTP#local_port*
Net::HTTP#local_port=* extended method:*
Net::HTTP#connect
uses local_host andlocal_port if specified.

* Time* change return
value:* Time#to_s
returned encoding
defaults to US-ASCII
but automatically* net/imap* new methods:*
Net::IMAP.default_port*
Net::IMAP.default_im* Struct* added method:* added
Struct#to_h returning
values with keys
corresponding to theinstance variablenames.

*
Net::IMAP.default_tls_port*
Net::IMAP.default_ssl_port*
Net::IMAP.default_im
aps_port* ostruct* new methods:* OpenStruct#[],[]=*OpenStruct#each_pair* OpenStruct#eql?
* OpenStruct#hash* OpenStruct#to_h
converts the struct toa hash.
* extended method:* OpenStruct.new
also accepts an
OpenStruct / Struct.

Syslog::Logger which
provides a Logger API
atop Syslog.
* Syslog::Priority,
Syslog::Level,
Syslog::Option and
Syslog::Macros
are introduced foreasy detection ofavailable constants
on arunning system.
* lib/tmpdir.rb* incompatiblechanges:* Dir.mktmpdir
uses
FileUtils.remove_entr
y instead of
FileUtils.remove_entr
y_secure. This meansthat applications
should notchange thepermission of thecreated temporary
directory to makeaccessible fromother users.

OpenSSL::ASN1::Primi
tive now raise
TypeError whencalling to_der on an
instance whose
value is nil. All
instances of
OpenSSL::ASN1::Cons
tructive
raise
NoMethodError in
the same case.
Constructing suchvalues is still
permitted.
* TLS 1.1 & 1.2
support by setting
OpenSSL::SSL::SSLCon
text#ssl_version to:TLSv1_2, :TLSv1_2_server, :TLSv1_2_cli
ent
or :TLSv1_1, :TLSv1_1_server:TLSv1_1_client.
The version being
effectively used canbe queried
with
OpenSSL::SSL#ssl_version. Furthermore, it
is also possible toblacklist the new
TLS versions with
OpenSSL::SSL:OP_NO_TLSv1_1 anddecrypting PEMencoded files to be atleastfour characterslong. This led toawkward situations
where an export witha password withfewer than fourcharacters was
possible, butaccessing thefile afterwards
failed.
OpenSSL::PKey::RSA,
OpenSSL::PKey::DSA
andOpenSSL::PKey::EC
therefore now
enforce the same
check when exportingaprivate key to PEM
with a password - it
has to be at least fourcharacterslong.
* SSL/TLS support
for the Next Protocol
Negotiation
extension. Supportedwith OpenSSL 1.0.1
and higher.
*
OpenSSL::OPENSSL_FI
PS allows client
applications to detect
whether OpenSSL
is running in FIPS
mode and to react tothe special
requirements thismight impy.

You can read themat NEWS file* pathname* extended method:* Pathname#find
returns an
enumerator if noblock is given.

* resolv* new methods:*
Resolv::DNS#timeouts=*
Resolv::DNS::Config#t
imeouts=* shellwords*
Shellwords#shellescape() now stringifies
the given object using
to_s.
*
Shellwords#shelljoin()
accepts non-string
objects in the given
array, each ofwhich is stringified
using to_s.
* syslog* zlib* Added streaming
support for
Zlib::Inflate andZlib::Deflate. This
allowsprocessing of a
stream without theuse of large amountsof memory.
* Added support for
the new deflatestrategies Zlib::RLE
and Zlib::FIXED.
* Zlib streams are
now processed
without the GVL. This
allows gzip, zlib anddeflate streams tobe processed inparallel.
* openssl* Consistently raise
an error when trying
to encode nil values.
All instancesof

OpenSSL::SSL::OP_NO_TLSv1_2.
* AddedOpenSSL::SSL::SSLCon
text#renegotiation_cb. A user-defined
callback
may be set whichgets called whenevera new handshake isnegotiated. This
also allows toprogrammaticallydecline (client)
renegotiation
attempts.
* Support for "0/n"splitting of records as
BEAST mitigation via
OpenSSL::SSL::OP_DO
NT_INSERT_EMPTY_F
RAGMENTS.
* OpenSSL requires* yaml* Syck has been
removed. YAML now
completely depends
on libyaml being
installed.
* objspace* new method:*
ObjectSpace.reachabl
e_objects_from(obj)=== Languagechanges* Added %i and %I
for symbol list
creation (similar
to %w and %W).
=== Compatibility
issues (excluding
feature bug fixes)* Signal.trap
See above.
* Merge Onigmo.
https://github.com/ktakata/Onigmo* The :close_others
option is true by
default for system()and exec().
Also, the close-onexec flag is set bydefault for all new filedescriptors.
This means filedescriptors doesn't
inherit to spawned
process unlessexplicitly requested
such as system(...,
fd=>fd).
*Kernel#respond_to?
against a protected
method now returns
false
unless the second
argument is true.
* Dir.mktmpdir in
lib/tmpdir.rb
See above.
* OpenStruct new
methods can conflictwith custom
attributes named"each_pair", "eql?","hash" or "to_h".

8goto :next_topic

Change the title ofthis presentation to...
9

Lecture series of Computer Science

How to make interpreter?
#3 Method dispatch
Prof. Koichi Sasada (*1)
Akihabara University (*2)
*1: Prof. means ...
*2: Of course, joking. No such University 
10Review slide
Requirement and Assumption• You need to finish “Ruby language basic” course• This course uses “Ruby” language/interpreter– One of the most popular languages– Used in world-wide programming• Web application• Text processing• and everything!!

– CRuby• Ruby has many alternative implementations• CRuby has their own VM
11

Review slide
How to implement virtual machine?
• Execute instructions– Execute compiled instructions (bytecodes)– Pointed by “Program counter” (PC)• Stack machine architecture– All of values on the stack– Stack top is pointed by “Stack pointer” (SP)– V.S. Register machine architecture• Advantages and disadvantages• Yunhe Shi, et al: “Virtual machine showdown: stack
versus registers” (2005)

12

Review slide
Stack machine execution (basic)
Ruby Program

a=b+cCompileYARV Instructions

getlocalgetlocalsend
setlocal

b
c
+
a

a
b+c
b

c

c

b+c
b

local env

YARV Stack

PC
Animation with PowerpointSP
13

Review slide[Advanced] Optimization techniques• Peephole optimizations (compiler technique)– Reduce instruction number• Make macro instructions– Operand unification– Instruction unification• Direct threading– Using GCC specific feature• Stack caching– n-level stack caching– Impact on CPU’s branch prediction
14

Review slide[Advanced] VM generator
VM Instrunction
Description

VM generator enables
flexible VM building
Dis-assembler
Assembler

Virtual Machine

Documents

Compiler(Optimizer)
15

Today’s lecture:
Method dispatch# Example
recv.selector(arg1, arg2)• recv: receiver• selector: method id• arg1, arg2: arguments
16

sp

Before method dispatch
1. Evaluate `recv’
2. Evaluate `arg1’ and `arg2’
3. Method dispatch (`selector’)

arg2

arg1
recv
Stack after #2# Ruby’s disassembled bytecodes of Ruby 2.0 trunk
0016 getlocal
recv, 0 # 1 receiver0019 getlocal
arg1, 0 # 2 arg10022 getlocal
arg2, 0 # 2 arg20025 send<callinfo!mid:selector, argc:2, ARGS_SKIP>
17

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
18

Overview
Method search• Search method from `klass’

BasicObject

1. Search method table of `klass’
1. if method `body’ is found, return`body’
2. `klass’ = super class of `klass’ andselector: body
repeat it...

2. If no method is given,
exceptional flow•

In Ruby language,`method_missing’ will be called

Each Class has
method table

KernelObject
C1
C2
19

Overview
Cheking arity and visibility• Checking arity– Compare with given argument number andexpected argument number• Checking visibility– In Ruby language, there are three visibilities (canyou explain each of them ?:-p)• public• private• protected20Overview
Building `local environment’• How to maintain local variables?
→ Prepare `local variables space’ in stack→ `local environment’ (short `env’)• Parameters are also in `env’

21Overview
Building `local environment’
sp

loc2

arg1

ep: env pointer

loc1

sp

arg2

ep

env

arg2

all local variables
are accessible with

arg1

`ep’
(ep[0], ep[-1], ep[-2], ...)

recv

recv

Stack before
method dispatch

Stack after
method dispatch
22

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.

About 7 steps

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

4. And continue VM execution

and simple!
and slow...
23

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

24Method dispatch
Ruby’s case1.

Check caller’s arguments
1.
2.

2.
3.

Check splat (*args)
Check block (given by compile time or block parameter (&block))Get class of `recv’ (`klass’)
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 process25

Ruby’s case
4. Dispatch method with `body’• Previous explanation is for Ruby methods– `body’ (defined as rb_method_definition_t in method.h) has several
types at least the following two types:• Method defined by Ruby code
• Method defined by C function (in C-extension)• Quiz: How many method types in CRuby?
– Hint: At least 2 types (Ruby method and C method)① 3 types② 6 types
Answer is③ 9 types
About
④
11
types
④ 11 types
26

Ruby’s case
Method types
1. VM_METHOD_TYPE_ISEQ: Ruby method (using `def’ keyword)
2. VM_METHOD_TYPE_CFUNC: C method
3.
4.
5.
6.
7.
8.
9.
10.
11.

VM_METHOD_TYPE_ATTRSET: defined by @attr_accessor
VM_METHOD_TYPE_IVAR: defined by @attr_reader
VM_METHOD_TYPE_BMETHOD: defind by `define_method’
VM_METHOD_TYPE_ZSUPER: used in internal
VM_METHOD_TYPE_UNDEF: `undef’ed method
VM_METHOD_TYPE_NOTIMPLEMENTED: not implemet
VM_METHOD_TYPE_OPTIMIZED: optimization
VM_METHOD_TYPE_MISSING: method_missing type
VM_METHOD_TYPE_CFUNC_FRAMELESS: optimization two

There are 11th different method dispatch procedure(dispatch by switch/case statement)27

Ruby’s case• Quiz: I introduce (virtual) registers `pc’, `sp’and `ep’. How many registers in virtual
machine (in Ruby 1.9.x)?
① 4 registers
Answer is② 6 registers
About ④ 11 registers③ 9 registers↓④ 11 registers
Need to store/restore
11 registers
each method call28

Ruby’s caseStore registers• Introduce “control frame stack” to store registers– To store `pc’, `sp’, `ep’ and other information, VM has
another stack named “control frame stack”– Not required structure, but it makes VM simple → Easy tomaintain/* 1.9.3 */11 regs

typedef struct {VALUE *pc;/* cfp[0] */VALUE *sp;/* cfp[1] */VALUE *bp;/* cfp[2] */rb_iseq_t *iseq;/* cfp[3] */VALUE flag;/* cfp[4] */VALUE self;/* cfp[5] / block[0] */VALUE *lfp;/* cfp[6] / block[1] */VALUE *dfp;/* cfp[7] / block[2] */rb_iseq_t *block_iseq;/* cfp[8] / block[3] */VALUE proc;/* cfp[9] / block[4] */const rb_method_entry_t *me;/* cfp[10] */} rb_control_frame_t;/* 2.0 */10 regs
reduced, but many yet

typedef struct {VALUE *pc;/* cfp[0] */VALUE *sp;/* cfp[1] */rb_iseq_t *iseq;/* cfp[2] */VALUE flag;/* cfp[3] */VALUE self;/* cfp[4] / block[0] */VALUE klass;/* cfp[5] / block[1] */VALUE *ep;/* cfp[6] / block[2] */rb_iseq_t *block_iseq;/* cfp[7] / block[3] */VALUE proc;/* cfp[8] / block[4] */const rb_method_entry_t *me;/* cfp[9] */}29

pushedvaluesrb_thread_t::cfp
points current control frame

locals
spval

SP

PC

args

BP

self

pushedvalueslocals

LFP
DFP
flags
SP

spval

BP

args

flags

me
iseq
block
iseq

foo block
iseq

proc
iseq
PC
me
self

pushedvalues

LFP

block
iseq

DFP

proc

locals

SP

PC

BP

self

spval

LFP

me

iseq

args

DFP

pushedvalues

flags

proc

SP

PC

localsBP

self

local[0]

LFP

$~

spval

DFP

$_

args

flags

flipflop
data

Value stackbar iseq

def foo
bar{
..
}
end
def bar
yield
end
foo

block
iseq

me
iseq

foo iseq

per method
Ruby 1.9 VM stacks structure

block
iseq

proc

Control frame

top iseq

30

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
31

Method dispatch
Ruby’s case1.

CHeck caller’s arguments
1.
2.

2.
3.

Check splat (*args)
Check block (given by compile time or block parameter (&block))Get class of `recv’ (`klass’)
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

ComplexandSlow!!!

And continue VM execution
32

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

Pentomino

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

Method33

Homework• Report about “Method Dispatch speedup techniques”
1. Analyze method dispatch overhead on your favorite
application
2. Survey method dispatch speed-up techniques
3. Propose your optimization techniques to improvemethod dispatch performance
4. Implement techniques and evaluate their performance• Deadline: 2012/11/15 (Thu) 23:59 JST• Submit to: Koichi Sasada <ko1@rvm.jp>• This report is important for your grade of this course!
34

Lecture was finished 

Presentation is not finished35

Back to the presentation“Implementation Details of Ruby 2.0 VM”

Report“Optimization techniques for
Ruby’s method dispatch”
Koichi Sasada

36

Speedup techniques
for method dispatch
1. Specialized instructions
Note that these optimizations
may not be my original.
2. Method caching
3. Caching checking results
4. Frameless CFUNC method
5. Special path for `send’ and `method_missing’Introduced techniques from Ruby 2.0
Today’s main subject 37

Method dispatch overheads

1. Check caller’s arguments
2. Search method `body’`selector’ from `klass’
3. Dispatch method with `body’
1. Check visibility and arity

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

38

Optimization
Specialized instruction (from 1.9)
• 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
39

Optimization
Specialized instruction• Pros.
– Eliminate all of dispatch cost (very effective)• Cons.
– Limited applicability• Limited classes, limited selectors• Tradeoff of VM instruction numbers– Additional overhead when not prepared class40

Optimization
Method caching• 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

miss
fill

C1
C2

fill
Global cachehash tablenaive search
41

Optimization
Caching checking results (from 2.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’

42

Optimization
Frameless CFUNC (from 2.0)
• Introduce “Frameless” CFUNC methods– Idea: Several CFUNC doesn’t need method frame• For example, String#length doesn’t need method
frame. It only return the size of given String
1. Check caller’s arguments
2. Search method `body’ `selector’ from `klass’

3. Dispatch method with `body’
Skip here

1.

Check visibility and arity

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

Optimization
Eliminate frame building (from 2.0)
• Compare with specialized instruction– Pros.
• You can define unlimited number of frameless methods– Cons.
• A bit slow compare with specialized instruction• Note that evaluation result I will show you
doesn’t include this techniqueOptimization
Special path for `send’ and `method_missing’ (from2.0)

BeforeAftersend(:foo)send(:foo)

invoke send method(cfunc)search `foo’

invoke `foo’ method

invoke `foo’ method

45

Faster than first date

Evaluation result
Micro benchmarks

Speedup ratio2
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*
vm2_super*0

trunk 2012/10/13

vm2_zsuper*

trunk 2012/10/31
46

Faster than first date

Evaluation results
Applications

1.4
Speedup ratio

1.2
1

app_aobench

0.8

app_factorial

0.6

app_mandelbrot

0.4

app_raise

0.2

app_tak

app_erbapp_fib

app_pentomino

app_strconcat

app_tarai
app_uri0

trunk 2012/10/13

trunk 2012/10/31
47

Future work
• Restructure “method frame”– Reduce required information per frame• Improve “yield” performance– Using something cached48

Conclusion
Method dispatch speed-up• Ruby’s method dispatch is nightmare– Too complex• Speedup upto 50% at simple method dispatchwith new optimizations• Need more effort to achieve performance
improvements49

Other optimizations from 2.0• Introducing Flonum (only on 64bit OSs)
• Lightweight Backtrace capturing• Re-structure VM stacks/ISeq data
• Bitmap marking garbage collection (by nari3)• “require” performance (not by me)

50

Introducing Flonum(only on 64bit CPU)
• Problem: Float objects are not immediate on Ruby 1.9– It causes GC overhead problem• To speedup floating calculation, represent Float object
as immediate object– Specified range Float objects are represented as immediateobject (Flonum) like Fixnum• 1.72723e-77 < |f| < 1.15792e+77 (approximately) and +0.0
• Out of this range and all Floats on 32bit CPU are allocated in heap

– No more GCs! (in most of case)– Flonum and old Float are also Float classes– Proposed by [K.Sasada 2008]– On 64bit CPU, object representation was changed51

0
vm_thread_pass

vm_thread_mutex1

vm3_thread_mutex

vm3_backtracevm2_super*

vm2_raise2*

vm2_poly_method_ov*

vm2_method*

vm2_case*

vm2_array*

vm1_rescue*

vm1_lvar_set*

vm1_length*vm1_float_calc*

vm1_block*

so_sieveso_pidigits

so_nsieve_bits

so_nbody

so_mandelbrot

so_fasta

so_count_words

so_arrayloop_whilelooploop_forio_select

io_file_create

app_tak

app_pentomino

app_factorial

app_answer

Benchmark results

3

2.5

2

1.5

1
clean/flonum

clean/flonum.z

0.5

52

Flonum: Float in Heap (1.9 or before)
On 64bit CPU

All of Float object
are allocated in heap

HEAD

Data structure in heap
contains IEEE754/double- T_FLOAT- Float
- etc

VALUE

IEEE754
Double8B x 6w =48 bytefor Float object-

Flonum: Encoding
IEEE754 double floating number
64bit doubleb63

b62-b52b51-b0s: sign（1bit）

e: exponent (11bit)

m: mantissa (52bit)

54

Flonum: Range
IEEE754 double

b63 b60-b62 b60-b52

b51-b0

Check if e (b52 to b62) is with-in 768 to 1279,
then it can be represent in Flonum.
This check can be done with b60-b62.
(+0.0 (0x00) is special case to detect)55

Flonum: Encoding
IEEE754 double

b63

b61
b62

b51-b0b60-b52

Only “rotate” and “mask”
Ruby’s Flonumb60-b52b51-b0b63

1 0Flonum representation bits (2 bits)#define FLONUM_P(v) ((v&3) == 2)☆ +0.0 is special case (0x02)
56

Flonum:
Object representation on VALUE
FixnumFlonumSymbolQfalse
Qnil
Qtrue
QundefPointer

Non Flonum
Flonum...xxxx xxx1...xxxx xxx1
N/A...xxxx xx10...xxxx 0000 1110 ...xxxx 0000 1100...0000 0000...0000 0000...0000 0100...0000 1000...0000 0010...0001 0100...0000 0110...0011 0100...xxxx xx00....xxxx x000
57

Lightweight Backtrace capturing• Backtrace is Array of String objects– [“file:lineno method”, ...]

• Idea: Capture only ISeqs and translate toString (file and line) only when it is accessed– Backtrace information may be ignored
iseq1

Stringiseq2

String・・・

・・・

iseq_nString58

After Ruby 2.0

What we should do?

59Performance overhead
rdoc
OthersRails
Others

Insn

Insn

MethodBlock
OthersCompileGC

VM

NotRuby

VM

MethodObj
Block
OthersCompileOthers

Cfunc

Obj

GC

NotRuby

OthersCfunc

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

VM techniques• On Rails and other applications, VM is not anbottleneck• On Mathematic, Symbolic computation, VM ismatter– To speedup then, we need compilation framework• 2.0?

61

Object Allocation andgarbage collection• Lightweight object allocation– Sophisticate object creation– Create objects in non-GC managed area

• Sophisticate Garbage collection– Per-type garbage collection– Generational garbage collection• Introduce write barriers with dependable techniques62

Parallelization• Multiple processes• Multiple VMs• Multiple Threads
No time and space to discuss about them!

63Conclusion

Our challenge has
just begun!!
俺たちの戦いはまだ始まったばかりだ！

64

Thank you for your attention
Koichi Sasada
Heroku, Inc.
ko1@heroku.com

65