First beta of the basic_string exponential shaper

[Paolo Carlini <pcarlini at unitus dot it>]

Hi all,

I'm attaching to this message our current beta of the expontial shaper, diffed against the
current mainline. Things definitely begins to settle. Both _M_mutate and _M_clone
correctly use the same policy, namely, when a new object must be created with a
minimal_capacity bigger than that of the original one (old_capacity, let's call it), it
gets a real capacity which is the max(2*old_capacity,  minimal_capacity).

There is regression in the assertion VERIFY( i06 <= i04 ) of test06 in
inserters_extractors.cc, which we must investigate further. That is probably not a real
regression but simply a mismatch between the (old) memory management of istringstream and
the new one of strings: i06 is 8 and i04 is 7. In that case, perhaps we can discuss
changing the test, or we may partially modify for istringstreams too memory allocation.
Or, my best option, incrementally, improving strings memory allocation while the test is
XFAILed, then work on istringstreams.

Now for some quite nice :-) numbers, first the original testcase (see
http://gcc.gnu.org/ml/libstdc++/2001-11/msg00201.html)

mainline
--------
1.480u 0.540s 0:02.05 98.5%     0+0k 0+0io 163pf+0w

mainline + expon alloc patch
----------------------------
0.900u 0.030s 0:00.96 96.8%     0+0k 0+0io 163pf+0w


The improvement is **much** more noticeable when each concatenated string is longer and/or
we are out of cache (I recall you that I'm on PII-400, 256M, Linux2.4.16, glibc2.2.4):

////////////////////
#include <string>

using namespace std;

int main()
{
        string s;
        int i;

        for( i=0; i<300000; i++ )
        {
                s+="abcdefghij";
        }
}


mainline
--------
4.920u 5.470s 0:10.60 98.0%     0+0k 0+0io 162pf+0w

mainline + expon alloc patch
----------------------------
0.340u 0.060s 0:00.40 100.0%    0+0k 0+0io 163pf+0w

////////////////////
#include <string>

using namespace std;

int main()
{
        string s;
        int i;

        for( i=0; i<30000; i++ )
        {
           s+="abcdefghijabcdefghijabcdefghijabcdefghijabcdefghij"
              "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghij";
        }
}

mainline
--------
4.820u 5.380s 0:10.44 97.7%     0+0k 0+0io 162pf+0w

mainline + expon alloc patch
----------------------------
0.090u 0.050s 0:00.21 66.6%     0+0k 0+0io 163pf+0w


On the other hand, we are seeing no noticeable improvement (but no regression either!!) on
the "nasty" testcase (http://gcc.gnu.org/ml/libstdc++/2001-11/msg00263.html) which, we
believe has its bottleneck elsewhere.

Currently, we are carrying more tests for different string operators too, trying to
understand better the above cited small regression and exploring different tunings
(perhaps growing slower than ~2x, as per Nathan's hint?)

Please help testing the patch!
Cheers,
Paolo.

//////////////////////////

--- basic_string.tcc.orig       Fri Nov 30 00:29:42 2001
+++ basic_string.tcc    Thu Nov 29 23:34:04 2001
@@ -271,15 +271,23 @@ namespace std
     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
     {
       size_type       __old_size = this->size();
-      const size_type __new_size = __old_size + __len2 - __len1;
+      const size_type __new_min_size = __old_size + __len2 - __len1;
       const _CharT*        __src = _M_data()  + __pos + __len1;
       const size_type __how_much = __old_size - __pos - __len1;

-      if (_M_rep()->_M_is_shared() || __new_size > capacity())
+      if (_M_rep()->_M_is_shared() || __new_min_size > capacity())
        {
          // Must reallocate.
          allocator_type __a = get_allocator();
-         _Rep* __r = _Rep::_S_create(__new_size, __a);
+          _Rep* __r;
+         size_type __new_size;
+         if (__new_min_size > capacity())
+           // Grow fast.
+           __new_size = __new_min_size > 2*capacity() ?
+                         __new_min_size : 2*capacity();
+         else
+           __new_size = __new_min_size;
+          __r = _Rep::_S_create(__new_size, __a);
          try
            {
              if (__pos)
@@ -302,8 +310,8 @@ namespace std
          traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
        }
       _M_rep()->_M_set_sharable();
-      _M_rep()->_M_length = __new_size;
-      _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
+      _M_rep()->_M_length = __new_min_size;
+      _M_data()[__new_min_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
     // You cannot leave those LWG people alone for a second.
     }

@@ -430,7 +438,13 @@ namespace std
     basic_string<_CharT, _Traits, _Alloc>::_Rep::
     _M_clone(const _Alloc& __alloc, size_type __res)
     {
-      _Rep* __r = _Rep::_S_create(_M_length + __res, __alloc);
+      _Rep* __r;
+      if (_M_length + __res > _M_capacity)
+       // Grow fast.
+       __r = _Rep::_S_create(_M_length + __res > 2*_M_capacity ?
+                              _M_length + __res : 2*_M_capacity, __alloc);
+      else
+       __r = _Rep::_S_create(_M_length + __res, __alloc);
       if (_M_length)
        {
          try