🕷 zenspider.com

by ryan davis



sitemap
Looking for the Ruby Quickref?

Recursive Functions in RubyInline

Published 2006-09-22 @ 16:20

Tagged rubyinline, ruby

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:

return FIX2INT(badfib(self, INT2FIX(n-1))) + FIX2INT(badfib(self, INT2FIX(n-2)));

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!