[Cuis] Ropes (functional strings)

[Ken Dickey]

On Wed, 13 Feb 2013 21:01:01 -0800
Casey Ransberger <casey.obrien.r at gmail.com> wrote:

> I'm curious: what's the difference WRT performance? Has anyone looked?

Two sets of performance measurements have been published:

IBM implementation of Ropes in Java:

	http://www.ibm.com/developerworks/java/library/j-ropes/index.html

C implementation of Ropes in the paper 'Ropes: an Alternative to Strings':

http://citeseer.ist.psu.edu/viewdoc/downloaddoi=10.1.1.14.9450&rep=rep1&type=pdf

The Java data is probably closer to what we might expect.

I have implemented the optimizations suggested in the Alternative to Strings paper, but more optimizations could be done.

I consider the current implementation a proof of concept that we could replace strings with ropes in the current editor.

Once we have immutable strings, it is (IMHO) easier to support multiple sizes of encodings for UTF8/16/32 characters & compact arrays.

The larger pieces of work would be to integrate the entire String protocol and then do the speed optimizations for parsing and regular expressions.  The IBM paper indicates an easy factor of 10 speedup in large regular expression tests.

I don't expect rope operations to be as fast as strings.  I do expect the code would be easier to get correct and to test.

$0.02
-KenD