watson1978	2017-05-27 14:41:02 +0900 (Sat, 27 May 2017)

  New Revision: 58922

  https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=58922

  Log:
    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 (?\194?\177 9.8%) i/s -     10.659M in   5.022659s
               Time#to_r      2.003M (?\194?\177 9.1%) i/s -      9.959M in   5.012445s
              Rational#+      3.843M (?\194?\177 0.9%) i/s -     19.274M in   5.016254s
              Rational#-      3.820M (?\194?\177 1.3%) i/s -     19.149M in   5.014137s
              Rational#*      5.198M (?\194?\177 1.4%) i/s -     26.016M in   5.005664s
    * After
             Time#subsec      2.902M (?\194?\177 2.9%) i/s -     14.505M in   5.001815s
               Time#to_r      2.503M (?\194?\177 4.8%) i/s -     12.512M in   5.011454s
              Rational#+      4.390M (?\194?\177 1.2%) i/s -     22.001M in   5.012413s
              Rational#-      4.391M (?\194?\177 1.2%) i/s -     22.013M in   5.014584s
              Rational#*      5.872M (?\194?\177 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

  Modified files:
    trunk/rational.c
Index: rational.c
===================================================================
--- rational.c	(revision 58921)
+++ rational.c	(revision 58922)
@@ -280,6 +280,9 @@ rb_gcd_gmp(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/rational.c#L280
 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) https://github.com/ruby/ruby/blob/trunk/rational.c#L293
     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

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/