From: "mame (Yusuke Endoh)" Date: 2013-11-23T22:07:04+09:00 Subject: [ruby-core:58528] [ruby-trunk - Bug #9121] [PATCH] Remove rbtree implementation of SortedSet due to performance regression Issue #9121 has been updated by mame (Yusuke Endoh). zzak (Zachary Scott) wrote: > See #7698 and https://github.com/seki/Drip/issues/4 Thank you, but it works now for me. $ ruby -v ruby 2.0.0p353 (2013-11-22 revision 43784) [x86_64-linux] $ gem -v 2.1.11 $ gem install rbtree Building native extensions. This could take a while... Successfully installed rbtree-0.4.1 Parsing documentation for rbtree-0.4.1 Done installing documentation for rbtree after 0 seconds 1 gem installed knu (Akinori MUSHA) wrote: > > 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 using rbtree on 2.0.0 everyday, but I have never encountered any problem. Where was the issue discussed? Could you show me a pointer? > > 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. In principle, I agree that it is not cool for a standard library to depend a third-party library. But in fact, (a part of) set.rb has depended on rbtree. As Joel said, some operations will become very slow if it is removed. Isn't it a compatibility problem? -- Yusuke Endoh ---------------------------------------- Bug #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regression https://bugs.ruby-lang.org/issues/9121#change-43110 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/