diff mbox series

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

Message ID aljrFphQzm3wuq7k@arm.com
State New
Headers
Series [1/4,libstdc++] : Templatize regex executor traversal mode [PR126274] |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed
linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap success Build passed

Commit Message

Tamar Christina July 16, 2026, 2:30 p.m. UTC 
  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%

  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.

---


--

Comments

Patrick Palka July 21, 2026, 3:27 a.m. UTC | #1 
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
>  	    {
> 
> 
> -- 
>
Patrick Palka July 21, 2026, 3:31 a.m. UTC | #2 
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
> >  	    {
> > 
> > 
> > -- 
> > 
>
diff mbox series

Patch

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
 	    {