This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[v3] Nathan's basic_string improvements
- From: Paolo Carlini <pcarlini at unitus dot it>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 13 Jun 2003 23:13:58 +0200
- Subject: [v3] Nathan's basic_string improvements
Hi,
tested for correcteness and performance by myself
(i686-pc-linux-gnu) and Loren ({i386,alpha}-unknown-freebsd4)
see the list for additional details...
Paolo.
/////////
2003-06-13 Nathan C. Myers <ncm-nospam@cantrip.org>
Avoid multi-processor bus contention on increment/decrement-and-
test of the reference count in the empty-string object, by comparing
addresses first, and never touching the reference count of the empty-
string object.
* include/bits/basic_string.h:
(_S_empty_rep_storage): Move into basic_string<>::_Rep for use by its
members.
(_Rep::_S_empty_rep()): New accessor.
(_Rep::_M_length, _Rep::_M_capacity, _Rep::_M_references): Move to
a base class _Rep_base.
(_Rep::_M_dispose, _Rep::_M_refcopy): Check for the empty string.
(basic_string()): Change to use _M_refdata() in place of _M_refcopy(),
since no longer must increment its refcount.
* include/bits/basic_string.tcc:
(_Rep::_M_destroy, _M_leak_hard): Check for the empty string and
return immediately. The former might be unnecessary. The latter
prevents begin() and end() from cloning it unnecessarily.
(_S_construct(_InIterator, _InIterator, const _Alloc&,
input_iterator_tag), _S_construct(_InIterator, _InIterator,
const _Alloc&, forward_iterator_tag), _S_construct(size_type, _CharT,
const _Alloc&)): Change to use _M_refdata() in place of _M_refcopy().
(_M_mutate): Check for the empty string and treat it as shared.
This is necessary here because _M_mutate is sometimes called with
all-zero arguments; in all other uses of _M_is_shared, the test comes
out right anyhow.diff -urN libstdc++-v3-orig/include/bits/basic_string.h libstdc++-v3/include/bits/basic_string.h
--- libstdc++-v3-orig/include/bits/basic_string.h 2003-06-10 23:59:29.000000000 +0200
+++ libstdc++-v3/include/bits/basic_string.h 2003-06-12 13:51:36.000000000 +0200
@@ -1,6 +1,6 @@
// Components for manipulating sequences of characters -*- C++ -*-
-// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002
+// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
@@ -140,7 +140,15 @@
// 4. All fields==0 is an empty string, given the extra storage
// beyond-the-end for a null terminator; thus, the shared
// empty string representation needs no constructor.
- struct _Rep
+
+ struct _Rep_base
+ {
+ size_type _M_length;
+ size_type _M_capacity;
+ _Atomic_word _M_references;
+ };
+
+ struct _Rep : _Rep_base
{
// Types:
typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
@@ -157,29 +165,33 @@
// npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
// Solving for m:
// m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
- // In addition, this implementation quarters this ammount.
+ // In addition, this implementation quarters this amount.
static const size_type _S_max_size;
static const _CharT _S_terminal;
- size_type _M_length;
- size_type _M_capacity;
- _Atomic_word _M_references;
-
+ // 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[];
+
+ static _Rep&
+ _S_empty_rep()
+ { return *reinterpret_cast<_Rep*>(&_S_empty_rep_storage); }
+
bool
_M_is_leaked() const
- { return _M_references < 0; }
+ { return this->_M_references < 0; }
bool
_M_is_shared() const
- { return _M_references > 0; }
+ { return this->_M_references > 0; }
void
_M_set_leaked()
- { _M_references = -1; }
+ { this->_M_references = -1; }
void
_M_set_sharable()
- { _M_references = 0; }
+ { this->_M_references = 0; }
_CharT*
_M_refdata() throw()
@@ -203,8 +215,9 @@
void
_M_dispose(const _Alloc& __a)
{
- if (__exchange_and_add(&_M_references, -1) <= 0)
- _M_destroy(__a);
+ if (__builtin_expect(this != &_S_empty_rep(), false))
+ if (__exchange_and_add(&this->_M_references, -1) <= 0)
+ _M_destroy(__a);
} // XXX MT
void
@@ -213,7 +226,8 @@
_CharT*
_M_refcopy() throw()
{
- __atomic_add(&_M_references, 1);
+ if (__builtin_expect(this != &_S_empty_rep(), false))
+ __atomic_add(&this->_M_references, 1);
return _M_refdata();
} // XXX MT
@@ -240,10 +254,6 @@
// Data Members (private):
mutable _Alloc_hider _M_dataplus;
- // 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[(sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
-
_CharT*
_M_data() const
{ return _M_dataplus._M_p; }
@@ -322,7 +332,7 @@
static _Rep&
_S_empty_rep()
- { return *reinterpret_cast<_Rep*>(&_S_empty_rep_storage); }
+ { return _Rep::_S_empty_rep(); }
public:
// Construct/copy/destroy:
@@ -859,7 +869,7 @@
template<typename _CharT, typename _Traits, typename _Alloc>
inline basic_string<_CharT, _Traits, _Alloc>::
basic_string()
- : _M_dataplus(_S_empty_rep()._M_refcopy(), _Alloc()) { }
+ : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
// operator+
template<typename _CharT, typename _Traits, typename _Alloc>
diff -urN libstdc++-v3-orig/include/bits/basic_string.tcc libstdc++-v3/include/bits/basic_string.tcc
--- libstdc++-v3-orig/include/bits/basic_string.tcc 2003-06-10 23:59:29.000000000 +0200
+++ libstdc++-v3/include/bits/basic_string.tcc 2003-06-12 20:36:01.000000000 +0200
@@ -48,7 +48,7 @@
template<typename _CharT, typename _Traits, typename _Alloc>
const typename basic_string<_CharT, _Traits, _Alloc>::size_type
basic_string<_CharT, _Traits, _Alloc>::
- _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
+ _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
template<typename _CharT, typename _Traits, typename _Alloc>
const _CharT
@@ -63,8 +63,9 @@
// at static init time (before static ctors are run).
template<typename _CharT, typename _Traits, typename _Alloc>
typename basic_string<_CharT, _Traits, _Alloc>::size_type
- basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[
- (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
+ basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
+ (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
+ sizeof(size_type)];
// NB: This is the special case for Input Iterators, used in
// istreambuf_iterators, etc.
@@ -78,7 +79,7 @@
input_iterator_tag)
{
if (__beg == __end && __a == _Alloc())
- return _S_empty_rep()._M_refcopy();
+ return _S_empty_rep()._M_refdata();
// Avoid reallocation for common case.
_CharT __buf[100];
size_type __i = 0;
@@ -138,7 +139,7 @@
forward_iterator_tag)
{
if (__beg == __end && __a == _Alloc())
- return _S_empty_rep()._M_refcopy();
+ return _S_empty_rep()._M_refdata();
// NB: Not required, but considered best practice.
if (__builtin_expect(__beg == _InIterator(), 0))
@@ -167,7 +168,7 @@
_S_construct(size_type __n, _CharT __c, const _Alloc& __a)
{
if (__n == 0 && __a == _Alloc())
- return _S_empty_rep()._M_refcopy();
+ return _S_empty_rep()._M_refdata();
// Check for out_of_range and length_error exceptions.
_Rep* __r = _Rep::_S_create(__n, __a);
@@ -242,7 +243,8 @@
template<typename _CharT, typename _Traits, typename _Alloc>
basic_string<_CharT, _Traits, _Alloc>&
- basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str)
+ basic_string<_CharT, _Traits, _Alloc>::
+ assign(const basic_string& __str)
{
if (_M_rep() != __str._M_rep())
{
@@ -371,7 +373,10 @@
basic_string<_CharT, _Traits, _Alloc>::_Rep::
_M_destroy(const _Alloc& __a) throw ()
{
- const size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
+ if (this == &_S_empty_rep())
+ return;
+ const size_type __size = sizeof(_Rep_base) +
+ (this->_M_capacity + 1) * sizeof(_CharT);
_Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
}
@@ -379,6 +384,8 @@
void
basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
{
+ if (_M_rep() == &_S_empty_rep())
+ return;
if (_M_rep()->_M_is_shared())
_M_mutate(0, 0, 0);
_M_rep()->_M_set_leaked();
@@ -400,7 +407,8 @@
const _CharT* __src = _M_data() + __pos + __len1;
const size_type __how_much = __old_size - __pos - __len1;
- if (_M_rep()->_M_is_shared() || __new_size > capacity())
+ if (_M_rep() == &_S_empty_rep()
+ || _M_rep()->_M_is_shared() || __new_size > capacity())
{
// Must reallocate.
allocator_type __a = get_allocator();
@@ -434,7 +442,7 @@
}
_M_rep()->_M_dispose(__a);
_M_data(__r->_M_refdata());
- }
+ }
else if (__how_much && __len1 != __len2)
{
// Work in-place
@@ -443,7 +451,7 @@
_M_rep()->_M_set_sharable();
_M_rep()->_M_length = __new_size;
_M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
- // You cannot leave those LWG people alone for a second.
+ // You cannot leave those LWG people alone for a second.
}
template<typename _CharT, typename _Traits, typename _Alloc>
@@ -505,7 +513,7 @@
// 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_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
+ size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep_base);
// The standard places no restriction on allocating more memory
// than is strictly needed within this layer at the moment or as
@@ -538,7 +546,7 @@
(__pagesize - ((__size + __malloc_header_size) % __pagesize))
% __pagesize;
__capacity += __extra / sizeof(_CharT);
- __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
+ __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep_base);
}
else if (__size > __subpagesize)
{
@@ -546,7 +554,7 @@
(__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
% __subpagesize;
__capacity += __extra / sizeof(_CharT);
- __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
+ __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep_base);
}
// NB: Might throw, but no worries about a leak, mate: _Rep()
@@ -565,33 +573,37 @@
_M_clone(const _Alloc& __alloc, size_type __res)
{
// Requested capacity of the clone.
- const size_type __requested_cap = _M_length + __res;
+ const size_type __requested_cap = this->_M_length + __res;
// See above (_S_create) for the meaning and value of these constants.
const size_type __pagesize = 4096;
const size_type __malloc_header_size = 4 * sizeof (void*);
// The biggest string which fits in a memory page.
const size_type __page_capacity =
- (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
+ (__pagesize - __malloc_header_size - sizeof(_Rep_base) - sizeof(_CharT))
/ sizeof(_CharT);
_Rep* __r;
- if (__requested_cap > _M_capacity && __requested_cap > __page_capacity)
+ if (__requested_cap > this->_M_capacity
+ && __requested_cap > __page_capacity)
// Growing exponentially.
- __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ?
- __requested_cap : 2*_M_capacity, __alloc);
+ __r = _Rep::_S_create(__requested_cap > 2*this->_M_capacity ?
+ __requested_cap : 2*this->_M_capacity, __alloc);
else
__r = _Rep::_S_create(__requested_cap, __alloc);
- if (_M_length)
+ if (this->_M_length)
{
try
- { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); }
+ {
+ traits_type::copy(__r->_M_refdata(), _M_refdata(),
+ this->_M_length);
+ }
catch(...)
{
__r->_M_destroy(__alloc);
__throw_exception_again;
}
}
- __r->_M_length = _M_length;
+ __r->_M_length = this->_M_length;
return __r->_M_refdata();
}