On Thu, 16 Jul 2026, Tamar Christina wrote:
> 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%
These are the cumulative improvements right? The previous patch had:
email: 55.5%
URI: 55.2%
IPv4: 68.0%
So the marginal improvement of this patch is around 2% for email / URI?
Not sure the increased complexity and _M_handle_match logic duplication
is worth it.
>
> 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
> {
>
>
> --
>
