Re: string optimization ideas [Re: precompiled regex's to lua]

[Mike Pall <mikelu-0611@...>]

Hi,

Paul Hudson wrote:
> So there should be something in the literature about this topic that might
> save some wheel re-invention?

The technique has already been re-invented many times in the past
decades. :-) I guess the canonical paper to read is from Hans J.
Boehm (of Boehm GC fame). He named it "ropes":

  http://citeseer.ist.psu.edu/587243.html

In my experience ropes are most useful when you deal with very
large strings which need small modifications. The classic example
is a text editor. It's not so useful for stream processing,
packet processing or any task where you need to deal with many
tiny strings.

It's basically a trade-off between the overhead for memory
copying of strings vs. the management overhead of ropes. Back in
the 90ies memory speed was closer to CPU speed, so strings won in
almost all cases. Nowadays with caches being the main bottleneck,
the results may differ.

But I have my doubts it's worth the added complexity for general
purpose string processing (such as in the Lua VM). For those
applications which really need it, you can roll your own in plain
Lua (with nested tables of strings).

Bye,
     Mike