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

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


I wrote:
> ... and the point of this issue is that we should not depend on it any more, so I'll go ahead anyway.

Oops, I mistook this issue for something else, I just thought that's another reason to ditch the rbtree dependency albeit optional.
----------------------------------------
Bug #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regression
https://bugs.ruby-lang.org/issues/9121#change-43109

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/