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 <[email protected]>
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.
