From a199da782fc165fd45f42a15cc9020994efd455d Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 27 Jan 2021 13:21:52 +0000 Subject: [PATCH] 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. --- libstdc++-v3/include/bits/string_view.tcc | 26 +++++++++++++++++------ 1 file changed, 19 insertions(+), 7 deletions(-) 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; } -- 2.30.2