From: Eric Mahurin <eric.mahurin@...>
Date: 2007-09-05T22:58:54+09:00
Subject: Re: Twisting a Rope (#137)

On 9/5/07, Carl Porth <badcarl@gmail.com> wrote:
> http://pastie.caboo.se/94118
>
> Eric, can I get a redo on those benchmarks? (I've always depended on
> the kindness of strangers.) Thanks!

Here is the latest:

CPU(user+sys,sec)   mem(peak,MB)
------------------- ------------
 build  sort  total build  sort  class
 -----  ----  ----- -----  ----  -----
  0.10  1.70   1.80   287  1327  String
  0.00  0.27   0.27    22   153  Porth::Rope (no dup)
  0.00  0.19   0.19    22    22  Porth::Rope (no dup)
  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 (uses immutables)
  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 (no dup)
  0.01  0.07   0.08    22    22  Kalenkovich::Rope (no dup, simple slice)

With the exception of Munkby::ArrayRope (which has an O(n)
concatenation problem), I don't trust any of the mutable "no dup"
implementations.  This will be a problem:

rope1 = ...
rope2 = ...
rope3 = ...
rope4 = RopeClass.new(rope1, rope2)
rope1 << rope2
rope2 << rope3

Without dups of the inputs (in initialize and #<<), rope4 and rope2
will be screwed up.

I only deal with immutable ropes, so dupping the ropes isn't
necessary.  The only concern you might have would be with the leaf
strings.  I added dups at that level and it didn't affect run-time or
memory.  You could also just make a requirement - incoming strings
should not be modified (externally dup if necessary).

I added dups to Kalenkovich's code and saw the same 150+MB usage as
Munkby's dup code.  I still don't understand this.