diff mbox series

[committed] libstdc++: Optimize std::string_view::find [PR 66414]

Message ID 20210127135315.GA1400335@redhat.com
State New
Headers show
Series [committed] libstdc++: Optimize std::string_view::find [PR 66414] | expand

Commit Message

Jonathan Wakely Jan. 27, 2021, 1:53 p.m. UTC 
This reuses the code from std::string::find, which was improved by
r244225, but string_view was not changed to match.

libstdc++-v3/ChangeLog:

	PR libstdc++/66414
	* include/bits/string_view.tcc
	(basic_string_view::find(const CharT*, size_type, size_type)):
	Optimize.

Tested x86_64-linux and powerpc64le-linux. Committed to trunk.

This makes string_view::find as fast as string::find, rather than 2-10
times slower! We should probably consider whether to define the find
algorithm once and reuse it in string and string_view, rather than
duplicating the code.

In stage 1 I'll look at using memmem here for the specializations
using std::char_traits<char|wchar_t|char8_t|char16_t|char32_t>.
commit a199da782fc165fd45f42a15cc9020994efd455d
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jan 27 13:21:52 2021

    libstdc++: Optimize std::string_view::find [PR 66414]
    
    This reuses the code from std::string::find, which was improved by
    r244225, but string_view was not changed to match.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/66414
            * include/bits/string_view.tcc
            (basic_string_view::find(const CharT*, size_type, size_type)):
            Optimize.
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/string_view.tcc b/libstdc++-v3/include/bits/string_view.tcc
index bcd8fc1339e..efb0edee26a 100644
--- a/libstdc++-v3/include/bits/string_view.tcc
+++ b/libstdc++-v3/include/bits/string_view.tcc
@@ -50,15 +50,27 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_requires_string_len(__str, __n);
 
       if (__n == 0)
-	return __pos <= this->_M_len ? __pos : npos;
+	return __pos <= _M_len ? __pos : npos;
+      if (__pos >= _M_len)
+	return npos;
 
-      if (__n <= this->_M_len)
+      const _CharT __elem0 = __str[0];
+      const _CharT* __first = _M_str + __pos;
+      const _CharT* const __last = _M_str + _M_len;
+      size_type __len = _M_len - __pos;
+
+      while (__len >= __n)
 	{
-	  for (; __pos <= this->_M_len - __n; ++__pos)
-	    if (traits_type::eq(this->_M_str[__pos], __str[0])
-		&& traits_type::compare(this->_M_str + __pos + 1,
-					__str + 1, __n - 1) == 0)
-	      return __pos;
+	  // Find the first occurrence of __elem0:
+	  __first = traits_type::find(__first, __len - __n + 1, __elem0);
+	  if (!__first)
+	    return npos;
+	  // Compare the full strings from the first occurrence of __elem0.
+	  // We already know that __first[0] == __s[0] but compare them again
+	  // anyway because __s is probably aligned, which helps memcmp.
+	  if (traits_type::compare(__first, __str, __n) == 0)
+	    return __first - _M_str;
+	  __len = __last - ++__first;
 	}
       return npos;
     }