[Patch, v7] compare(string) optimization

[Paolo Carlini <pcarlini at suse dot de>]

Hi,

we are missing this useful optimization, AFAICS.

Similarly to analogous situations in istream, for example, I believe
it's safe only for char / wchar_t, but in my opinion would be ok also
for any non-totally-crazy char_traits. Any comment about the last point
in particular?

Tested x86-linux, both bases, will go in mainline/4_1 too as ext/vstring.h

Paolo.

P.S. Took the occasion for an unrelated trivial tweak.

/////////////////

2005-12-09  Paolo Carlini  <pcarlini@suse.de>

	* include/ext/sso_string.h (__sso_string<>::_M_compare): Add,
	specialized for char and wchar_t to return immediately true when
	we a string is compared to itself.
	* include/ext/rc_string.h (__rc_string<>::_M_compare): Likewise,
	for the same _Rep.
	* include/bits/basic_string.h (compare(const string&)): Use it.
	* src/sso_string-inst.cc: Adjust includes order.
	* src/rc_string-inst.cc: Likewise.
	* testsuite/performance/21_strings/string_compare.cc: New.

	* include/ext/sso_string.h (__sso_string<>::_M_destroy): Deallocate
	passed size + 1.
	(_M_dispose, _M_reserve): Adjust.

Index: include/ext/sso_string.h
===================================================================
--- include/ext/sso_string.h	(revision 108062)
+++ include/ext/sso_string.h	(working copy)
@@ -102,7 +102,7 @@
       _M_dispose()
       {
 	if (!_M_is_local())
-	  _M_destroy(_M_allocated_capacity + 1);
+	  _M_destroy(_M_allocated_capacity);
       }
 
       void
@@ -225,13 +225,17 @@
 
       void
       _M_erase(size_type __pos, size_type __n);
+
+      bool
+      _M_compare(const __sso_string&) const
+      { return false; }
     };
 
   template<typename _CharT, typename _Traits, typename _Alloc>
     void
     __sso_string<_CharT, _Traits, _Alloc>::
     _M_destroy(size_type __size) throw()
-    { _CharT_alloc_type(_M_get_allocator()).deallocate(_M_data(), __size); }
+    { _CharT_alloc_type(_M_get_allocator()).deallocate(_M_data(), __size + 1); }
 
   template<typename _CharT, typename _Traits, typename _Alloc>
     void
@@ -497,7 +501,7 @@
 	  else if (!_M_is_local())
 	    {
 	      _S_copy(_M_local_data, _M_data(), _M_length() + 1);
-	      _M_destroy(__capacity + 1);
+	      _M_destroy(__capacity);
 	      _M_data(_M_local_data);
 	    }
 	}
@@ -540,6 +544,28 @@
 
       _M_set_length(_M_length() - __n);
     } 
+
+  template<>
+    inline bool
+    __sso_string<char, std::char_traits<char>,
+		 std::allocator<char> >::
+    _M_compare(const __sso_string& __rcs) const
+    {
+      if (this == &__rcs)
+	return true;
+      return false;
+    }
+
+  template<>
+    inline bool
+    __sso_string<wchar_t, std::char_traits<wchar_t>,
+		 std::allocator<wchar_t> >::
+    _M_compare(const __sso_string& __rcs) const
+    {
+      if (this == &__rcs)
+	return true;
+      return false;
+    }
 } // namespace __gnu_cxx
 
 #endif /* _SSO_STRING_H */
Index: include/ext/rc_string.h
===================================================================
--- include/ext/rc_string.h	(revision 108013)
+++ include/ext/rc_string.h	(working copy)
@@ -333,6 +333,10 @@
       
       void
       _M_erase(size_type __pos, size_type __n);
+
+      bool
+      _M_compare(const __rc_string&) const
+      { return false; }
     };
 
   template<typename _CharT, typename _Traits, typename _Alloc>
@@ -667,7 +671,29 @@
 	}
 
       _M_rep()->_M_set_length(__new_size);      
-    } 
+    }
+
+  template<>
+    inline bool
+    __rc_string<char, std::char_traits<char>,
+		std::allocator<char> >::
+    _M_compare(const __rc_string& __rcs) const
+    {
+      if (_M_rep() == __rcs._M_rep())
+	return true;
+      return false;
+    }
+
+  template<>
+    inline bool
+    __rc_string<wchar_t, std::char_traits<wchar_t>,
+		std::allocator<wchar_t> >::
+    _M_compare(const __rc_string& __rcs) const
+    {
+      if (_M_rep() == __rcs._M_rep())
+	return true;
+      return false;
+    }
 } // namespace __gnu_cxx
 
 #endif /* _RC_STRING_H */
Index: include/bits/basic_string.h
===================================================================
--- include/bits/basic_string.h	(revision 108013)
+++ include/bits/basic_string.h	(working copy)
@@ -1704,6 +1704,9 @@
       int
       compare(const basic_string& __str) const
       {
+	if (this->_M_compare(__str))
+	  return 0;
+
 	const size_type __size = this->size();
 	const size_type __osize = __str.size();
 	const size_type __len = std::min(__size, __osize);
Index: src/sso_string-inst.cc
===================================================================
--- src/sso_string-inst.cc	(revision 106945)
+++ src/sso_string-inst.cc	(working copy)
@@ -32,9 +32,9 @@
 //
 
 #include <bits/c++config.h>
-#include <ext/sso_string.h>
 #include <memory> 	// For allocator.
 #include <bits/char_traits.h>
+#include <ext/sso_string.h>
 
 // Instantiation configuration.
 #ifndef C
Index: src/rc_string-inst.cc
===================================================================
--- src/rc_string-inst.cc	(revision 106945)
+++ src/rc_string-inst.cc	(working copy)
@@ -32,9 +32,9 @@
 //
 
 #include <bits/c++config.h>
-#include <ext/rc_string.h>
 #include <memory> 	// For allocator.
 #include <bits/char_traits.h>
+#include <ext/rc_string.h>
 
 // Instantiation configuration.
 #ifndef C
Index: testsuite/performance/21_strings/string_compare.cc
===================================================================
--- testsuite/performance/21_strings/string_compare.cc	(revision 0)
+++ testsuite/performance/21_strings/string_compare.cc	(revision 0)
@@ -0,0 +1,66 @@
+// 2005-12-09  Paolo Carlini  <pcarlini@suse.de>
+//
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <string>
+#include <vector>
+#include <testsuite_performance.h>
+
+using namespace std;
+using namespace __gnu_test;
+
+const int length = 1000;
+const int loop_count = 1000000;
+
+void test01()
+{
+  time_counter time;
+  resource_counter resource;
+
+  vector<string> vs;
+  for (int j = 0; j < length; ++j)
+    vs.push_back(string(j, 'a'));
+
+  vector<int> vi(length);
+  
+  start_counters(time, resource);
+  for (int i = 0; i < loop_count; ++i)
+    {
+      for (int j = 0; j < length; ++j)
+	vi[j] &= vs[j].compare(vs[j]);
+    }
+  stop_counters(time, resource);
+
+  report_performance(__FILE__, "", time, resource);
+}
+
+int main()
+{
+  test01();
+  return 0;
+}