PATCH] libstdc++: skip regex_search positions that cannot start a match

[Jonathan Wakely]

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

Attaching patches as application/octet-stream makes it hard to review
them.  A patch is not binary data, it's plain text.  I can't reply to
the patch inline, because my mail client (mutt) shows this as the
patch when I reply to your email: