https://redmine.ruby-lang.org/
https://redmine.ruby-lang.org/favicon.ico?1711330511
2017-04-24T11:07:39Z
Ruby Issue Tracking System
Ruby master - Bug #13503: Improve performance of some Time & Rational methods
https://redmine.ruby-lang.org/issues/13503?journal_id=64447
2017-04-24T11:07:39Z
watson1978 (Shizuo Fujita)
watson1978@gmail.com
<ul></ul><a name="Pull-Req"></a>
<h3 >Pull Req<a href="#Pull-Req" class="wiki-anchor">¶</a></h3>
<p><a href="https://github.com/ruby/ruby/pull/1596" class="external">https://github.com/ruby/ruby/pull/1596</a></p>
Ruby master - Bug #13503: Improve performance of some Time & Rational methods
https://redmine.ruby-lang.org/issues/13503?journal_id=64448
2017-04-24T12:35:50Z
watson1978 (Shizuo Fujita)
watson1978@gmail.com
<ul><li><strong>Description</strong> updated (<a title="View differences" href="/journals/64448/diff?detail_id=44827">diff</a>)</li></ul>
Ruby master - Bug #13503: Improve performance of some Time & Rational methods
https://redmine.ruby-lang.org/issues/13503?journal_id=64646
2017-05-03T03:41:15Z
normalperson (Eric Wong)
normalperson@yhbt.net
<ul></ul><p><a href="mailto:watson1978@gmail.com" class="email">watson1978@gmail.com</a> wrote:</p>
<blockquote>
<h2>Bug <a class="issue tracker-1 status-5 priority-4 priority-default closed" title="Bug: Improve performance of some Time & Rational methods (Closed)" href="https://redmine.ruby-lang.org/issues/13503">#13503</a>: Improve performance of some Time & Rational methods<br>
<a href="https://bugs.ruby-lang.org/issues/13503#change-64447" class="external">https://bugs.ruby-lang.org/issues/13503#change-64447</a>
</h2>
<p>Some Time methods will call internal quov() function.<br>
quov() calls Rational#quo -> f_muldiv() -> i_gcd() in rational.c<br>
i_gcd() will calculate GCD using Euclidean's Algorithm and it lose a long time in modulo method (ie "x = y % x;").</p>
<p>This patch will replace i_gcd() with Stein's algorithm which is faster algorithm for GCD.<br>
(<a href="https://en.wikipedia.org/wiki/Binary_GCD_algorithm" class="external">https://en.wikipedia.org/wiki/Binary_GCD_algorithm</a>)</p>
<p>Some Rational methods also call i_gcd().</p>
</blockquote>
<p>(+Cc tadf, I guess he has been inactive, lately)</p>
<p>While looking at git history, I noticed we used to use Stein's<br>
algorithm for i_gcd, but tadf reverted it in Aug 2008:<br>
commit 5185955f3f64d53f55e34bfe4eaf059b7b347fc4 (r18925)</p>
<p>I do not know why tadf did it, but I tried your benchmarks<br>
but got some regressions and smaller improvements:</p>
<p>==> before <==<br>
Calculating -------------------------------------<br>
Time#subsec 2.811M (± 6.0%) i/s - 14.024M in 5.008796s<br>
Time#- 4.886M (± 5.8%) i/s - 24.347M in 5.001174s<br>
Time#round 537.049k (± 9.0%) i/s - 2.663M in 5.000207s<br>
Time#to_f 6.974M (± 3.3%) i/s - 34.896M in 5.009425s<br>
Time#to_r 2.878M (± 4.5%) i/s - 14.361M in 5.000027s<br>
Rational#+ 6.691M (± 0.3%) i/s - 33.471M in 5.002484s<br>
Rational#- 6.125M (± 2.2%) i/s - 30.659M in 5.008375s<br>
Rational#* 6.917M (± 0.7%) i/s - 34.684M in 5.014488s</p>
<p>==> after <==<br>
Calculating -------------------------------------<br>
Time#subsec 3.035M (± 4.1%) i/s - 15.163M in 5.003889s<br>
Time#- 4.973M (± 3.6%) i/s - 24.889M in 5.010858s<br>
Time#round 405.146k (± 9.8%) i/s - 2.007M in 5.002065s<br>
Time#to_f 6.588M (± 3.7%) i/s - 32.927M in 5.004823s<br>
Time#to_r 2.280M (± 4.9%) i/s - 11.410M in 5.016082s<br>
Rational#+ 6.242M (± 3.5%) i/s - 31.210M in 5.006053s<br>
Rational#- 6.644M (± 2.2%) i/s - 33.284M in 5.012740s<br>
Rational#* 7.157M (± 1.0%) i/s - 35.873M in 5.012748s</p>
<p>Maybe CPU and compiler differences can account for this.<br>
What CPU and compiler are you using?<br>
I tested with AMD FX-8320 @ 3.5GHz + gcc (via Debian 4.9.2-10)</p>
<p>Thank you (quoting the rest for tadf's benefit)</p>
<blockquote>
<a name="Before"></a>
<h3 >Before<a href="#Before" class="wiki-anchor">¶</a></h3>
<pre><code>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
</code></pre>
<a name="After"></a>
<h3 >After<a href="#After" class="wiki-anchor">¶</a></h3>
<pre><code>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
</code></pre>
<a name="Test-code"></a>
<h3 >Test code<a href="#Test-code" class="wiki-anchor">¶</a></h3>
<pre><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
</code></pre>
</blockquote>
Ruby master - Bug #13503: Improve performance of some Time & Rational methods
https://redmine.ruby-lang.org/issues/13503?journal_id=64647
2017-05-03T03:51:08Z
normalperson (Eric Wong)
normalperson@yhbt.net
<ul></ul><p>Eric Wong <a href="mailto:normalperson@yhbt.net" class="email">normalperson@yhbt.net</a> wrote:</p>
<blockquote>
<p>(+Cc tadf, I guess he has been inactive, lately)</p>
</blockquote>
<p><a href="mailto:tadf@dotrb.org" class="email">tadf@dotrb.org</a> (expanded from <a href="mailto:tadf@ruby-lang.org" class="email">tadf@ruby-lang.org</a>): host<br>
dotrb.org[219.94.129.152] said: 553 5.3.0 <a href="mailto:tadf@dotrb.org" class="email">tadf@dotrb.org</a>... User unknown,<br>
not local address (in reply to RCPT TO command)</p>
<p>Hmm... :<</p>
Ruby master - Bug #13503: Improve performance of some Time & Rational methods
https://redmine.ruby-lang.org/issues/13503?journal_id=64648
2017-05-03T03:51:08Z
normalperson (Eric Wong)
normalperson@yhbt.net
<ul></ul><p>Eric Wong <a href="mailto:normalperson@yhbt.net" class="email">normalperson@yhbt.net</a> wrote:</p>
<blockquote>
<p>Maybe CPU and compiler differences can account for this.<br>
What CPU and compiler are you using?<br>
I tested with AMD FX-8320 @ 3.5GHz + gcc (via Debian 4.9.2-10)</p>
</blockquote>
<p>Here is my Pentium M laptop @ 1.60GHz (same gcc):</p>
<p>==> before <==<br>
Calculating -------------------------------------<br>
Time#subsec 877.041k (± 4.8%) i/s - 4.376M in 5.003931s<br>
Time#- 641.496k (± 0.8%) i/s - 3.211M in 5.006323s<br>
Time#round 92.460k (± 6.2%) i/s - 461.538k in 5.010971s<br>
Time#to_f 667.671k (± 0.7%) i/s - 3.352M in 5.021237s<br>
Time#to_r 363.584k (± 1.8%) i/s - 1.827M in 5.026851s<br>
Rational#+ 1.905M (± 0.4%) i/s - 9.549M in 5.012380s<br>
Rational#- 1.969M (± 0.6%) i/s - 9.866M in 5.009592s<br>
Rational#* 2.297M (± 0.5%) i/s - 11.499M in 5.007220s</p>
<p>==> after <==<br>
Calculating -------------------------------------<br>
Time#subsec 851.197k (± 3.3%) i/s - 4.266M in 5.017699s<br>
Time#- 620.533k (± 0.6%) i/s - 3.113M in 5.016971s<br>
Time#round 87.844k (± 7.1%) i/s - 438.845k in 5.021267s<br>
Time#to_f 646.047k (± 0.5%) i/s - 3.233M in 5.004371s<br>
Time#to_r 346.689k (± 1.5%) i/s - 1.738M in 5.014382s<br>
Rational#+ 1.922M (± 1.0%) i/s - 9.629M in 5.009889s<br>
Rational#- 2.026M (± 0.4%) i/s - 10.130M in 4.999171s<br>
Rational#* 2.320M (± 0.5%) i/s - 11.618M in 5.007548s</p>
Ruby master - Bug #13503: Improve performance of some Time & Rational methods
https://redmine.ruby-lang.org/issues/13503?journal_id=64699
2017-05-08T16:29:40Z
watson1978 (Shizuo Fujita)
watson1978@gmail.com
<ul></ul><p>normalperson (Eric Wong) wrote:</p>
<blockquote>
<p>Maybe CPU and compiler differences can account for this.<br>
What CPU and compiler are you using?<br>
I tested with AMD FX-8320 @ 3.5GHz + gcc (via Debian 4.9.2-10)</p>
</blockquote>
<p>I have used MacBook Pro (Retina, 15-inch, Late 2013) and my enviroment is</p>
<ul>
<li>OS : macOS 10.12.4</li>
<li>CPU : Intel Core i7 2.6 GHz</li>
<li>Compiler : clang-802.0.42 in Xcode 8.3.2</li>
</ul>
<p>In additional, I turned off turbo boost feater in Intel CPU when measured the benchmark using <a href="https://github.com/rugarciap/Turbo-Boost-Switcher" class="external">https://github.com/rugarciap/Turbo-Boost-Switcher</a></p>
<p>Thank you.</p>
Ruby master - Bug #13503: Improve performance of some Time & Rational methods
https://redmine.ruby-lang.org/issues/13503?journal_id=65125
2017-05-27T05:41:07Z
watson1978 (Shizuo Fujita)
watson1978@gmail.com
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li></ul><p>Applied in changeset trunk|r58922.</p>
<hr>
<p>Improve performance of some Time & Rational methods</p>
<p>rational.c (i_gcd): replace GCD algorithm from Euclidean algorithm to Stein<br>
algorithm (<a href="https://en.wikipedia.org/wiki/Binary_GCD_algorithm" class="external">https://en.wikipedia.org/wiki/Binary_GCD_algorithm</a>).</p>
<pre><code>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
<a href="/issues/13503">[ruby-core:80843]</a> [Bug #13503] [Fix GH-1596]
</code></pre>
<a name="Before"></a>
<h3 >Before<a href="#Before" class="wiki-anchor">¶</a></h3>
<pre><code> Time#subsec 2.142M (± 9.8%) i/s - 10.659M in 5.022659s
Time#to_r 2.003M (± 9.1%) i/s - 9.959M in 5.012445s
Rational#+ 3.843M (± 0.9%) i/s - 19.274M in 5.016254s
Rational#- 3.820M (± 1.3%) i/s - 19.149M in 5.014137s
Rational#* 5.198M (± 1.4%) i/s - 26.016M in 5.005664s
</code></pre>
<ul>
<li>
<p>After<br>
Time#subsec 2.902M (± 2.9%) i/s - 14.505M in 5.001815s<br>
Time#to_r 2.503M (± 4.8%) i/s - 12.512M in 5.011454s<br>
Rational#+ 4.390M (± 1.2%) i/s - 22.001M in 5.012413s<br>
Rational#- 4.391M (± 1.2%) i/s - 22.013M in 5.014584s<br>
Rational#* 5.872M (± 2.2%) i/s - 29.369M in 5.003666s</p>
</li>
<li>
<p>Test code<br>
require 'benchmark/ips'</p>
</li>
</ul>
<p>Benchmark.ips do |x|<br>
x.report "Time#subsec" do |t|<br>
time = Time.now<br>
t.times { time.subsec }<br>
end</p>
<p>x.report "Time#to_r" do |t|<br>
time = Time.now<br>
t.times { time.to_r }<br>
end</p>
<p>x.report "Rational#+" do |t|<br>
rat1 = 1/2r<br>
rat2 = 1/3r<br>
t.times { rat1 + rat2 }<br>
end</p>
<p>x.report "Rational#-" do |t|<br>
rat1 = 1/3r<br>
rat2 = 1/2r<br>
t.times { rat1 - rat2 }<br>
end</p>
<p>x.report "Rational#*" do |t|<br>
rat1 = 1/3r<br>
rat2 = 1/2r<br>
t.times { rat1 * rat2 }<br>
end<br>
end</p>
Ruby master - Bug #13503: Improve performance of some Time & Rational methods
https://redmine.ruby-lang.org/issues/13503?journal_id=74197
2018-09-25T22:33:23Z
mame (Yusuke Endoh)
mame@ruby-lang.org
<ul><li><strong>Has duplicate</strong> <i><a class="issue tracker-2 status-5 priority-4 priority-default closed" href="/issues/15161">Feature #15161</a>: making gcd faster for 3x3</i> added</li></ul>