[PATCH] Basic_string::insert
Paolo Carlini
pcarlini@unitus.it
Tue Dec 18 12:46:00 GMT 2001
Hi,
this patch should improve the performance of 4 insert methods: insert(__pos1,
__str), insert(__pos1, __str, __pos2, __n), insert(__pos, __s) and insert(__pos,
__s, __n).
The hard work is carried out by the latter, while the others use it, according
to the general scheme already used for assign. With this patch, the source data
is *never* buffered and, when it comes from the destination string itself
(in-place), there are no reallocations either (if the final result is smaller
than the capacity, of course).
Often, however, the (almost) unavoidable move and copy operations dominate and
the improvement is not noticeable.
This is a particularly favourable example (in-place):
#include <string>
int main()
{
std::string str = "a";
for (int i = 0; i < 20000000; i++)
str.insert(str.size() / 3, str.c_str(), str.size() / 3);
}
mainline + this patch
---------------------
6.080u 0.000s 0:06.16 98.7% 0+0k 0+0io 202pf+0w
mainline
--------
10.820u 0.010s 0:10.99 98.5% 0+0k 0+0io 202pf+0w
2.95.3
------
8.420u 0.020s 0:08.55 98.7% 0+0k 0+0io 94pf+0w
//////////////
This one shows the gain coming from not-buffering *by itself*, about 2x, already
seen for the append members (seen when nothing else dominates):
#include <string>
int main()
{
std::string str = "a";
std::string str2 = "12345678901234567890123456789012345678901234567890"
"12345678901234567890123456789012345678901234567890";
for (int i = 0; i < 400000; i++)
str.insert(str.size(), str2, 0, std::string::npos);
for (int j = 0; j < 10; j++)
{
str = "";
for (int i = 0; i < 400000; i++)
str.insert(str.size(), str2, 0, std::string::npos);
}
}
mainline + this patch
---------------------
3.670u 0.560s 0:04.45 95.0% 0+0k 0+0io 204pf+0w
mainline
--------
6.450u 0.640s 0:07.24 97.9% 0+0k 0+0io 204pf+0w
2.95.3
------
5.570u 6.270s 0:12.08 98.0% 0+0k 0+0io 96pf+0w
///////////
Regtested i686-pc-linux-gnu.
Cheers,
Paolo.
//////////////////
2001-12-18 Paolo Carlini <pcarlini@unitus.it>
Nathan Myers <ncm@cantrip.org>
* include/bits/basic_string.h (insert(__pos, __s, __n)):
Optimize by avoiding temporaries and working "in-place" when possible.
(insert(__pos, __s)): Call insert(__pos, __s, __n).
(insert(__pos1, __str)): Call insert(__pos1, __str, __pos2, __n).
(insert(__pos1, __str, __pos2, __n)): Call insert(__pos, __s, __n).
* testsuite/21_strings/insert.cc (test02): New testcases.
diff -prN libstdc++-v3-orig/include/bits/basic_string.h
libstdc++-v3/include/bits/basic_string.h
*** libstdc++-v3-orig/include/bits/basic_string.h Tue Dec 18 13:23:16 2001
--- libstdc++-v3/include/bits/basic_string.h Tue Dec 18 21:10:17 2001
*************** namespace std
*** 531,559 ****
basic_string&
insert(size_type __pos1, const basic_string& __str)
! {
! iterator __p = _M_check(__pos1);
! this->replace(__p, __p, __str._M_ibegin(), __str._M_iend());
! return *this;
! }
basic_string&
insert(size_type __pos1, const basic_string& __str,
size_type __pos2, size_type __n)
! {
! iterator __p = _M_check(__pos1);
! this->replace(__p, __p, __str._M_check(__pos2),
! __str._M_fold(__pos2, __n));
! return *this;
}
basic_string&
insert(size_type __pos, const _CharT* __s, size_type __n)
! {
! iterator __p = _M_check(__pos);
! this->replace(__p, __p, __s, __s + __n);
! return *this;
! }
basic_string&
insert(size_type __pos, const _CharT* __s)
--- 531,583 ----
basic_string&
insert(size_type __pos1, const basic_string& __str)
! { return this->insert(__pos1, __str, 0, __str.size()); }
basic_string&
insert(size_type __pos1, const basic_string& __str,
size_type __pos2, size_type __n)
! {
! const size_type __strsize = __str.size();
! if (__pos2 > __strsize)
! __throw_out_of_range("basic_string::insert");
! const bool __testn = __n < __strsize - __pos2;
! const size_type __newsize = __testn ? __n : __strsize - __pos2;
! return this->insert(__pos1, __str._M_data() + __pos2, __newsize);
}
basic_string&
insert(size_type __pos, const _CharT* __s, size_type __n)
! {
! const size_type __size = this->size();
! if (__pos > __size)
! __throw_out_of_range("basic_string::insert");
! if (__n + __size > this->max_size())
! __throw_length_error("basic_string::insert");
! if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
! || less<const _CharT*>()(_M_data() + __size, __s))
! return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
! __s, __s + __n);
! else
! {
! // Work in-place. If _M_mutate reallocates the string, __s
! // does not point anymore to valid data, therefore we save its
! // offset, then we restore it.
! const size_type __off = __s - _M_data();
! _M_mutate(__pos, 0, __n);
! __s = _M_data() + __off;
! _CharT* __p = _M_data() + __pos;
! if (__s + __n <= __p)
! traits_type::copy(__p, __s, __n);
! else if (__s >= __p)
! traits_type::copy(__p, __s + __n, __n);
! else
! {
! traits_type::copy(__p, __s, __p - __s);
! traits_type::copy(__p + (__p - __s), __p + __n, __n - (__p - __s));
! }
! return *this;
! }
! }
basic_string&
insert(size_type __pos, const _CharT* __s)
diff -prN libstdc++-v3-orig/testsuite/21_strings/insert.cc
libstdc++-v3/testsuite/21_strings/insert.cc
*** libstdc++-v3-orig/testsuite/21_strings/insert.cc Tue Aug 7 05:38:28 2001
--- libstdc++-v3/testsuite/21_strings/insert.cc Tue Dec 18 21:04:00 2001
*************** int test01(void)
*** 187,195 ****
--- 187,253 ----
return test;
}
+ // Once more
+ // string& insert(size_type __p, const char* s, size_type n);
+ // string& insert(size_type __p, const char* s);
+ // but now s points inside the _Rep
+ int test02(void)
+ {
+ bool test = true;
+
+ std::string str01;
+ const char* title = "Everything was beautiful, and nothing hurt";
+ // Increasing size: str01 is reallocated every time.
+ str01 = title;
+ str01.insert(0, str01.c_str() + str01.size() - 4, 4);
+ VERIFY( str01 == "hurtEverything was beautiful, and nothing hurt" );
+ str01 = title;
+ str01.insert(0, str01.c_str(), 5);
+ VERIFY( str01 == "EveryEverything was beautiful, and nothing hurt" );
+ str01 = title;
+ str01.insert(10, str01.c_str() + 4, 6);
+ VERIFY( str01 == "Everythingything was beautiful, and nothing hurt" );
+ str01 = title;
+ str01.insert(15, str01.c_str(), 10);
+ VERIFY( str01 == "Everything was Everythingbeautiful, and nothing hurt" );
+ str01 = title;
+ str01.insert(15, str01.c_str() + 11, 13);
+ VERIFY( str01 == "Everything was was beautifulbeautiful, and nothing hurt"
);
+ str01 = title;
+ str01.insert(0, str01.c_str());
+ VERIFY( str01 == "Everything was beautiful, and nothing hurt"
+ "Everything was beautiful, and nothing hurt");
+ // Again: no reallocations.
+ str01 = title;
+ str01.insert(0, str01.c_str() + str01.size() - 4, 4);
+ VERIFY( str01 == "hurtEverything was beautiful, and nothing hurt" );
+ str01 = title;
+ str01.insert(0, str01.c_str(), 5);
+ VERIFY( str01 == "EveryEverything was beautiful, and nothing hurt" );
+ str01 = title;
+ str01.insert(10, str01.c_str() + 4, 6);
+ VERIFY( str01 == "Everythingything was beautiful, and nothing hurt" );
+ str01 = title;
+ str01.insert(15, str01.c_str(), 10);
+ VERIFY( str01 == "Everything was Everythingbeautiful, and nothing hurt" );
+ str01 = title;
+ str01.insert(15, str01.c_str() + 11, 13);
+ VERIFY( str01 == "Everything was was beautifulbeautiful, and nothing hurt"
);
+ str01 = title;
+ str01.insert(0, str01.c_str());
+ VERIFY( str01 == "Everything was beautiful, and nothing hurt"
+ "Everything was beautiful, and nothing hurt");
+
+ #ifdef DEBUG_ASSERT
+ assert(test);
+ #endif
+ return test;
+ }
+
int main()
{
__set_testsuite_memlimit();
test01();
+ test02();
return 0;
}
More information about the Libstdc++
mailing list