Project

General

Profile

Bug #9121

[PATCH] Remove rbtree implementation of SortedSet due to performance regression

Added by xshay (Xavier Shay) over 6 years ago. Updated 5 months ago.

Status:
Assigned
Priority:
Normal
Target version:
ruby -v:
2.0.0-p247
[ruby-core:58396]

Description

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)


Related issues

Related to Ruby master - Feature #2348: RBTree Should be Added to the Standard LibraryRejectedmatz (Yukihiro Matsumoto)Actions

Also available in: Atom PDF