From: Zachary Scott Date: 2013-11-23T12:09:02+00:00 Subject: [ruby-core:58525] Re: [ruby-trunk - Bug #9121] [PATCH] Remove rbtree implementation of SortedSet due to performance regression --_av-bg2dXxEFhI07nitfHHLEzg Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit See #7698 and https://github.com/seki/Drip/issues/4 > On Nov 23, 2013, at 6:09 PM, "mame (Yusuke Endoh)" wrote: > > > Issue #9121 has been updated by mame (Yusuke Endoh). > > > knu (Akinori MUSHA) wrote: >> rbtree is seemingly broken for the latest version of ruby. > > What do you mean? What broke rbtree? > I'm afraid it is a more serious problem than this ticket itself. > > -- > Yusuke Endoh > ---------------------------------------- > Bug #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regression > https://bugs.ruby-lang.org/issues/9121#change-43101 > > 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/ --_av-bg2dXxEFhI07nitfHHLEzg Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable
See #7698 and https://github.com/seki/Drip/i= ssues/4

On Nov 23, 2013, at 6:09 PM, "mame (Yusuke Endoh)= " <mame@tsg.ne.jp> wrote:

Issue #9121 h= as been updated by mame (Yusuke Endoh).


knu (Akinori MUSHA) wrote:
rbtree is seemingly broken for the latest version of ruby.<= br>

What do you mean?  What broke r= btree?
I'm afraid it is a more serious problem than this ti= cket itself.

--
Yusuke En= doh <mame@tsg.ne.jp>
= ----------------------------------------
Bug #9121: [= PATCH] Remove rbtree implementation of SortedSet due to performance regress= ion
https://bugs.ruby-lang.org/issues/9121#change-43101

Author: xshay (Xavier Shay)
= Status: Assigned
Priority: Normal
Assignee:= knu (Akinori MUSHA)
Category: lib
Target v= ersion:
ruby -v: 2.0.0-p247
Backport: 1.9.= 3: UNKNOWN, 2.0.0: UNKNOWN


rbtree is slower than the pure ruby version.

<= span>I have provided benchmarks and a patch here:
https://github.com/rub= y/ruby/pull/451

ruby sorted_set_benchmark.rb
using rbtree<= /span>
      user    = ; system      total     &= nbsp;  real
#add  0.010000   0.000= 000   0.010000 (  0.016446)
#delete  0.= 020000   0.000000   0.020000 (  0.013248)#include? 1000 items  0.010000   0.000000  &nbs= p;0.010000 (  0.011822)
#include? 2000 items  0.0= 20000   0.000000   0.020000 (  0.012572)#include? 3000 items  0.020000   0.000000   = ;0.020000 (  0.013610)
#include? 4000 items  0.02= 0000   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  &nb= sp;0.030000   1.760000 (  1.773069)
#to_a 40= 00 items  2.370000   0.040000   2.410000 (  2= .420450)
#to_a 5000 items  2.920000   0.0500= 00   2.970000 (  2.975497)
ruby sorted_set_benchmark.rb
NOT usin= g rbtree
      user  &n= bsp;  system      total   &nbs= p;    real
#add  0.010000  &n= bsp;0.000000   0.010000 (  0.007889)
#delete=  0.010000   0.000000   0.010000 (  0.004631)=
#include? 1000 items  0.000000   0.000000 &= nbsp; 0.000000 (  0.005060)
#include? 2000 items =  0.010000   0.000000   0.010000 (  0.005950)<= /span>
#include? 3000 items  0.010000   0.000000 &n= bsp; 0.010000 (  0.005814)
#include? 4000 items &= nbsp;0.010000   0.000000   0.010000 (  0.005993)
#include? 5000 items  0.010000   0.000000 &nb= sp; 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  &nb= sp;0.000000   0.000000 (  0.002428)
<= br>
--
http://bugs.ruby-lang.org/
<= img src=3D"http://mandrillapp.com/track/open.php?u=3D30080831&id=3Daf87169f= 3e7c446ea0f5891ac8ee803f" height=3D"1" width=3D"1"> --_av-bg2dXxEFhI07nitfHHLEzg--