Speeding up v3 basic_string

[Paolo Carlini]

Hi all.

Let us suppose I change replace in this way:

-------------
  template<typename _CharT, typename _Traits, typename _Alloc>
    basic_string<_CharT, _Traits, _Alloc>&
    basic_string<_CharT, _Traits, _Alloc>::
    replace(size_type __pos1, size_type __n1, const basic_string& __str,
            size_type __pos2, size_type __n2)
    {
      if (_M_rep() != __str._M_rep())
        return _M_replace_safe(_M_check(__pos1), _M_fold(__pos1, __n1),
                               __str._M_check(__pos2),
                               __str._M_fold(__pos2, __n2));
      else
        return this->replace(_M_check(__pos1), _M_fold(__pos1, __n1),
                             __str._M_check(__pos2),
                             __str._M_fold(__pos2, __n2));
    }
--------------

This is what I obtain for the following stupid testcase on my PII-400 (-O2):

#include <string>
int main()
{
  std::string a = "libstdc++-v3";
  std::string b = "libstdc++-v3";

  for (int i = 0; i < 10000000; ++i)
    a.replace(0, 11, b, 0, 11);
}


baseline (current mainline)
---------------------------
    9.630u 0.020s 0:09.77 98.7%     0+0k 0+0io 204pf+0w

baseline with modified replace
------------------------------
    4.240u 0.010s 0:04.33 98.1%     0+0k 0+0io 203pf+0w

2.95.3
------
    6.460u 0.020s 0:06.56 98.7%     0+0k 0+0io 93pf+0w


As you can see it seems that there many *great* opportunities of improvement
from avoiding as much as possible creating temporaries: currently, too many
member functions (not append, +, and co, of course) still end up calling
unnecessarily the general "paranoic" version of _M_replace in order to be deadly
sure to be correct wrt overlapping ranges.

If this approach is safe (it is?? i.e. two strings always belong to different
reference counted classes iff _M_rep of the first is != _M_rep of the second??)
we could extend and improve this idea to speedup noticeably all of basic_string.

Also, what about testing for _M_rep()->_M_is_shared() of the destination string?
In such cases too, due to the copy on write mechanism, should be safe to not
buffer the source data.

What do you think???

Cheers,
Paolo.