From: Eric Wong Date: 2017-05-03T03:40:55+00:00 Subject: [ruby-core:80983] Re: [Ruby trunk Bug#13503] Improve performance of some Time & Rational methods 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: