https://redmine.ruby-lang.org/https://redmine.ruby-lang.org/favicon.ico?17113305112019-06-17T21:29:31ZRuby Issue Tracking SystemRuby master - Misc #15925: Speed up SortedSet#min, #max, #sum etc.?https://redmine.ruby-lang.org/issues/15925?journal_id=786562019-06-17T21:29:31Zjeremyevans0 (Jeremy Evans)merch-redmine@jeremyevans.net
<ul><li><strong>File</strong> <a href="/attachments/7839">sorted-set-min-max-sum.patch</a> <a class="icon-only icon-download" title="Download" href="/attachments/download/7839/sorted-set-min-max-sum.patch">sorted-set-min-max-sum.patch</a> added</li><li><strong>Status</strong> changed from <i>Open</i> to <i>Assigned</i></li><li><strong>Assignee</strong> set to <i>knu (Akinori MUSHA)</i></li></ul><p>Your recommended implementation greatly improves performance. From the benchmark in the attached patch:</p>
<pre><code>Calculating -------------------------------------
../ruby2/run_ruby run_ruby
min 4.811k 1.166M i/s - 14.501k times in 3.014412s 0.012441s
max 4.761k 1.215M i/s - 14.187k times in 2.979777s 0.011680s
minmax 4.530k 321.515k i/s - 13.505k times in 2.980916s 0.042004s
sum 5.924k 113.139k i/s - 17.646k times in 2.978920s 0.155968s
Comparison:
min
run_ruby: 1165552.1 i/s
../ruby2/run_ruby: 4810.6 i/s - 242.29x slower
max
run_ruby: 1214686.2 i/s
../ruby2/run_ruby: 4761.1 i/s - 255.13x slower
minmax
run_ruby: 321514.7 i/s
../ruby2/run_ruby: 4530.5 i/s - 70.97x slower
sum
run_ruby: 113138.6 i/s
../ruby2/run_ruby: 5923.6 i/s - 19.10x slower
</code></pre> Ruby master - Misc #15925: Speed up SortedSet#min, #max, #sum etc.?https://redmine.ruby-lang.org/issues/15925?journal_id=786702019-06-18T08:39:23Zjanosch-x (Janosch Müller)
<ul></ul><p>jeremyevans0 (Jeremy Evans) wrote:</p>
<blockquote>
<p>Your recommended implementation greatly improves performance.</p>
</blockquote>
<p>I fear this benchmark result "over-idealizes" the performance improvements because <code>SortedSet#to_a</code> is memoized <a href="https://github.com/ruby/ruby/blob/afd68cd87114fb49158462f1594cacfd2b765e9b/lib/set.rb#L781-L784" class="external">here</a> on the first run, and only cleared when set contents are changed.</p>
<p>Real world performance improvements should end up between 2x (at most) for a fresh or modified set (by virtue of avoiding the extra iteration mentioned in the report), and the results of this benchmark.</p> Ruby master - Misc #15925: Speed up SortedSet#min, #max, #sum etc.?https://redmine.ruby-lang.org/issues/15925?journal_id=903652021-02-13T07:49:45Zjeremyevans0 (Jeremy Evans)merch-redmine@jeremyevans.net
<ul><li><strong>Status</strong> changed from <i>Assigned</i> to <i>Closed</i></li></ul><p>SortedSet is no longer part of stdlib, so this can be closed.</p>