From: Carl Porth <badcarl@...>
Date: 2007-09-04T11:36:27+09:00
Subject: Re: Twisting a Rope (#137)

Eric, thanks for taking the time to run benchmarks for everyone's
solutions.  It clears things up when they're run all on the same
machine.

Carl

On Sep 3, 6:48 pm, "Eric Mahurin" <eric.mahu...@gmail.com> wrote:
> On 8/31/07, Ruby Quiz <ja...@grayproductions.net> wrote:
>
> > This week's task is to implement the Rope data structure as a Ruby class.
>
> I modified my implementation a bit more and provided results along
> with the other ruby implementations (sorry Mauricio) submitted.  The
> benchmark test I used is attached.  It can run the original build/sort
> that assumes mutable ropes and a build/sort that can also be used with
> immutable ropes (in addition to mutable ropes).  These tests assume
> that << can only take another rope.  I included some testing to ensure
> the results are correct.  I also used the linux /proc/$$/status to get
> the memory.
>
> Mahurin::StringRope is almost the same as my previous submission.  The
> main change was handling a boundary case better so I don't
> unecessarily concat an empty rope (a < should have been a <=) - this
> almost doubled the performance.
>
> I added the class Mahurin::MutableStringRope which is a wrapper around
> an immutable rope.  I just reassign the instance variable (@rope) to
> make changes.  I implemented a bunch of String/Array mutable methods
> in this class.  This wrapper class hurt performance much more than I
> expected (double the run-time).
>
> I also tried out not auto-balancing and using an explicit normalize
> (Mahurin::DenormalStringRope).  This gave much faster build time as
> expected, but the sort time slowed down just as much.  I guess for
> this random data set (I use a fixed seed), qsort doesn't keep the tree
> balanced (pivot doesn't necessarily partition equally).  The larger
> depth for the non-auto-balanced rope hurts the slice time.  I think
> biting the bullet for auto-balancing is the better way to go.
>
> I added a subclass for handling flattening concatenations of short
> strings (Mahurin::ShortStringRope) just to be complete.  It isn't
> useful in this benchmark, but also doesn't hurt much (within the 0.01
> second error margin).
>
> CPU(user+sys,sec)   mem(peak,MB)
> ------------------- ------------
>  build  sort  total build  sort  class
>  -----  ----  ----- -----  ----  -----
>   0.10  1.70   1.80   287  1327  String
>   0.01  0.27   0.28    22   153  Porth::Rope
>   0.02  0.83   0.85    22    34  Choudhury::Rope *
>   0.02  0.06   0.08    22    29  Mahurin::StringRope +
>   0.00  0.08   0.08    22    30  Mahurin::DenormalStringRope +
>   0.02  0.14   0.16    22    29  Mahurin::MutableStringRope
>   0.07  0.10   0.17   151   151  Munkby::ArrayRope
>   0.02  0.73   0.75    22   655  Kalenkovich::Rope *
>
> CPU : minimum from 40 iterations
> mem : peak over the 40 iterations
>
> * : self-checking failed
> + : immutable benchmark needed
>
>  test2.rb
> 4KDownload
>
>  mahurin.rb
> 11KDownload