[PATCH] _M_replace (take3): better clean up + speed ups!!
Paolo Carlini
pcarlini@unitus.it
Sun Dec 9 04:01:00 GMT 2001
So,
I went ahead and instead of waiting for the final approval of my cleanup I started
implementing Nathan's outline (http://gcc.gnu.org/ml/libstdc++/2001-12/msg00142.html).
This is what I have done:
1- Wrote a new _M_replace_safe (similar to old _M_replace(forward_iterator_tag))
which does *not* buffer internally.
2- Old _M_replace(input_iterator_tag) now calls _M_replace_safe.
3- Old _M_replace(forward_iterator_tag) does not exist anymore.
4- The various append now calls _M_replace_safe.
And there are *good* numbers!
(http://gcc.gnu.org/ml/libstdc++/2001-07/msg00030.html):
mainline
--------
Execution time of 10000 string::append(char) calls: 0.01 sec.
Execution time of 10000 string::append(const string&) calls: 0.01 sec.
Execution time of 100000 string::append(char) calls: 0.05 sec.
Execution time of 100000 string::append(const string&) calls: 0.09 sec. <----
Execution time of 1000000 string::append(char) calls: 0.41 sec.
Execution time of 1000000 string::append(const string&) calls: 0.86 sec. <----
Execution time of 10000000 string::append(char) calls: 4.24 sec.
Execution time of 10000000 string::append(const string&) calls: 8.59 sec. <----
mainline + this patch
---------------------
Execution time of 10000 string::append(char) calls: 0 sec.
Execution time of 10000 string::append(const string&) calls: 0.01 sec.
Execution time of 100000 string::append(char) calls: 0.04 sec.
Execution time of 100000 string::append(const string&) calls: 0.05 sec. <----
Execution time of 1000000 string::append(char) calls: 0.42 sec.
Execution time of 1000000 string::append(const string&) calls: 0.35 sec. <----
Execution time of 10000000 string::append(char) calls: 4.21 sec.
Execution time of 10000000 string::append(const string&) calls: 3.56 sec. <----
2.95.3
------
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.03 sec.
Execution time of 100000 string::append(const string&) calls: 0.05 sec. <----
Execution time of 1000000 string::append(char) calls: 0.35 sec.
Execution time of 1000000 string::append(const string&) calls: 0.35 sec. <----
Execution time of 10000000 string::append(char) calls: 3.47 sec.
Execution time of 10000000 string::append(const string&) calls: 3.55 sec. <----
As you can see, it really was the redundant buffering to slow down libstc++-v3 vs v2 on
string.append.
At this point I think I will *not* attempt other more invasive changes, and will wait for
your feedback on this first round.
Tested i686-pc-linux-gnu.
Cheers,
Paolo.
/////////////////
2001-12-09 Paolo Carlini <pcarlini@unitus.it>
Nathan Myers <ncm@cantrip.org>
* include/bits/basic_string.tcc (_M_replace_safe): New.
* include/bits/basic_string.tcc (_M_replace(input_iterator_tag),
append members): use it.
* include/bits/basic_string.tcc (_M_replace(forward_iterator_tag)): Remove.
* include/bits/basic_string.h: Adjust declarations.
* src/string-inst.cc: Adjust declarations.
diff -urN libstdc++-v3-orig/include/bits/basic_string.h
libstdc++-v3/include/bits/basic_string.h
--- libstdc++-v3-orig/include/bits/basic_string.h Sat Dec 8 17:57:02 2001
+++ libstdc++-v3/include/bits/basic_string.h Sun Dec 9 12:09:40 2001
@@ -639,10 +639,10 @@
_M_replace(iterator __i1, iterator __i2, _InputIterator __k1,
_InputIterator __k2, input_iterator_tag);
- template<class _FwdIterator>
+ template<class _InputIterator>
basic_string&
- _M_replace(iterator __i1, iterator __i2, _FwdIterator __k1,
- _FwdIterator __k2, forward_iterator_tag);
+ _M_replace_safe(iterator __i1, iterator __i2, _InputIterator __k1,
+ _InputIterator __k2);
// _S_construct_aux is used to implement the 21.3.1 para 15 which
// requires special behaviour if _InIter is an integral type
diff -urN libstdc++-v3-orig/include/bits/basic_string.tcc
libstdc++-v3/include/bits/basic_string.tcc
--- libstdc++-v3-orig/include/bits/basic_string.tcc Sat Dec 8 17:56:54 2001
+++ libstdc++-v3/include/bits/basic_string.tcc Sun Dec 9 12:09:03 2001
@@ -497,16 +497,17 @@
_M_replace(iterator __i1, iterator __i2, _InputIter __k1,
_InputIter __k2, input_iterator_tag)
{
- basic_string __s(__k1, __k2);
- return this->replace(__i1, __i2, __s._M_ibegin(), __s._M_iend());
+ // Save concerned source string data in a temporary.
+ basic_string __temp(__k1, __k2);
+ return _M_replace_safe(__i1, __i2, __temp.begin(), __temp.end());
}
template<typename _CharT, typename _Traits, typename _Alloc>
- template<typename _ForwardIter>
+ template<typename _InputIter>
basic_string<_CharT, _Traits, _Alloc>&
basic_string<_CharT, _Traits, _Alloc>::
- _M_replace(iterator __i1, iterator __i2, _ForwardIter __k1,
- _ForwardIter __k2, forward_iterator_tag)
+ _M_replace_safe(iterator __i1, iterator __i2, _InputIter __k1,
+ _InputIter __k2)
{
size_type __dnew = static_cast<size_type>(distance(__k1, __k2));
size_type __dold = __i2 - __i1;
@@ -515,16 +516,11 @@
if (__dmax <= __dnew)
__throw_length_error("basic_string::_M_replace");
size_type __off = __i1 - _M_ibegin();
-
- // Save concerned source string data in a temporary.
- basic_string __temp(__k1, __k2);
_M_mutate(__off, __dold, __dnew);
-
- // Invalidated __i1, __i2 (and clobbered original source string
- // data when destination string == source string and the string
- // is unshared).
+
+ // Invalidated __i1, __i2
if (__dnew)
- _S_copy_chars(_M_data() + __off, __temp.begin(), __temp.end());
+ _S_copy_chars(_M_data() + __off, __k1, __k2);
return *this;
}
@@ -537,7 +533,7 @@
{
return this->replace(_M_check(__pos1), _M_fold(__pos1, __n1),
__str._M_check(__pos2),
- __str._M_fold(__pos2, __n2));
+ __str._M_fold(__pos2, __n2));
}
template<typename _CharT, typename _Traits, typename _Alloc>
@@ -552,8 +548,8 @@
size_type __len = __size + this->size();
if (__len > this->capacity())
this->reserve(__len);
- return this->replace(_M_iend(), _M_iend(), __str._M_ibegin(),
- __str._M_iend());
+ return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
+ __str._M_iend());
}
template<typename _CharT, typename _Traits, typename _Alloc>
@@ -567,8 +563,8 @@
size_type __len = min(__str.size() - __pos, __n) + this->size();
if (__len > this->capacity())
this->reserve(__len);
- return this->replace(_M_iend(), _M_iend(), __str._M_check(__pos),
- __str._M_fold(__pos, __n));
+ return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
+ __str._M_fold(__pos, __n));
}
template<typename _CharT, typename _Traits, typename _Alloc>
@@ -579,7 +575,7 @@
size_type __len = __n + this->size();
if (__len > this->capacity())
this->reserve(__len);
- return this->replace(_M_iend(), _M_iend(), __s, __s + __n);
+ return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
}
template<typename _CharT, typename _Traits, typename _Alloc>
diff -urN libstdc++-v3-orig/src/string-inst.cc libstdc++-v3/src/string-inst.cc
--- libstdc++-v3-orig/src/string-inst.cc Sat Dec 8 18:42:47 2001
+++ libstdc++-v3/src/string-inst.cc Sun Dec 9 12:10:22 2001
@@ -71,21 +71,38 @@
template
S&
S::_M_replace(S::iterator, S::iterator, S::iterator, S::iterator,
- forward_iterator_tag);
+ input_iterator_tag);
template
S&
S::_M_replace(S::iterator, S::iterator, S::const_iterator,
- S::const_iterator, forward_iterator_tag);
+ S::const_iterator, input_iterator_tag);
template
S&
- S::_M_replace(S::iterator, S::iterator, C*, C*, forward_iterator_tag);
+ S::_M_replace(S::iterator, S::iterator, C*, C*, input_iterator_tag);
template
S&
S::_M_replace(S::iterator, S::iterator, const C*, const C*,
- forward_iterator_tag);
+ input_iterator_tag);
+
+ template
+ S&
+ S::_M_replace_safe(S::iterator, S::iterator, S::iterator, S::iterator);
+
+ template
+ S&
+ S::_M_replace_safe(S::iterator, S::iterator, S::const_iterator,
+ S::const_iterator);
+
+ template
+ S&
+ S::_M_replace_safe(S::iterator, S::iterator, C*, C*);
+
+ template
+ S&
+ S::_M_replace_safe(S::iterator, S::iterator, const C*, const C*);
template
C*
More information about the Libstdc++
mailing list