[Bug libstdc++/88545] New: std::find compile to memchr in trivial random access cases (patch)

[gcc at gms dot tf]

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