Improve performance of some Time & Rational methods

rational.c (i_gcd): replace GCD algorithm from Euclidean algorithm to Stein
    algorithm (https://en.wikipedia.org/wiki/Binary_GCD_algorithm).

    Some Time methods will call internal quov() function and it calls
    Rational#quo -> f_muldiv() -> i_gcd() in rational.c
    And some Rational methods also call i_gcd().

    The implementation of Euclidean algorithm spent a long time at modulo
    operation (ie "x = y % x;").
    The Stein algorithm will replace with shift operation which is faster
    than modulo.

    Time#subsec -> 36 % up
    Time#to_r   -> 26 % up
    Rational#+  -> 14 % up
    Rational#-  -> 15 % up
    Rational#*  -> 13 % up

    [ruby-core:80843] [Bug #13503] [Fix GH-1596]

### Before
         Time#subsec      2.142M (± 9.8%) i/s -     10.659M in   5.022659s
           Time#to_r      2.003M (± 9.1%) i/s -      9.959M in   5.012445s
          Rational#+      3.843M (± 0.9%) i/s -     19.274M in   5.016254s
          Rational#-      3.820M (± 1.3%) i/s -     19.149M in   5.014137s
          Rational#*      5.198M (± 1.4%) i/s -     26.016M in   5.005664s
* After
         Time#subsec      2.902M (± 2.9%) i/s -     14.505M in   5.001815s
           Time#to_r      2.503M (± 4.8%) i/s -     12.512M in   5.011454s
          Rational#+      4.390M (± 1.2%) i/s -     22.001M in   5.012413s
          Rational#-      4.391M (± 1.2%) i/s -     22.013M in   5.014584s
          Rational#*      5.872M (± 2.2%) i/s -     29.369M in   5.003666s

* Test code
require 'benchmark/ips'

Benchmark.ips do |x|
  x.report "Time#subsec" do |t|
    time = Time.now
    t.times { time.subsec }
  end

  x.report "Time#to_r" do |t|
    time = Time.now
    t.times { time.to_r }
  end

  x.report "Rational#+" do |t|
    rat1 = 1/2r
    rat2 = 1/3r
    t.times { rat1 + rat2 }
  end

  x.report "Rational#-" do |t|
    rat1 = 1/3r
    rat2 = 1/2r
    t.times { rat1 - rat2 }
  end

  x.report "Rational#*" do |t|
    rat1 = 1/3r
    rat2 = 1/2r
    t.times { rat1 * rat2 }
  end
end

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@58922 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 25 insertions, 5 deletions

diff --git a/rational.c b/rational.c
index 54fac1e5bc..bd32399e79 100644
--- a/rational.c
+++ b/rational.c
@@ -280,6 +280,9 @@ rb_gcd_gmp(VALUE x, VALUE y)
 inline static long
 i_gcd(long x, long y)
 {
+    unsigned long u, v, t;
+    int shift;
+
     if (x < 0)
 	x = -x;
     if (y < 0)
@@ -290,12 +293,29 @@ i_gcd(long x, long y)
     if (y == 0)
 	return x;
 
-    while (x > 0) {
-	long t = x;
-	x = y % x;
-	y = t;
+    u = (unsigned long)x;
+    v = (unsigned long)y;
+    for (shift = 0; ((u | v) & 1) == 0; ++shift) {
+	u >>= 1;
+	v >>= 1;
     }
-    return y;
+
+    while ((u & 1) == 0)
+	u >>= 1;
+
+    do {
+	while ((v & 1) == 0)
+	    v >>= 1;
+
+	if (u > v) {
+	    t = v;
+	    v = u;
+	    u = t;
+	}
+	v = v - u;
+    } while (v != 0);
+
+    return (long)(u << shift);
 }
 
 inline static VALUE