Re: [Fwd: basic_string<> - useless because of its poor performance]

[Nathan Myers <ncm at nospam dot cantrip dot org>]

On Fri, Jul 06, 2001 at 07:37:07AM -0500, Loren James Rittle wrote:
> >> Only if you fail to use reserve() wisely as suggested by Stroustrup... ;-)
> 
> > No.  The standard says that string growth is "amortized linear".
>  
> >> I do basically agree that we should do something better than
> >> per-character growth given what we generally know about malloc
> >> implementations.  However, it is unclear that an exponential growth
> >> policy is wise.
> 
> > An exponential growth policy is the only way to get the performance
> > required by the standard.  In fact, exponential growth with base 2
> > is required by the wording, although there have been suggestions that 
> > 1.5 should be allowed in future amendments.
> 
> Could you explain how the standard can say ``that string growth is
> "amortized linear"'' yet ``[a]n exponential growth policy is the only
> way to get the performance required by the standard''?  This seems
> quite contradictory to me.
> 
> To me, ``amortized linear'' implies growing by a fixed block size not
> doubling in size each growth.  But, I know you are much better read on
> the actual standard in most areas than me...

The "amortized linear" requirement means that adding <N> characters 
<M> times should take o(NM) time.  (<X> is a random variable with
expectation X.)  With a linear allocation strategy, allocation time
dominates the runtime, and you get much slower performance than NM, 
as measured.  With an exponential allocation strategy, allocation time
drops out and the copying time dominates, as required.

Or something like that.  Anyway, every other implementation uses
exponential allocation, although some fudge by using a 1.5 multiplier.

Nathan Myers
ncm at cantrip dot org