Kurt Stephens

Nerd Up!

Ruby: Date / Rational / Fixnum#gcd hack increased app performance by 15%

This discussion is closed: you can't post new comments.
Kurt on Wed, 2007-03-28 22:23.

UPDATE: Fixnum#gcd was accepted int MRI 1.8: See http://kurtstephens.com/node/114 .

Ruby Date uses Rational heavily, which calls Integer#gcd for every new Rational. The Integer#gcd method is generic to handle Bignums, but performs terribly for Fixnum#gcd(Fixnum), which is probably the most often case.

This RubyInline hack saved 15% execution time in a large Rails application:

require 'inline'

class Fixnum
  inline do | builder |
    builder.c_raw '
    static
    VALUE 
    gcd(int argc, VALUE *argv, VALUE self) {
      if ( argc != 1 ) {
        rb_raise(rb_eArgError, "wrong number of arguments (%d for %d)",
                 argc, 1);
      }
      /* Handle Fixnum#gcd(Fixnum) case directly. */
      if ( FIXNUM_P(argv[0]) ) {
        /* fprintf(stderr, "Using Fixnum#gcd(Fixnum)\n"); */
        long a = FIX2LONG(self);
        long b = FIX2LONG(argv[0]);
        long min = a < 0 ? - a : a;
        long max = b < 0 ? - b : b;
        while ( min > 0 ) {
          int tmp = min;
          min = max % min;
          max = tmp;
        }
        return LONG2FIX(max);
      } else {
        /* fprintf(stderr, "Using super#gcd\n"); */
        return rb_call_super(1, argv);
      }
    }
    '
  end
end

Update:

Sorry for the late reply. If the code above does not work via cut-and-paste, download it from here.

This will be released soon as a gem dynamic library called speedfreaks,
with other performance-enhancing snippets.

Thanks for the feedback!

links: Kurt's blog | 12077 reads

submit


you might consider submitting this to the Ruby core people. Why not?

I think your code got hosed


I think the paste hosed your code, since FIX2LONG and LONG2FIX require params, thus the above code section does not compile.

Looks like the correct code would be, “long a= FIX2LONG’(self)’;” and also “return LONG2FIX’(max)’;” —minus the single ticks (had to put those in for the comment to correctly render).

Copy-paste compilation of the original code also errors because of the invalid quote characters.

Thanks for sharing the trick!

When’s speedfreaks


When’s speedfreaks coming? I’ve been looking forward to it for a while now. My application is using up a lot of CPU time on my host and I’m desperate for ways to speed it up.

Ruby 1.9 and a Gem soon?


Fixnum#gcd patch has been submitted for Ruby 1.8 and 1.9 core. There are some hacks that I’m testing at work. We’ll probably roll them together soon.
Sorry for the wait.

— Kurt

accepted?


was the patch accepted?

accepted?


Nope.

try again


Maybe creating a ticket on http://redmine.ruby-lang.org/issues/show/174 would cause more publicity :)
-R

gem


Is this a drop in replacement for it? If so you could release a gem that integrates it, a la
require ‘gcd_fix’
Is that even possible?
:)
-R

Rejected again


Appears that the patch was rejected as “already applied” for ruby 1.9—is that the case?

http://www.ruby-forum.com/topic/163628#new

Ruby 1.9


The 1.9 patch improves Fixnum#gcd performance by 300%

already applied


I did some of my own tests and it appears that ruby 1.9 “already has” an optimized gcd. Do yours differ?
Please respond :)
-=R

1.9?


I don’t use 1.9 for production code; there are a lot of people who are still using 1.8.

— Kurt