Ruby -> Lisp translator = much faster Ruby interpreter

[harsh]

I got bored over the weekend and spent some time working on a very
basic Ruby to Lisp translator. My goal was to get a basic idea of the
kind of performance that could be expected from such a thing.

It's at the point now where this:

def fib(n)
if n < 3 then 1 else fib(n-1) + fib(n -2) end
end

translates to this:

(DEFMETHOD RMETH::M-FIB
((|self| OBJECT-INSTANCE) |n|)
(IF (RUBY::TRUEP (RMETH::M-< |n| 3))
1
(RMETH::M-+ (RMETH::M-FIB |self| (RMETH::M-- |n| 1))
(RMETH::M-FIB |self| (RMETH::M-- |n|
2)))))

The Lisp version runs pretty quickly on CMUCL. Run times for "fib(32)"
on my machine are:

- 0.8 seconds in the translated-to-Lisp version
- 11.5s for vanilla Ruby 1.8.2
- 3.8s for YARV 0.4.0/Ruby 1.9.0
- 3.3s for Python 2.3.5
- 5.0s for Perl 5.8.4

It's just a couple days' work, and doesn't yet support much of the
language (basically just method definitions, instance variables, and
method calls; and even support them fully). But if there's enough
interest I'd probably keep working on it, and/or publicly post the
soure code.

 

[gabriele renzi]

(e-mail address removed) ha scritto:

The Lisp version runs pretty quickly on CMUCL. Run times for "fib(32)"
on my machine are:

- 0.8 seconds in the translated-to-Lisp version
- 11.5s for vanilla Ruby 1.8.2
- 3.8s for YARV 0.4.0/Ruby 1.9.0
- 3.3s for Python 2.3.5
- 5.0s for Perl 5.8.4

I guess this code is easily translatable in binary even via YARV's
ruby->C translator and/or ruby2c, it would be nice to see comparisons

It's just a couple days' work, and doesn't yet support much of the
language (basically just method definitions, instance variables, and
method calls; and even support them fully). But if there's enough
interest I'd probably keep working on it, and/or publicly post the
soure code.

interestingly, the PyPy guys have an (outdated) CMUCL backend, so I
think at least the idea of running $language on a lisp implementation is
not so strange
It would be interesting to see what you've done, and I wonder if you
used some of the previous work such as ripper to build the AST or
ParseTree or metaruby's type inferencer or whatever.

 

[ts]

h> - 0.8 seconds in the translated-to-Lisp version
h> - 11.5s for vanilla Ruby 1.8.2
h> - 3.8s for YARV 0.4.0/Ruby 1.9.0

Well, if I'm right, yarv actually don't have tail-call optimization
actived.

 

[Robert Klemme]

I got bored over the weekend and spent some time working on a very
basic Ruby to Lisp translator. My goal was to get a basic idea of the
kind of performance that could be expected from such a thing.

It's at the point now where this:

def fib(n)
if n < 3 then 1 else fib(n-1) + fib(n -2) end
end

translates to this:

(DEFMETHOD RMETH::M-FIB
((|self| OBJECT-INSTANCE) |n|)
(IF (RUBY::TRUEP (RMETH::M-< |n| 3))
1
(RMETH::M-+ (RMETH::M-FIB |self| (RMETH::M-- |n| 1))
(RMETH::M-FIB |self| (RMETH::M-- |n|
2)))))

The Lisp version runs pretty quickly on CMUCL. Run times for "fib(32)"
on my machine are:

- 0.8 seconds in the translated-to-Lisp version
- 11.5s for vanilla Ruby 1.8.2
- 3.8s for YARV 0.4.0/Ruby 1.9.0
- 3.3s for Python 2.3.5
- 5.0s for Perl 5.8.4

It's just a couple days' work, and doesn't yet support much of the
language (basically just method definitions, instance variables, and
method calls; and even support them fully). But if there's enough
interest I'd probably keep working on it, and/or publicly post the
soure code.

In this case the obvious improvement here is of course to use an
iterative approach...

robert@fussel ~
$ ruby bin/fib.rb.txt
8.843
0.0

robert@fussel ~
$ cat bin/fib.rb.txt
def fib(n)
if n < 3 then 1 else fib(n-1) + fib(n -2) end
end
def fibi(n)
a=[]
n.times{|i| a = i < 3 ? 1 : a[i-1] + a[i-2]}
a[n]
end
t1 = Time.now
fib 32
t2 = Time.now
fibi 32
t3 = Time.now
puts t2-t1, t3-t2

Is it worth the effort to improve the speed of an inefficient algorithm
by making it run on a different platform? Or put differently: what kind
of problems are you trying to solve with this? Or even differently:
when speed is more important than simplicity, wouldn't you write Lisp,
Java, C++ etc. in the first place? Personally I'd probably prefer see
efforts go into optimization of the Ruby runtime (for example detecting
and improving tail recursion).

Kind regards

robert

 

[Erik Hollensbe]

Is it worth the effort to improve the speed of an inefficient algorithm
by making it run on a different platform? Or put differently: what
kind of problems are you trying to solve with this? Or even
differently: when speed is more important than simplicity, wouldn't you
write Lisp, Java, C++ etc. in the first place? Personally I'd probably
prefer see efforts go into optimization of the Ruby runtime (for
example detecting and improving tail recursion).

I think he already answered that.

-Erik