https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88545
Bug ID: 88545
Summary: std::find compile to memchr in trivial random access
cases (patch)
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: gcc at gms dot tf
Target Milestone: ---
Created attachment 45259
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=45259&action=edit
specialize std::find to memchr for character searches in continous memory
If std::find() is called with continuous random access iterators and a trivial
char sized value, then calling memchr() is much more efficient than calling
into the generic __find_if().
The attached patch implements this optimization.
That means it specializes a std::find helper on the iterator category and the
value and calls __builtin_memchr() if possible.
I've tested it on Fedora 27 and Fedora 29 (libstdc++-8.2.1-5.fc29.x86_64), but
it should apply to the master branch as well.
Note that the patch uses techniques similar to what is already used for other
algorithms in bits/stl_algo.h and bits/stl_algobase.h for detecting continuous
random access iterators and specializations (e.g. std::equal calling memcmp if
possible, other algorithms calling memmove, etc.).
I benchmarked some memchr()/std::find() implementations and one relevant result
was that glibc's memchr() outperforms libstc++'s std::find() status-quo
implementation (which does some manual loop unrolling in the find_if helper) by
a factor of 1.5 or so (it always outperforms std::find(), but the factors vary
between different CPU families). Also, on many CPUs, std::find() is even slower
than a simple loop. (i.e. when using it for character searches)
See also: https://gms.tf/stdfind-and-memchr-optimizations.html#measurements
