From: e@... Date: 2014-01-21T17:07:12+00:00 Subject: [ruby-core:59934] [ruby-trunk - Bug #9121] [PATCH] Remove rbtree implementation of SortedSet due to performance regression Issue #9121 has been updated by Zachary Scott. I just wanted to remind everyone of the discussion that took place regarding adding RBTree to stdlib in [Feature #2348] ---------------------------------------- Bug #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regression https://bugs.ruby-lang.org/issues/9121#change-44474 * Author: Xavier Shay * Status: Assigned * Priority: Normal * Assignee: Akinori MUSHA * Category: lib * Target version: Next Major * 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/