[patch 4/4][libstdc++]: Inline simple regex repeating matches in DFS [PR126274]

[Patrick Palka]

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
>  	    {
> 
> 
> -- 
>