Ruby » Ruby master

Bug #13503

Updated by watson1978 (Shizuo Fujita) over 7 years ago

Some Time methods will call internal quov() function. 
 quov() calls Rational#quo -> f_muldiv() -> i_gcd() in rational.c 
 i_gcd() will calculate GCD using Euclidean's Algorithm and it lose a long time in modulo method (ie "x = y % x;"). 

 This patch will replace i_gcd() with Stein's algorithm which is faster algorithm for GCD. 
 (https://en.wikipedia.org/wiki/Binary_GCD_algorithm) 

 Some Rational methods also call i_gcd().  

 ### Before 
 ~~~ 
 Calculating ------------------------------------- 
          Time#subsec        2.017M 1.977M (± 8.6%) 9.0%) i/s -       10.052M        9.816M in     5.020331s 5.003551s 
               Time#-        4.246M 3.844M (± 1.1%) 4.9%) i/s -       21.259M 19.220M in     5.006968s 5.011682s 
           Time#round      402.944k (±11.0%) 397.118k (±10.5%) i/s -        1.996M 1.976M in     5.014424s 5.032733s 
            Time#to_f        5.627M 5.566M (± 1.3%) 1.9%) i/s -       28.195M 27.876M in     5.011366s 5.010230s 
            Time#to_r        1.927M 1.874M (± 8.2%) 8.7%) i/s -        9.590M 9.339M in     5.009198s 5.018589s 
           Rational#+        3.894M 3.889M (± 1.0%) 0.8%) i/s -       19.545M 19.521M in     5.019923s 5.019869s 
           Rational#-        3.811M 3.684M (± 1.0%) 0.9%) i/s -       19.125M 18.517M in     5.018842s 5.026471s 
           Rational#*        5.148M 3.681M (± 1.1%) 0.9%) i/s -       25.858M 18.501M in     5.023586s 5.025969s 
 ~~~ 

 ### After 
 ~~~ 
 Calculating ------------------------------------- 
          Time#subsec        2.648M 2.640M (± 3.0%) i/s -       13.257M 13.204M in     5.010600s 5.005680s 
               Time#-        4.265M 4.241M (± 1.4%) 2.1%) i/s -       21.372M 21.225M in     5.012480s 5.006865s 
           Time#round      393.309k (±12.5%) 404.738k (±10.9%) i/s -        1.934M 2.003M in     5.000319s 5.009187s 
            Time#to_f        5.638M 5.659M (± 2.0%) 2.1%) i/s -       28.223M 28.297M in     5.008422s 5.002788s 
            Time#to_r        2.313M 2.263M (± 5.2%) 7.0%) i/s -       11.568M 11.307M in     5.015379s 5.024765s 
           Rational#+        4.366M 4.386M (± 1.6%) 0.6%) i/s -       21.846M 22.029M in     5.004487s 5.023014s 
           Rational#-        4.443M 4.391M (± 1.2%) 0.7%) i/s -       22.255M 22.037M in     5.009509s 5.018534s 
           Rational#*        5.776M 4.355M (± 1.1%) 1.7%) i/s -       28.888M 21.820M in     5.002322s 5.011914s 
 ~~~ 

 ### 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#-" do |t| 
     time1 = Time.now 
     time2 = Time.now 
     t.times { time1 - time2 } 
   end 

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

   x.report "Time#to_f" do |t| 
     time = Time.now 
     t.times { time.to_f } 
   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 
 ~~~ 

Back