https://bugs.ruby-lang.org/https://bugs.ruby-lang.org/favicon.ico?17113305112013-11-18T09:43:21ZRuby Issue Tracking SystemRuby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=429902013-11-18T09:43:21Zzzak (zzak _)
<ul><li><strong>Category</strong> set to <i>lib</i></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> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=430042013-11-19T07:04:20Zvjoel (Joel VanderWerf)vjoel@users.sourceforge.net
<ul></ul><p>As noted at <a href="https://github.com/ruby/ruby/pull/451#issuecomment-28741490" class="external">https://github.com/ruby/ruby/pull/451#issuecomment-28741490</a>:</p>
<p>These benchmarks miss the point of using rbtree, which is to pay a small insertion cost to keep the structure sorted so that ordered lookups are fast. If you only need to perform lookups <em>after</em> the structure is built, then rbtree is a waste of time.</p>
<p>See <a href="https://gist.github.com/vjoel/7535917" class="external">https://gist.github.com/vjoel/7535917</a>.</p>
<p>Also, this part of the benchmark is particularly misleading:</p>
<p>b.report("#to_a #{n} items") {<br>
10000.times { s.to_a }<br>
}</p>
<p>because the non-rbtree implementation <em>caches</em> the #to_a output and will never drop that cache inside of the above loop.</p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=431002013-11-23T17:51:11Zknu (Akinori MUSHA)knu@ruby-lang.org
<ul></ul><p>Thanks for your input, guys.</p>
<p>I think I'll drop the optional rbtree version of SortedSet for now, since rbtree is seemingly broken for the latest version of ruby.</p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=431012013-11-23T18:09:35Zmame (Yusuke Endoh)mame@ruby-lang.org
<ul></ul><p>knu (Akinori MUSHA) wrote:</p>
<blockquote>
<p>rbtree is seemingly broken for the latest version of ruby.</p>
</blockquote>
<p>What do you mean? What broke rbtree?<br>
I'm afraid it is a more serious problem than this ticket itself.</p>
<p>--<br>
Yusuke Endoh <a href="mailto:mame@tsg.ne.jp" class="email">mame@tsg.ne.jp</a></p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=431072013-11-23T21:23:21Zzzak (zzak _)
<ul></ul><p>See <a class="issue tracker-1 status-5 priority-4 priority-default closed" title="Bug: RubyGems 2.0 has an incompatibility about installation of extension libraries (Closed)" href="https://bugs.ruby-lang.org/issues/7698">#7698</a> and <a href="https://github.com/seki/Drip/issues/4" class="external">https://github.com/seki/Drip/issues/4</a></p>
<blockquote>
<p>On Nov 23, 2013, at 6:09 PM, "mame (Yusuke Endoh)" <a href="mailto:mame@tsg.ne.jp" class="email">mame@tsg.ne.jp</a> wrote:</p>
<p>Issue <a class="issue tracker-2 status-5 priority-4 priority-default closed" title="Feature: [PATCH] Remove rbtree implementation of SortedSet due to performance regression (Closed)" href="https://bugs.ruby-lang.org/issues/9121">#9121</a> has been updated by mame (Yusuke Endoh).</p>
<p>knu (Akinori MUSHA) wrote:</p>
<blockquote>
<p>rbtree is seemingly broken for the latest version of ruby.</p>
</blockquote>
<p>What do you mean? What broke rbtree?<br>
I'm afraid it is a more serious problem than this ticket itself.</p>
<h2>--<br>
Yusuke Endoh <a href="mailto:mame@tsg.ne.jp" class="email">mame@tsg.ne.jp</a>
</h2>
<p>Bug <a class="issue tracker-2 status-5 priority-4 priority-default closed" title="Feature: [PATCH] Remove rbtree implementation of SortedSet due to performance regression (Closed)" href="https://bugs.ruby-lang.org/issues/9121">#9121</a>: [PATCH] Remove rbtree implementation of SortedSet due to performance regression<br>
<a href="https://bugs.ruby-lang.org/issues/9121#change-43101" class="external">https://bugs.ruby-lang.org/issues/9121#change-43101</a></p>
<p>Author: xshay (Xavier Shay)<br>
Status: Assigned<br>
Priority: Normal<br>
Assignee: knu (Akinori MUSHA)<br>
Category: lib<br>
Target version:<br>
ruby -v: 2.0.0-p247<br>
Backport: 1.9.3: UNKNOWN, 2.0.0: UNKNOWN</p>
<p>rbtree is slower than the pure ruby version.</p>
<p>I have provided benchmarks and a patch here:<br>
<a href="https://github.com/ruby/ruby/pull/451" class="external">https://github.com/ruby/ruby/pull/451</a></p>
<blockquote>
<p>ruby sorted_set_benchmark.rb<br>
using rbtree<br>
user system total real<br>
#add 0.010000 0.000000 0.010000 ( 0.016446)<br>
#delete 0.020000 0.000000 0.020000 ( 0.013248)<br>
#include? 1000 items 0.010000 0.000000 0.010000 ( 0.011822)<br>
#include? 2000 items 0.020000 0.000000 0.020000 ( 0.012572)<br>
#include? 3000 items 0.020000 0.000000 0.020000 ( 0.013610)<br>
#include? 4000 items 0.020000 0.000000 0.020000 ( 0.014295)<br>
#include? 5000 items 0.010000 0.000000 0.010000 ( 0.018024)<br>
#to_a 1000 items 0.580000 0.020000 0.600000 ( 0.616104)<br>
#to_a 2000 items 1.170000 0.040000 1.210000 ( 1.213406)<br>
#to_a 3000 items 1.730000 0.030000 1.760000 ( 1.773069)<br>
#to_a 4000 items 2.370000 0.040000 2.410000 ( 2.420450)<br>
#to_a 5000 items 2.920000 0.050000 2.970000 ( 2.975497)<br>
ruby sorted_set_benchmark.rb<br>
NOT using rbtree<br>
user system total real<br>
#add 0.010000 0.000000 0.010000 ( 0.007889)<br>
#delete 0.010000 0.000000 0.010000 ( 0.004631)<br>
#include? 1000 items 0.000000 0.000000 0.000000 ( 0.005060)<br>
#include? 2000 items 0.010000 0.000000 0.010000 ( 0.005950)<br>
#include? 3000 items 0.010000 0.000000 0.010000 ( 0.005814)<br>
#include? 4000 items 0.010000 0.000000 0.010000 ( 0.005993)<br>
#include? 5000 items 0.010000 0.000000 0.010000 ( 0.006923)<br>
#to_a 1000 items 0.000000 0.000000 0.000000 ( 0.001863)<br>
#to_a 2000 items 0.000000 0.000000 0.000000 ( 0.002145)<br>
#to_a 3000 items 0.000000 0.000000 0.000000 ( 0.002129)<br>
#to_a 4000 items 0.000000 0.000000 0.000000 ( 0.002265)<br>
#to_a 5000 items 0.000000 0.000000 0.000000 ( 0.002428)</p>
</blockquote>
<p>--<br>
<a href="http://bugs.ruby-lang.org/" class="external">http://bugs.ruby-lang.org/</a></p>
</blockquote> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=431082013-11-23T21:53:31Zknu (Akinori MUSHA)knu@ruby-lang.org
<ul></ul><p>mame (Yusuke Endoh) wrote:</p>
<blockquote>
<p>knu (Akinori MUSHA) wrote:</p>
<blockquote>
<p>rbtree is seemingly broken for the latest version of ruby.</p>
</blockquote>
<p>What do you mean? What broke rbtree?</p>
</blockquote>
<p>Try it yourself and you'll see. It relies on the internal data structure of RHash at some point of Ruby that lasted until 1.9.3.</p>
<blockquote>
<p>I'm afraid it is a more serious problem than this ticket itself.</p>
</blockquote>
<p>It is obviously a third-party issue and the point of this issue is that we should not depend on it any more, so I'll go ahead anyway.</p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=431092013-11-23T22:01:46Zknu (Akinori MUSHA)knu@ruby-lang.org
<ul></ul><p>I wrote:</p>
<blockquote>
<p>... and the point of this issue is that we should not depend on it any more, so I'll go ahead anyway.</p>
</blockquote>
<p>Oops, I mistook this issue for something else, I just thought that's another reason to ditch the rbtree dependency albeit optional.</p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=431102013-11-23T22:07:03Zmame (Yusuke Endoh)mame@ruby-lang.org
<ul></ul><p>zzak (Zachary Scott) wrote:</p>
<blockquote>
<p>See <a class="issue tracker-1 status-5 priority-4 priority-default closed" title="Bug: RubyGems 2.0 has an incompatibility about installation of extension libraries (Closed)" href="https://bugs.ruby-lang.org/issues/7698">#7698</a> and <a href="https://github.com/seki/Drip/issues/4" class="external">https://github.com/seki/Drip/issues/4</a></p>
</blockquote>
<p>Thank you, but it works now for me.</p>
<p>$ ruby -v<br>
ruby 2.0.0p353 (2013-11-22 revision 43784) [x86_64-linux]<br>
$ gem -v<br>
2.1.11<br>
$ gem install rbtree<br>
Building native extensions. This could take a while...<br>
Successfully installed rbtree-0.4.1<br>
Parsing documentation for rbtree-0.4.1<br>
Done installing documentation for rbtree after 0 seconds<br>
1 gem installed</p>
<p>knu (Akinori MUSHA) wrote:</p>
<blockquote>
<blockquote>
<p>What do you mean? What broke rbtree?</p>
</blockquote>
<p>Try it yourself and you'll see. It relies on the internal data structure of RHash at some point of Ruby that lasted until 1.9.3.</p>
</blockquote>
<p>I'm using rbtree on 2.0.0 everyday, but I have never encountered any problem.<br>
Where was the issue discussed? Could you show me a pointer?</p>
<blockquote>
<blockquote>
<p>I'm afraid it is a more serious problem than this ticket itself.</p>
</blockquote>
<p>It is obviously a third-party issue and the point of this issue is that we should not depend on it any more, so I'll go ahead anyway.</p>
</blockquote>
<p>In principle, I agree that it is not cool for a standard library to depend<br>
a third-party library. But in fact, (a part of) set.rb has depended on rbtree.<br>
As Joel said, some operations will become very slow if it is removed.<br>
Isn't it a compatibility problem?</p>
<p>--<br>
Yusuke Endoh <a href="mailto:mame@tsg.ne.jp" class="email">mame@tsg.ne.jp</a></p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=431112013-11-23T22:44:21Zknu (Akinori MUSHA)knu@ruby-lang.org
<ul><li><strong>Target version</strong> set to <i>3.0</i></li></ul><p>Maybe. And I noticed the second preview (not RC though) of 2.1.0 was out, so I'll postpone any change to SortedSet to the next major.</p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=432862013-12-01T06:09:40Ztmm1 (Aman Karmani)ruby@tmm1.net
<ul></ul><p>The following patch fixes rbtree on ruby 2.1: <a href="https://gist.github.com/tmm1/7609371" class="external">https://gist.github.com/tmm1/7609371</a></p>
<p>I emailed it to <a href="mailto:burningdowntheopera@yahoo.co.jp" class="email">burningdowntheopera@yahoo.co.jp</a> 8 days ago, but no response.</p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=432972013-12-01T12:06:57Zzzak (zzak _)
<ul></ul><p>Thank you tmm1!</p>
<p>There is also rbtree2 (<a href="https://github.com/kitak/rbtree2" class="external">https://github.com/kitak/rbtree2</a>), that is also seemingly unmaintained, but perhaps they will be more willing to do a release. Ofcourse, it would be best if we could get OZAWA-san to respond to the patch and release.</p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=438962013-12-26T00:00:19Zknu (Akinori MUSHA)knu@ruby-lang.org
<ul></ul><p>On second thought, if a working version rbtree is available out there (at least for CRuby and hopefully for JRuby) then I would like SortedSet to be moved from the standard library to a third-party gem.</p>
<p>The non-rbtree implementation of SortedSet should be seen as an ad hoc substitute, not a professional, production quality implementation to provide the performance characteristics that would be naturally expected from the name.</p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=444742014-01-21T17:07:12Zzzak (zzak _)
<ul></ul><p>I just wanted to remind everyone of the discussion that took place regarding adding RBTree to stdlib in [Feature <a class="issue tracker-2 status-6 priority-4 priority-default closed" title="Feature: RBTree Should be Added to the Standard Library (Rejected)" href="https://bugs.ruby-lang.org/issues/2348">#2348</a>]</p> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=485022014-08-27T03:29:25Zhsbt (Hiroshi SHIBATA)hsbt@ruby-lang.org
<ul><li><strong>Related to</strong> <i><a class="issue tracker-2 status-6 priority-4 priority-default closed" href="/issues/2348">Feature #2348</a>: RBTree Should be Added to the Standard Library</i> added</li></ul> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=892142020-12-14T12:49:02Znaruse (Yui NARUSE)naruse@airemix.jp
<ul><li><strong>Tracker</strong> changed from <i>Bug</i> to <i>Feature</i></li><li><strong>Target version</strong> deleted (<del><i>3.0</i></del>)</li><li><strong>ruby -v</strong> deleted (<del><i>2.0.0-p247</i></del>)</li><li><strong>Backport</strong> deleted (<del><i>1.9.3: UNKNOWN, 2.0.0: UNKNOWN</i></del>)</li></ul> Ruby master - Feature #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regressionhttps://bugs.ruby-lang.org/issues/9121?journal_id=940692021-10-07T20:20:40Zjeremyevans0 (Jeremy Evans)merch-redmine@jeremyevans.net
<ul><li><strong>Status</strong> changed from <i>Assigned</i> to <i>Closed</i></li></ul><p>SortedSet was removed in <a class="changeset" title="[ruby/set] Remove SortedSet implementations It required RBTree to perform decently and the exter..." href="https://bugs.ruby-lang.org/projects/ruby-master/repository/git/revisions/a3db08d7b6ff119223f77e3df00b4f6deac971e2">a3db08d7b6ff119223f77e3df00b4f6deac971e2</a></p>