From: Kurt Stephens <ks@...>
Date: 2007-12-14T02:39:46+09:00
Subject: Ruby Core Performance Patch: Fixnum#gcd

This is a multi-part message in MIME format.
--------------020701080405040203030209
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

See the attached patch.

Much Love to Ruby,
Kurt Stephens

=======================================================

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 hack saved 15% execution time in a large Rails application.

See http://kurtstephens.com/node/34

=======================
# fixnum_gcd_test.rb

require 'benchmark'
require 'rational'

srand(1212398)

args = (0...10000).map do | x |
  [ rand(100000), rand(100000) ]
end
# puts args.inspect

Benchmark.bmbm do | bm |
  bm.report("Fixnum#gcd") do
    100.times do
      args.each do | x, y |
        x.gcd(y)
      end
    end
  end
end

=======================

 > ruby-trunk/ruby fixnum_gcd_test.rb
Rehearsal ----------------------------------------------
Fixnum#gcd   1.160000   0.000000   1.160000 (  1.191571)
------------------------------------- total: 1.160000sec

                 user     system      total        real
Fixnum#gcd   1.160000   0.010000   1.170000 (  1.203422)

 > ruby-trunk-orig/ruby fixnum_gcd_test.rb
Rehearsal ----------------------------------------------
Fixnum#gcd   3.980000   0.000000   3.980000 (  4.089624)
------------------------------------- total: 3.980000sec

                 user     system      total        real
Fixnum#gcd   3.960000   0.000000   3.960000 (  4.031807)



--------------020701080405040203030209
Content-Type: text/x-patch;
 name="ruby-trunk.fixnum-gcd.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="ruby-trunk.fixnum-gcd.patch"

--- ruby-trunk-orig/numeric.c	2007-12-12 12:58:00.000000000 -0600
+++ ruby-trunk/numeric.c	2007-12-13 11:33:51.000000000 -0600
@@ -2316,10 +2316,85 @@
       default:
 	return rb_num_coerce_bin(x, y);
     }
 }
 
+/*
+
+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 hack saved 15% execution time in a large Rails application.
+
+See http://kurtstephens.com/node/34
+
+=======================
+# fixnum_gcd_test.rb
+
+require 'benchmark'
+require 'rational'
+
+srand(1212398)
+
+args = (0...10000).map do | x |
+  [ rand(100000), rand(100000) ]
+end
+# puts args.inspect
+
+Benchmark.bmbm do | bm |
+  bm.report("Fixnum#gcd") do
+    100.times do 
+      args.each do | x, y |
+        x.gcd(y)
+      end
+    end
+  end
+end
+
+=======================
+
+ > ruby-trunk/ruby fixnum_gcd_test.rb 
+Rehearsal ----------------------------------------------
+Fixnum#gcd   1.160000   0.000000   1.160000 (  1.191571)
+------------------------------------- total: 1.160000sec
+
+                 user     system      total        real
+Fixnum#gcd   1.160000   0.010000   1.170000 (  1.203422)
+ > ruby-trunk-orig/ruby fixnum_gcd_test.rb 
+Rehearsal ----------------------------------------------
+Fixnum#gcd   3.980000   0.000000   3.980000 (  4.089624)
+------------------------------------- total: 3.980000sec
+
+                 user     system      total        real
+Fixnum#gcd   3.960000   0.000000   3.960000 (  4.031807)
+
+*/
+
+static VALUE 
+fix_gcd(int argc, VALUE *argv, VALUE self) {
+  if ( argc != 1 ) {
+    rb_raise(rb_eArgError, "wrong number of arguments (%d for %d)", argc, 1);
+  }
+  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 ) {
+      long tmp = min;
+      min = max % min;
+      max = tmp;
+    }
+    return LONG2FIX(max);
+  } else {
+    return rb_call_super(1, argv);
+  }
+}
+
 static VALUE
 int_pow(long x, unsigned long y)
 {
     int neg = x < 0;
     long z = 1;
@@ -3151,10 +3226,11 @@
     rb_define_method(rb_cFixnum, "%", fix_mod, 1);
     rb_define_method(rb_cFixnum, "modulo", fix_mod, 1);
     rb_define_method(rb_cFixnum, "divmod", fix_divmod, 1);
     rb_define_method(rb_cFixnum, "quo", fix_quo, 1);
     rb_define_method(rb_cFixnum, "fdiv", fix_quo, 1);
+    rb_define_method(rb_cFixnum, "gcd", (VALUE(*)(ANYARGS)) fix_gcd, -1);
     rb_define_method(rb_cFixnum, "**", fix_pow, 1);
 
     rb_define_method(rb_cFixnum, "abs", fix_abs, 0);
 
     rb_define_method(rb_cFixnum, "==", fix_equal, 1);

--------------020701080405040203030209--