YARV
Progress Report
RubyConf 2005 Oct. 14

SASADA Koichi
Tokyo University of Agriculture and Technology
Nihon Ruby no Kai

Ko1@atdot.net

1

Agenda Self Introduction and Japanese Activities
 Overview of YARV Goal of YARV Current YARV Status• YARV Design, Optimization Review• Evaluation

 Conclusion

2

Self Introduction
 “SASADA” the family name
 “Koichi” is given name → “ko1” A Student for Ph.D. 2nd grade

Not aSon-shi• Systems Software for Multithreaded Arch.

• SMT / CMP or other technologies• i.e.: Hyper threading (Intel), CMT (Sun), Power (IBM)• OS, Library, Compiler and Interpreter• YARV is my first step for Parallel interpreter (?)• Computer Architecture for Next Generation

At Public Position3

Well known asTakahashi
Self Introduction (cont.)
Method Nihon Ruby no Kai• Organized by Mr. Takahashi (maki) Rubyist Magazine (http://jp.rubyst.net/magazine)• vol. 10 at 10 Oct. 2005
• 1 anniversary at 6 Sep. 2005 (vol. 9)
thstth Ruby-dev summary English Diary some days

• But retired…

4

OverviewofYARV
5

Overview: Background Ruby is used world-wide,

one of the Most Comfortable
Programming Language
 Ruby is slow, because interpreter

doesn’t use Virtual Machine techniques→ We need RubyVM!
6

Overview: YARV YARV: Yet Another RubyVM• Started development on 1 Jan. 2004st

• At that time, there were some VMs for Ruby

• Simple Stack Virtual Machine http://www.atdot.net/yarv/
 Ruby’s license, of course

7

Overview:
FAQ (review of last year FAQ) Q: How does “YARV” pronounce?
 A: You can pronounce “YARV” what you like.
 Q: Should I remember the name of “YARV”?
 A: No.

If YARV succeeds, it renames to Rite, if
doesn’t, no one remember YARV.
• About YARV, name is NOT important Q: YARV will be Ruby 2.0?
 A: I hope so. But Matz will decide it.
8Overview:
YARV System
Ruby Program

Compiler

AOT Compiler

YARV Instruction
Sequence

C Souce

JIT Compiler
Native code

Virtual Machine

C Compiler
Extension Lib.
9

Overview:
Current Interpreter
Abstract Syntax Tree

Ruby Program
Parse

a=b+c
Current Interpreter
traverses AST
directlya=Method
Dispatch(:+)
bc10

Overview
YARV - Stack Machine
Ruby Program

a=b+cCompileYARV Instructions

getlocalgetlocalsendsetlocalbc+aab+cbccb+cb
YARV Stack11

The GoalofYARV12

The Goal of YARV YARV: Yet Another RubyVM→ The RubyVM• To be the Ruby 2.0 VM Rite Fastest Ruby Interpreter• Easy to beat current fastest VM
13

The Goal of YARV (cont.)
 Support all Ruby features

New features• Include Ruby 2.0 new syntaxes

 Native Thread Support• Concurrent execution (Giant VM lock)• Parallel execution on parallel machine Multi-VM Instance• Same as MVM in Java
14

Goal: Ruby 2.0 syntax
 Matz will decide it  “{|…| … }” == “->(…){ … }”
 Multiple-values

Really?

• Same as Array? Or first classmultiple-values support?

 Selector-namespace?
15

Goal:
Native Thread Support
 Three different thread models
 Model 1: User-level thread (Green Thread)• Same as current Ruby interpreter

 Model 2: Native-thread with giant VM lock

• Same as current Ruby interpreter• Easy to implement

 Model 3: Native-thread with fine grain lock• Run ruby threads in parallel• For enterprise?

16

Goal: Native Thread Support (cont.)
Current Ruby Interpreter& Model 1
CPU 1

Thread 1

Thread 2

Thread 1
OS Thread 1

CPU 2IDLE

17

Goal: Native Thread Support (cont.)
Model 2:Native thread with Giant VM LockThread 1

Thread 1
CPU 1

OS Thread 1

LockThread 2Lock
OS Thread 2

CPU 2

IDLE
18

Goal: Native Thread Support (cont.)
Model 3:Native thread with Fine Grain Lock
CPU 1

Thread 1

Busy
CPU 2

OS Thread 1

Thread 2
OS Thread 2
19

Goal: Native Thread Support
Summary
Model 1Model 2Model 3

Scalability

BadBad?

BestLock overhead

NoSomeHigh

Impl. Difficulty

Norm.

Easy

Hard

Portability

GoodBadBad20

Goal:
Multi-VM Instance
Current Ruby Process

Process
Ruby Interpreter (VM)
Ruby Process with Multi-VM Instance

Process

Ruby
Interpreter (VM)
Ruby インタープリタ（VM）

Ruby インタープリタ（VM）
Ruby インタープリタ（VM）
21

Goal: Multi-VM Instance (cont.) Current Ruby can hold only 1 interpreterin 1 process• Interpreter structure causes this problem• Using many global variables Multiple-VM instance• Running some VM in 1 process• It will help ruby embedded applications• mod_ruby, etc

22Multi-VM Instance +Thread Model 2
Thread 1

Thread 1

OS Thread 1

Lock of VM1
CPU 1

Lock of VM1

Thread 2

Busy
CPU 2

OS Thread 2

VM1Thread 1 on VM 2

Lock of VM2

OS Thread 3

23

VM2

Review
Summary with MV
M1

M2

M2+MV

M3

Scalability

Bad

Bad?

Lock overhead

None

Some Some HighImpl. Difficulty

Norm.

Easy

Easy Hard

Portability

GoodBad

Bad

Good Best

Bad24

Goal: Load Map
 All Ruby features support• Feb. 2006 …?

 Native Thread Support• Experimental: Dec. 2005
• Complete: 2006?(model 2) 2007?(model 3) Multi-VM Support• Experimental: Feb. 2006
• Complete: 2006?
25

StatusofYARV
26

Status: System
Ruby Program
AlmostIncomplete

Compiler

AOT Compiler

AlmostYARV Instruction

Not yetJIT Compiler
AlmostNative code

Virtual Machine

C SouceC Compiler
Extension Lib.
27

Status:
Supported Ruby Features
 Almost all Ruby features Not supported:… {|*arg| …}• Few syntaxes• Visibility• Safe level ($SAFE)• Some methods written in C for current Ruby
implementation• Around Signal• C extension libraries• Because yarv can’t run “mkmf.rb”
28

Status: Versions
 0.2: YARV as C Extension• Need a patch to Ruby interpreter 0.3 (2005-8): YARV as Ruby Interpreter• Merged to Ruby source code (Ruby 1.9 HEAD)• Maintained on my Subversion repository Latest version: 0.3.2• Native thread (pthread / win32) supports on model 229

YARV 0.2.x
Ruby Interpreter
Evaluator
PatchedUsing C API

Use as C Extension

YARV
Compiler
VM
Optimizer
30

YARV 0.3.x
YARV merged with Ruby Interpreter
Future Work
Generational GC

m17n
Selector Namespace…

YARV
Compiler
VM
Optimizer
31

Status:Compile & Disasm CGI
 http://www.atdot.net/yc/32

Status:VM Design 5 registers• PC: Program Counter• SP: Stack Pointer• CFP: Control Frame Pointer• LFP: Local Frame Pointer• DFP: Dynamic Frame Pointer Some stack frame Control stack and value stack33

Status:VM Design – Stack Frame
Stack

LFP
PC
SPBP
ISEQ
Self
LFP
DFP
…

Ctrl
Frame

…

…

…

Args
Locals

Args
Locals

Args
Locals

Block
Ptr

Prev
Env Ptr

Prev
Env Ptr

DFPSP

CFPCtrl
FrameCtrl
FrameControl FrameStack34

Status:VM Design – Closure
HEAP…
Args
LocalsDFP

Proc（Closure）

Prev
Env Ptr

LFP

Env.
Env.
Env.
35

Status:VM Design – Exception
Call Graph of YARV Execution

SearchException
Table
If not match,
longjmp

VM handler Func (setjmp)
VM Func
C Func
VM handler Func(setjmp)
VM Func
C FuncRaise withlongjmp

36

Status:
VM Generator (in Ruby)
VM Instrunction
Description

AOT Compiler

C Source
Dis-assembler
Assembler

Virtual MachineCompiler(Optimizer)

Documents
Future work
Verifier37

Status:
Optimization
 Simple Stack Virtual Machine• Re-design Exception handling Peep-hole optimization on compile time

• I gave up static program analysis• Dynamicity is your friend, but my ENEMY

 Direct Threaded code with GCC

38

Status: Optimization (cont.) Specialized Instruction• i.e.) Ruby program “x+y” compiled to special instruction
instead of a method dispatch instruction// Specialized “+” instruction
instruction opt_plus(x, y){if(x is Fixnum && y is Fixnum)
if(Fixnum#+ is not re-defined)
return x+y;
return x.+(y);39Status: Optimization (cont.) In-line Cache• In-line Method Cache• In-line Constant Value Cache• Because Ruby’s “Constant Variable” is not Constant!

 Embed values in an Instruction sequence40

Status: Optimization (cont.)
In-line Constant Value cache
Ruby Program
A::B::C

getinlinecacheputnilcompilegetconstant A
optimized getconstant B
putnilgetconstant C
getconstant A
setinlinecachegetconstant B
Skip if value is cached!
getconstant C
41

Status: Optimization (cont.) Unified Instruction• Operands Unification• Insn_A x → Insn_A_x• Instructions Unification• Insn_A, Insn_B → Insn_A_B

 Unified instructions are auto generated byVM generator• I only decide which instructions should becombined.

42

Status: Optimization (cont.)
 Stack Caching• 2 registers, 5 states• putobject (put 1 values on stack)• putobject_xx_ax• putobject_ax_ab• putobject_bx_ba• putobject_ab_ba• putobject_ba_ab

43Status: Optimization (cont.)
Stack Caching
Ruby Program

v1 = v2 + v3
YARV Insns

Reg Ab+cv1

regA
b+cv2

v2

Reg Bv3

regB
v3

getlocal_xx_ax
getlocal v2 v2getlocal_ax_ab
getlocal v3 v3 No need toYARV
send_ab_ax
send+ + touch the Stack
Stack
setlocal_ax_xx
setlocal v1 v1

44

Status: Optimization (cont.)
 JIT Compilation• I made easy one for x86, but…
• Too hard to do alone. I retired.

 AOT Compilation• YARV bytecode → C Source• Easy to develop• Hard to support exception
45

Status: Demo
 YARV Building Demo?
 YARV Running Demo?

46

Status: Evaluation
Fast
Max.times{}i=0i+=1 while i<Max

Yield Blockis not fast

Base: only base VM
OU: Operand Unification IMC: Inline Method Cache
DTC: Direct Threaded Code IU: Instruction Unification SC: Stack Caching
SI: Specialized Instruction

47

Status: Evaluation (cont.)

x20 Faster48

Status: Evaluation (cont.)
No speed-up.
VM is not bottleneck.

BignumRegexp

Objectallocation

Build Exception
49
objectStatus: Evaluation (cont.)
Compare with other languages
Slow50Status: Awards
 2004: Funded by IPA Exploratory Software

Development “Youth”• IPA: Information-technology Promotion Agency,Japan 2005: Funded by IPA Exploratory Software

Development (continuance)• I can’t walk away from the development  2004: Got Award as “Super Creator” from IPA
51

Conclusion
52

Conclusion
 YARV supports almost Ruby syntaxes
 YARV supports some Ruby libraries• But can’t build Extension Libraries• Because YARV can’t run “mkmf.rb”

 YARV 0.3.2 supports native thread YARV achieves significant speedup for

Ruby programs execution which have
VM bottleneck• This means that we can enjoy Symbol
Programming with Ruby53

Conclusion: Future work Support all Ruby features• At least, YARV must work with “mkmf.rb”

 Support every Thread Model• Especially model 2 and 3

 Support Multi-VM Instance54

How Can You Help me Any comments are welcome• Build reports, Bug reports, architecture reports, …

 yarv-devel Mailing List

• English ML for YARV development• Matz and other Japanese also join

 YARVWiki• http://yarv.rubyforge.org/pukiwiki/pukiwiki.php

Give me a job (I’ll finish my course 2 years later)55

Special Thanks
 Matz the architect of Ruby
 IPA: Information-technology Promotion

Agency, Japan (my sponsor)
 Gabriele Renzi, Ippei Tate YARV development ML subscribers• Yarv-dev (Japanese)• Yarv-devel (English)

 All rubyists

56

Finish“YARV Progress Report”
Thank you for your attention.
Any Questions?

SASADA Koichi
ko1@atdot.net
57