Ok, here's my last submission (I hope).  I modified slice to return a
Rope for a speed increase and cleaned up a bit.

I never explained my design: I just have the Rope instances represent
string concatenations such that only leaf nodes are strings.  This
way, I can just recurse left and right without doing any type
checking, resulting in fairly clean code.

Oh, and I cheated to get full String functionality (but not completely
tested).

http://pastie.caboo.se/94118

Eric, can I get a redo on those benchmarks? (I've always depended on
the kindness of strangers.) Thanks!

Carl


On Sep 4, 8:20 pm, "Eric Mahurin" <eric.mahu... / gmail.com> wrote:
> On 9/4/07, Eugene Kalenkovich <rub... / softover.com> wrote:
>
> > Eric, may I ask you to test one more thing: your #slice does not have any
> > input checks. To make a fair comparison, could you please comment first 3
> > lines of my #slice,
>
> Sure.  I also did the same to Gustav Munkby's code.  Here are the new results:
>
> 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 (failed)
>   0.02  0.06   0.08    22    29  Mahurin::StringRope (immutable)
>   0.00  0.08   0.08    22    30  Mahurin::DenormalStringRope (immutable)
>   0.02  0.14   0.16    22    29  Mahurin::MutableStringRope
>   0.07  0.10   0.17   151   151  Munkby::ArrayRope
>   0.00  0.09   0.09    22    22  Munkby::ArrayRope (no dup)
>   0.00  0.07   0.07    22    22  Munkby::ArrayRope (no dup, simple slice)
>   0.01  0.12   0.13    22    22  Kalenkovich::Rope
>   0.01  0.07   0.08    22    22  Kalenkovich::Rope (simple slice)
>
> Munkby::ArrayRope is marginally the fastest.  Upon closer inspection
> of the code, there is a pretty significant problem - concatenation is
> O(n) where n is the number of segments in the right rope of the
> concatenation.  A normal rope has O(1) concatenations and a
> self-balancing one (Mahurin::StringRope) has O(log(n)).  The reason
> this isn't a problem in this benchmark is that qsort iterates over the
> segments (n>1) for the right rope of a concat right before the concat.
>  So the big-O performance is the same for the qsort - O(n*log(n)).
> Munkby::ArrayRope may not look so good on other benchmarks.
>
> I'm surprised that the dup version of Munkby::ArrayRope takes so much
> memory.   I don't see anything that the benchmark uses that would
> modify the strings, so it looks like the COW in string.c doesn't work.
>  I added dup on the input strings to Mahurin::StringRope, and it made
> no difference in run-time or memory.