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

Issue #9121 has been updated by knu (Akinori MUSHA).


mame (Yusuke Endoh) wrote:
> knu (Akinori MUSHA) wrote:
> > rbtree is seemingly broken for the latest version of ruby.
> 
> 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 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.
----------------------------------------
Bug #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regression
https://bugs.ruby-lang.org/issues/9121#change-43108

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/