This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Patch: speeding up the basic_string modifications


The attached patch speeds up the basic_string. 
Now we have the same speed in string modification operations as in gcc 2.9.x.

Just run the benchmark I send in my posting
"Fwd: basic_string<> - useless because of its poor performance",
http://gcc.gnu.org/ml/libstdc++/2001-07/msg00030.html
to see the results.

Here are my benchmark results after the change:
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 dec instead of 1.4 hours! :-)
                        -----------------------------


2001-07-12  Ryszard Kabatek <Ryszard.Kabatek@softax.pl>
 
    * Modification of _M_mutate - better reallocation strategy
    * Calling reserve in append only if appending itself


Regards
-- 
Ryszard Kabatek
*** /home/rysio/gcc-3.0-1/include/g++-v3/bits/basic_string.tcc	Wed Jul 11 15:56:40 2001
--- basic_string.tcc	Thu Jul 12 09:51:14 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 (__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 (__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,537 ----
      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 (__len > this->capacity())
! 	        this->reserve(__len);
!       }
        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);
      }
  
--- 540,545 ----

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]