This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: std::string::reserve()
Paolo Carlini wrote:
<snip>
> The standard is like this exactly because wants to make possible
> an efficient refcopied implementation.
In other words, it's better to make correct usage as efficient as
possible, even at the expense of guarding against unsafe usage.
You're right.
I surrender :-)
_M_set_sharable() call added, regtested i686-linux, diffs attached.
Neil.
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 12 Feb 2004 17:50:55 -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 12 Feb 2004 17:51:04 -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,459 ----
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())
+ {
+ _M_rep()->_M_set_sharable();
+ 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.
--- 502,507 ----
*************** 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.
--- 509,522 ----
// 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.