[Bug libstdc++/66414] string::find ten times slower than strstr

[redi at gcc dot gnu.org via Gcc-bugs]

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

--- Comment #17 from Jonathan Wakely  ---
See comment 9

[Bug libstdc++/66414] string::find ten times slower than strstr

[scc at teamt5 dot org via Gcc-bugs]

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

--- Comment #16 from Chih-Hsuan Yang  ---
(In reply to Jonathan Wakely from comment #15)
> (In reply to Chih-Hsuan Yang from comment #11)
> > Could you please provide an update on the progress here?
> 
> 
> All progress is already recorded above.

Would you like to change this ticket's status to close? And marking this issue
is solved since gcc 10.1, libstdc++6.0.28

[Bug libstdc++/66414] string::find ten times slower than strstr

[redi at gcc dot gnu.org via Gcc-bugs]

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

--- Comment #15 from Jonathan Wakely  ---
(In reply to Chih-Hsuan Yang from comment #11)
> Could you please provide an update on the progress here?


All progress is already recorded above.

[Bug libstdc++/66414] string::find ten times slower than strstr

[scc at teamt5 dot org via Gcc-bugs]

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

--- Comment #14 from Chih-Hsuan Yang  ---
(In reply to Chih-Hsuan Yang from comment #11)
> Hi all, 
> 
> I hope this message finds you well.
> 
> I wanted to inquire about the current status of our project. It has come to
> my attention that our program is facing performance issues when using gcc
> 13.2. Considering this situation, I am willing to take on the responsibility
> of addressing this issue by taking ownership of the related ticket.
> 
> Could you please provide an update on the progress here?
> 
> Thank you for your attention to this matter.

sorry, it's my fault, it seems being solved.

[Bug libstdc++/66414] string::find ten times slower than strstr

[scc at teamt5 dot org via Gcc-bugs]

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

--- Comment #13 from Chih-Hsuan Yang  ---
Hi all,


I hope this message finds you well.

I wanted to inquire about the current status of our project. It has come to my
attention that our program is facing performance issues when using gcc 13.2.
Considering this situation, I am willing to take on the responsibility of
addressing this issue by taking ownership of the related ticket.

Could you please provide an update on the progress here?

Thank you for your attention to this matter.

[Bug libstdc++/66414] string::find ten times slower than strstr

[scc at teamt5 dot org via Gcc-bugs]

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

--- Comment #12 from Chih-Hsuan Yang  ---
Hi all,


I hope this message finds you well.

I wanted to inquire about the current status of our project. It has come to my
attention that our program is facing performance issues when using gcc 13.2.
Considering this situation, I am willing to take on the responsibility of
addressing this issue by taking ownership of the related ticket.

Could you please provide an update on the progress here?

Thank you for your attention to this matter.

[Bug libstdc++/66414] string::find ten times slower than strstr

[scc at teamt5 dot org via Gcc-bugs]

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

Chih-Hsuan Yang  changed:

   What|Removed |Added

 CC||scc at teamt5 dot org

--- Comment #11 from Chih-Hsuan Yang  ---
Hi all, 

I hope this message finds you well.

I wanted to inquire about the current status of our project. It has come to my
attention that our program is facing performance issues when using gcc 13.2.
Considering this situation, I am willing to take on the responsibility of
addressing this issue by taking ownership of the related ticket.

Could you please provide an update on the progress here?

Thank you for your attention to this matter.

[Bug libstdc++/66414] string::find ten times slower than strstr

[cvs-commit at gcc dot gnu.org via Gcc-bugs]

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

--- Comment #10 from CVS Commits  ---
The master branch has been updated by Jonathan Wakely :

https://gcc.gnu.org/g:a199da782fc165fd45f42a15cc9020994efd455d

commit r11-6931-ga199da782fc165fd45f42a15cc9020994efd455d
Author: Jonathan Wakely 
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.

[Bug libstdc++/66414] string::find ten times slower than strstr

[redi at gcc dot gnu.org via Gcc-bugs]

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

--- Comment #9 from Jonathan Wakely  ---
(In reply to AK from comment #8)
> Should we consider this fixed?

I think we can still do better, by using GNU memmem when it's available:

https://gcc.gnu.org/pipermail/gcc-patches/2017-January/466460.html
https://gcc.gnu.org/pipermail/gcc-patches/2017-January/466469.html
https://gcc.gnu.org/pipermail/gcc-patches/2017-January/466471.html

For now we should also use the new code in basic_string_view::find which is
currently much slower.

[Bug libstdc++/66414] string::find ten times slower than strstr

[hiraditya at msn dot com]

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

AK  changed:

   What|Removed |Added

 CC||hiraditya at msn dot com

--- Comment #8 from AK  ---
Should we consider this fixed?

[Bug libstdc++/66414] string::find ten times slower than strstr

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely  ---
Author: redi
Date: Mon Jan  9 13:05:58 2017
New Revision: 244225

URL: https://gcc.gnu.org/viewcvs?rev=244225=gcc=rev
Log:
PR66414 optimize std::string::find

2017-01-09  Jonathan Wakely  
Aditya Kumar  

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

Modified:
trunk/libstdc++-v3/ChangeLog
trunk/libstdc++-v3/include/bits/basic_string.tcc

[Bug libstdc++/66414] string::find ten times slower than strstr

[hiraditya at msn dot com]

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

AK  changed:

   What|Removed |Added

 CC||hiraditya at msn dot com

--- Comment #6 from AK  ---
I have posted a patch up for review for string::find which might help as well.

https://gcc.gnu.org/ml/libstdc++/2016-12/msg00051.html

Please give feedback for improvement.
-Aditya

[Bug libstdc++/66414] string::find ten times slower than strstr

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely  ---
This patch would implement the requested change:

--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -2291,9 +2291,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
*  it begins.  If not found, returns npos.
   */
   size_type
-  find(const _CharT* __s, size_type __pos = 0) const
+  find(const _CharT* __s, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
   {
__glibcxx_requires_string(__s);
+   if (__are_same<_Traits, char_traits<_CharT>>::__value)
+ {
+   if (__are_same<_CharT, char>::__value)
+ {
+   const char* __data = (const char*)data();
+   const char* __p
+ = __builtin_strstr(__data + __pos, (const char*)__s);
+   return __p ? (__p - __data) : npos;
+ }
+#if _GLIBCXX_USE_WCHAR_T
+   else if (__are_same<_CharT, wchar_t>::__value)
+ {
+   const wchar_t* __data = (const wchar_t*)data();
+   const wchar_t* __p
+ = __builtin_wcsstr(__data + __pos, (const wchar_t*)__s);
+   return __p ? (__p - __data) : npos;
+ }
+#endif
+ }
return this->find(__s, __pos, traits_type::length(__s));
   }


But it causes a huge regression in this example, where currently it is hundreds
of times faster than strstr:

#include 
#include 
#include 
#include 
#include 

int main()
{
  std::string haystack(5000, 'a');
  std::string needle = haystack;
  needle.back() = 'b';
  std::size_t pos[1000];

  auto start = std::chrono::high_resolution_clock::now();
  for (auto& p : pos)
p = haystack.find(needle.c_str());
  auto stop = std::chrono::high_resolution_clock::now();
  std::cout << (stop - start).count() << std::endl;
  for (auto p : pos)
assert(p == std::string::npos);

  start = std::chrono::high_resolution_clock::now();
  for (auto& p : pos)
  {
auto ptr = std::strstr(haystack.c_str(), needle.c_str());
p = ptr ? ptr - haystack.c_str() : std::string::npos;
  }
  stop = std::chrono::high_resolution_clock::now();
  std::cout << (stop - start).count() << std::endl;
  for (auto p : pos)
assert(p == std::string::npos);
}

This is because the current code uses char_traits::length() (i.e. strlen)
first, so if the needle is longer than the haystack we don't bother looking for
it.

I don't think it's clear that using strstr is an improvement.

The C++17 library provides Boyer-Moore and Boyer-Moore-Horspool searchers, so
that already offers you more control than basic_string::find or strstr.

[Bug libstdc++/66414] string::find ten times slower than strstr

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely  ---
Although we can only do that for the overload that assumes null-terminated
input, not all cases that basic_string::find supports.

We can use the GNU memmem extension for the general case, but that's not
standard.