fredag, januari 19, 2007

YARV tail call optimization in JRuby

After some further developments on the YARVMachine, I can report that JRuby trunk supports most of the optimized instructions that YARV makes use of. The big thing missing is the local cache optimization. But that is just an aside from the main course.

Because right now there is support in JRuby's YARVMachine to handle a limited form of tail call optimization. Specifically, if the last call in a method is to the method we're in and the receiver of that call is the same as the current self, tail call optimization will happen. That allows JRuby to run this script:
def fact(n, acc)
if n == 0
acc
else
fact n-1, n*acc
end
end

p fact(25000, 1)
That will explode in both YARV and MRI, long before getting anywhere, since the stack goes out. But this will work correctly in JRuby with -y, provided that the tail call optimization is actually turned on. To turn it on, use $JAVA_OPTS and set the variable jruby.tailcall.enabled to true, like this:
JAVA_OPTS="-Djruby.tailcall.enabled=true"
jruby -y testRecFact.rbc
Of course, you need latest trunk for this to work, and you need to compile the YARV file as described in my previous post. But provided you have done that, the above will actually work perfectly, without deepening the stack at all. The reason this is not turned on by default in the YARVMachine is that it isn't completely safe yet. There is one small kink, which is that if you redefine the current method within the current method, and then call self, this will not work as expected. It should be easy to add checks for this behavior, though, so that will come soon.

Of course, the big problem with something like this is the stack trace. How to handle it? The implementation behavior would make it look like those 25000 calls to fact was just a single one. In the same manner, trace methods won't get called.

But trunk will actually report when these tail calls have been done. Say you have a script like this:
def a(n)
if n > 20000
raise "hell"
end
a(n+1)
end

a(0)
(it is designed to explode at a certain depth, of course.) In current JRuby trunk, executed with -y, this will generate an output that looks like this:
testRaise.rb:-1:in `a' TAIL CALL(20001): hell (RuntimeError)
from testRaise.rb:-1
So it is quite obvious that the exception was raised in the 20001:th invocation of 'a'.

This work goes forward very fast, and it's funny to see progress happen this quickly. Yesterday SASADA Koichi visited the #jruby and #rubinius IRC channels, and we had some very interesting discussions on further collaboration. The future looks bright indeed, and this weekend I'll probably have time enough to take a first crack at a YARV compiler for JRuby.

1 kommentar:

Anonym sa...

Hi Ola,

Cool post.

For offline reading, I usually do prints. I use firefox and use the PRINT PREVIEW feature to limit the number of pages printed.

You're an Über hacker, so I assume that it won't be impossible for you to make print previews good on your blog ?

Right now, when I try to do print preview, the 1st page is blank, 2nd page is OK. 3rd page is kinda empty.

Thank you,

BR,
~A