Patch: improving performance of basic_string modification functions
Ryszard Kabatek
Ryszard.Kabatek@softax.pl
Tue Aug 21 04:05:00 GMT 2001
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 ----
More information about the Libstdc++
mailing list