The Ruby VM: Episode V

For details about this ongoing interview, please see my introductory post.

You have told us before that one of the big reasons to move to a new Ruby VM was to provide new options for optimization. Can you talk a little about the optimizations you have added to the new Ruby VM thus far and what operations will likely be faster because of them?

ko1:

OK. At first, I write about basic of YARV instruction. YARV has two type instructions. First is primitive instruction. It's as written, primitive. Ruby code can be represented in these primitive instruction. Second is instructions for optimization. It's not needed to represent Ruby scripts, but they are added for optimization. Primitive instructions doesn't include _ in their name (like putobject), and optimize instructions do (like opt_plus). This policy helps you if you want to see VM instructions. Initially, you need to read primitive instructions.

The most easy and effective optimization is Specialized Instructions. This optimization replace method call with another VM instruction, such as Fixnum#+ to opt_plus. Current Ruby's numeric calculation is slow because all operations are method call. For example, 1 + 2 means 1.+(2). But numeric operations are more lightweight than Ruby's method invocation. So method call is only overhead for numeric operation. Specialized Instructions allow the VM to skip method call overhead.

But we can't know which expression is numeric operation or not at compile time. See this expression: a = c ? 1 : [:elem], a will be Fixnum or Array at runtime.

So, we can't replace + expression with numeric operation instruction. Specialized Instruction, for example opt_plus which is replaced with + method invocation will do following code:

def opt_plus(recv, val) # simple version
   if recv.class == Fixnum && val.class == Fixnum
     if Fixnum#+ is not redefined
       return calculate "recv + val" without method call
     end
   end
   # normal method invocation
   recv.+(val)
end

Check receiver and value are Fixnum or not, and check Fixnum#+ are not redefined. After these check, calculate them without method invocation. In fact, Float#+ are also checked. There are other specialized instructions.

YARV eases to implement such instructions with VM generator. You shouldn't write bothersome code such as stack manipulation. If you write VM instruction such as opt_plus in simple VM DSL, VM generator will translate it to C code.

Specialized Instruction is very simple, but effective for simple benchmark such as fib() or tak() and some calculate bound program.

One question I thought of while reading your previous answer was: will Ruby scripts be able to access these VM instructions, if desired?

ko1:

Simple answer is "yes".

On YARV, bytecode and other information are represented as the VM::InstructionSequence class. I often use the name "ISeq" to point that class. ISeq object contains a bytecode sequence, a catch table (to retrieve exception and other global escape such as break), a local variable name table and others.

ISeq object can be dumped in Ruby's primitive objects such as Array, Hash, Fixnum and so on. In the same way, ISeq can be built with such data with primitive objects. This means that you can built YARV bytecode without YARV compiler. Of course, this feature can be used for other purpose such as ruby script obfuscation (this is like Java class file).

(BTW, I use this feature on Ruby2C compiler. It is hard to translate Ruby program to C program directly. But from YARV instruction, translation is easy. If I finished it, I want to bundle this with Ruby.)

Therefore it is hard to write ISeq dumped data. So I had prepared "lib/yasm.rb" as YARV Assembler (this is not committed on current trunk). With YASM, you can write YARV bytecode sequence on Ruby program. Note that YARV/ISeq loader doesn't have the byte code verifier. So illegal bytecode sequence is loaded, YARV/Ruby will dumps core.

If I commit lib/yasm.rb, I'll write tutorial to use that.

Does the new Ruby VM optimize tail recursive methods? If no, are there any plans to add this optimization?

ko1:

YARV doesn't support "tail recursion optimization", but supports "tail call optimization".

See this program:

class C
   def foo
     foo # (A) tail recursive call
   end
end

class D < C
   def foo
     super
   end
end

D.new.foo

Can you replace goto with (A)? (A) should call D#foo so we eliminate tail method call. Yes, we can implement this optimization with following trick.

class C
   def foo
     if search_method(:foo) == C#foo
       goto first_of_foo
     else
       foo
     end
   end
end

But we must think of inter block tail recursion or so (inter block goto is not permitted) if implement tail recursion optimization.

BTW, YARV support tail call optimization, eliminate stack frame of caller. You can call method which at tail position without consuming VM stack like scheme language. So you can use method call to loop something. You can make state transition with method call.

Note that tail call optimization has some caution. First is backtrace elimination. You can't see caller method of tail method with backtrace. Second, this optimization does not speedup method call. Tail call process is almost same as process of normal method call. At end of normal method call process, check if tail call or not. If that method call is tail call, use current method frame to setup method frame instead of pushing new stack frame.

Current Ruby 1.9 (trunk) is not enabled this optimization. If you want to try this, please re-write that option in "vm_opts.h" (OPT_TAILCALL_OPTIMIZATION) and re-compile that. I think release version of Ruby 1.9 is enabled this optimization. I need more comments of it. Please teach me if you find out some critical problem.

Can you talk a little about some optimizations you would like to add to the new Ruby VM in the future?

ko1:

In near future, I'll release AOT, Ruby to C compiler. This translator will support all Ruby specification, so it's shouldn't be silver bullet for performance.

Keeping all Ruby spec means "can't achieve high performance". If I ignore some spec, I'll be able to do more drastic optimization. So C code translated from Ruby script will be slow (of course, faster than normal interpretation).

Ruby specification is enemy for compiler/VM developer. So I want to add a "pragma" syntax to add programer's knowledge. For example, "eval is not appear in this file" or "Fixnum methods are not re-defined". These information will help compiler to do more effective optimization.

And I'm planning to implement block inlining. I think it is very effective for Ruby. An experimental, incomplete version has been made. I need more research to realize it.

BTW, I will not touch JIT compilation. I think it is not reasonable (not worth the cost of implementation). Everyone love "JIT" words, but I think it's not effective on Ruby spec.

Add Your Thoughts

You can use Markdown in the body of your comment to format text and make links.

Note that I reserve the right to edit any content you post here. I typically exercise this right to fix formatting issues. All posts must be approved so spam will never been seen on these pages.

Author:

URL or Email (optional):

Body: