ruby-core

Issue #13503 has been updated by watson1978 (Shizuo Fujita).


### Pull Req
https://github.com/ruby/ruby/pull/1596



----------------------------------------
Bug #13503: Improve performance of some Time & Rational methods
https://bugs.ruby-lang.org/issues/13503#change-64447

* Author: watson1978 (Shizuo Fujita)
* Status: Open
* Priority: Normal
* Assignee: 
* Target version: 
* ruby -v: 
* Backport: 2.2: UNKNOWN, 2.3: UNKNOWN, 2.4: UNKNOWN
----------------------------------------
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      1.977M (賊 9.0%) i/s -      9.816M in   5.003551s
              Time#-      3.844M (賊 4.9%) i/s -     19.220M in   5.011682s
          Time#round    397.118k (賊10.5%) i/s -      1.976M in   5.032733s
           Time#to_f      5.566M (賊 1.9%) i/s -     27.876M in   5.010230s
           Time#to_r      1.874M (賊 8.7%) i/s -      9.339M in   5.018589s
          Rational#+      3.889M (賊 0.8%) i/s -     19.521M in   5.019869s
          Rational#-      3.684M (賊 0.9%) i/s -     18.517M in   5.026471s
          Rational#*      3.681M (賊 0.9%) i/s -     18.501M in   5.025969s
~~~

### After
~~~
Calculating -------------------------------------
         Time#subsec      2.640M (賊 3.0%) i/s -     13.204M in   5.005680s
              Time#-      4.241M (賊 2.1%) i/s -     21.225M in   5.006865s
          Time#round    404.738k (賊10.9%) i/s -      2.003M in   5.009187s
           Time#to_f      5.659M (賊 2.1%) i/s -     28.297M in   5.002788s
           Time#to_r      2.263M (賊 7.0%) i/s -     11.307M in   5.024765s
          Rational#+      4.386M (賊 0.6%) i/s -     22.029M in   5.023014s
          Rational#-      4.391M (賊 0.7%) i/s -     22.037M in   5.018534s
          Rational#*      4.355M (賊 1.7%) i/s -     21.820M in   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
~~~




-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>