Speeding up v3 basic_string

[Nathan Myers]

On Wed, Dec 12, 2001 at 12:47:25AM +0100, Paolo Carlini wrote:
> Let us suppose I change replace in this way:
>       if (_M_rep() != __str._M_rep())
>         return _M_replace_safe(...
>       else
>         return this->replace(...
> 
> As you can see it seems that there many *great* opportunities of
> improvement from avoiding as much as possible creating temporaries:
> ...
> 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.

Yes, there are many opportunities to radically improve string performance.
 
> 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.

Look at the three cases, for the source string: 
1. If the source string is shared, it's immutable.
  (Even if it becomes unshared during the operation, that's the same as...)
2. If it's not shared, then we're the only thread using it.
3. If it's leaked, we're still the only thread using it.

1. If the destination string is shared, you have to copy (parts of) it
  before you change it, but then our private working copy is known not
  to be shared.
2. If ... is not shared, we have the only copy and can do what we like,
3. If ... is leaked, any iterators are invalidated by the replace
  operation, so we change it to not shared.

If the source and destination string have the same _Rep, and/or it turns
out you have to allocate new storage anyway, you don't need to copy to 
a temporary first because you can just copy the correct characters 
directly into their final place in the newly-allocated storage.  If 
the source range doesn't overlap the replaced range, you may not need 
to allocate at all, if you do things in the right order.

Note that in general you often don't have to copy a whole string, you 
only ever have to copy the parts you need, which are often much smaller
than either whole string.  

You save time by (1) avoiding calls to malloc, (2) shortening memcpy 
ranges, (3) avoiding unnecessary memcpy calls, (4) avoiding checks
for very rare special cases.  Only (4) conflicts with the others.

Keep in mind that malloc is often the most expensive operation, by far,
and it's worth doing a lot of checking to avoid doing it.  If the result 
string will be equal to or shorter than the the original destination,
and is not already shared, we can (and should) work in place, using 
memmove for some ranges.

Nathan Myers
ncm at cantrip dot org