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