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.
Benchmarks improvements compared to GCC previous patch in series:
at -O2:
email: +4.7%
URI: +5.1%
IPv4 -1.1%
at -O3:
email: +4.5%,
URI: +4.1%
IPv4: -0.2%
And finally gets us better than GCC 15.
The last review had some concern about the complexity. I'd note that if
I outline the code to a helper, it does become easier to read as it
replaces the nested conditionals with just early outs.
I can do that if preferred?
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
b1a87da5afee4d854708207906d119f4b5b151b4..e0835049de7e7790b7065f035b732b23d4d4d52d
100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -400,7 +400,24 @@ namespace __detail
_M_current);
else
_M_frames.emplace_back(_S_fopcode_next, __state._M_next);
- return _M_rep_once_more(__match_mode, __i);
+ _StateIdT __next = _M_rep_once_more(__match_mode, __i);
+ if constexpr (__search_mode == _Search_mode::_Dfs)
+ 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 // Non-greedy mode
{
--
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index b1a87da5afee4d854708207906d119f4b5b151b4..e0835049de7e7790b7065f035b732b23d4d4d52d 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -400,7 +400,24 @@ namespace __detail
_M_current);
else
_M_frames.emplace_back(_S_fopcode_next, __state._M_next);
- return _M_rep_once_more(__match_mode, __i);
+ _StateIdT __next = _M_rep_once_more(__match_mode, __i);
+ if constexpr (__search_mode == _Search_mode::_Dfs)
+ 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 // Non-greedy mode
{
