The basic_string, basic_string_view and <algorithm>/<ranges> search members scan or compare their inputs with scalar, element-by-element loops. This patch routes the contiguous, default-comparator specializations through the standard C library block functions, which every target's libc implements with tuned, vectorized code:
* basic_string / basic_string_view::find(const CharT*) -> memchr + memmem
* ::rfind(const CharT*) -> memrchr + memcmp
* ::rfind(CharT) -> memrchr
* ::find_first_of / _not_of / find_last_of / _not_of -> portable O(n)
256-bit byte-set bitmap (no libc set-scan exists; replaces the O(n*set)
double loop)
* std::search / std::ranges::search -> memchr + memmem
* std::find_end / std::ranges::find_end -> memchr + memmem
* std::find_first_of / std::ranges::find_first_of -> byte-set bitmap
* the wchar_t std::search/find_end/ranges variants -> wmemchr + wmemcmp
There is no wmemmem or wmemrchr, so the wchar_t substring searches compose a
bounded wmemchr first-element scan with a wmemcmp verify, and find_first_of
stays scalar for wchar_t (the byte-set bitmap has no 4-byte analogue).
Each memmem path is preceded by a memchr first-byte filter: a needle whose first
byte is rare or absent in the haystack short-circuits in a single vectorized
memchr (exactly as the scalar path does), so it never pays a full memmem scan.
The frequent-first-byte case is unchanged -- memchr finds the first byte at
offset ~0 and memmem then runs from there -- so there is no regression relative
to the scalar implementation on any workload.
All paths are gated on __cpp_if_constexpr (and, for the header-only algorithms,
__glibcxx_type_trait_variable_templates) and on !is_constant_evaluated(), so
constant evaluation and pre-C++17 translation units keep the existing scalar
behaviour byte-for-byte. find/search fall back to the scalar loop below a
64-element guard, where the block-function call setup would not pay off. Only
1-byte character types (char, char8_t, unsigned char, ...) take the memmem /
memrchr paths; wchar_t takes the wmem* paths; other element types are unchanged.
Because the acceleration is delivered by the platform libc, this uplifts every
architecture rather than one target. Measured on NVIDIA Vera (aarch64),
worst-case full-scan medians on stock glibc -- i.e. the algorithm change alone,
no special libc -- improve as follows:
basic_string::find(substr) 256 B 4.4x, 1 KB 4.2x, 16 KB 4.3x
basic_string::rfind(substr) 2.8x - 3.5x
basic_string::rfind(char) 2.3x - 2.4x
find_first_of family (bitmap) 1.9x - 3.8x
std::search 2.3x - 2.6x
std::find_end 2.2x - 2.6x
std::find_first_of 4.4x (16 B) - 8.3x (16 KB)
The same shape reproduces on x86-64 Granite Rapids (Xeon 6980P) and AMD Turin
96c (EPYC 9655P, Zen 5): find(substr) 2.6x - 3.6x, find_first_of 1.6x - 3.8x,
std::find_first_of up to 2.5x. The memchr first-byte filter keeps a
rare/absent-first-byte find at parity with the scalar path on all three
architectures (it was ~5-10x slower without the filter). A libc tuned for the
target compounds this further: with a Vera-tuned libc, basic_string::find
reaches
14x at 16 KB and std::search 7.8x, and wchar_t wstring::find runs ~1.3x - 1.4x
faster than glibc once wmemchr/wmemcmp are tuned, all with no header change.
New performance tests under testsuite/performance exercise the accelerated
routines on worst-case scans (a random 16-symbol-alphabet haystack with an
absent needle) so a stock-vs-patched libstdc++ comparison shows the effect: on
NVIDIA Vera, basic_string::find ~4x, find_first_of family ~3x, std::search ~2x,
std::find_end ~2x, std::find_first_of ~13x, with the rare-first-byte find held
at parity.
libstdc++-v3/ChangeLog:
* include/bits/basic_string.tcc: Include <string.h>.
(basic_string::find(const _CharT*, size_type, size_type)): Route the
1-byte specialization through a memchr first-byte filter and memmem,
with a small-size scalar fallback.
(basic_string::rfind(const _CharT*, size_type, size_type)): Route
through memrchr and __builtin_memcmp.
(basic_string::rfind(_CharT, size_type)): Route through memrchr.
(basic_string::find_first_of(const _CharT*, size_type, size_type))
(basic_string::find_first_not_of(const _CharT*, size_type, size_type))
(basic_string::find_last_of(const _CharT*, size_type, size_type))
(basic_string::find_last_not_of(const _CharT*, size_type, size_type)):
Scan with a 256-bit byte-set bitmap, after a memchr prefix so early
matches (the common tokenizing case) stay at parity with the scalar
path.
* include/bits/string_view.tcc: Likewise for basic_string_view, and
include <string.h>.
* include/bits/stl_algo.h: Include <string.h> and <wchar.h>.
(std::search): Route the contiguous default-comparator case through a
memchr filter + memmem (1-byte) or wmemchr + wmemcmp (wchar_t), with a
small-size scalar fallback.
(std::find_end): Likewise, keeping the last match.
(std::find_first_of): Scan with a 256-bit byte-set bitmap, after a
cheap scalar prefix so early matches stay at parity with the scalar
path.
* include/bits/ranges_util.h: Include <string.h> and <wchar.h>.
(ranges::__search_fn::operator()): As for std::search.
* include/bits/ranges_algo.h: Include <string.h> and <wchar.h>.
(ranges::__find_end_fn::operator()): As for std::find_end.
(ranges::__find_first_of_fn::operator()): As for std::find_first_of.
* testsuite/performance/21_strings/find_worst_case.cc: New test.
* testsuite/performance/21_strings/find_first_of.cc: New test.
* testsuite/performance/25_algorithms/search.cc: New test.
* testsuite/performance/25_algorithms/find_first_of.cc: New test.
* testsuite/performance/25_algorithms/find_end.cc: New test.
0001-libstdc-route-string-algorithm-search-through-libc-m.patch
Description: 0001-libstdc-route-string-algorithm-search-through-libc-m.patch
