Monday, April 09, 2007

New compiler for RLisp - teaser

giggling by sachama from flickr (CC-NC-ND)RLisp is slow. On a few random benchmarks it is about 50x slower than Ruby - possibly too slow to be useful. But that's only because the implementation was created without giving any thought whatsoever to performance. There's nothing in RLisp as a language that forces it to be slow. In fact it could easily be much faster than Ruby and still enjoy full access to Ruby runtime. I tried a few optimizations in the past, without too much measurable success. My latest approach is building a new compiler from scratch (keeping the parser, and possibly parts of the standard library). The compiler generates Ruby code, but it limits itself to a small subset of it. The subset is inspired by Lua 5.0 virtual machine. Here's compiled (fn (x) (fn (y) (+ x y))) function:
class Function_2 < Function
   def initialize(globals, x)
       @globals = globals
       @x = x
   end
   def call(a_y)
       y = Variable.new
       y.set a_y
       t0 = @globals[:+]
       t1 = @x.get
       t2 = y.get
       t3 = t0.call(t1, t2)
       return t3
   end
end
class Function_1 < Function
   def call(a_x)
       x = Variable.new
       x.set a_x
       t4 = Function_2.new(@globals, x)
       return t4
   end
end
t5 = Function_1.new(@globals)
The basic trick is division of variables into three classes - global (accessed through @globals), closure (accessed through instance variables of a closure - all being Variable objects), and local (Ruby local variables). A few things could be easily optimized, like creating Variable objects only for variables which are passed to subclosures and modified somewhere, and using fewer temporaries. But what I really hope for is being able to connect RLisp compiler to a backend like LLVM. Here's one more example - Fibonacci function:
(let fib (fn (x)
 (if (< x 2)
   1
   (+
     (fib (- x 1))
     (fib (- x 2))
))))
which gets compiled to:

class Function_1 < Function
   def call(a_x)
       x = Variable.new
       x.set a_x
       t0 = @globals[:<]
       t1 = x.get
       t2 = 2
       t3 = t0.call(t1, t2)
       t4 = Variable.new
       if t3
           t5 = 1
           t4.set t5
       else
           t6 = @globals[:+]
           t7 = @globals[:fib]
           t8 = @globals[:-]
           t9 = x.get
           t10 = 1
           t11 = t8.call(t9, t10)
           t12 = t7.call(t11)
           t13 = @globals[:fib]
           t14 = @globals[:-]
           t15 = x.get
           t16 = 2
           t17 = t14.call(t15, t16)
           t18 = t13.call(t17)
           t19 = t6.call(t12, t18)
           t4.set t19
       end
       t20 = t4.get
       return t20
   end
end
t21 = Function_1.new(@globals)
@globals[:fib] = t21
return t21
The hardest major optimization, at least for Ruby code output, would probably be inlining without harming semantics. Not inlining basic functions like + and send unfortunately guarantees bad performance. Other cool things would be making sure let behaves intuitively as much as possible, and at least partial tail recursion optimization (for calls to self).

No comments:

Post a Comment