Building
the Ruby Interpreter
What is easy and what is difficult?

Koichi Sasada
ko1@heroku.net

2014
Very important year for me
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

th10

Anniversary
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

th10

Anniversary
YARV development (2004/01-)
Ruby no Kai (2004/07-)
Rubyist Magazine (2004/09-)
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

th10

Anniversary
Continuous efforts
on development of Ruby
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Today’s talk

Ruby development

Easy part
何が簡単なの？

Difficult part
何が難しいの？
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Who am I?
A Programmer• CRuby developer (a committer)• Interpreter core such as VM, GC, and so on• Join 2007-• Member of Heroku Matz team
• Full time CRuby developer with Matz and Nobu
• Join at 2012-• One of the directors of Ruby Association• Join at 2013

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Who am I?
Contributions• YARV: Yet Another RubyVM (Ruby 1.9)
• Native Thread strategy (Ruby 1.9)
• Fiber (Ruby 1.9)
• Flonum (on 64bit CPU) (Ruby 2.0)
• New method cache (Ruby 2.0)
• RGenGC: Restricted Generational GC (Ruby 2.1)
• RincGC: Restricted incremental GC (Ruby 2.2?)• Research projects• Community activities
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Contributions
YARV: Yet Another RubyVM (1.9-)
Ruby (Rails) app

i gigantum umeris insidentes
Standing on the shoulders of giants

So many gems
such as Rails, pry, thin, … and so on.
RubyGems/Bundler

Ruby interpreter
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Contributions
YARV: Yet Another RubyVM (1.9-)
Ruby
scriptBundledLibraries
Embeddedclasses and methods(Array, String, …)

Parse

CompileThreading

Ruby
BytecodeGem
Libraries

Evaluator

Ruby Interpreter
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Objectmanagement(GC)Contributions
YARV: Yet Another RubyVM (1.9-)• Stack based virtual machine• Ruby specific bytecode• Compiler Ruby script to bytecode sequence• Bytecode interpreter• Develop at 2004/01/01• I was 1st year doctor course student and had plenty time

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Contribution
Native thread strategy (1.9-)• Native (OS) threads for each Ruby threads with GVL• Fast context switch, easy to manage threads
Thread 1

Thread 1
CPU 1

OS Thread 1

Lock
Thread 2

Lock
OS Thread 2

CPU 2

IDLE
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Contribution
Fiber (1.9-)• Abstraction objects of execution contexts• Fiber is from Windows API• Cooperative thread• Coroutine (or Semi-Coroutine)• Fast fiber context switch with non-portable methods
Fiber1
resumeFiber1Fiber2
resumeFiber2Fiber3

yeild

yield
time

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Contributions
New method cache (2.0-)

First time

Second time

• Store checking results into method cache• Eliminate method frame building
1.
2.

Check caller’s arguments
Search method `body’ `selector’ from `klass’

3. Dispatch method with `body’
1.

Check visibility and arity
1.

2.
3.
4.

Cache result into inline method cache

Push new control frame
Build `local environment’
Initialize local variables by `nil’

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Contributions
Flonum (on 64bit CPU) (2.0-)• Embedded “double” into VALUE like Fixnum• About 2 times faster
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)
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014☆ +0.0 is special case (0x02)

Contributions
RGenGC: Generational GC for Ruby (2.1-)• Introduce RGenGC by inventing “WB-unprotected”
objects technique and reduce marking time dramatically• Incremental GC by same technique (for Ruby 2.2)
Accumulated
execution time (sec)• See Rubyist Magazine vol. 0048 or attend RubyConf2014
15
10

About x15 speedup!

50
Total mark time (ms)w/o RGenGC

Total sweep time (sec)

RGenGC* Disabled lazy sweep to measure correctly.

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Contributions
Research projects• Performance• Ruby to C compiler (3 versions)• Ruby to C# compiler• Ruby to X10 compiler• Regexp compiler• Mix Ruby and C program• Memory management with mmap

• Parallelization• Parallel threads CRuby• MVM: Multiple virtual machines• Inter-processes shared objects mechanism• Profilers• Memory profiler• High-speed profiler• And others….
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Contributions
Community activities• Nihon Ruby no Kai• Director (2004-2011)• Rubyist Magazine (2004-)• RubyKaigi (2006-2011)• Ruby Association• Director (2012-)• and other activities• see http://www.atdot.net/~ko1/activities/ for otheractivities

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Contributions
Community activities• Conference in the world• 2014/03 RubyConf Philippines 2014, Manila, Philippines• 2014/04 RubyConf Taiwan 2014, Taipei, Taiwan• 2014/05 Ogasawara, Tokyo, Japan (Honeymoon)• 2014/06 RedDotRubyConf 2014, Singapore• 2014/07 Deccan RubyConf 2014, Pune, India• 2014/08 RubyConf Brasil 2014, São Paulo, Brazil• 2014/09 RubyKaigi 2014 (NOW)• 2014/10 ?? (No plan, please invite me)• 2014/11 RubyConf2014, San Diego, US
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

http://www.flickr.com/photos/donkeyhotey/8422065722

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Today’s talk

Ruby development
Easy part
何が簡単なの？

Difficult part
何が難しいの？

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Mission ofRuby interpreter developers
Improve theQualityof the Ruby interpreter

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Quality• Reliability / Availability• Run Ruby program correctly• No bugs!!

• High performance• Nobody blames speed-up• Low machine resources• Low memory, low energy, …

• Good compatibility• Ruby level and C-API level• Extensibility• Productivity on Ruby interpreter development
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Trade-off• Many trade-off, for example:

B is good• Performance <-> Reliability• Performance <-> Low resource• Performance <-> Compatibility• Performance <-> Extensibility

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

A is goodTrade-off• We engineers/programmers need to:

B is good• Know trade-off• Consider trade-off• Overcome trade-off

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

A is good

Overcoming “trade-off” technology• Object-oriented scripting language Ruby
• Improve “Productivity” by overcoming trade-off
between “Language power” and “Easy-to-read/write”• Performance improvements of Ruby interpreter• Improve “Performance” by overcoming trade-off
between “Productivity” and “Performance”

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Ruby’s Performance
Serial execution performance
Parallel execution performance
GC performance
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Serial execution• [EASY]• Introduce virtual machine (done)• Introduce (simple) JIT (AOT) compilation• [Difficult]• Keep productivity, reliability, compatibility• Improve performance with aggressive
optimization• Interoperability with C codes

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Serial execution
Designing simple VM• Add bytecode incrementally• Increase support ruby features• For YARV, ruby has an answer set! (test case)• VM is simple and easy software• Loop fetch and execute instructions• Details are not so easy
• Implement block data structure is hell
• But time can solve (maybe…)
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Serial execution
Keeping productivity• (1) VM code needs many similar codes→ Solution: VM code generator• Generate VM related codes from simple definitions• No need to write complicated codes• (2) Manipulate native code for more optimizations→ Solution: similar code generation technique (planning)

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Serial execution
Aggressive optimization• For meaningful speed, aggressive optimizations are needed• Method/block inlining• Constant folding• Partial redundancy elimination (PRE)• Lambda lifting• … (many well-known traditional optimizations)• Ruby is highly dynamically programming language• Method redefinition• Accessing local variables via “eval” method• Key technique is [DE-OPTIMIZATION]• Revert aggressive optimizations• It is difficult to revert from mangled states to plain states dynamically
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Serial execution
Interoperability with C codes• C code is low-level, faster than Ruby’s code
• However, C code doesn’t have internal details
which aggressive optimization requires• Most of Java class libraries are written in Java
program → Rubinius way (Ruby in Ruby)• Ideas• (1) Rewrite with ruby• (2) Write annotations to C code
• (3) Analyze C code with LLVM infrastructure and so on• (4) Mix C code with Ruby code
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Performance
Serial execution performance
Parallel execution performance
GC performance
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Parallel execution• [EASY]• Providing parallel threads• [Difficult]• Provide good programming experience• Programming model• Debugger• Good serial performance• Need synchronization everywhere• Keep code quality, reliability, compatibility• Interpreter should be robust• Thread programming is needed!
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Parallel execution
Provide good programing experience• “Why Threads Are A Bad Idea (for most purposes)”• Quoted from John Ousterhout, 1995

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Parallel execution
Provide good programing experience• Shared everything and need correct synchronizations• Typical bugs
• Data race
• Atomicity violation• Order violation• Non-deterministic nature• Bugs are not reproducible• Terrible experiences make Ruby programming unhappy• I hope Ruby programming is happy experience
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Parallel execution
Provide good programing experience• Educate programmers• Provide good concurrent programming models• Provide smart debugging tools

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Parallel execution
Concurrent programming model• Approaches of other languages• Data models• Concurrent data: Java (java.util.concurrent)• Immutable (functional) data: Functional languages• STM: Clojure• Type system: D, Haskell
Functional
Threads• Execution models:• Actor: Erlang, Scala• CSP: Go-lang

languages

DangerFreedom• “Can write safe code” vs. “Must write safe code”
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Safe
RestrictedParallel execution
Concurrent programming model• Trade-off: Performance, Flexibility <-> Reliability• “Parallel threads” (shared everything) is very primitive• Enable to write best-speed programs• Difficult to debug because of non-deterministic nature• Similar trade-off: free() vs. GC• Liberty vs. Restriction• Manual free() is high-performance• However, Ruby has good enough performance

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Parallel execution
Concurrent programming model• Ideas• Better inter-process communication• MVM: Multiple virtual machines• Spawn full set Ruby virtual machine• Too big and performance neck• Smaller isolated ruby• Subset of Ruby
• mruby?

• Introduce “owner threads” for each objects• Detect “owner thread violation” dynamically• Pre-locked objects
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Parallel execution
Make program deterministic• Non-deterministic behavior kills programmers• Many research on thread debugging tools• Detecting inter-thread conflicts• Change OS scheduler to make programs
deterministic

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Performance
Serial execution performance
Parallel execution performance
GC performance
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

GC Performance• [Easy]• Write GC algorithms• [Difficult]• Keep reliability• Non-deterministic behavior• Keeping compatibility• Lack of write-barriers• Conservative algorithms• Mostly copying/compaction GC

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

GC Performance
GC algorithm and implementation• GC algorithms are simple, only a hundred oflines• Mark & Sweep• Copy, Compaction• Reference count• Other than GC algorithm is very difficult• GC algorithm need assumptions, and need tochange all of Interpreter code
• Only one bug causes critical bugs
• Also we need to care compatibility
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

GC Performance
Example: Write barrier• Write barrier technique is required for many
GC algorithms, but it is difficult to insert WBs
correctly because of compatibility issue• Solution: Invent new GC algorithm without
enough WBs

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

GC Performance
Reliability• Non-deterministic behavior• GC bugs appear in unexpected place• Solution: Debugging feature• GC.stress: invoke GC many times forcibly• Check assertions• List up all assertions• Check assertions for debug

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

GC Performance
Example: detect write barrier miss• Assertion (RGenGC):
Old objects should not
point new objects(without remember set)
• Traverse all objects andbuild objects relationgraph• Check assertion

Root objects

Rememberset (RSet)

new
WB
u

new
old

BUG!!

old

• GC.verify_internal_consistency
methodBuilding the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

old
old

new
new

Measurement• [EASY]• Measure execution time

• [Difficult]• Making periodically observing environment• What application should we measure?
• What measurement should we measure by?

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Measurement
Periodical observing environment• To measure correct benchmark results,
physical environments are required• We have a small rack space, cooperation by Prof.
Sugaya, Shibaura Institute of Technology• Only two machines… • Ideal resources• Multiple OSs (linux, MacOSX, Windows, …),
multiple architectures (Intel, ARM, …)• Multiple nodes for periodical benchmarking
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Measurement
Applications• What applications should we measure?
• Micro benchmarks• Rails application – discourse benchmark

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Measurement
Index• What should we use
measurement?
• Execution time
• Which execution time?
• Include launch time?

• Memory usage• Peak value?
• Average/Median values?

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Development community• [EASY]• Become a Ruby committer• [Difficult]• Become a Ruby developer• Keep motivation and continuous development• Increase Ruby developers

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Community
Become a Ruby developer• Ruby Hacking guide• Published in Japanese• Translated into English

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Community
Become a Ruby developer• Ruby Under a Microscope• Published in English• (Translating into Japanese)

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Community
Become a Ruby developer• 2014/09/20 15:30- @ Hall B

Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Community
Continuous development• Survey new technologies• Blogs• Meet-up• Academic papers• Consideration, Discussion• Thinking on the desk
• Chatting on SNS• Developer’s meeting• Talking at conferences• Implementation and Evaluation… and overcome trade-off
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Message

We are facing with large
blue ocean yet.
Join us for your profession
and fun!
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Today’s talk

Ruby development

Easy part
何が簡単なの？

Difficult part
何が難しいの？
Building the Ruby Interpreter -What is easy and what is difficult?-,
Koichi Sasada, RubyKaigi2014

Thank you for your attention
Koichi Sasada<ko1@heroku.com>