Re: basic_string capacity strategy < 128 characters

[Joachim Schurig <js at logoport dot net>]

Hi Paolo,

> A quick comment (more later): the standard requires asymptotic (i.e., 
> amortized) linear behavior, not linear behavior tout court, and the v3 
> strategy for sure guarantees that, since december 2001. See f.i.:
>
>    http://gcc.gnu.org/ml/libstdc++/2001-12/msg00144.html 

But how do you explain the fact that the libstdc++-v3 allocates a new 
buffer with size += 1 for each added character, then copies the whole 
existing buffer, and then frees the existing buffer?

Is this what you understand by amortized linear? For me, amortized means 
something like "expect a performance penalty every some characters", but 
for sure not with every new character.

Your link above only tells me that when adding some thousand characters, 
v3 is not regressive compared to v2. I however tried to solve a problem 
in an application that rarely uses strings larger than 100 characters of 
size, and was amazed how slow it works on SMP machines.

It is very well possible that the performance impact isn't measurable on 
UP machines, as a copy of 127 bytes should be done quite fast with 
today's processors, but the interaction with the current standard 
allocator on SMP machines leads to problematic results that could be 
avoided with another capacity strategy.

Whatsoever, could you tell me a good reason for the capacity design 
decision as it is in use in -v3 as of today?

Curious,

best regards,

Joachim Schurig