From: Eric Mahurin <eric.mahurin@...>
Date: 2007-09-05T12:20:34+09:00
Subject: Re: [QUIZ] Twisting a Rope (#137)

On 9/4/07, Eugene Kalenkovich <rubify@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.