> 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.

Whether to use a binary tree or an array is a classical decision, and one
of the reasons that I implemented my rope using an array was because
I suspected that it would not matter much for the benchmark.

> 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.

The perhaps surprising, but oh so obvious solution here is that dup doesn't
(always) do sharing. This was somewhat explained here:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/74742

I've found out, that one can replace 's.dup' with 's[0..-1]' to enforce sharing.
I've tried this and memory usage went down, without sacrificing the 'safety'.
So apparently, the rule is; use dup if you want to modify the duplicate, or
s[0..-1] if you want to protect the duplicate from changes to the original. =)

>  I added dup on the input strings to Mahurin::StringRope, and it made
> no difference in run-time or memory.

This is easily explained by the fact that Mahurin::StringRope treats strings
and ropes differently, and thereby only dups on first insertion, whereas my
solution dups all the time.

!g