This post originated from an RSS feed registered with Ruby Buzz
by Ryan Davis.
Original Post: Recursive Functions in RubyInline
Feed Title: Polishing Ruby
Feed URL: http://blog.zenspider.com/index.rdf
Feed Description: Musings on Ruby and the Ruby Community...
harrisj filed a bug against inline today regarding recursive functions failing. The simplest example is fibonacci. The problem is simple, and its solution (workaround really) is simple too. Let's dig in, shall we?
Pure Ruby
class Fib
def rubyfib(n)
return 1 if n <= 1
rubyfib(n-1) + nfib(n-2)
end
end
Simple enough example, but because of its recursive nature it takes a long time to run (less to do with its recursiveness than the simple fact of the matter that it is doing a ton of method dispatches in general.
Inline C
So, let's say that we have this code coming up at the top of our profile and we want to speed it up. We grab our trusty inline and pop in the equivalent in C:
require 'inline'
class Fib
inline do |builder|
builder.c <<-END
long badfib(long n) {
if (n <= 1) {
return 1;
} else {
return badfib(n-1) + badfib(n-2);
}
}
END
end
end
The Recursion Problem
The problem is that this doesn't compile properly. Why? It looks right. Indeed it does, but you need to dig deeper to understand what inline is doing for you to make this stuff look so easy. What it is really generating is this:
static VALUE badfib(VALUE self, VALUE _n) {
long n = NUM2INT(_n);
if (n == 0 || n == 1) {
return INT2NUM(1);
} else {
return INT2NUM(badfib(n-1) + badfib(n-2));
}
}
The problem is twofold. badfib has two arguments, not one, and both of them are VALUE, not long. The "simple" solution is to pass in self, but you still have to convert the second arg as well and the return value. The last line starts to look gross:
That is icky. It works, is damn fast compared to the pure ruby example (14.5s vs 0.3s in my benchmarks), but it is still icky. I'll even take a speed hit to reduce icky. That said, there is a much simpler solution.
Pure C Recursion, Ruby Wrapper
Instead of mixing the two languages at that level (and it really is an oil and water problem at this stage--maybe if we shake it enough we'll get a vinaigrette), strictly separate them:
builder.prefix <<-END
long realfib(long n) {
if (n <= 1) {
return 1;
} else {
return realfib(n-1) + realfib(n-2);
}
}
END
builder.c <<-END
long cfib(long n) {
return realfib(n);
}
END
Here we've popped the real work into builder.prefix instead of builder.c which just injects the code raw. As a result, we have one layer doing ruby-to-c-to-ruby conversions and another doing the work. It is even faster because you get rid of all those icky conversions at every level. Even the resulting code looks much better:
long realfib(long n) {
if (n <= 1) {
return 1;
} else {
return realfib(n-1) + realfib(n-2);
}
}
static VALUE cfib(VALUE self, VALUE _n) {
long n = NUM2INT(_n);
return INT2NUM(realfib(n));
}
Just one problem
There is one problem I want to point out here. Granted, the problem itself is slightly contrived, but I see examples like this coming up over and over in IRC and the mailing list. The problem is this: people get so myopically focused on using C to make things faster that they don't bother looking at their algorithms or data-structures. It is sad. Ruby may be slow for method dispatch, but bad code can be slow in ANY language. Wanna see a simple and readable pure ruby solution to the above that kicks the crap out of my fastest C solution?
##
# Classic fibonacci is boring, cache the hell out of it.
@@fib = {}
def fasterfib(n)
return 1 if n <= 1
unless @@fib.has_key? n then
@@fib[n] = fasterfib(n-1) + fasterfib(n-2)
end
@@fib[n]
end
C doesn't make ruby fast. Avoiding method dispatch makes ruby fast. You can do that using pure ruby quite a bit of the time by applying your noodle. Check out the times:
% ./fib.rb 10000 15
# of iterations = 10000
user system total real
null_time 0.000000 0.000000 0.000000 ( 0.001779)
fib-ruby 14.450000 0.060000 14.510000 ( 14.628854)
badfib 0.310000 0.000000 0.310000 ( 0.318015)
cfib 0.150000 0.000000 0.150000 ( 0.147117)
fib-cached 0.010000 0.000000 0.010000 ( 0.012523)
And Zed, before you get started, I picked 10k because that was all I had the patience to sit through. This isn't a scientific writeup. So nyah!
Previous Topic
