std::string::reserve()

[Neil Ferguson <nferguso at eso dot org>]

Hi, all -

I noticed earlier that calling std::string::reserve() in a
shrink-to-fit request can sometimes end up allocating exactly
the same amount of memory as the string already had.

This is because _S_create() rounds up allocations of over 128
bytes to 128 byte subpages, and of over 4k to 4k pages, for
more efficient use of malloc().

When the reallocated block is the same size as the original
one, the entire contents of the string are effectively being
copied unnecessarily. Further shrink-to-fit calls keep doing
it, too, since the requested capacity remains less than the
actual capacity.

I've attached diffs against latest CVS that try to avoid doing
this, and I'd be interested to know what you think.

Neil.

PS. The diffs seem to work with a small test program, but I
    can't get the dejagnu test suite to work right now (lots
    of cc1plus segfaults?) so please treat with caution...

Index: libstdc++-v3/include/bits/basic_string.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/basic_string.h,v
retrieving revision 1.57
diff -c -p -r1.57 basic_string.h
*** libstdc++-v3/include/bits/basic_string.h	8 Feb 2004 04:46:40 -0000	1.57
--- libstdc++-v3/include/bits/basic_string.h	11 Feb 2004 19:59:26 -0000
*************** namespace std
*** 169,174 ****
--- 169,204 ----
  	static const size_type	_S_max_size;
  	static const _CharT	_S_terminal;
  
+         // The standard places no restriction on allocating more memory
+         // than is strictly needed within this layer at the moment or as
+         // requested by an explicit application call to reserve().
+ 
+         // Many malloc implementations perform quite poorly when an
+         // application attempts to allocate memory in a stepwise fashion
+         // growing each allocation size by only 1 char.  Additionally,
+         // it makes little sense to allocate less linear memory than the
+         // natural blocking size of the malloc implementation.
+         // Unfortunately, we would need a somewhat low-level calculation
+         // with tuned parameters to get this perfect for any particular
+         // malloc implementation.  Fortunately, generalizations about
+         // common features seen among implementations seems to suffice.
+ 
+         // __pagesize need not match the actual VM page size for good
+         // results in practice, thus we pick a common value on the low
+         // side.  __malloc_header_size is an estimate of the amount of
+         // overhead per memory allocation (in practice seen N * sizeof
+         // (void*) where N is 0, 2 or 4).  According to folklore,
+         // picking this value on the high side is better than
+         // low-balling it (especially when this algorithm is used with
+         // malloc implementations that allocate memory blocks rounded up
+         // to a size which is a power of 2).
+ 
+         // must be 2^i * __subpagesize
+         static const size_type _S_pagesize;
+         // should be >> __malloc_header_size
+         static const size_type _S_subpagesize;
+         static const size_type _S_malloc_header_size;
+ 
  	// The following storage is init'd to 0 by the linker, resulting
          // (carefully) in an empty string with one reference.
          static size_type _S_empty_rep_storage[];
*************** namespace std
*** 203,208 ****
--- 233,281 ----
  	  return (!_M_is_leaked() && __alloc1 == __alloc2)
  	          ? _M_refcopy() : _M_clone(__alloc1);
  	}
+ 
+         // Biggest string capacity which fits in a memory page
+         static size_type
+         _S_page_capacity()
+         {
+           return ((_S_pagesize - _S_malloc_header_size - sizeof(_Rep) 
+                    - sizeof(_CharT)) / sizeof(_CharT));
+         }
+ 
+         // Minimum allocation size needed for the given string capacity
+         static size_type
+         _S_min_size(size_type __capacity)
+         {
+           // NB: Need an array of char_type[__capacity], plus a terminating
+           // null char_type() element, plus enough for the _Rep data 
+           // structure. Whew. Seemingly so needy, yet so elemental.
+           return ((__capacity + 1) * sizeof(_CharT) + sizeof(_Rep));
+         }
+ 
+         // Adjusted capacity to match basic_string's memory allocation 
+         // strategy, as required for the given allocation size
+         static size_type
+         _S_adj_capacity(size_type __size, size_type __capacity)
+         {
+           const size_type __adj_size = __size + _S_malloc_header_size;
+ 
+           if (__adj_size > _S_pagesize)
+           {
+             const size_type __extra = _S_pagesize - __adj_size % _S_pagesize;
+             __capacity += __extra / sizeof(_CharT);
+             // Never allocate a string bigger than _S_max_size.
+             if (__capacity > _S_max_size)
+                 __capacity = _S_max_size;
+           }
+           else if (__size > _S_subpagesize)
+           {
+             const size_type __extra = (_S_subpagesize 
+                                        - __adj_size % _S_subpagesize);
+             __capacity += __extra / sizeof(_CharT);
+           }
+ 
+           return __capacity;
+         }
  
  	// Create & Destroy
  	static _Rep*

Index: libstdc++-v3/include/bits/basic_string.tcc
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/basic_string.tcc,v
retrieving revision 1.67
diff -c -p -r1.67 basic_string.tcc
*** libstdc++-v3/include/bits/basic_string.tcc	8 Feb 2004 17:11:07 -0000	1.67
--- libstdc++-v3/include/bits/basic_string.tcc	11 Feb 2004 20:02:46 -0000
*************** namespace std
*** 67,72 ****
--- 67,87 ----
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      const typename basic_string<_CharT, _Traits, _Alloc>::size_type
+     basic_string<_CharT, _Traits, _Alloc>::
+     _Rep::_S_pagesize = 4096;
+ 
+   template<typename _CharT, typename _Traits, typename _Alloc>
+     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
+     basic_string<_CharT, _Traits, _Alloc>::
+     _Rep::_S_subpagesize = 128;
+ 
+   template<typename _CharT, typename _Traits, typename _Alloc>
+     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
+     basic_string<_CharT, _Traits, _Alloc>::
+     _Rep::_S_malloc_header_size = 4 * sizeof (void*);
+ 
+   template<typename _CharT, typename _Traits, typename _Alloc>
+     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
      basic_string<_CharT, _Traits, _Alloc>::npos;
  
    // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
*************** namespace std
*** 416,428 ****
      void
      basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
      {
        if (__res != this->capacity() || _M_rep()->_M_is_shared())
          {
  	  if (__res > this->max_size())
  	    __throw_length_error(__N("basic_string::reserve"));
- 	  // Make sure we don't shrink below the current size
- 	  if (__res < this->size())
- 	    __res = this->size();
  	  const allocator_type __a = get_allocator();
  	  _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
  	  _M_rep()->_M_dispose(__a);
--- 431,456 ----
      void
      basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
      {
+       // Make sure we don't shrink below the current size.
+       if (__res < this->size())
+ 	__res = this->size();
+ 
+       // Return if the reserved capacity would require _M_clone() to 
+       // allocate the same amount of memory as we already have. 
+       if (__res < this->capacity() && !_M_rep()->_M_is_shared())
+       {
+         size_type __res_size = _Rep::_S_min_size(__res);
+         size_type __res_capacity = _Rep::_S_adj_capacity(__res_size, __res);
+ 
+         if (__res_capacity == this->capacity())
+           return;
+       }
+ 
+       // Perform the capacity change, if necessary. 
        if (__res != this->capacity() || _M_rep()->_M_is_shared())
          {
  	  if (__res > this->max_size())
  	    __throw_length_error(__N("basic_string::reserve"));
  	  const allocator_type __a = get_allocator();
  	  _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
  	  _M_rep()->_M_dispose(__a);
*************** namespace std
*** 471,499 ****
        // than is strictly needed within this layer at the moment or as
        // requested by an explicit application call to reserve().
  
-       // Many malloc implementations perform quite poorly when an
-       // application attempts to allocate memory in a stepwise fashion
-       // growing each allocation size by only 1 char.  Additionally,
-       // it makes little sense to allocate less linear memory than the
-       // natural blocking size of the malloc implementation.
-       // Unfortunately, we would need a somewhat low-level calculation
-       // with tuned parameters to get this perfect for any particular
-       // malloc implementation.  Fortunately, generalizations about
-       // common features seen among implementations seems to suffice.
- 
-       // __pagesize need not match the actual VM page size for good
-       // results in practice, thus we pick a common value on the low
-       // side.  __malloc_header_size is an estimate of the amount of
-       // overhead per memory allocation (in practice seen N * sizeof
-       // (void*) where N is 0, 2 or 4).  According to folklore,
-       // picking this value on the high side is better than
-       // low-balling it (especially when this algorithm is used with
-       // malloc implementations that allocate memory blocks rounded up
-       // to a size which is a power of 2).
-       const size_type __pagesize = 4096; // must be 2^i * __subpagesize
-       const size_type __subpagesize = 128; // should be >> __malloc_header_size
-       const size_type __malloc_header_size = 4 * sizeof (void*);
- 
        // The below implements an exponential growth policy, necessary to
        // meet amortized linear time requirements of the library: see
        // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
--- 499,504 ----
*************** namespace std
*** 501,536 ****
        // system pagesize. This is consistent with the requirements of the
        // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
  
-       // The biggest string which fits in a memory page
-       const size_type __page_capacity = ((__pagesize - __malloc_header_size
- 					  - sizeof(_Rep) - sizeof(_CharT))
- 					 / sizeof(_CharT));
- 
        if (__capacity > __old_capacity && __capacity < 2 * __old_capacity
! 	  && __capacity > __page_capacity)
  	__capacity = 2 * __old_capacity;
  
!       // NB: Need an array of char_type[__capacity], plus a terminating
!       // null char_type() element, plus enough for the _Rep data structure.
!       // Whew. Seemingly so needy, yet so elemental.
!       size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
! 
!       const size_type __adj_size = __size + __malloc_header_size;
!       if (__adj_size > __pagesize)
! 	{
! 	  const size_type __extra = __pagesize - __adj_size % __pagesize;
! 	  __capacity += __extra / sizeof(_CharT);
! 	  // Never allocate a string bigger than _S_max_size.
! 	  if (__capacity > _S_max_size)
! 	    __capacity = _S_max_size;
! 	  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
! 	}
!       else if (__size > __subpagesize)
! 	{
! 	  const size_type __extra = __subpagesize - __adj_size % __subpagesize;
! 	  __capacity += __extra / sizeof(_CharT);
! 	  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
! 	}
  
        // NB: Might throw, but no worries about a leak, mate: _Rep()
        // does not throw.
--- 506,519 ----
        // system pagesize. This is consistent with the requirements of the
        // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
  
        if (__capacity > __old_capacity && __capacity < 2 * __old_capacity
! 	  && __capacity > _S_page_capacity())
  	__capacity = 2 * __old_capacity;
  
!       // Adjust allocation size & string capacity for efficient malloc()
!       size_type __size = _S_min_size(__capacity);
!       __capacity = _S_adj_capacity(__size, __capacity);
!       __size = _S_min_size(__capacity);
  
        // NB: Might throw, but no worries about a leak, mate: _Rep()
        // does not throw.