Optimize the common DFS NFA shape repeat -> match -> repeat, which is produced
by repeated character classes such as [\w]+, [^\s?#]+, and #+.
Since the second patch the DFS continuation already avoids pushing a separate
_S_fopcode_next frame for many states. This patch adds a small improvement
for greedy repeats.
After creating the same fallback and repeat bookkeeping frames as before, if
the repeated body is a single match state that returns to the repeat state,
consume that match state immediately and continue at the repeat.
Backtracking behavior is unchanged. _M_rep_once_more still creates the
restore/decrement frames, and the repeat exit fallback is still saved before
trying the body. If the body match fails, the helper returns
_S_invalid_state_id so the normal frame loop restores repeat state and tries
pending fallbacks.
Benchmark improvements compared to:
GCC 16:
email: 57.4%
URI: 57.2%
IPv4: 68.0%
GCC 15:
email: 6.7%
URI: 3.8%
IPv4: 23.2%
Bootstrapped Regtested on aarch64-none-linux-gnu,
arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
-m32, -m64 and no issues.
Ok for master?
Thanks,
Tamar
libstdc++-v3/ChangeLog:
PR libstdc++/126274
* include/bits/regex_executor.tcc (_M_dfs_next): Inline consume matches
on _S_opcode_repeat.
---
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc
b/libstdc++-v3/include/bits/regex_executor.tcc
index
3a3bad8ecac485d452970c0aa26e6db34cabd1e5..558d29feaef1eecd9ec13ba395a53f3ede990178
100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -796,7 +796,28 @@ namespace __detail
{
_M_frames.emplace_back(_S_fopcode_fallback_next,
__state._M_next, _M_current);
- return _M_rep_once_more(__match_mode, __i);
+
+ // Consume the match state here so the straight-line loop avoids
+ // one extra _M_dfs_next dispatch per repeated character. The
+ // repeat bookkeeping and fallback frames are still produced by
+ // _M_rep_once_more, so backtracking order is unchanged.
+ _StateIdT __next = _M_rep_once_more(__match_mode, __i);
+ if (__next != _S_invalid_state_id)
+ {
+ const auto& __alt_state = _M_nfa[__next];
+ if (__alt_state._M_opcode() == _S_opcode_match
+ && __alt_state._M_next == __i)
+ {
+ if (_M_current != _M_end
+ && __alt_state._M_matches(*_M_current))
+ {
+ ++_M_current;
+ return __i;
+ }
+ return _S_invalid_state_id;
+ }
+ }
+ return __next;
}
else
{
--
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 3a3bad8ecac485d452970c0aa26e6db34cabd1e5..558d29feaef1eecd9ec13ba395a53f3ede990178 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -796,7 +796,28 @@ namespace __detail
{
_M_frames.emplace_back(_S_fopcode_fallback_next,
__state._M_next, _M_current);
- return _M_rep_once_more(__match_mode, __i);
+
+ // Consume the match state here so the straight-line loop avoids
+ // one extra _M_dfs_next dispatch per repeated character. The
+ // repeat bookkeeping and fallback frames are still produced by
+ // _M_rep_once_more, so backtracking order is unchanged.
+ _StateIdT __next = _M_rep_once_more(__match_mode, __i);
+ if (__next != _S_invalid_state_id)
+ {
+ const auto& __alt_state = _M_nfa[__next];
+ if (__alt_state._M_opcode() == _S_opcode_match
+ && __alt_state._M_next == __i)
+ {
+ if (_M_current != _M_end
+ && __alt_state._M_matches(*_M_current))
+ {
+ ++_M_current;
+ return __i;
+ }
+ return _S_invalid_state_id;
+ }
+ }
+ return __next;
}
else
{
