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