<div dir="auto"><div><br><br><div class="gmail_quote gmail_quote_container"><div dir="ltr" class="gmail_attr">On Thu, 30 Jul 2026, 04:59 Andrea Pinski, <<a href="mailto:andrew.pinski@oss.qualcomm.com">andrew.pinski@oss.qualcomm.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Wed, Jul 29, 2026 at 6:19 PM Sebastian Pop <<a href="mailto:spop@nvidia.com" target="_blank" rel="noreferrer">spop@nvidia.com</a>> wrote:<br>
><br>
> std::regex_search advances one position at a time and runs a full NFA match<br>
> attempt at every position, which is O(n*m) on a text with few matches. For most<br>
> patterns a match can only begin with a byte from a small, statically known set:<br>
> the "first-character set", i.e. the bytes accepted by the _S_opcode_match states<br>
> in the epsilon-closure of the NFA start state. This patch computes that set once<br>
> per regex and, before each match attempt, skips over input positions whose byte<br>
> is not in it:<br>
><br>
> * a single required byte -> memchr (the platform libc scans it vectorized);<br>
> * a small byte set -> a 256-bit byte-set bitmap scan.<br>
><br>
> The set is computed at the end of NFA construction, while the automaton is still<br>
> single-threaded, and cached in _NFA_base; it is then immutable, so a const<br>
> std::regex stays safe to share across threads, and repeated searches<br>
> (regex_iterator / regex_token_iterator) pay no per-call setup.<br>
><br>
> The optimization is disabled -- falling back to the exact stock scan -- whenever<br>
> it could change behaviour: when the start-closure can reach an empty match<br>
> (_S_opcode_accept), an anchor (^, $, \b, \B), a lookahead, or a backref; for<br>
> non-1-byte character types; for non-contiguous iterators; and under<br>
> match_continuous. It is guarded on __cpp_if_constexpr, so pre-C++17 translation<br>
> units keep the scalar behaviour byte-for-byte. Because a non-empty,<br>
> non-anchored match must begin with a byte from the set, skipping the others<br>
> finds exactly the same matches: the 28_regex conformance suite is unchanged, and<br>
> a dedicated harness confirms byte-identical match positions, prefixes and<br>
> regex_replace output across anchors, empty/optional matches, alternation,<br>
> character classes, case-insensitivity, multiline, backrefs, lookahead, embedded<br>
> NUL bytes and the match flags.<br>
><br>
> Because the scan is delivered by the platform libc (memchr) or a portable<br>
> bitmap, this uplifts every architecture. Measured on NVIDIA Vera (aarch64)<br>
> with a stock glibc, via testsuite/performance/28_regex/first_char_skip.cc (a<br>
> 32 MiB corpus with sparse matches): a literal-prefix pattern (Z[a-z]+, single<br>
> required byte) improves ~88x, and a digit-class IPv4 pattern (bitmap skip)<br>
> ~37x. On the mariomka regex benchmark corpus the IPv4 pattern improves ~35x and<br>
> dense first-character sets (URI/email word characters) ~1.1x, with match counts<br>
> unchanged. A libc tuned for the target compounds the memchr case further.<br>
<br>
<br>
Note libstdc++ patches should be CC'ed to libstdc++@ also. Some of the<br>
maintainers of libstdc++ are not subscribed to the main gcc-patches@<br>
list.<br>
<br>
Thanks,<br>
Andrea<br>
<br>
><br>
> libstdc++-v3/ChangeLog:<br>
><br>
> * include/bits/regex_automaton.h (_NFA_base): Add first-character-set<br>
> cache fields _M_first_char_state, _M_first_char_count, _M_first_char<br>
> and _M_first_char_set.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">This is an ABI break.</div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote gmail_quote_container"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
> (_NFA::_M_compute_first_char_set): New member function; compute the set<br>
> of bytes a match may begin with as the epsilon-closure of the start<br>
> state, stopping at match states, and cache it; mark it unusable on empty<br>
> match, anchor, lookahead, backref or non-1-byte character type.<br>
> * include/bits/regex_compiler.tcc (_Compiler::_Compiler): Call<br>
> _M_compute_first_char_set once the NFA is fully built.<br>
> * include/bits/regex_executor.tcc (_Executor::_M_search): When the<br>
> cached set is usable and the input is contiguous 1-byte, skip positions<br>
> that cannot start a match with memchr (single byte) or a byte-set<br>
> bitmap before each match attempt.<br>
> * testsuite/performance/28_regex/first_char_skip.cc: New test.<br>
><br>
> Signed-off-by: Sebastian Pop <<a href="mailto:spop@nvidia.com" target="_blank" rel="noreferrer">spop@nvidia.com</a>><br>
><br>
</blockquote></div></div></div>