On Thu, 30 Jul 2026, 04:59 Andrea Pinski, <[email protected]> wrote:
> On Wed, Jul 29, 2026 at 6:19 PM Sebastian Pop <[email protected]> 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. > > > Note libstdc++ patches should be CC'ed to libstdc++@ also. Some of the > maintainers of libstdc++ are not subscribed to the main gcc-patches@ > list. > > Thanks, > Andrea > > > > > 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. > This is an ABI break. > (_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 <[email protected]> > > >
