Re: [ANN] Lua 5.2.1 (work1) now available

[Coda Highland <chighland@...>]

On Fri, Mar 23, 2012 at 12:08 PM, Mike Pall <mikelu-1203@mike.de> wrote:
> Axel Kittenberger wrote:
>>  But how about when concating two strings the Lua VM stores a datatype
>> that just says "this is str1 joined with str2". Only whenever you do
>> an operation that cannot be used on this string of strings, like using
>> it as a table key, it is joined and interned.
>
> I know this is a ceterum censeo, but I have to repeat my warning:
>
> Ropes are a good idea on paper, but they increase complexity and
> rarely pay off outside targeted benchmarks and textbook examples.
> Yes, there may be some specific applications where ropes are the
> right data structure (*). However ropes are certainly not the data
> structure of choice for a generic string type in a generic
> programming language.
>
> Don't fall into the premature optimization trap. Whatever code you
> envision that might benefit from ropes is simply uncommon. But all
> of your code will pay the price of managing linked, shared and
> reference-counted data structures as well as iterating over trees
> all the time. This is very cache-inefficient, pointer-chasing has
> a high latency, your CPU hardware prefetcher doesn't handle this
> very well, you pay a high cost for creation _and_ destruction, and
> so on. Modern CPUs are crazy beasts and linear data structures
> very often beat elaborate data structures, even for medium-sized
> use cases.
>
> There's even compelling evidence, including benchmarks, that
> flattened, colocated strings (which is what Lua 5.1 uses) are the
> best option: http://ssw.jku.at/Research/Papers/Haeubl08Master/
>
> (*) I guess almost everyone would place a bet that ropes are the
> perfect data structure for a text editor. But don't trust your
> intuition: e.g. gap buffers are less complex and much faster.
>
> --Mike

I respect your experience in optimization, but I have to wonder how
your link even relates to the proposal at hand. The abstract looks
fairly unrelated -- a discussion of how to handle metadata for strings
with relationship to its content.

No one here was promoting ropes as being the basic string
implementation for Lua. It was being proposed specifically as an
intermediate structure for the concatenation operator, to be flattened
on demand when the object is needed in a string context (except for
more concatenation, and possibly getting the length as it's a common
enough idiom to append until a certain size is reached). Certainly
having to deal with ropes as a general issue would be a bad idea, but
I know at least one library (Qt) that offers a "string builder" class
specifically for concatenation that implicitly converts to a proper
string object on demand. In Qt's case this is a substantial
performance improvement over serial concatenation and has no impact on
anything that isn't concatenation.

/s/ Adam