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

[Jonathan Wakely]

On Thu, 30 Jul 2026 at 10:54 +0100, Jonathan Wakely wrote:
>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:

i.e. nothing.

So copying and pasting your patch into a new mail and manually adding
quote characters ...

>--- a/libstdc++-v3/include/bits/regex_automaton.h
>+++ b/libstdc++-v3/include/bits/regex_automaton.h
>@@ -217,6 +217,18 @@ namespace __detail
>     _StateIdT                 _M_start_state;
>     size_t                    _M_subexpr_count;
>     bool                      _M_has_backref;
>+
>+#if __cpp_if_constexpr
>+    // First-character-set cache, computed once when the NFA is built
>+    // (see _NFA::_M_compute_first_char_set) and thereafter immutable, so a const
>+    // std::regex remains safe to share across threads.  Reused by every
>+    // regex_search over this automaton.  _M_first_char_state: 0 = uncomputed,
>+    // 1 = usable, 2 = not usable.
>+    unsigned char             _M_first_char_state = 0;
>+    int                       _M_first_char_count = 0;
>+    int                       _M_first_char = -1;
>+    unsigned long             _M_first_char_set[4] = {0, 0, 0, 0};
>+#endif
>   };

There are a few of problems with this.

Firstly, you're adding new members which would give GCC 17 std::regex
a different ABI from GCC 16. Secondly, you're only adding them for
C++17 and later which would give std::regex a different ABI when
compiled with -std=gnu++17 or -std=gnu++11. Both these problems are
absolute showstoppers and the patch is instantly rejected.

Thirdly, there is no reason whatsoever to gate these on support for
if-constexpr, because you can use if-constexpr in C++11. See numerous
examples in the libstdc++ code where -Wc++17-extensions is disabled
using diagnostic pragmas. The std::regex code already makes use of it.

Please see https://gcc.gnu.org/PR126337 for a hypothetical solution to
the ABI breaks.

>--- /dev/null
>+++ b/libstdc++-v3/testsuite/performance/28_regex/first_char_skip.cc
>@@ -0,0 +1,103 @@
>+// Copyright The GNU Toolchain Authors.
>+//

I'm going to guess from this that you used an LLM to create this test
(maybe the entire patch?)i because LLMs don't seem to have
https://gcc.gnu.org/onlinedocs/libstdc++/manual/test.html#test.new_tests
in their training set yet. Please read what it says there about
copyright and licence notices in new tests.

If the patch was assisted by an LLM then please see the new policy
regarding such contributions: https://gcc.gnu.org/ai-policy.html

Also the test will fail when run as C++98 because it's missing an
effective target.