This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[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();
     }
   

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