[ruby-core:28503] Re: [Feature #905] Add String.new(fixnum) to preallocate large buffer

On Fri, 5 Mar 2010, Yusuke ENDOH wrote:

> Hi,
> 
> 2010/3/5 Hugh Sasse <[e-mail]>:
> >> At first glance, the document explains the difference of destructive
> >> and non-destructive concatenations, like String#+ and #<<.
> >>
> >> It is absolutely different topic from pre-allocation.
> >
> > It is related: the algorithm constructs large strings from smaller
> > ones in an elegant way using a "tower of Hanoi", and if the top
> > string concatenation gets bigger than the one below it, only then
> > are they joined together.  Result is less copying and merging.
> 
> 
> Ah, sorry.  I had to read all more carefully.
> 
> The algorithm itself is interesting, but I understand it is
> just workaround to implement efficient string buffer by using
> *immutable* strings (because Lua String seems always immutable).
> 
> But Ruby String is mutable.  Is it also more efficient with
> *mutable* string than current direct concatenation?  I wonder
> if the algorithm needs more memcpy than the current.

Possibly.  I've not gone into this in much depth.  I thought it
might be helpful to raise it in case this would give significant
help to garbage collection.  I'm thinking that as the strings get
longer they fill up space in the heap so need to be moved to the
newly allocated space.  Dealing with only the top of the "tower of
Hanoi" would be handling smaller chunks.  I think this would need to
be tested, but could be worth exploring.  Lua is rather quick, and
the article talks about a big speed increase.

On the other hand, it is difficult to decide when to invoke this
algorithm.  It is probably too heavy for just joining two strings,
but for reading in lots of chunks and appending them, it could be a
big help.  I don't know how to detect that distinction in user code.
It might be too much work.

        Hugh


> 
> -- 
> Yusuke ENDOH <[e-mail]>
>