Past, Present and Future
Koichi “ko1” Sasada
ささだこういち
ko1 at atdot dot net
1

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Ruby Meets VM, Koichi Sasada, EURUKO 2008

RUBY MEETS VM

Ｋｏｉｃｈｉ Ｓａｓａｄａ
ko1 at atdot dot net

2

Point of This Presentation
3

Merging YARV is not a goal,
but a start

YARV: Yet Another RubyVM
Ruby Meets VM, Koichi Sasada, EURUKO 2008

Notice4

I canʼt speak English well, so I write down
all things what I want to say.
 Do you get ready for opera glasses?

 Unfortunately, some slides are written inJapanese

You can ask questions withJapanese, C, Ruby, …, or slow/short English.
“How to impl. Ruby”, not “How to use Ruby”“x50” is too big mouth Maybe x20

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Self Introduction
5Koichi (given name) Sasada (family name) ささだ（family name) こういち (given name) 笹⽥ (family name) 耕⼀ (given name)

Lecturer @ University of Tokyo (Feb. 2008-)
Only VM developer Donʼt have compatibility with Matz Please call me “ko-i-chi”

Ruby Meets VM, Koichi Sasada, EURUKO 2008Agenda
6

History of YARVAdvanced VM Topics
 Performance Parallel Thread Execution
 Embedding Float Value JIT Compiler

 Pre-Compiler

 “Ruby to Compiled file” Compiler
 “Ruby to C” Compiler New Feature Multi-VM Creation

 Customizable Ruby Core Debug/Profile support feature

Summary

Ruby Meets VM, Koichi Sasada, EURUKO 2008

History of YARV
74 Years

 1, Jan 2004

Project Start
 2004-2005 VM Core, Optimization

 Supported by MITO youth Project (IPA) 2005-2006 Thread, etc

 Supported by MITO Project (IPA) 1, Apr 2006 Got a Job (Assistant on U-Tokyo)

 2006-2007 etc, etc

 Supported by MITO Project (IPA) 25, Dec 2007 Got a Ph.D

 25, Dec 2007 (GMT) 1.9 Release
Ruby Meets VM, Koichi Sasada, EURUKO 2008

FYI
8Ruby 2.0 – since 2003 3/31
Perl 6 – since 2003 4/1

Ruby Meets VM, Koichi Sasada, EURUKO 2008

YARV Policy
9Performance Speed, Speed, Speed

 Applied many many many optimization Tech.

Compatibility

 C extension API

 Not language compatibility

Auto-generation

 VM description to Concrete VM source code

Ruby Meets VM, Koichi Sasada, EURUKO 2008

YARV: Performance Improvement
10

Ruby Meets VM, Koichi Sasada, EURUKO 2008

VM Generator
11

VM Instrunction
Description

AOT Compiler

C Source
Dis-assembler
Assembler

Virtual MachineCompiler(Optimizer)

Documents
Future work
Verifier

Enemies of YARV
12

Ruby Specification ≒ Matz

 Ruby Spec kills many optimization techs

 We love “Dynamic” “Meta” Programming,

but…

Changing Spec is also Nightmare
Portability

 We canʼt use system depending techs.

Rivals (not Enemy)

 Jruby, Rubinius, IronRuby, …

Peggy work on my Job

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Evaluation: Improve case
13

Max: x20

Evaluation: Macro-Benchmark
14

15

Evaluation:
Compare with Other Languages
Faster than
Other VMs

Limited byBignumCaclulation

Evaluation: VM doesn’t affect16

Overhead
is not in VM

Advanced VM Topics
17

Performance Parallel Thread Execution
 Embedding Float Value JIT Compiler

 Pre-Compiler

 “Ruby to Compiled file” Compiler
 “Ruby to C” Compiler

New Feature Multi-VM Creation

 Customizable Ruby Core Debug/Profile support feature
Ruby Meets VM, Koichi Sasada, EURUKO 2008

Ph.D ThesisEfficient Implementation of Ruby Virtual Machine
18

Implement a High-Speed
Ruby Interpreter
Introduce VM↓YARV(Merged into Ruby 1.9)

Parallel Ruby Execution↓Parallel Thread Execution

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Parallel Thread Execution
19

Using Native Thread
Get rid of Giant VM Lock

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Method (1)Ruby Thread and Native Thread (1:N) a.k.a -1.8 Ruby model
20

Ruby (YARV)RTNative Thread
System S/W

RTNT・・・

RT・・・

Thread Scheduler

S/W
H/W
Processor(s)PEPE

PE: Processor Element, UL: User Level, KL: Kernel Level

・・・

PE

Method (2)Ruby Thread and Native Thread (1:1)
21

Ruby (YARV)Native Thread
System S/W

RT

RT・・・

RT

NT

NT・・・

NT

Thread Scheduler

S/W
H/W
Processor(s)PEPE

PE: Processor Element, UL: User Level, KL: Kernel Level

・・・

PE

Method (3)Ruby Thread and Native Thread (N:M)
22

Ruby (YARV)
RT

RT・・・

RT

NT

NT

・・・

NT

RT

Native Thread
System S/W

Thread Scheduler

S/W
H/W
Processor(s)PEPE

PE: Processor Element, UL: User Level, KL: Kernel Level

・・・PE23

Discussion
Ruby Thread and Native Thread
Mapping with Native Thread and Ruby
ThreadProsCons
1:N

Lightweight Thread
ControlCan’t run in Parallel

1:1

Run in Parallel
Simple, Portable

Heavyweight Thread
Control (Creation, etc)

N:M

Lightweight Thread
Control, Run in Parallel

Complication, NonPortable Accept 1:1 model to make Ruby Simple

 Depend Performance on Native Thread Libraries

Accepted Method:
Ruby Thread and Native Thread (1:1) ← Ruby 1.9/YARV
24

Ruby (YARV)Native Thread
System S/W

RT

RT・・・

RT

NTNT・・・

NTThread Scheduler

S/W
H/W
Processor(s)PEPE

PE: Processor Element, UL: User Level, KL: Kernel Level

・・・PEIntroduction of Mutual Exclusion
25

Needed at

Global VM Management Data
2. Object Management / GC
3. Inline Cache
4. Thread Unsafe “C” methods
1.

(1)

Global VM Management Data

26

Managed by Table Variable Name → Value

 Method Name → Method Body
…

Introduce Synchronization at TableOperation
 Get/Set
 Easy(2) Object Management/GC
27

Synchronous GC

(2) Object Management
Lock-Free Object Allocation with Thread Local Free List28

(2) Object Management
Lock-Free Object Allocation with Thread Local Free List29

(3) Inline Cache
30

Using by VM performance Embed Cache Entries in Instruction Sequence

Sync. For Coherence -> Performance Problem
 Key and Value of Cache Entry

Sync.-Free Inline Cache Cache Miss -> Make a new entry
 GC will clean-up old cache entries

 Increase Miss-Penalty, but Good for average(4) Thread Unsafe “C” Methods
31

CRuby has many many methods
implemented by “C”
 All of them are “Thread Unsafe”

 Because -1.8 doesnʼt support parallelization

Basic Policy: Using Giant-Lock Invoke old “C” method with Giant-Lock Acquire Re-write C methods as Thread Safe, thismethod will be Giant-Lock freeProblem
Conflict of Giant-Lock Acquirement
32

GL Conflict →Performance Decrement
Limit Running CPU

 Check GL Conflict Periodically Limit their CPU Using pthread_setaffinity_np on NTPL
 SetThreadAffinityMask on Windows

Running CPU Limitation
33

Ruby (YARV)
RT1

Native Thread
System S/WNT

GL
Conflict

RT2・・・

RTnNT・・・

NT

Thread Scheduler

S/W
H/W
Processor(s)PEPE

PE: Processor Element, UL: User Level, KL: Kernel Level・・・PE

Force to run RT1 andRT2 in Serial→Avoid Conflict

Running CPU Limitation
34

Ruby (YARV)
RT1

Native Thread
System S/WNTGLConflict

RT2・・・RTnNT・・・

NTThread Scheduler

S/W
H/W
Processor(s)PEPE

PE: Processor Element, UL: User Level, KL: Kernel Level

・・・

PE

Performance Evaluation
Environment
35

Evaluation Environment

 CPU: Intel Xeon CPU E5335 2.0GHz

Quad core x 2 = 8 core

 OS: GNU/Linux 2.6.18 x86_64 SMP / NPTL Compiler: gcc version 4.1.2Ruby

 ruby 1.8.6 (2007-11-02) [x86_64-linux]

YARV Optimization

 All except Unification, Stack cachingEvaluation
Thread control Primitives
36Creation, Switch: 0.1M, Mutual Exclusion: 1M
Low Performance for Creation/Join because of Native Thread

Native Thread Overhead



Memory Allocation OverheadHigh Performance Synchronization
High Performance Thread Context Switch
 Independent Stack-Depth (1.8 depends on depth)

Ruby (sec)

YARV (sec)Ratio

NTPL (sec)Creation

0.89

1.95

0.46

0.59

Mutual Exclusion

0.67

0.38

1.76

-Switch (depth:1)

6.01

0.06

100.17-Switch (depth:16)

11.55

0.06

192.5-Evaluation
Result (Micro-benchmark)37•fib: fib(N) (Make new Thread if N>30)•hetero: fib + concat (1 thread)•mandel: Mandelbrot (Big GC overhead)•concat: String Concatenate (No Parallelism)

38

Evaluation
Result (Micro-benchmark)x 7.4
w/8 Cores

CPU Limitation
39

Using Limitation

x3.4

No Limitation

40

Parallel Thread Execution
ProblemUnsafe “Old C” methods

 Replacing all is not easy task
 Man Power Problem?

Programming Model Is Parallel Thread Application easy to write?

Ruby 1.9

 1.9 support Native Thread 1.9 doesnʼt support Parallel Thread Execution

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Embedded Float Representation
41

Float object is not immediate type

 This means that Float is “allocated” each time Ex) Fixnum, Symbol, etc

Half execution time of Float calculation isMemory management

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Toy-Program
42i = 0; f = 0.0
while i<30_000_000
i += 1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1end

43

List of Execution Time
Toy-Program

MemoryManagement

Float Calc
Using OProfile
Linux 2.6 (x86_64), Xeon
Ruby 1.9.0

Embed Float Object as Fixnum
44

Solution: Embed 64bit Float value to 64bit
CPU Pointer type!

Ruby Meets VM, Koichi Sasada, EURUKO 2008

45

Review
IEEE 754 Double Precision Representation
64bit Doubleb63

b62-b52b51-b0s: Sign (1 bit)e: exponential (11bit)

m: Mantissa (52bit)

Discussion
How to Embed 64 bit Double?
46

VALUE embed Object doesnʼt needmemory overhead
64bit CPU have 64 bit pointer type
→ Use 64 bit CPU
At least we need 1 bit for TAG bit From Mantissa?

 Decrease Precision From Exponential?
 Decrease

Representation Range

Proposal
47

From Exponential
But Store Float in Heap if it is Out of Range→ Save a Range and Precision Often used 01000000000b〜10111111111b（）

 If Float is out of range, alloc from Heap Float Out of this Range is Rare Number on

Numeric Application -> Practical Solution

48

Proposal
Real Program
1) Check the Range of “e” (512〜1535)
2) IEEE745 double -> Float (Encoding)3) Float -> IEEE745 double (Decoding)49

ProposalFloat Representation with Tag
e: 10000000000b〜01111111111b
Note that if “b62 != b61”, we can embed.
On Ruby, Tag is at LSB→ Left Rotate 3bit
b63 b62 b61 b60 … b0 → 3 bit rotate
b60 … b0 b63 b62 b61

50

Proposal
Real Encoding Code
VALUE rb_float_new(double dbl) {VALUE v1 = BIT_DOUBLE2VALUE(dbl);
VALUE v2 = BIT_ROTL(v1, 3);if ((v2 + 1) & 0x02) // check lower 2 bits
return v2 | 0x01;// Embed tagelse {if (dbl == 0) // 0.0
return ruby_float_zero;else// alloc from Heap
return rb_float_new_in_heap(dbl);}}

51

Proposal
Real Decode Codedouble RFLOAT_VALUE(VALUE v) {if (v & 1) {VALUE v1 = v ^ ((v >> 1) & 1);
VALUE v2 = BIT_ROTR(v1, 3);
return BIT_VALUE2DOUBLE(v2);}elsereturn RFLOAT(v)->float_value;}Implementation
52

Ruby 1.9.0-0
Easy to Implementation
No Spec Changes

53

Evaluation
Toy-Program

9Reduce Mem Time
9Encode/Decode don’t
affect to Performance

54Evaluation
Compared with other Ruby Impl.

From Comp. Lang. Shootout [4]55

Evaluation
Compared with Other Languages
Evaluate with other languages
Note that C/Java use “volatile” to avoid
optimizationi = 0; f = 0.0
while i<30_000_000
i += 1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
end

56

Evaluation
Compared with Other Languages

57[PLAN]JIT CompilerIʼm re-designing to reduce VM
instructions to impl. it easy Current VM has about 50 instructions

 Ex) “definemethod” move to “Method”

Ruby Meets VM, Koichi Sasada, EURUKO 2008

58

[PLAN]
Pre-Compiler
YARV VM Generator helps us
 Ruby to “Pre-compiled”
 Ruby to “C”

Purpose Eliminate Loading-Time More aggressive optimization
 Obfuscation (?)

Ruby Meets VM, Koichi Sasada, EURUKO 2008

59

[PLAN]
Multi-VM Creation
Purpose Embed Ruby into Application
 mod_ruby, …

 Sand-box

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Multi-VM Overview
60

Ruby (YARV)VM1VM2RT

Native Thread
System S/W・・・RTNT

NT

RT・・・

NT

Thread Scheduler

S/W
H/W
Processor(s)PEPE

PE: Processor Element, UL: User Level, KL: Kernel Level

・・・

PE

Multi-VM Points
61

How to control VMs?

 C Level? → Designed with Nobuyoshi Nakada
 Making new VM is need only 3 lines

 Ruby Level?

How to share environments Inter VM
 Trade off between Isolation and Util.

Ruby Meets VM, Koichi Sasada, EURUKO 2008

62

[PLAN]
Customizable VM Core
Ruby is tooooo FAT to use XXX purpose Many Many Convenience Methods/Feature

Need Re-design Ruby CoreRuby Meets VM, Koichi Sasada, EURUKO 2008

63

[PLAN]
Debug/Profile Support Feature
Only cheep Debugger/Profiler API set_trace_func, Thread#set_trace_func

Introduce “break” instruction?

Ruby Meets VM, Koichi Sasada, EURUKO 2008

64

Future Work
BenchmarkCurrent Benchmark suits is for checking
YARV Performance Focus to YARV optimization
 Toy benchmarks

We need more pragmatic benchmarks

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Summary65

YARV Merged into Ruby 1.9Iʼm working at Advanced VM Topics
Performance Parallel Thread Execution
 Embedding Float Value JIT Compiler
 Pre-Compiler

 “Ruby to Compiled file” Compiler
 “Ruby to C” Compiler

New Feature Multi-VM Creation
 Customizable Ruby Core Debug/Profile support feature
Ruby Meets VM, Koichi Sasada, EURUKO 2008

Summary66

Merging YARV is not a goal,
but a start
VM is a very flexible
infrastructure to hack
Ruby Meets VM, Koichi Sasada, EURUKO 2008

67

One more thing…

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Sasada Lab@U-Tokyo
68

Iʼll make a laboratory from 2009, Apr Department of Creative Informatics,

Graduate School of Information Science andTechnology, The University of Tokyo Graduate School Lab is at Akihabara, Tokyo, Japan

Unfortunately I canʼt employ you as
Research Assistant There are not enough grants in Japan…

Ruby Meets VM, Koichi Sasada, EURUKO 2008

Research Topics
69

Ruby, Ruby, Ruby, PHP, Ruby, Ruby
Ruby, Ruby, Ruby, Ruby, Python, Ruby
Ruby, Perl, Ruby, Ruby, Ruby, Ruby
Ruby, Ruby, Ruby, Ruby, Lua, Ruby
Ruby, Ruby, Java, Ruby, Ruby, Ruby
Implementation of Programming Language
Operating System / Processor Architecture
Software development
Ruby Meets VM, Koichi Sasada, EURUKO 2008

Sasada Lab.
70

if you.have_interest(:Japan, Tokyo, :Akihabara,:Japanese,:Ruby, :Research, :Development)
you.send_mail_to “ko1 at atdot dot net”
end

Ruby Meets VM, Koichi Sasada, EURUKO 2008

71

Thank you for your attention!
Any Questions?
ささだ こういち
Koichi Sasada
Ko1 at atdot dot net
Ruby Meets VM, Koichi Sasada, EURUKO 2008