Second beta of basic_string exponential shaper

[Paolo Carlini]

Hi again,

here is a new beta of the shaper. In the meanwhile, I have understood the real reason of
the regression I was seeing.

In fact, it was not a "real" regression, since the failing test did *not* enforce any
requirement of the standard but only a particular implementation feature of the current
basic_string memory allocation. In short, in the first beta, the blocking code and the
exponential shaper each one wanted to round-up the capacity of short strings in different
ways, and this surfaced in that test, which compares the capacity of a string with that of
his copy via an istringstream. In the second case, capacity was rounded, at the end of an
exponential progression, to the higher value 8=2^3.

Now, the failing test may be considered as a proof that the exponential shaper, since
implemented in the low level functions _M_mutate and _M_clone, is fully at work even for
istringstreams!!

On the other hand, even if that was not a troublesome regression, "post hoc" seems to me
very reasonable, considering the "philosophy" of the blocking code, to disable the
exponential shaper for allocations below the size of the memory page. In order to do that
I had to write some more lines of code, but in fact, at run time, the cost is only one
additional && in the main if switch of the shaper.

In the future, we may consider the possibility of simplifying the blocking code if
eventually the benefit of page alignment will prove to be smaller than that of the
exponential growth. Please, help on this too!

The benchmark numbers are identical to those of the first beta.

I have also run one additional benchmark, which appeared in
http://gcc.gnu.org/ml/libstdc++/2001-07/msg00030.html

mainline
--------
Execution time of 10000 string::append(char) calls: 0 sec.
Execution time of 10000 string::append(const string&) calls: 0 sec.
Execution time of 100000 string::append(char) calls: 0.06 sec.
Execution time of 100000 string::append(const string&) calls: 0.1 sec.
Execution time of 1000000 string::append(char) calls: 1.48 sec.
Execution time of 1000000 string::append(const string&) calls: 1.91 sec.

mainline + beta2
----------------
Execution time of 10000 string::append(char) calls: 0 sec.
Execution time of 10000 string::append(const string&) calls: 0 sec.
Execution time of 100000 string::append(char) calls: 0.06 sec.
Execution time of 100000 string::append(const string&) calls: 0.09 sec.
Execution time of 1000000 string::append(char) calls: 0.43 sec.
Execution time of 1000000 string::append(const string&) calls: 0.87 sec.


Cheers,
Paolo.


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

*** basic_string.tcc.orig Fri Nov 30 19:41:48 2001
--- basic_string.tcc Fri Nov 30 19:12:45 2001
*************** namespace std
*** 271,285 ****
      _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 _CharT*        __src = _M_data()  + __pos + __len1;
        const size_type __how_much = __old_size - __pos - __len1;

!       if (_M_rep()->_M_is_shared() || __new_size > capacity())
   {
     // Must reallocate.
     allocator_type __a = get_allocator();
!    _Rep* __r = _Rep::_S_create(__new_size, __a);
     try
       {
         if (__pos)
--- 271,303 ----
      _M_mutate(size_type __pos, size_type __len1, size_type __len2)
      {
        size_type       __old_size = this->size();
!       // Minimal required capacity for the new string
!       const size_type __minimal_new_cap = __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() || __minimal_new_cap > capacity())
   {
     // Must reallocate.
     allocator_type __a = get_allocator();
!
!    // See below for the meaning and value of these constants!
!    const size_type __pagesize = 4096;
!    const size_type __malloc_header_size = 4 * sizeof (void*);
!    // The biggest string which fits in a memory page
!    const size_type __page_capacity =
!      (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
!      / sizeof(_CharT);
!
!    _Rep* __r;
!    if (__minimal_new_cap > capacity() &&
!        __minimal_new_cap > __page_capacity)
!      // Growing exponentially
!      __r = _Rep::_S_create(__minimal_new_cap > 2*capacity() ?
!                            __minimal_new_cap : 2*capacity(), __a);
!    else
!      __r = _Rep::_S_create(__minimal_new_cap, __a);
!
     try
       {
         if (__pos)
*************** namespace std
*** 302,309 ****
     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)
      // You cannot leave those LWG people alone for a second.
      }

--- 320,327 ----
     traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
   }
        _M_rep()->_M_set_sharable();
!       _M_rep()->_M_length = __minimal_new_cap;
!       _M_data()[__minimal_new_cap] = _Rep::_S_terminal; // grrr. (per 21.3.4)
      // You cannot leave those LWG people alone for a second.
      }

*************** namespace std
*** 430,436 ****
      basic_string<_CharT, _Traits, _Alloc>::_Rep::
      _M_clone(const _Alloc& __alloc, size_type __res)
      {
!       _Rep* __r = _Rep::_S_create(_M_length + __res, __alloc);
        if (_M_length)
   {
     try
--- 448,472 ----
      basic_string<_CharT, _Traits, _Alloc>::_Rep::
      _M_clone(const _Alloc& __alloc, size_type __res)
      {
!       // Minimal required capacity for the clone
!       const size_type __minimal_new_cap = _M_length + __res;
!
!       // See above for the meaning and value of these constants!
!       const size_type __pagesize = 4096;
!       const size_type __malloc_header_size = 4 * sizeof (void*);
!       // The biggest string which fits in a memory page
!       const size_type __page_capacity =
!         (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
!         / sizeof(_CharT);
!
!       _Rep* __r;
!       if (__minimal_new_cap > _M_capacity && __minimal_new_cap > __page_capacity)
!         // Growing exponentially.
!         __r = _Rep::_S_create(__minimal_new_cap > 2*_M_capacity ?
!                               __minimal_new_cap : 2*_M_capacity, __alloc);
!       else
!         __r = _Rep::_S_create(__minimal_new_cap, __alloc);
!
        if (_M_length)
   {
     try