[PATCH] Re: string and __thread
Nathan Myers
ncm-nospam@cantrip.org
Mon Apr 7 01:38:00 GMT 2003
On Mon, Mar 31, 2003 at 04:31:35PM -0600, Benjamin Kosnik wrote:
>
> >Obviously we want experience, which is why I posted. The problem
> >is well-known, and has been belabored at length in the literature,
> >e.g. Herb Sutter's benchmarks.
>
> Perhaps you could consider adding this in the 21_strings
> documentation as part of your patch below? I'd appreciate it.
It's hard to write isolated performance tests, because a small test
operates entirely out of cache, and it's a cache interactions that
slow things down. But I'll try.
In the meantime, the place to test the patch is in big programs
that are contention-bound. Any takers willing to try it?
> ...
> >That alternative is to test the pointer for equality to the known
> >empty-string object before doing an increment or decrement-and-test.
> >I will prepare a patch if Paolo doesn't get to it first.
See patch below.
I used __builtin_expect with an assumption that actually executing
the atomic operation will result in a stall in any case. Hence,
speculative execution should assume it's probably operating on the
empty string; that way, if it is, the test is cheap, and if it's not
it doesn't matter because the read-modify-write bus cycle swamps
the pipeline. (Anybody who understands modern CPUs better than I do
is welcome to correct me gently with two-by-four.)
This patch doesn't do anything to try to work around the problem
that comparing addresses of library globals involves a lot of
relocation lookup. That work can be done after this has been
checked out. This should be a win regardless.
I had to do some foolery in this patch to work around a compiler bug.
It insisted that _Rep was an "incomplete type" that sizeof could not
report anything about; hence _Rep_base. I also moved some functions
from basic_string.h to basic_string.tcc that should never have been
inline in the first place. Those changes probably should be backported
to 3.3.
Nathan Myers
ncm-nospam@cantrip.org
Index: basic_string.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/basic_string.h,v
retrieving revision 1.27
diff -u -u -r1.27 basic_string.h
--- basic_string.h 2 Dec 2002 22:15:54 -0000 1.27
+++ basic_string.h 7 Apr 2003 01:29:50 -0000
@@ -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,14 +226,15 @@
_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
_CharT*
_M_clone(const _Alloc&, size_type __res = 0);
};
-
+
// Use empty-base optimization: http://www.cantrip.org/emptyopt.html
struct _Alloc_hider : _Alloc
{
@@ -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:
@@ -499,37 +509,10 @@
assign(const basic_string& __str);
basic_string&
- assign(const basic_string& __str, size_type __pos, size_type __n)
- {
- const size_type __strsize = __str.size();
- if (__pos > __strsize)
- __throw_out_of_range("basic_string::assign");
- const bool __testn = __n < __strsize - __pos;
- const size_type __newsize = __testn ? __n : __strsize - __pos;
- return this->assign(__str._M_data() + __pos, __newsize);
- }
+ assign(const basic_string& __str, size_type __pos, size_type __n);
basic_string&
- assign(const _CharT* __s, size_type __n)
- {
- if (__n > this->max_size())
- __throw_length_error("basic_string::assign");
- if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
- || less<const _CharT*>()(_M_data() + this->size(), __s))
- return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n);
- else
- {
- // Work in-place
- const size_type __pos = __s - _M_data();
- if (__pos >= __n)
- traits_type::copy(_M_data(), __s, __n);
- else if (__pos)
- traits_type::move(_M_data(), __s, __n);
- _M_rep()->_M_length = __n;
- _M_data()[__n] = _Rep::_S_terminal;
- return *this;
- }
- }
+ assign(const _CharT* __s, size_type __n);
basic_string&
assign(const _CharT* __s)
@@ -558,49 +541,10 @@
basic_string&
insert(size_type __pos1, const basic_string& __str,
- size_type __pos2, size_type __n)
- {
- const size_type __strsize = __str.size();
- if (__pos2 > __strsize)
- __throw_out_of_range("basic_string::insert");
- const bool __testn = __n < __strsize - __pos2;
- const size_type __newsize = __testn ? __n : __strsize - __pos2;
- return this->insert(__pos1, __str._M_data() + __pos2, __newsize);
- }
+ size_type __pos2, size_type __n);
basic_string&
- insert(size_type __pos, const _CharT* __s, size_type __n)
- {
- const size_type __size = this->size();
- if (__pos > __size)
- __throw_out_of_range("basic_string::insert");
- if (__size > this->max_size() - __n)
- __throw_length_error("basic_string::insert");
- if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
- || less<const _CharT*>()(_M_data() + __size, __s))
- return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
- __s, __s + __n);
- else
- {
- // Work in-place. If _M_mutate reallocates the string, __s
- // does not point anymore to valid data, therefore we save its
- // offset, then we restore it.
- const size_type __off = __s - _M_data();
- _M_mutate(__pos, 0, __n);
- __s = _M_data() + __off;
- _CharT* __p = _M_data() + __pos;
- if (__s + __n <= __p)
- traits_type::copy(__p, __s, __n);
- else if (__s >= __p)
- traits_type::copy(__p, __s + __n, __n);
- else
- {
- traits_type::copy(__p, __s, __p - __s);
- traits_type::copy(__p + (__p - __s), __p + __n, __n - (__p - __s));
- }
- return *this;
- }
- }
+ insert(size_type __pos, const _CharT* __s, size_type __n);
basic_string&
insert(size_type __pos, const _CharT* __s)
@@ -657,25 +601,7 @@
basic_string&
replace(size_type __pos, size_type __n1, const _CharT* __s,
- size_type __n2)
- {
- const size_type __size = this->size();
- if (__pos > __size)
- __throw_out_of_range("basic_string::replace");
- const bool __testn1 = __n1 < __size - __pos;
- const size_type __foldn1 = __testn1 ? __n1 : __size - __pos;
- if (__size - __foldn1 > this->max_size() - __n2)
- __throw_length_error("basic_string::replace");
- if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
- || less<const _CharT*>()(_M_data() + __size, __s))
- return _M_replace_safe(_M_ibegin() + __pos,
- _M_ibegin() + __pos + __foldn1, __s, __s + __n2);
- // Todo: optimized in-place replace.
- else return
- _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1,
- __s, __s + __n2,
- typename iterator_traits<const _CharT*>::iterator_category());
- }
+ size_type __n2);
basic_string&
replace(size_type __pos, size_type __n1, const _CharT* __s)
@@ -943,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>
Index: basic_string.tcc
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/basic_string.tcc,v
retrieving revision 1.33
diff -u -u -r1.33 basic_string.tcc
--- basic_string.tcc 5 Mar 2003 22:24:56 -0000 1.33
+++ basic_string.tcc 7 Apr 2003 01:29:50 -0000
@@ -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 == _InIter(), 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())
{
@@ -256,11 +258,126 @@
}
template<typename _CharT, typename _Traits, typename _Alloc>
+ basic_string<_CharT, _Traits, _Alloc>&
+ basic_string<_CharT, _Traits, _Alloc>::
+ assign(const basic_string& __str, size_type __pos, size_type __n)
+ {
+ const size_type __strsize = __str.size();
+ if (__pos > __strsize)
+ __throw_out_of_range("basic_string::assign");
+ const bool __testn = __n < __strsize - __pos;
+ const size_type __newsize = __testn ? __n : __strsize - __pos;
+ return this->assign(__str._M_data() + __pos, __newsize);
+ }
+
+
+ template<typename _CharT, typename _Traits, typename _Alloc>
+ basic_string<_CharT, _Traits, _Alloc>&
+ basic_string<_CharT, _Traits, _Alloc>::
+ assign(const _CharT* __s, size_type __n)
+ {
+ if (__n > this->max_size())
+ __throw_length_error("basic_string::assign");
+ if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
+ || less<const _CharT*>()(_M_data() + this->size(), __s))
+ return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n);
+ else
+ {
+ // Work in-place
+ const size_type __pos = __s - _M_data();
+ if (__pos >= __n)
+ traits_type::copy(_M_data(), __s, __n);
+ else if (__pos)
+ traits_type::move(_M_data(), __s, __n);
+ _M_rep()->_M_length = __n;
+ _M_data()[__n] = _Rep::_S_terminal; // grr.
+ return *this;
+ }
+ }
+
+ template<typename _CharT, typename _Traits, typename _Alloc>
+ basic_string<_CharT, _Traits, _Alloc>&
+ basic_string<_CharT, _Traits, _Alloc>::
+ insert(size_type __pos1, const basic_string& __str,
+ size_type __pos2, size_type __n)
+ {
+ const size_type __strsize = __str.size();
+ if (__pos2 > __strsize)
+ __throw_out_of_range("basic_string::insert");
+ const bool __testn = __n < __strsize - __pos2;
+ const size_type __newsize = __testn ? __n : __strsize - __pos2;
+ return this->insert(__pos1, __str._M_data() + __pos2, __newsize);
+ }
+
+ template<typename _CharT, typename _Traits, typename _Alloc>
+ basic_string<_CharT, _Traits, _Alloc>&
+ basic_string<_CharT, _Traits, _Alloc>::
+ insert(size_type __pos, const _CharT* __s, size_type __n)
+ {
+ const size_type __size = this->size();
+ if (__pos > __size)
+ __throw_out_of_range("basic_string::insert");
+ if (__size > this->max_size() - __n)
+ __throw_length_error("basic_string::insert");
+ if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
+ || less<const _CharT*>()(_M_data() + __size, __s))
+ return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
+ __s, __s + __n);
+ else
+ {
+ // Work in-place. If _M_mutate reallocates the string, __s
+ // does not point anymore to valid data, therefore we save its
+ // offset, then we restore it.
+ const size_type __off = __s - _M_data();
+ _M_mutate(__pos, 0, __n);
+ __s = _M_data() + __off;
+ _CharT* __p = _M_data() + __pos;
+ if (__s + __n <= __p)
+ traits_type::copy(__p, __s, __n);
+ else if (__s >= __p)
+ traits_type::copy(__p, __s + __n, __n);
+ else
+ {
+ traits_type::copy(__p, __s, __p - __s);
+ traits_type::copy(__p + (__p-__s), __p + __n, __n - (__p-__s));
+ }
+ return *this;
+ }
+ }
+
+ template<typename _CharT, typename _Traits, typename _Alloc>
+ basic_string<_CharT, _Traits, _Alloc>&
+ basic_string<_CharT, _Traits, _Alloc>::
+ replace(size_type __pos, size_type __n1,
+ const _CharT* __s, size_type __n2)
+ {
+ const size_type __size = this->size();
+ if (__pos > __size)
+ __throw_out_of_range("basic_string::replace");
+ const bool __testn1 = __n1 < __size - __pos;
+ const size_type __foldn1 = __testn1 ? __n1 : __size - __pos;
+ if (__size - __foldn1 > this->max_size() - __n2)
+ __throw_length_error("basic_string::replace");
+ if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
+ || less<const _CharT*>()(_M_data() + __size, __s))
+ return _M_replace_safe(_M_ibegin() + __pos,
+ _M_ibegin() + __pos + __foldn1, __s, __s + __n2);
+ // Todo: optimized in-place replace.
+ else
+ return _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1,
+ __s, __s + __n2,
+ typename iterator_traits<const _CharT*>::iterator_category());
+ }
+
+ template<typename _CharT, typename _Traits, typename _Alloc>
void
basic_string<_CharT, _Traits, _Alloc>::_Rep::
_M_destroy(const _Alloc& __a) throw ()
{
- size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
+ if (this == &_S_empty_rep())
+ return;
+ size_type __size = sizeof(_Rep_base) +
+ (this->_M_capacity + 1) * sizeof(_CharT);
_Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
}
@@ -268,6 +385,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();
@@ -289,7 +408,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();
@@ -298,9 +418,9 @@
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))
- / sizeof(_CharT);
+ const size_type __page_capacity =
+ (__pagesize - __malloc_header_size -
+ sizeof(_Rep_base) - sizeof(_CharT)) / sizeof(_CharT);
_Rep* __r;
if (__new_size > capacity() && __new_size > __page_capacity)
// Growing exponentially.
@@ -323,7 +443,7 @@
}
_M_rep()->_M_dispose(__a);
_M_data(__r->_M_refdata());
- }
+ }
else if (__how_much && __len1 != __len2)
{
// Work in-place
@@ -332,7 +452,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>
@@ -394,7 +514,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
@@ -427,7 +547,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)
{
@@ -435,7 +555,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()
@@ -454,33 +574,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();
}
More information about the Libstdc++
mailing list