This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Patch: improving performance of basic_string modification functions
- To: libstdc++ at gcc dot gnu dot org
- Subject: Patch: improving performance of basic_string modification functions
- From: Ryszard Kabatek <Ryszard dot Kabatek at softax dot pl>
- Date: Tue, 21 Aug 2001 13:06:52 +0200
- Reply-To: Ryszard dot Kabatek at softax dot pl
The gcc-3.0.1 is released, so it is a good time to speed up
the basic_string modification functions.
To see why it is neccessary you can run the attached benchmark (bs_benchmark.cc).
Here my results (g++ -O2) on PIII/750, linux:
1. gcc version egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)
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.02 sec.
Execution time of 100000 string::append(const string&) calls: 0.03 sec.
Execution time of 1000000 string::append(char) calls: 0.18 sec.
Execution time of 1000000 string::append(const string&) calls: 0.26 sec.
2. gcc version 3.0/3.0.1 (Thread model: single)
Execution time of 10000 string::append(char) calls: 0.1 sec.
Execution time of 10000 string::append(const string&) calls: 0.09 sec.
Execution time of 100000 string::append(char) calls: 11.67 sec.
Execution time of 100000 string::append(const string&) calls: 12.23 sec.
Execution time of 1000000 string::append(char) calls: 5931.55 sec.
Execution time of 1000000 string::append(const string&) calls: 6087.62 sec.
The reason is the reallocation every time, the append member function is called.
I know, one can call basic_string::reserve, but it is not a good solution.
In my patch I modified basic_string::_M_mutate - now if a reallocation is necessary
the storage will be expanded by power of 2 (necessary capacity*2). The calls of reserve
in the append member functions occurres only if the string will be appended to itself.
Here the benchmark results after alying my patch:
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.02 sec.
Execution time of 100000 string::append(const string&) calls: 0.02 sec.
Execution time of 1000000 string::append(char) calls: 0.22 sec.
Execution time of 1000000 string::append(const string&) calls: 0.25 sec.
In the last case we get 0.25 seconds instead of 1.4 hours! :-)
---------------------------------
My patch for gcc-3.0.1 is attached in basic_string.diff.
2001-08-21 Ryszard Kabatek <Ryszard.Kabatek@softax.pl>
* Modification of _M_mutate - better reallocation strategy
* Calling reserve in append only if appending itself
Regards
--
Ryszard Kabatek
*** basic_string.tcc Fri Jul 20 02:14:09 2001
--- /home/rysio/tmp/gcc-3.0.1/libstdc++-v3/include/bits/basic_string.tcc Tue Aug 21 12:36:49 2001
*************** namespace std
*** 278,285 ****
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)
--- 278,294 ----
if (_M_rep()->_M_is_shared() || __new_size > capacity())
{
// Must reallocate.
+ size_type __new_capacity = _M_rep()->_M_is_shared() ?
+ __new_size : // _M_leak_hard
+ (__new_size < 17 ? 32 : __new_size*2);
+ // We get an exception. OK
+ if (__new_size > _Rep::_S_max_size)
+ __new_capacity = __new_size;
+ else if (__new_capacity > _Rep::_S_max_size) // Avoid an exception. OK
+ __new_capacity = _Rep::_S_max_size;
+
allocator_type __a = get_allocator();
! _Rep* __r = _Rep::_S_create(__new_capacity, __a);
try
{
if (__pos)
*************** namespace std
*** 477,489 ****
basic_string<_CharT,_Traits,_Alloc>::
append(const basic_string& __str)
{
! // Iff appending itself, string needs to pre-reserve the
// correct size so that _M_mutate does not clobber the
// iterators formed here.
! size_type __size = __str.size();
! 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());
}
--- 486,501 ----
basic_string<_CharT,_Traits,_Alloc>::
append(const basic_string& __str)
{
! // If appending itself, string needs to pre-reserve the
// correct size so that _M_mutate does not clobber the
// iterators formed here.
! if (this == &__str)
! {
! size_type __size = __str.size();
! size_type __len = __size + this->size();
! if (_M_rep()->_M_is_shared() || __len > this->capacity())
! this->reserve(__len);
! }
return this->replace(_M_iend(), _M_iend(), __str._M_ibegin(),
__str._M_iend());
}
*************** namespace std
*** 493,504 ****
basic_string<_CharT,_Traits,_Alloc>::
append(const basic_string& __str, size_type __pos, size_type __n)
{
! // Iff appending itself, string needs to pre-reserve the
// correct size so that _M_mutate does not clobber the
// iterators formed here.
! 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));
}
--- 505,519 ----
basic_string<_CharT,_Traits,_Alloc>::
append(const basic_string& __str, size_type __pos, size_type __n)
{
! // If appending itself, string needs to pre-reserve the
// correct size so that _M_mutate does not clobber the
// iterators formed here.
! if (this == &__str)
! {
! size_type __len = min(__str.size() - __pos, __n) + this->size();
! if (_M_rep()->_M_is_shared() || __len > this->capacity())
! this->reserve(__len);
! }
return this->replace(_M_iend(), _M_iend(), __str._M_check(__pos),
__str._M_fold(__pos, __n));
}
*************** namespace std
*** 508,516 ****
basic_string<_CharT,_Traits,_Alloc>::
append(const _CharT* __s, size_type __n)
{
! size_type __len = __n + this->size();
! if (__len > this->capacity())
! this->reserve(__len);
return this->replace(_M_iend(), _M_iend(), __s, __s + __n);
}
--- 523,541 ----
basic_string<_CharT,_Traits,_Alloc>::
append(const _CharT* __s, size_type __n)
{
! // If appending a part of itself, string needs to pre-reserve the
! // correct size so that _M_mutate does not clobber the
! // iterators formed here.
! if (__s >= this->_M_data() && __s < this->_M_data() + this->size())
! {
! size_type __len = __n + this->size();
! if (_M_rep()->_M_is_shared() || __len > this->capacity())
! {
! size_type __pos = __s - this->_M_data(); // Save the position
! this->reserve(__len);
! __s = this->_M_data() + __pos; // Restore the pointer
! }
! }
return this->replace(_M_iend(), _M_iend(), __s, __s + __n);
}
*************** namespace std
*** 519,527 ****
basic_string<_CharT,_Traits,_Alloc>::
append(size_type __n, _CharT __c)
{
- size_type __len = __n + this->size();
- if (__len > this->capacity())
- this->reserve(__len);
return this->replace(_M_iend(), _M_iend(), __n, __c);
}
--- 544,549 ----
#include <ctime>
#include <iostream>
#include <string>
using namespace std;
void
test_append_char(int how_much)
{
string buf; // no preallocation
for (int i = 0; i < how_much; ++i)
buf.append(static_cast<string::size_type>(1) , 'x');
}
void
test_append_string(int how_much)
{
string s(static_cast<string::size_type>(1) , 'x');
string buf; // no preallocation
for (int i = 0; i < how_much; ++i)
buf.append(s);
}
void
run_benchmark1(int how_much)
{
clock_t t0 = clock();
test_append_char(how_much);
clock_t t1 = clock();
cout << "Execution time of " << how_much
<< " string::append(char) calls: "
<< (static_cast<float>(t1 - t0)/CLOCKS_PER_SEC) << " sec."<< endl;
}
void
run_benchmark2(int how_much)
{
clock_t t0 = clock();
test_append_string(how_much);
clock_t t1 = clock();
cout << "Execution time of " << how_much
<< " string::append(const string&) calls: "
<< (static_cast<float>(t1 - t0)/CLOCKS_PER_SEC) << " sec." << endl;
}
int main()
{
run_benchmark1(10000);
run_benchmark2(10000);
run_benchmark1(100000);
run_benchmark2(100000);
run_benchmark1(1000000);
run_benchmark2(1000000);
}