[ruby-core:58528] [ruby-trunk - Bug #9121] [PATCH] Remove rbtree implementation of SortedSet due to performance regression

Issue #9121 has been updated by mame (Yusuke Endoh).


zzak (Zachary Scott) wrote:
> See #7698 and https://github.com/seki/Drip/issues/4

Thank you, but it works now for me.

  $ ruby -v
  ruby 2.0.0p353 (2013-11-22 revision 43784) [x86_64-linux]
  $ gem -v
  2.1.11
  $ gem install rbtree
  Building native extensions.  This could take a while...
  Successfully installed rbtree-0.4.1
  Parsing documentation for rbtree-0.4.1
  Done installing documentation for rbtree after 0 seconds
  1 gem installed


knu (Akinori MUSHA) wrote:
> > What do you mean?  What broke rbtree?
> 
> 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.

I'm using rbtree on 2.0.0 everyday, but I have never encountered any problem.
Where was the issue discussed?  Could you show me a pointer?

> > I'm afraid it is a more serious problem than this ticket itself.
> 
> 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.

In principle, I agree that it is not cool for a standard library to depend
a third-party library.  But in fact, (a part of) set.rb has depended on rbtree.
As Joel said, some operations will become very slow if it is removed.
Isn't it a compatibility problem?

-- 
Yusuke Endoh <[e-mail]>
----------------------------------------
Bug #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regression
https://bugs.ruby-lang.org/issues/9121#change-43110

Author: xshay (Xavier Shay)
Status: Assigned
Priority: Normal
Assignee: knu (Akinori MUSHA)
Category: lib
Target version: 
ruby -v: 2.0.0-p247
Backport: 1.9.3: UNKNOWN, 2.0.0: UNKNOWN


rbtree is slower than the pure ruby version.

I have provided benchmarks and a patch here:
https://github.com/ruby/ruby/pull/451

> ruby sorted_set_benchmark.rb
using rbtree
       user     system      total        real
#add  0.010000   0.000000   0.010000 (  0.016446)
#delete  0.020000   0.000000   0.020000 (  0.013248)
#include? 1000 items  0.010000   0.000000   0.010000 (  0.011822)
#include? 2000 items  0.020000   0.000000   0.020000 (  0.012572)
#include? 3000 items  0.020000   0.000000   0.020000 (  0.013610)
#include? 4000 items  0.020000   0.000000   0.020000 (  0.014295)
#include? 5000 items  0.010000   0.000000   0.010000 (  0.018024)
#to_a 1000 items  0.580000   0.020000   0.600000 (  0.616104)
#to_a 2000 items  1.170000   0.040000   1.210000 (  1.213406)
#to_a 3000 items  1.730000   0.030000   1.760000 (  1.773069)
#to_a 4000 items  2.370000   0.040000   2.410000 (  2.420450)
#to_a 5000 items  2.920000   0.050000   2.970000 (  2.975497)
> ruby sorted_set_benchmark.rb
NOT using rbtree
       user     system      total        real
#add  0.010000   0.000000   0.010000 (  0.007889)
#delete  0.010000   0.000000   0.010000 (  0.004631)
#include? 1000 items  0.000000   0.000000   0.000000 (  0.005060)
#include? 2000 items  0.010000   0.000000   0.010000 (  0.005950)
#include? 3000 items  0.010000   0.000000   0.010000 (  0.005814)
#include? 4000 items  0.010000   0.000000   0.010000 (  0.005993)
#include? 5000 items  0.010000   0.000000   0.010000 (  0.006923)
#to_a 1000 items  0.000000   0.000000   0.000000 (  0.001863)
#to_a 2000 items  0.000000   0.000000   0.000000 (  0.002145)
#to_a 3000 items  0.000000   0.000000   0.000000 (  0.002129)
#to_a 4000 items  0.000000   0.000000   0.000000 (  0.002265)
#to_a 5000 items  0.000000   0.000000   0.000000 (  0.002428)


-- 
http://bugs.ruby-lang.org/