basic_string capacity strategy < 128 characters

[Joachim Schurig]

Hi,

during a tedious investigation concerning bad runtime behaviour of a 
multithreaded server application on an Intel Quad SMP system, I realized 
that parts of the bad allocator response (using the standard 
__pool_allocator) were due to the heavy use of the allocator for strings.

In fact, the current basic_string implementation in libstdc++ allocates 
a new string buffer with single increment for every added character, if 
the string length is < 128.

On a Quad SMP machine, this leads to complete congestion with only 3-4 
running threads creating and appending strings.

A simple fix is attached, it more or less reimplements the linear 
capacity strategy of libstdc++-v2:

Minimum buffer size is 16 bytes (still inefficient, as for chars this 
only leaves 3 chars effective buffer), doubles the buffer size if 
needed, and respects malloc header space of 4*sizeof(void). This 
algorithm doubles the total representation size, not the real string 
capacity, as this fits best in __mt_alloc's fixed allocator bins.

I read many of the earlier comments, and am aware of a comment that 
delegated responsibility for better runtime behaviour to the programmer 
(who should use appropriate reserve() calls), but there are many 
situations left where you cannot reserve() in advance (just because you 
do not know how much).

As the standard requires a linear behaviour, and as it was implemented 
likewise in libstdc++-v2 and lots of code is written expecting such, you 
might want to rethink the current strategy (or clarify why it was chosen 
the way it is for -v3).

BTW, in the gcc/libstdc++ documentation, there is a paragraph comparing 
MS CString vs. libstdc++ string, pointing out how badly CString's 
capacity strategy is chosen (simply incrementing by 1) compared to the 
string implementation of libstdc++. As far as I am aware of, the CString 
implementation was changed time ago, and now the picture is exactly the 
other way round.

Best regards,

Joachim Schurig


-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: basic_string.diff
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20030611/2022fdcc/attachment.ksh>