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

[Patrick Palka]

On Mon, 20 Jul 2026, Patrick Palka wrote:

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

... and hopefully we can get rid of _M_dfs_next as mentioned in the 2/4
patch thread.


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