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]

Re: on the speed of std::string::find


Paolo Carlini wrote:

... - The old string::find; 2- The current string::find; 3- The version forwarding to memmem; + double check that 1- added of the first char optimization becomes equivalent to 3-.

Denis, can you try on your real data the below, which changes find to simply become similar to glibc' memmem? Here, in some basic tests it does rather well, better than going through std::search... humm...


Thanks,
Paolo.

///////////
Index: include/bits/basic_string.tcc
===================================================================
--- include/bits/basic_string.tcc	(revision 116659)
+++ include/bits/basic_string.tcc	(working copy)
@@ -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 Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]