(Implementation Details of Ruby 2.0 VM).succ

笹田 耕一
Koichi Sasada

ko1@atdot.net@koichisasada

1(“Implementation Details of Ruby 2.0 VM”).succ#=> "Implementation Details of Ruby 2.0 VN"

笹田 耕一
Koichi Sasada

ko1@atdot.net@koichisasada

2

(Implementation Details of Ruby 2.0 VM).succ!=
Ruby 2.0 sucks
笹田 耕一
Koichi Sasada

ko1@atdot.net@koichisasada

3

(Implementation Details of Ruby 2.0 VM).succ==
Ruby 2.0 Rocks!
笹田 耕一
Koichi Sasada

ko1@atdot.net@koichisasada

4

Disclaimer• (As you can see) I canspeak English little.
• 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.

http://www.flickr.com/photos/andosteinmetz/2901325908/

5

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• Many mails to ruby-core/ruby-dev
6Matz team at Heroku, Inc.
Matz @ Shimane
Boss

ko1 @ Tokyome

Communication
with Skype

Nobu @ Tochigi
Drunker7

Commit number/day of Ruby's trunk
90
80
70
60
50
40

total

30
20
10
0

8

Commit number/day of Ruby's trunk
90
80
70
60
50
40
30

total
matz

20
10
0

9

Commit number/day of Ruby's trunk
90
80
70
60
50
40
30
20

total
matz
ko1

10
0

10

Commit number/day of Ruby's trunk
90
80
70
60
50
40
30
20

total
matz
ko1
nobu

10
0

11

Today’s topics• Ruby 2.0 Features• Ruby 2.0 Optimizations – Method dispatch• After Ruby 2.0

12Ruby 2.0
20th Anniversary Releaseof Ruby language
will be release at
2013/02/24(Fixed)ADD (Anniversary Driven Development)

13

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

14

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

2012/Dec
Now
Preview2

2012/Nov
Preview1

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

2013/Jan
RC1

2012/Dec
X’mas
Code freeze

2013/Feb
RC2

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

Introduction of Ruby 2.0 features

What features are introduced?

16

# -*- rdoc -*= NEWS for Ruby 2.0.0
This document is a list of user
visible feature changes madebetweenreleases except for bug fixes.
Note that each entry is kept so
brief that no reason behind orreference information is
supplied with. For a full list ofchangeswith all sufficient information,
see the ChangeLog file.
== Changes since the 1.9.3
release=== C API updates* NUM2SHORT() andNUM2USHORT() added. They
are similar to NUM2INT, but
short.
* rb_newobj_of() and
NEWOBJ_OF() added. They
create a new object of a givenclass.
=== Library updates(outstanding ones only)* builtin classes* Array* added method:* added Array#bsearch forbinary search.
* incompatible changes:* random parameter ofArray#shuffle! andArray#sample now
will be called with one
argument, maximum value.
* when given Range
arguments, Array#values_at
now returns nil for eachvalue that is out-of-range.
* Enumerable* added method:* added Enumerable#lazy
method for lazy enumeration.
* Enumerator* added method:* added Enumerator#size
for lazy size evaluation.
* extended method:* Enumerator.new accept
an argument for lazy size
evaluation.
* ENV* aliased method:* ENV.to_h is a new alias
for ENV.to_hash* Fiber* incompatible changes:* Fiber#resume cannot
resume a fiber which invokes"Fiber#transfer".
* File* extended method:* File.fnmatch? now
expands braces in the pattern
if
File::FNM_EXTGLOB
option is given.
* GC* improvements:* introduced the bitmap
marking which suppresses tocopy a memory page
with Copy-on-Write.
* introduced the nonrecursive marking which
avoids unexpected stack
overflow.
* GC::Profiler* added method:* added
GC::Profiler.raw_data which
returns raw profile data for GC.
* Hash* added method:* added Hash#to_h as
explicit conversion method,
like Array#to_a.
* extended method:* Hash#default_proc= canbe passed nil to clear thedefault proc.

* __callee__ has returnedto the original behavior, andnow
returns the called namebut not the original name in analiased method.
* Kernel#inspect does notcall #to_s anymore(it used to call redefined#to_s).
* LoadError* added method:* added LoadError#path
method to return the filename that could not beloaded.
* Module* added method:* added Module#prepend
which is similar to
Module#include,
however a method in theprepended module overrides
thecorresponding method in
the prepending module.
* added Module#refine,which extends a class or
module locally.
[experimental]* addedModule#refinements, which
returns refinements defined inthereceiver. [experimental]* added Module#using,which imports refinements
into the receiver.
[experimental]* extended method:* Module#define_method
accepts a UnboundMethodfrom a Module.
* Module#const_get
accepts a qualified constantstring, e.g.

* added nil.to_h which
returns {}* Process* added method:* added getsid for getting
session id (unix only).
* Range* added method:* added Range#size for lazy
size evaluation.
* added Range#bsearch forbinary search.
* Signal* added method:* added Signal.signame
which returns signal name* incompatible changes:* Signal.trap raises
ArgumentError
when :SEGV, :BUS, :ILL, :FPE, :VTALRMare specified.
* String* added method:* added String#b returninga copied string whose
encoding is ASCII-8BIT.
* change return value:* String#lines now returns
an array instead of an
enumerator.
* String#chars now returns
an array instead of an
enumerator.
* String#codepoints now
returns an array instead of an
enumerator.
* String#bytes now returns
an array instead of an
enumerator.

variable has been set.
* addedThread#backtrace_locations
which returns similar
information of
Kernel#caller_locations.
* incompatible changes:* Thread#join andThread#value now raises a
ThreadError if target threadis the current or mainthread.
* Time* change return value:* Time#to_s returned
encoding defaults to US-ASCII
but automaticallytranscodes to
Encoding.default_internal if it
is set.
* TracePoint* new class. This class is
replacement of set_trace_func.
Easy to use and efficient
implementation.
* toplevel* added method:* addedmain.define_method which
defines a global function.

* 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 and local_port if
specified.
* net/imap* new methods:* Net::IMAP.default_port*
Net::IMAP.default_imap_port*
Net::IMAP.default_tls_port*
Net::IMAP.default_ssl_port*
Net::IMAP.default_imaps_port* objspace* new method:*
ObjectSpace.reachable_objects_from(obj)* openssl* Consistently raise an error
when trying to encode nil
values. All instancesof OpenSSL::ASN1::Primitive
now raise TypeError whencalling to_der on an
instance whose value is nil.
All instances of
OpenSSL::ASN1::Constructive
raise NoMethodError in thesame case. Constructing suchvalues is still
permitted.
* TLS 1.1 & 1.2 support by
setting
OpenSSL::SSL::SSLContext#ssl_
version to:TLSv1_2, :TLSv1_2_server, :TLSv1_2_client
or :TLSv1_1, :TLSv1_1_server:TLSv1_1_client. The version
being effectively used can bequeriedwith
OpenSSL::SSL#ssl_version.
Furthermore, it is also possible
toblacklist the new TLS
versions with
OpenSSL::SSL:OP_NO_TLSv1_1
and

OpenSSL::SSL::OP_DONT_INSE
RT_EMPTY_FRAGMENTS.
* OpenSSL requires
passwords for decrypting
PEM-encoded files to be atleastfour characters long. This
led to awkward situations
where an export witha password with fewer thanfour characters was possible,
but accessing thefile afterwards failed.
OpenSSL::PKey::RSA,
OpenSSL::PKey::DSA and
OpenSSL::PKey::EC
therefore now enforce thesame check when exporting a
private key to PEM with apassword - it has to be at least
four characterslong.
* SSL/TLS support for the
Next Protocol Negotiation
extension. Supportedwith OpenSSL 1.0.1 andhigher.
* OpenSSL::OPENSSL_FIPS
allows client applications todetect whether OpenSSL
is running in FIPS mode andto react to the special
requirements thismight impy.

This version is largely
backwards-compatible withprevious rdoc versions.
The most notable change isan update to the ri data format(ri data must
be regenerated for gems
shared across rdoc versions).
Further API changes
are internal and won't affectmost users.
See
https://github.com/rdoc/rdoc/
blob/master/History.rdoc for alist ofchanges in rdoc 4.0.
* resolv* new methods:* Resolv::DNS#timeouts=*
Resolv::DNS::Config#timeouts=* rexml* REXML::Document#write
supports Hash arguments.
* REXML::Document#write
supports new :encoding
option. It changes
XML document encoding.
Without :encoding option,
encoding in
XML declaration is used for
XML document encoding.

now stringifies the given
object using to_s.
* Shellwords#shelljoin()
accepts non-string objects in
the givenarray, each of which isstringified using to_s.
* syslog* Added Syslog::Logger which
provides a Logger API atop
Syslog.
* Syslog::Priority,
Syslog::Level, Syslog::Option
and Syslog::Macros
are introduced for easy
detection of available
constants on arunning system.
* tmpdir* incompatible changes:* Dir.mktmpdir uses
FileUtils.remove_entry insteadof
FileUtils.remove_entry_secure.
This means that applications
should notchange the permission of
the created temporary
directory to makeaccessible from other users.

You can read themat NEWS file

* Kernel* added method:* added Kernel#Hashconversion method like Array()or Float().
* added Kernel#using,which imports refinements
into the current scope.
[experimental]* added Kernel#__dir__which returns a current
dirname.
* addedKernel#caller_locations which
returns an array offrame information objects.
* extended method:* Kernel#warn accepts
multiple args in like puts.
* Kernel#caller accepts
second optional argument `n'which specify
required caller size.
* Kernel#to_enum andenum_for accept a block forlazy size evaluation.
* incompatible changes:* system() and exec()
closes non-standard filedescriptors(The defaultof :close_others option ischanged to true by default.)* respond_to? against a
protected method now
returns false unlessthe second argument istrue.

Object.const_get("Foo::Bar::Baz")* Mutex* added method:* added Mutex#owned?
which returns the mutex isheld by current
thread or not.
[experimental]* incompatible changes:* Mutex#lock,Mutex#unlock,Mutex#try_lock,Mutex#synchronize
and Mutex#sleep are nolonger allowed to be usedfrom trap handler
and raise a ThreadError insuch case.
* Mutex#sleep may
spurious wakeup. Check after
wakeup.
* NilClass* added method:* Struct* added method:* added Struct#to_h
returning values with keys
corresponding to theinstance variable names.
* Thread* added method:* addedThread#thread_variable_get
for getting thread local
variables(these are different thanFiber local variables).
* addedThread#thread_variable_set
for setting thread local
variables.
* addedThread#thread_variables forgetting a list of the thread
local
variable keys.
* addedThread#thread_variable? fortesting to see if a particularthread* cgi* Add HTML5 tag maker.
* CGI#header has beenrenamed to CGI#http_header
andaliased to CGI#header.
* When HTML5 tagmakercalled, overwrite CGI#header,
CGI#header function is tocreate a <header> element.
* iconv* Iconv has been removed.
Use String#encode instead.

* io/wait* new features:* added IO#wait_writable
method.
* added IO#wait_readable
method as alias of IO#wait.

* net/http* new features:* Proxies are now
automatically detected fromthe http_proxy environment
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 across connections fora single instance.
This speeds up connection
by using a previously
negotiated session.

OpenSSL::SSL::OP_NO_TLSv1_
2.
* AddedOpenSSL::SSL::SSLContext#ren
egotiation_cb. A user-defined
callback
may be set which gets called
whenever a new handshake isnegotiated. This
also allows toprogrammatically decline(client) renegotiation attempts.
* Support for "0/n" splittingof records as BEAST mitigation
via

Doubled from Nov/2012* ostruct* new methods:* OpenStruct#[], []=* OpenStruct#each_pair* OpenStruct#eql?
* OpenStruct#hash* OpenStruct#to_h converts
the struct to a hash.
* extended method:* OpenStruct.new also
accepts an OpenStruct / Struct.

* pathname* extended method:* Pathname#find returns an
enumerator if no block is given.
* rake* rake has been updated toversion 0.9.5.

This version is backwardscompatible with previous rakeversions andcontains many bug fixes.
See

http://rake.rubyforge.org/doc/
release_notes/rake0_9_5_rdoc.html for a listof changes in rake 0.9.3,
0.9.4 and 0.9.5.
* rdoc* rdoc has been updated toversion 4.0* RubyGems* Updated to 2.0.0.preview2
RubyGems 2.0.0 features
the following improvements:* Improved support for
default gems shipping withruby 2.0.0+* A gem can have arbitrary
metadata throughGem::Specification#metadata* `gem search` now defaults
to --remote and is anchoredlike gem list.
* Added --document toreplace --rdoc and --ri. Use -no-document todisable documentation, -document=rdoc to only
generate rdoc.
* Only ri-format
documentation is generated
by default.
* `gem server` uses
RDoc::Servlet from RDoc 4.0 togenerate HTML
documentation.

* yaml* Syck has been removed.
YAML now completelydepends on libyaml being
installed.

* zlib* Added streaming support
for Zlib::Inflate andZlib::Deflate. This allows
processing of a stream
without the use of large
amounts of memory.
* Added support for the new
deflate strategies Zlib::RLE andZlib::FIXED.
* Zlib streams are now
processed without the GVL.
This allows gzip, zlib anddeflate streams to beprocessed in parallel.

These methods no longer
return an Enumerator,
although passing a
block is still supported forbackwards compatibility.
Code likestr.lines.with_index(1) { |line,
lineno| ... } no longer
works because str.lines
returns an array. Replace lines
witheach_line in such cases.
* Signal.trap
See above.
* Merge Onigmo.
https://github.com/ktakata/Onigmo* The :close_others option istrue by default for system()and exec().
Also, the close-on-exec flagis set by default for all new filedescriptors.
This means file descriptors
doesn't inherit to spawned
process unlessexplicitly requested such assystem(..., 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 conflict with custom
attributes named"each_pair", "eql?", "hash"or "to_h".

=== Language changes* Thread#join, Thread#value* Added %i and %I for symbol
list creation (similar to %w
and %W).

See above.

* Default source encoding ischanged to UTF-8. (was USASCII)* Mutex#lock, Mutex#unlock,Mutex#try_lock,Mutex#synchronize andMutex#sleep
See above.

For an expanded list of
updates and bug fixes see:=== Compatibility issues(excluding feature bug fixes)

https://github.com/rubygems/
rubygems/blob/master/Histor
y.txt* Array#values_at* shellwords* Shellwords#shellescape()* String#chars* String#codepoints* String#bytes

See above.
* String#lines

17

Ruby 2.0 Main features• Traces– TracePoint– DTrace

Internal
Inspection• Inspection

Ruby 2.0 introduces
huge inspection support– caller_locations– debug_inspector API• Memory inspection– ObjectSpace.reachable_objects_from(obj)– GC.stat[:total_allocated_object]
18

Internal Inspection features• Generally, you don’t need to use these
inspection features• If you got a trouble, please remember
inspection features

Nobody knows, so I
introduce them today
19TracePoint• OO designed set_trace_func• Usage# old style
set_trace_func(lambda{|ev,file,line,id,klass,binding|puts “#{ev} #{file}:#{line}”}# new style with TracePoint
trace = TracePoint.trace{|tp|# access event info by methods
puts “#{tp.event}, #{tp.path}:#{tp.line}”}20

TracePoint
Flexible on/off
trace = TracePoint.new{...}
trace.enable do... # enable trace only in this blockend
trace.enabe # enable trace after this point
trace.disalbe{... # disable trace only in this block}21

TracePoint
Events• Same as set_trace_func– line– call/return, c_call/c_return– class/end– raise• New events (only for TracePoint)– thread_begin/thread_end– b_call/b_end
22TracePoint
Filtering events• TracePoint.new(events) only hook “events”

TracePoint.trace(:call, :return){...}...

23

TracePoint
Event info
• Same as set_trace_func– event– path, lineno– defined_class, method_id– binding• New event info
– return_value (only for retun, c_return, b_return)– raised_exception (only for raise)24

TracePoint
Advantages• Advantage of TracePoint compared with
set_trace_func– OO style– On/Off– Lightweight• Creating binding object each time is too costly– Event filtering

25

DTrace• Solaris, MacOSX FreeBSD and Linux has DTrace
tracing features• Ruby interpreter support some events• See https://bugs.rubylang.org/projects/ruby/wiki/DTraceProbes– Not stable. Be careful this probe spec can bechanged before and after Ruby 2.0 release.

Skip this section because I’m not an expert.
26

caller_locations• caller() returns Backtrace strings array.
– like ["t.rb:1:in `<main>'"]• caller_locations() retuns OO style backtrace
information– caller_locations(0).each{|loc|p "#{loc.path}:#{loc.lineno}“}– No need to parse Backtrace string!

• [advanced] caller and caller_locations support
range and 2nd argument like Array#[] to specify
how many backtrace information are needed27

Debug inspection API• Returns all bindings of current stack– Provided as C API– Debugger can use them28Memory inspection
ObjectSpace.reachable_objects_from• ObjectSpace.reachable_objects_from(obj)
returns reachable objects– Examples:(1) When obj is [“a”, “b”, “c”], returns [Array, “a”, “b”, “c”]
(2) When obj is [“a”, “a”], returns [Array, “a”, “a”]
(3) When obj is [a = “a”, a], returns [Array, “a”]
(1)
(2)
array
(3)
Array
array
obj

Array

obj
“b”

“c”

array
obj

Array

“a”

“a”

“a”

“a”

29

Memory inspection
ObjectSpace.reachable_objects_from• You can analyze memory leak. ... Maybe.
• Combination with ObjectSpace.memsize_of()(introduced at 1.9) is also helpful to calculate
how many memories consumed by obj.
array
obj

Array

12 byte“a”
1 byteTotal 14 bytes(this is fake example)“a”
1 byteDEMO

30

Memory inspection
GC.stat[:total_allocated_object]• GC.stat returns implementation dependent GC(memory) usage by hash
– :count means how many GC occurs• From 2.0, two information are added• :total_allocated_object• How many objects are allocated since interpreter launched• :total_freeed_object• How many objects are freed by GC.

– Note that these numbers can be overflow.
31Desirable behavior

100_000.times{|i| ""; # Generate an empty stringh = GC.statputs "#{i}¥t#{h[:total_allocated_object]}¥t#{h[:total_freed_object]}"}Leakey behavior
Live obj#

ary = []
100_000.times{|i| ary << "" # generate an empty string and store (leak)h = GC.statputs "#{i}¥t#{h[:total_allocated_object]}¥t#{h[:total_freed_object]}"}Internal Inspection features
Again• Generally, you don’t need to use these
inspection features• If you got a trouble, please remember
inspection features34

goto :next_topic

Change the title ofthis presentation to...
35

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 
36

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
37

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)

38

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

SP
39

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
40

Review slide[Advanced] VM generator
VM Instrunction
Description

VM generator enables
flexible VM building
Dis-assembler
Assembler

Virtual Machine

Documents

Compiler(Optimizer)
41

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

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

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

KernelObjectC1
C2
45

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

Overview
Building `local environment’• How to maintain local variables?
→ Prepare `local variables space’ in stack→ `local environment’ (short `env’)• Parameters are also in `env’47

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 dispatch48

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...
49

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

50

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 process51

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
52

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)53

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 call54

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] */}55

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

56

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
supported57

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
58

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

Method59

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/12/23 (Sun) 23:59 JST• Submit to: Koichi Sasada <ko1@rvm.jp>• This report is important for your grade of this course!
60

Lecture was finished 

Presentation is not finished61

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

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

62

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 63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’

64

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
65

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 class66

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
67

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’

68

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’
69

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

71

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
72

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
73

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

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
improvements

75

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)76

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 changed77

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

78

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)

80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)81

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)
82

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
83

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_nString84

After Ruby 2.0

What we should do?

85

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. Shiba86

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?

87

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 techniques88Parallelization• Multiple processes• Multiple VMs• Multiple Threads
No time and space to discuss about them!

89Conclusion

90

Conclusion

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

91

謝謝
Thank you for your attention
笹田 耕一
Koichi Sasada
Heroku, Inc.
ko1@heroku.com@koichisasada
92