ruby-core

watson1978@gmail.com wrote:
> Bug #13503: Improve performance of some Time & Rational methods
> https://bugs.ruby-lang.org/issues/13503#change-64447
> ----------------------------------------
> 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(). 

(+Cc tadf, I guess he has been inactive, lately)

While looking at git history, I noticed we used to use Stein's
algorithm for i_gcd, but tadf reverted it in Aug 2008:
commit 5185955f3f64d53f55e34bfe4eaf059b7b347fc4 (r18925)

I do not know why tadf did it, but I tried your benchmarks
but got some regressions and smaller improvements:

==> before <==
Calculating -------------------------------------
         Time#subsec      2.811M (賊 6.0%) i/s -     14.024M in   5.008796s
              Time#-      4.886M (賊 5.8%) i/s -     24.347M in   5.001174s
          Time#round    537.049k (賊 9.0%) i/s -      2.663M in   5.000207s
           Time#to_f      6.974M (賊 3.3%) i/s -     34.896M in   5.009425s
           Time#to_r      2.878M (賊 4.5%) i/s -     14.361M in   5.000027s
          Rational#+      6.691M (賊 0.3%) i/s -     33.471M in   5.002484s
          Rational#-      6.125M (賊 2.2%) i/s -     30.659M in   5.008375s
          Rational#*      6.917M (賊 0.7%) i/s -     34.684M in   5.014488s

==> after <==
Calculating -------------------------------------
         Time#subsec      3.035M (賊 4.1%) i/s -     15.163M in   5.003889s
              Time#-      4.973M (賊 3.6%) i/s -     24.889M in   5.010858s
          Time#round    405.146k (賊 9.8%) i/s -      2.007M in   5.002065s
           Time#to_f      6.588M (賊 3.7%) i/s -     32.927M in   5.004823s
           Time#to_r      2.280M (賊 4.9%) i/s -     11.410M in   5.016082s
          Rational#+      6.242M (賊 3.5%) i/s -     31.210M in   5.006053s
          Rational#-      6.644M (賊 2.2%) i/s -     33.284M in   5.012740s
          Rational#*      7.157M (賊 1.0%) i/s -     35.873M in   5.012748s

Maybe CPU and compiler differences can account for this.
What CPU and compiler are you using?
I tested with AMD FX-8320 @ 3.5GHz + gcc (via Debian 4.9.2-10)

Thank you (quoting the rest for tadf's benefit)

> ### 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

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