This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ 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]

[Patch] To string::find


Hi,

the below is the complete patch I tested on x86 and x86_64. The performance number I'm getting are consistently better than the current ones and, after all, we are talking about the same algorithm of glibc' memmem, and also the same of the old string::find + a "trivial" but effective optimization, something trustworthy. For example, on a dual core Athlon 64 2200+, for our string::find performance testcase:

Current
3.996u 0.000s 0:03.99 100.0%    0+0k 0+0io 0pf+0w

Patched
2.728u 0.000s 0:02.72 100.0%    0+0k 0+0io 0pf+0w

Tomorrow I'd like to go ahead...

Paolo.

///////////////
2006-09-05  Paolo Carlini  <pcarlini@suse.de>

	* include/bits/basic_string.tcc (find(const _CharT*, size_type,
	size_type)): Reimplement in terms of traits::eq and traits::compare.
	* include/ext/vstring.tcc (find(const _CharT*, size_type,
	size_type)): Likewise.
	* src/string-inst.cc: Remove unneded std::search instantiation.
Index: include/ext/vstring.tcc
===================================================================
--- include/ext/vstring.tcc	(revision 116682)
+++ include/ext/vstring.tcc	(working copy)
@@ -1,6 +1,6 @@
 // Versatile string -*- C++ -*-
 
-// Copyright (C) 2005 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006 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
@@ -271,17 +271,17 @@
     find(const _CharT* __s, size_type __pos, size_type __n) const
     {
       __glibcxx_requires_string_len(__s, __n);
-      size_type __ret = npos;
       const size_type __size = this->size();
-      if (__pos + __n <= __size)
-	{
-	  const _CharT* __data = this->_M_data();
-	  const _CharT* __p = std::search(__data + __pos, __data + __size,
-					  __s, __s + __n, traits_type::eq);
-	  if (__p != __data + __size || __n == 0)
-	    __ret = __p - __data;
-	}
-      return __ret;
+      const _CharT* __data = this->_M_data();
+
+      if (__n == 0)
+	return __pos <= __size ? __pos : npos;
+
+      for (; __pos + __n <= __size; ++__pos)
+	if (traits_type::eq(__data[__pos], __s[0])
+	    && traits_type::compare(__data + __pos + 1, __s + 1, __n - 1) == 0)
+	  return __pos;
+      return npos;
     }
 
   template<typename _CharT, typename _Traits, typename _Alloc,
Index: include/bits/basic_string.tcc
===================================================================
--- include/bits/basic_string.tcc	(revision 116682)
+++ include/bits/basic_string.tcc	(working copy)
@@ -1,6 +1,6 @@
 // Components for manipulating sequences of characters -*- C++ -*-
 
-// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
+// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -710,17 +710,17 @@
     find(const _CharT* __s, size_type __pos, size_type __n) const
     {
       __glibcxx_requires_string_len(__s, __n);
-      size_type __ret = npos;
       const size_type __size = this->size();
-      if (__pos + __n <= __size)
-	{
-	  const _CharT* __data = _M_data();
-	  const _CharT* __p = std::search(__data + __pos, __data + __size,
-					  __s, __s + __n, traits_type::eq);
-	  if (__p != __data + __size || __n == 0)
-	    __ret = __p - __data;
-	}
-      return __ret;
+      const _CharT* __data = _M_data();
+
+      if (__n == 0)
+	return __pos <= __size ? __pos : npos;
+
+      for (; __pos + __n <= __size; ++__pos)
+	if (traits_type::eq(__data[__pos], __s[0])
+	    && traits_type::compare(__data + __pos + 1, __s + 1, __n - 1) == 0)
+	  return __pos;
+      return npos;
     }
 
   template<typename _CharT, typename _Traits, typename _Alloc>
Index: src/string-inst.cc
===================================================================
--- src/string-inst.cc	(revision 116682)
+++ src/string-inst.cc	(working copy)
@@ -1,6 +1,6 @@
 // Components for manipulating sequences of characters -*- C++ -*-
 
-// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
+// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -77,10 +77,6 @@
     S::_S_construct(const C*, const C*, const allocator<C>&,
 		    forward_iterator_tag);
 
-  // Used in str::find.
-  template
-    const C*
-    search(const C*, const C*, const C*, const C*, bool(*)(const C&, const C&));
 _GLIBCXX_END_NAMESPACE
 
 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)

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