[Bug libstdc++/66416] string::find_last_of 3.5 times slower than memrchr

[Bug libstdc++/66416] string::find_last_of 3.5 times slower than memrchr

[hiraditya at msn dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66416

AK <hiraditya at msn dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hiraditya at msn dot com

--- Comment #2 from AK <hiraditya at msn dot com> ---
Could it be because string::find is more optimized than string::rfind?
see: https://gcc.gnu.org/legacy-ml/libstdc++/2017-01/msg00034.html

[Bug libstdc++/66416] string::find_last_of 3.5 times slower than memrchr

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66416

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2024-02-19
           Keywords|                            |missed-optimization
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=23112
             Status|UNCONFIRMED                 |NEW

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The problem is that string::find(char) uses std::char_traits::find, which is
optimized to use memchr, but there is no char-traits API for rfind, so
string::rfind(char) is a manual loop from the end of the string to the start.

We could add configure checks for memrchr and do something like:

--- a/libstdc++-v3/include/bits/string_view.tcc
+++ b/libstdc++-v3/include/bits/string_view.tcc
@@ -121,6 +121,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        {
          if (--__size > __pos)
            __size = __pos;
+#if _GLIBCXX_HAVE_MEMRCHR
+         if constexpr (is_same_v<_Traits, char_traits<char>>)
+           {
+           if (auto __ptr = memrchr(_M_str, __c, __size))
+             return __ptr - _M_str;
+           }
+         else
+#endif
          for (++__size; __size-- > 0; )
            if (traits_type::eq(this->_M_str[__size], __c))
              return __size;

And then duplicate that in std::string::rfind, and ranges::find_last.