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

[Loren James Rittle <rittle at latour dot rsch dot comm dot mot dot com>]

>> Ryszard, you'll need to post sample code before Nathan or others will be
>> able to help you in any kind of constructive manner. Would you be willing
>> to do this?

> I posted a sample some time ago. 

And I posted a complete analysis of your problem, as you framed it at
that time, on ``8 Jun 2001 03:19:46'' (See Message-ID:
<200106080819.f588JWa28868@latour.rsch.comm.mot.com>).  Last month,
you thought mutex locking overhead to be the problem.  I hope I
explained why that was not the problem (less than 2% overhead by my
study).

[...]
> 1. gcc version egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)
[...]
> Execution time of 1000000 string::append(const string&) calls: 0.26 sec.

> 2. gcc version 3.0 (Thread model: single)
[...]
> Execution time of 1000000 string::append(const string&) calls: 6087.62 sec.

Here is a version of your example code suitable for profiling:

#include <string>
using namespace std;

int
main()
{
  string s(static_cast<string::size_type>(1) , 'x');
  string buf; // no preallocation
  for (int i = 0; i < 50000; ++i)
     buf.append(s);
}

I compiled this example under g++ 2.95.X (I used this as a proxy for
egcs-2.91.66) and 3.0 with -pg -O2.  I also looked at the example
under gdb with exactly one breakpoint set on malloc (I knew to do this
based on the analysis I posted for your example last time).

The C++ library that shipped with egcs-2.91.66 actually allocates 32
bytes of string storage at first (even when ``no preallocation'') then
allocates memory at an exponential rate (32, 64, 128, 256, etc).

The 3.0 C++ library actually allocates and copies memory at a linear
rate of 1 malloc() call and copy per append() call after the string
size surpasses _MAX_BYTES (currently, 128).  First of all, since the
C++ library is allocating memory for strings using the standard
malloc() interface, it should consider always starting and growing the
allocation by pagesize instead of 1 after it may no longer use the
fast allocator.  This is independent of any change back to an
exponential growth allocator.  This is a QoI issue but it would add
some system-dependent complexity at a higher layer of software.  The
current implementation is simple, direct and 100% compliant with the
standard.

Now, as a user of a standard C++ library, you may call reserve()
explicitly to advise the implementation of how large you estimate a
string will grow to be.  Did you know that the primary author of C++
recommends that you take that responsibility on your shoulders as an
application writter?  If you want to read about this issue yourself,
please see: pg. 456 _The C++ Programming Language_, SE.  The
discussion there regards vector<>(), but it is the exact same argument
for string<>().

Now, I personally believe that the implementation should never grow
the size of the underlaying memory area for a string<>() at a rate of
1 character, especially once the sizes become larger than will be
provided from the custom allocator, but who can argue with Stroustrup
on the matter of what is your responsibility if you want to ensure
good performance of your application code?

Regards,
Loren
-- 
Loren J. Rittle
Senior Staff Software Engineer, Distributed Object Technology Lab
Networks and Infrastructure Research Lab (IL02/2240), Motorola Labs
rittle@rsch.comm.mot.com, KeyID: 2048/ADCE34A5, FDC0292446937F2A240BC07D42763672