From: "knu (Akinori MUSHA)" Date: 2013-11-23T21:53:33+09:00 Subject: [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/