From: "xshay (Xavier Shay)" Date: 2013-11-18T09:24:40+09:00 Subject: [ruby-core:58396] [ruby-trunk - Bug #9121][Open] [PATCH] Remove rbtree implementation of SortedSet due to performance regression Issue #9121 has been reported by xshay (Xavier Shay). ---------------------------------------- Bug #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regression https://bugs.ruby-lang.org/issues/9121 Author: xshay (Xavier Shay) Status: Open Priority: Normal Assignee: Category: 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/