Towards Ruby 2.0:
Progress of (VM) Internals
The results of “My Code”

Koichi Sasada
Heroku, Inc1

Agenda• Background• Finished work - Ruby 2.0 Internal Changes– Support Module#prepend– Introducing Flonum– New set_trace_func– Controllable asynchronous interrupts– Deep changes• Remaining work - Ruby 2.0 Internal Features– Virtual machine changes• Enable “disabled-optimizing” options• Optimize “send” instruction• Change VM data structures– C APIs for “incomplete features”• Future work – Dreams: After Ruby 2.02Introduction• Koichi Sasada– Heroku, Inc.
• Heroku is a cloud application platform - a new way ofbuilding and deploying web apps.
• No longer a professor – One of CRuby committer• Full-time committer employed by Heroku, Inc.
• Toward Ruby 2.0 (next release)• Matz is my boss.

3

Background
Brief History of Ruby Interpreter
1993 2/24
Birth of Ruby
(in Matz’ computer)

1996/12Ruby 1.0

1995/12Ruby 0.95

1999/12Ruby 1.4

1998/12Ruby 1.2

2000/6
Ruby 1.6

2012/92003/8Ruby 1.8

イマココ

2009/1
Ruby 1.9.0

1st release2000 Book:
Programming Ruby

2004～
Ruby on Rails
4

Background
Ruby 2.0 Roadmap

2012/Sep
イマココ

2012/Aug“Big-feature” freeze(was invalidated?)

2013/2/24
Ruby 2.0 Release(20th anniversary)
2012/Oct
Feature freeze

Quoted from “[ruby-core:40301]
5
A rough release schedule for 2.0.0”

Background
Ruby 2.0 Policy• Compatibility• Compatibility• Compatibility• Usability• Performance6

Finished work
Ruby 2.0 Internal Changes

7Finished work
Ruby 2.0 Internal Changes• Support Module#prepend• Introducing Flonum• New backtrace API “caller_locations”• New set_trace_func related features• Controllable asynchronous interrupts• Deep changes

8Module#prepend• Classes can include modules
module M; end
class C; include M; end• The method search order is “Original ->Included module”
C

M0• Object#extend allow to put module, but it’s
only extend an object
obj

M1

C

M0

Module#prepend• Module#prepend enables to extend the classwhich override original class

C
obj

M1

C

M0

10

Module#prepend• Example– Invoke specific procedure before/after the method
invocation (“around”)
module EachTracer
def each(*args)
before_eachr = super(*args) # call originalafter_each
r
end
end
class Array
prepend EachTracer
def before_each; p :befor_each; end
def after_each; p :after_each; end
end[1, 2, 3].each{|i| p i}#=>
:befor_each
1
2
3:after_each11

Ruby 1.9
or before

C0
super
IClass
M0

M0
super

C1
super
IClass
M1

M1

super
Singleton
class
Class

obj

class C0; end
module M0; end
module M1; end
class C1 < C0
include M0
end
obj = C1.newobj.extend M1

m_tblAfter Ruby 2.0
Module#prepend

M0

C0
super

m_tbl

super

IClassC1

IClass
M0

m_tbl

super
IClassM1

no m_tbl

super
C1

IClass
M2
Class

obj

class C0; end
module M0; end
module M1; end
module M2; end
class C1 < C0
include M0
prepend M1
prepend M2
end
obj = C1.new

M1
m_tbl

M2
m_tbl

super

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 changed14

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

15

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)

17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)18

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)
19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
20

New backtrace API “caller_locations”• Problem: caller() returns an array of strings• Introduce “caller_locations”– Returns an array of object which has methods
such as “lineno”, “path”, etc– caller_locations(0)[0].path #=> “foo.rb”– caller_locations(0)[0].lineno #=> 23• Boost creating backtrace speed by internalchanges→ Speedup exception creation
21

New “set_trace_func”• Problem: set_trace_func is not flexible and slow
• TracePoint API– TracePoint.trace(events) do block end– Specify “events” to invoke– Add new events (block_enter, etc)

• New C APIs
– Rewrite all trace_func related code and enable
lightweight probes for profilers– x2~ faster for “very lightweight” probes
22

Controllable asynchronous interrupts• Problem: Can not make safe program with
Async-interrupts such as TimeoutError• Thread#control_interrupt(hash) do block end– hash contains exception classes as keys andsymbols represents 3 states as values• immediate: interrupt immediately• on_blocking: interrupt only when before blocking• never: never interrupt– Async interrupts specified by hash are masked in
block
23

Controllable asynchronous interrupts# example: Guard from TimeoutError
require 'timeout'
Thread.control_interrupt(TimeoutError => :never) {timeout(10){# TimeoutError doesn't occur here
Thread.control_interrupt(TimeoutError => :on_blocking) {# possible to be killed by TimeoutError# while blocking operation}# TimeoutError doesn't occur here}}24

Deep changes• Remove “finish” frame from control frames• Unify “lfp” and “dfp” into “ep”

• Call “allocation function” directly– Lightweight object allocation– miniruby -I./lib -rbenchmark -e 'GC.disable;Benchmark.bm{|x|x.report{10_000_000.times{Object.new}}}‘ #=>Execution time (sec)– Reduce time of creating method frame (control
frame) is important than reduce time of accessing
local variables
2.5
2
1.5
1
0.5
0
BeforeAfter

25

Remaining tasks for Ruby 2.026

Remaining works
Ruby 2.0 Internal Features• Virtual machine changes– Enable “disabled-optimizing” options– Optimize “send” instruction– Change VM data structures• More supports for Profiler/Debugger• C APIs for “incomplete features”

27Virtual machine changes
Enable “disabled-optimizing” options• Operand/Instruction unification– Unify instruction and specific operand and makeadditional instructions– Macro instructions• Tail-call optimization?
– Eliminate method frame if the call is tail-call– To avoid stack overflow– I prefer auto expanding VM stack than it28

Unification result

29Virtual machine changes
Optimize “send” instruction
Ruby is OO language→ Everything aremethods→ Optimizing Method
call is important__i686.get_pc_th
rb_method_entry
rb_search_methom_core_define_m*__GI___libc_mal__pthread_enable__nptl_deallocate__pthread_disabl_dl_runtime_resol
vm_define_metho__libc_thread_fre__libc_disable_as__i686.get_pc_th
rb_method_entry
add_packed_direc
ruby_stack_check__kernel_vsyscall
rb_add_method
rb_obj_dummy_int_malloc
thread_timer
rb_safe_level
ruby_xmalloc
vm_xmalloc
vm_get_cref
st_numhash_setjmp@plt
st_lookup
start_thread
rb_funcall2
call_cfunc
malloc@plt
vm_call0_dl_fixup
read@plt
vm_exec
st_insert_setjmpselectreadcaller_setup_args_asynccancel
unk.bxynccancel
d_entry
eres@plt
_make
ethod
unk.cx
_tsd
loc
ve
dt
0%
0%
0%
0%
0%
0%
4%e_asynccancel
1%0%
0%
0%
0%

vm_call_method13%vm_setup_method15%
vm_exec_core
66%30

Virtual machine changes
Optimize “send” instruction• Inline cache– More sophisticate cache invalidation protocol– Cache checking results such as visibilities, numberof parameters and so on– Direct C function call path

• Compilation (future work)– JIT compilation only for “send” instruction is
feasible / cost effective– Need to consider about maintenance31

Virtual machine changes
Change VM data structures• Reconstruct rb_control_frame_t– make it small to boost pushing new frames• Introduce rb_code_context_t to represent
code context (iseq + cref + method info + ...)
• Re-arrange boot sequence to make it easy for
application embedded usage32rb_method_entry_t

rb_method_def_t

method_flag: public

type

mark

original_id

m_tbl

called_idbody (iseq, etc)

iv_index_table

klass

alias_count: 1

RClassclassext_t

def

iv_index

method table@i0

initialize

@j

1

a

@k

2

b (alias of a)class CCONST = 1
@iv = 2@@cv = 3
def initialize@i = @j = @k = 0
end
def a
# ...
end
alias b aend

rb_method_def_t
rb_method_entry_t
method_flag: public
mark

type

rb_method_entry_t

original_id

method_flag: public

body (iseq, etc)

markalias_count: 2

called_id

rb_classext_structcalled_id

super: Object

klass

klass

def

def

iv_tblconst_tbl
const table
CONST

1

iv table
@iv

2

@@cv

3

Current method tabledata structure

Current ISeq data structure
catch table entry

ISeq

type
iseq
start, end: trap range
cont, sp: continue info
inline cache entry
key:
vmstatclass
value (union):valuemethodindexline info entry
position (この PC は)
line_info (何行目)
cref stack entry
visibility
class
next (link)

ISeq of m

static data:
namefilename
arg info
bytecode body
← catch_table entries← line info entries
local_table (ID *)stack_max
parent_iseq (直近の親)
local_iseq (lfp 指し先)
mark ary

parentCREF (D)

local

share

local

CREF
(Object)のid)

Bytecode body
Insn
1

Op1
ptr

Op2
ptr

Insn
2

Insn
3

Op1
ptr

Op2
Im
m

ISeq bodymark ary
String“foo”

Regexp/bar/

ISeq obj

Op3Imm

ISeq ofblock2

ISeq of m_c

CREF (C)dynamic data:
self
orig
← inline cache entries
klass (def したクラス)← cref_stack
defined_id (define_method されたときISeq ofblock1

...

Insn
n

parentclass Cclass Ddef m
1.times{# block1
1.times{# block2
}
}
end
end
def m_cendendrb_method_entry_t

RClassmethod_flag: publicclassext_t

klass: Cm_tbl

callee_id: initialize

iv_index_table

original_id: initialize

1

alias_count_ptr

iv_index

method table@i0

initialize

@j

1

a

@k

2

b (alias of a)method_type: iseq
iseq
cref_stackrb_classext_structclass CCONST = 1
@iv = 2@@cv = 3
def initialize@i = @j = @k = 0
end
def a
# ...
end
alias b aend

rb_method_entry_t

rb_method_entry_t

method_flag: public

method_flag: public

klass: C

klass: Ccallee_id: asuper: Object

callee_id: b

original_id: aoriginal_id: a

iv_tblalias_count_ptr

const_tbl

method_type: iseq

method_type: iseq

iseq

iseq

cref_stack

cref_stack

const table
CONST

1

2

alias_count_ptr

iv table
@iv

2

@@cv

3

Proposed method table data structuremethod table
initializeab (alias of a)rb_code_context_t

rb_iseq_t
static data:

type: method | iseq

rb_code_context_t:

iseq
cref_stackother_info

rb_method_info_t

method_flag:
publiccallee_id: aorig_id: aklass
alias_ptr
method_other_inf
2o

rb_code_context_t

type: block | iseq

type
iseq
cref_stackother_info
namefilename
arg info
bytecode body
catch_table entries
line info entries
local_table (ID *)stack_max
parent_iseq (直近の親)mark ary
self

local[1] code

ISeq
RVALUE

local[1] code

iseq

local[1] code

cref_stackother_info

rb_iseq_t

rb_code_context_t

rb_code_context_t

local[1] code

type: class, c_eval| iseq
iseq
ISeq
RVALUE

cref_stackother_info

Proposed code context (iseq) data structure
Value stackrb_code_context_t

T_CLASS

method table

type: method | iseq

classext_t

initialize

iseq

a

cref_stackb (alias of a)other_info

m_tbl
iv_index_tablerb_method_info_t

rb_code_context_t

method_flag:
publictype: method | iseq

callee_id: a

iseq

orig_id: am_tbl

cref_stackklass

iv_index_table

other_info

alias_ptr

T_ICLASS
classext_t

method_other_infomethod table
initializeab (alias of a)rb_method_info_t

method_flag:
publiccallee_id: aorig_id: aklass
alias_ptr
method_other_inf
o2

pushedvaluesCurrent VM stacks structure

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

block
iseq

foo iseq

me
iseq
block
iseq

proc

Control frame

top iseq

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

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

pushed values
localslocal[2] prev
local[1] code
local[0] self

foo block
code

args
pushed values
localslocal[3] spval
local[2] block
local[1] code
local[0] selfbar codeargs
pushed values
localslocal[3] spval
local[2] block
local[1] code
local[0] self

foo code
top iseq
top iseq
klass,
cref
called, orig_id

flipflop
data
$~
$_

args
pushed values
localslocal[3] spval
local[2] block
local[1] code
local[0] selfargs
Value stack

SP

PC

EP

flags:B

SP

PC

EP

flags:M

SP
EP

PC
flags:M

SP

PC

EP

flags:T

Control frame

2.0 VM

pushed values

foo blockcode

localslocal[1] code
local[0] prev

bar codeargs

def foo
bar{
..
}
end
def bar(&b)
b.callend
foopushed values
localsProc

local[2] spval
local[1] code
local[0] block

code
env

args

Env
localspushed values

local[2] spval
local[1] code
local[0] block

SP

PC

EP

flags:B

SP

PC

EP

flags:Margs
top iseq

top iseq
klass,
cref
called, orig_id

flipflopdatapushed values$~

local[2] spval
local[1] code
local[0] blockEPflags:M

SP

PC

args

EP

flags:T$_

localsValue stackSP

Control framePCC APIs for “incomplete features”• Discussion about several features are notcompleted– “require” framework– Instrumentation framework– ...

• Strategy: Introduce “C APIs” secretly andexperiment new features in gem

41

Future work
Dreams: After Ruby 2.0• Compilation• Parallel execution• Pluggable features42

Student’s research: CastOff
A performance improvement tool for ruby1.9.3(1) Use fromruby script

Programmer

require ‘cast_off’
CastOff.compile(
Klass,:Method,binding,
TypeInfo)•Compile Klass#Method•Load compiled binary•Run faster…

(2) Use fromcommand line
$ CastOff “program”
Programmer
Slides from RubyConf2011•Run and Profile“program”•Compile methods
in “program”•Run fasterCompilation flow
Ruby program# Tuning codeclass Sample
CastOff.compile(self, :sample,
binding,:f => Foo)
end

Makefile

CodeManager

C Source

Configuration
Compilation
TargetC build
tools

Code
Generator

C
.conf
.conf
.conf
Configuration
Extention

Slides from RubyConf2011

44

Performance improvements
Execution time ratio（CRuby 1.9.3 / CastOff）
Guard

NoGuard

90

7

1.2

80

6

1

70

5

faster

60
50

4

40

3

30

0.8
0.6
0.4

2

20

0.2

1

10
0

0
bm_nested_loop.rb bm_mandelbrot.rb

bm_tarai.rb0
bm_sieve.rb bm_lists.rb

Slides from RubyConf2011

bm_rdocParallel Execution• Run threads in parallel (JRuby, MacRuby, …)– Good: Well known approach– Bad: Difficult to make safe/correct multi-threaded
programs• Many tragedy (in Java, etc.)– Bad: Difficult to make efficient implementation with
fine-grain lock
• Parallel processes (dRuby, …)– Good: No need to implement– Bad: Marshal overheads
Slides from RubyConf2011

46

Support friendly
Coarse-grained parallel computing• Encourage Multi-process– Traditional well-known approach– Toward advanced dRuby• Multi-VM– VMs in one process– Light-weight communication

Slides from RubyConf201147

Student’s reseachTunnel: Inter-process
communication w/shared memory• Object transfer w/ shared memory

Slides from RubyConf201148

Student reserch (cont.)
Space: Inter-process
Space w/shared memory• Shared space between ruby processes– Similar to Linda/Rinda

Slides from RubyConf201149

Evaluation of Tunnel

Slides from RubyConf201150

Parallel Execution
MVM

Slides from RubyConf2011

51

Parallel Execution
Multiple-VM (MVM) on Ruby
• Multiple VMs in one process– VMs are completely isolated (Each VM has an independent object
space (heap))– VMs run in parallel• Each VM has own GVL (w/o fine grained lock)

Ruby process
Ruby VM

Ruby VM
GVL

ThreadThreadSerial execution w/GVL

Channel- Passing References- Memory copy
Slides from RubyConf2011

GVL

ThreadThread52

Our Approach
Multiple-VM (MVM) on Ruby
• Channel: Inter-VM Communication mechanism– The only way to communicate with other VMs– Simply passing references or copying memory in the same
address space
Ruby process

Share the same address space

Ruby VM

Ruby VM
GVL

ThreadThreadSerial execution w/GVL

Channel- Passing References- Memory copy
Slides from RubyConf2011

GVL

ThreadThread53

Evaluation
HTML rendering app• Master dispatch string to worker and worker
returns rendered HTML.
Ruby process
Master VM

StringWorker VM

RenderedHTML
54
Slides from RubyConf2011

54

Evaluation
HTML rendering app
987

Speedup ratio

6
5
Processes+pipe

4

MVM+channel
3
2
1
0
0

5

10

15
# of VMs/Processes

20

Slides from RubyConf2011

25

30

55

Evaluation
DB app••••Benchmark assuming web application
Several front-end VMs and one DB VM
YUBIN-Number (zip-code) DB on memory
Using dRuby (w/MVM) framework
Ruby process
Front-end VM

Query String(YUBIN#)

Result String(Address)

DB VM
On memory
YUBIN# DB

56
Slides from RubyConf2011

56

Evaluation
DB appQuery/sec

Slides from RubyConf2011

57

Future work on MVM/Parallel••

Extend this communication channel between inter-process (w/ shared memory),
inter-nodeMigratable Ruby activity (threads, blocks (closures) and so on)

Node

Node

Ruby Process

Ruby Process

VM

ThreadVM

ThreadChannelVM

ThreadThreadVM

ThreadChannelThreadThreadThreadChannelRuby Process
VM

ThreadThreadVM

Thread(Abstract)
Shared Object Space

ThreadsharedobjectSlides from RubyConf2011

sharedobject58

Summary• Finished work - Ruby 2.0 Internal Changes• Remaining work - Ruby 2.0 Internal Features• Future work – Dreams: After Ruby 2.0

We will release Ruby 2.0 next year!
Don’t miss it!

59Thank you!
Koichi Sasada
Heroku, Inc.
ko1@heroku.com

60