[2/4,libstdc++] : Continue with regex DFS traversals without next frames [PR126274]

  The change in r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20 changed
the recursive implementation with an iterative one using an explicit heap.

However one benefit of the previous implementation is that the frame did
not have to be saved and popped when the match is supposed to continue.

This means that on hot paths we now have additional memory accesses and
need additional instructions to calculate the memref addresses.

For DFS matching this is clearly suboptimal since when _M_rep_once_more
then we push and pop the same state but there is enough other acceses
in between the push and pop that we get a lot of cache misses.

This patch keeps the new frame based executor, however adds a fast path
for _M_rep_once_more cases.  This is done by having _M_rep_once_more
return the state as return value, and have the caller decide what to
do with it.  BFS does not change and immediately stores the frame.

For DFS we try to consume the state immediately until we're told to
stop.

The patch also reserves some frames in the initial vector to avoid having
resizes on the hot path.  To avoid large RSS before matching even starts
we provide a cap to the initial reservations.

Benchmark improvements vs GCC 16:
  email: 53.7%
  URI:   52.8%
  IPv4:  44.4%

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.h (_Executor): Reserve frame space.
	(_M_rep_once_more): Return state.
	(_M_dfs_next): New.
	* include/bits/regex_executor.tcc (_M_rep_once_more): Return state.
	(_M_dfs_next): New.
	(_M_dfs): Traverse states iteratively for _S_fopcode_next,
	_S_fopcode_fallback_next, _S_fopcode_fallback_rep_once_more
	and _S_fopcode_rep_once_more.

---


--
  

On Thu, 16 Jul 2026 at 15:31, Tamar Christina <tamar.christina@arm.com> wrote:
>
> The change in r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20 changed
> the recursive implementation with an iterative one using an explicit heap.
>
> However one benefit of the previous implementation is that the frame did
> not have to be saved and popped when the match is supposed to continue.
>
> This means that on hot paths we now have additional memory accesses and
> need additional instructions to calculate the memref addresses.
>
> For DFS matching this is clearly suboptimal since when _M_rep_once_more
> then we push and pop the same state but there is enough other acceses
> in between the push and pop that we get a lot of cache misses.
>
> This patch keeps the new frame based executor, however adds a fast path
> for _M_rep_once_more cases.  This is done by having _M_rep_once_more
> return the state as return value, and have the caller decide what to
> do with it.  BFS does not change and immediately stores the frame.
>
> For DFS we try to consume the state immediately until we're told to
> stop.
>
> The patch also reserves some frames in the initial vector to avoid having
> resizes on the hot path.  To avoid large RSS before matching even starts
> we provide a cap to the initial reservations.
>
> Benchmark improvements vs GCC 16:
>   email: 53.7%
>   URI:   52.8%
>   IPv4:  44.4%
>
> Bootstrapped Regtested on aarch64-none-linux-gnu,
> arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
> -m32, -m64 and no issues.
>
> Ok for master?

Some minor comments below while Patrick reviews this series and we
confirm the benefits at -O2 ...

>
> Thanks,
> Tamar
>
> libstdc++-v3/ChangeLog:
>
>         PR libstdc++/126274
>         * include/bits/regex_executor.h (_Executor): Reserve frame space.
>         (_M_rep_once_more): Return state.
>         (_M_dfs_next): New.
>         * include/bits/regex_executor.tcc (_M_rep_once_more): Return state.
>         (_M_dfs_next): New.
>         (_M_dfs): Traverse states iteratively for _S_fopcode_next,
>         _S_fopcode_fallback_next, _S_fopcode_fallback_rep_once_more
>         and _S_fopcode_rep_once_more.
>
> ---
> diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
> index f6e55f2f4aaa8fb3fa8d963b04d5bcf0b3b191d3..0a63b9b83789a700de63081ee61a7857028548e0 100644
> --- a/libstdc++-v3/include/bits/regex_executor.h
> +++ b/libstdc++-v3/include/bits/regex_executor.h
> @@ -87,6 +87,11 @@ namespace __detail
>         using namespace regex_constants;
>         if (__flags & match_prev_avail) // ignore not_bol and not_bow
>           _M_flags &= ~(match_not_bol | match_not_bow);
> +       // Reserve NFA sized frames up front to prevent having to constantly
> +       // reallocate frames.  To avoid an explosion in state with large regexp
> +       // before any matching is every done limit the reservation to 256.

"is ever done" ?

> +       // This should cover a large class of regexp.
> +       _M_frames.reserve(std::min<size_t>(_M_nfa.size(), 256));

Was 256 determined empirically? It seems quite high to me.
The geometric growth policy of std::vector should mean it doesn't
_constantly_ reallocate frames. We'll reallocate frequently while the
number of frames is small, but as the size increases we'll end up
allocating larger blocks and need to reallocate less often.


>         if (_M_search_mode == _Search_mode::_BFS)
>           _M_visited_states = new bool[_M_nfa.size()];
>        }
> @@ -114,7 +119,7 @@ namespace __detail
>        _M_search();
>
>      private:
> -      void
> +      _StateIdT
>        _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
>
>        template<_Search_mode __search_mode>
> @@ -157,6 +162,9 @@ namespace __detail
>         void
>        _M_node(_Match_mode, _StateIdT);
>
> +      _StateIdT
> +      _M_dfs_next(_Match_mode, _StateIdT);
> +
>        template<_Search_mode __search_mode>
>         void
>        _M_dfs(_Match_mode __match_mode, _StateIdT __start);
> diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
> index 86f6c6240853d673f47099a5fd15fe84fc99316e..bf0594912688e0014a5928b6c6d600af6f80b31a 100644
> --- a/libstdc++-v3/include/bits/regex_executor.tcc
> +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> @@ -250,8 +250,14 @@ namespace __detail
>    // infinite loop by refusing to continue when it's already been
>    // visited more than twice. It's `twice` instead of `once` because
>    // we need to spare one more time for potential group capture.
> +  //
> +  // If the node cannot be re-entered anymore from the current state then return
> +  // _S_invalid_state_id otherwise return the current state without going
> +  // through a vector, allowing the caller to decide what to do with the state
> +  // This is beneficial for DFS since DFS can continue with the next state
> +  // immediately
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> -    void _Executor<_BiIter, _Alloc, _TraitsT>::
> +    _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_rep_once_more(_Match_mode, _StateIdT __i)
>      {
>        const auto& __state = _M_nfa[__i];
> @@ -263,7 +269,7 @@ namespace __detail
>           _M_frames.back()._M_count = __rep_count.second;
>           __rep_count.first = _M_current;
>           __rep_count.second = 1;
> -         _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> +         return __state._M_alt;
>         }
>        else
>         {
> @@ -271,9 +277,10 @@ namespace __detail
>             {
>               __rep_count.second++;
>               _M_frames.emplace_back(_S_fopcode_decrement_rep_count, __i);
> -             _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> +             return __state._M_alt;
>             }
>         }
> +      return _S_invalid_state_id;
>      }
>
>    // _M_alt branch is "match once more", while _M_next is "get me out
> @@ -611,6 +618,121 @@ namespace __detail
>         }
>      }
>
> +
> +  // Execute one DFS state in a form optimized for immediate progress.
> +  //
> +  // Returning a state id means "continue with this successor now".  Returning
> +  // _S_invalid_state_id means the helper either failed this path or delegated
> +  // to the generic frame-based handler, so the outer DFS loop should pop the
> +  // next pending frame.
> +  //
> +  // The helper is intentionally small and it's intended to cover states that
> +  // are common in scanning regexes and have an obvious preferred successor.
> +  // For example, in "[\w]+://" most successful work is: enter repeat, consume
> +  // a match state, repeat, then try the literal ':' path.
> +  // The key is to avoid a push/pop for each immediate _S_fopcode_next.   When
> +  // it sees a state whose behavior that's not an obvious direct match it calls
> +  // _M_node<_Search_mode::_DFS> and resumes the normal flow.
> +  template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +#ifdef __OPTIMIZE__
> +    [[__gnu__::__always_inline__]]
> +#endif
> +    inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> +    _M_dfs_next(_Match_mode __match_mode, _StateIdT __i)
> +    {
> +      const auto& __state = _M_nfa[__i];
> +
> +      switch (__state._M_opcode())
> +       {
> +       case _S_opcode_subexpr_begin:
> +         // Capture group 0 is the whole match.  Without backreferences no
> +         // later state can observe the old group-0 boundary during
> +         // backtracking, so continue directly with the next state.
> +         //
> +         // Example: for regex_search with "[0-9]+", only the final group-0
> +         // boundaries are reported; there is no backref that can read
> +         // an intermediate group-0 value.
> +         if (!_M_nfa._M_has_backref && __state._M_subexpr == 0)
> +           {
> +             _M_cur_results[0].first = _M_current;
> +             return __state._M_next;
> +           }
> +         break;
> +
> +       case _S_opcode_subexpr_end:
> +         // Same group-0 shortcut for the end boundary.  For other capture
> +         // groups we delegate to _M_node so their old values are restored
> +         // correctly when a later alternative fails.  For example, in
> +         // "(a|ab)c" the capture for group 1 may need to roll back from "a"
> +         // to try "ab" so the shortcut cannot be used.
> +         if (!_M_nfa._M_has_backref && __state._M_subexpr == 0)
> +           {
> +             auto& __res = _M_cur_results[0];
> +             __res.second = _M_current;
> +             __res.matched = true;
> +             return __state._M_next;
> +           }
> +         break;
> +
> +       case _S_opcode_match:
> +         // Consume one character and return the next state instead of pushing
> +         // _S_fopcode_next.  On a long input matched by e.g. "#+", this
> +         // removes one frame round trip per consumed '#'.
> +         if (_M_current != _M_end && __state._M_matches(*_M_current))
> +           {
> +             ++_M_current;
> +             return __state._M_next;
> +           }
> +         return _S_invalid_state_id;
> +
> +       case _S_opcode_accept:
> +         // Accept needs to store the frame, so call the generic handler and
> +         // stop any linear consumptions in the optimized paths.
> +         _M_handle_accept<_Search_mode::_DFS>(__match_mode, __i);
> +         return _S_invalid_state_id;
> +
> +       case _S_opcode_repeat:
> +         // For greedy repeats, DFS should try the body first and remember the
> +         // exit as a fallback.  Example: for "[0-9]+" at "123x", keep the
> +         // "exit repeat" state on the stack, but immediately continue into the
> +         // digit-matching body.  When the body later fails at 'x', the
> +         // fallback accepts the repeat at the position after '3'.
> +         if (!__state._M_neg)
> +           {
> +             _M_frames.emplace_back(_S_fopcode_fallback_next,
> +                                    __state._M_next, _M_current);
> +             return _M_rep_once_more(__match_mode, __i);
> +           }
> +         else
> +           {
> +             _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> +                                    __i, _M_current);
> +             return __state._M_next;
> +           }
> +
> +       case _S_opcode_alternative:
> +         // ECMAScript alternatives are ordered.  Try _M_alt first and keep _M_next
> +         // as a fallback, e.g. "foo|fo" should prefer "foo" if it succeeds.
> +         // If the preferred arm fails, the fallback restores _M_current and
> +         // tries the other arm.  POSIX alternatives require longest-match
> +         // merging, so they stay on the generic path.
> +         if (_M_nfa._M_flags & regex_constants::ECMAScript)
> +           {
> +             _M_frames.emplace_back(_S_fopcode_fallback_next,
> +                                    __state._M_next, _M_current);
> +             return __state._M_alt;
> +           }
> +         break;
> +
> +       default:
> +         break;
> +       }
> +
> +      // Any opcode not handled above still uses the existing mechanism
> +      _M_node<_Search_mode::_DFS>(__match_mode, __i);
> +      return _S_invalid_state_id;
> +    }
> +
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
>    template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
> @@ -632,7 +754,15 @@ namespace __detail
>                 _M_current = __frame._M_pos;
>               [[__fallthrough__]];
>             case _S_fopcode_next:
> -             _M_node<__search_mode>(__match_mode, __frame._M_state_id);
> +             if constexpr (__search_mode == _Search_mode::_DFS)
> +               // Follow immediate successors without re-entering the frame
> +               // loop untill we fail.  This avoids the needless state save and

"until"

> +               // restore through memory.
> +               for (_StateIdT __next = __frame._M_state_id;
> +                    __next != _S_invalid_state_id;)
> +                 __next = _M_dfs_next(__match_mode, __next);
> +             else
> +               _M_node<_Search_mode::_BFS>(__match_mode, __frame._M_state_id);
>               break;
>
>             case _S_fopcode_fallback_rep_once_more:
> @@ -642,7 +772,21 @@ namespace __detail
>                 _M_current = __frame._M_pos;
>               [[__fallthrough__]];
>             case _S_fopcode_rep_once_more:
> -             _M_rep_once_more(__match_mode, __frame._M_state_id);
> +             {
> +               _StateIdT __next
> +                 = _M_rep_once_more(__match_mode, __frame._M_state_id);
> +               if constexpr (__search_mode == _Search_mode::_DFS)
> +                 // _M_rep_once_more returned the repeated body's start state.
> +                 // Continue directly in DFS; BFS must materialize the state as
> +                 // a queue/frame item because it advances by input position
> +                 // rather than by backtracking order.  Splittig this in a

"Splitting"

> +                 // specialized path preserves the behavior for both but has
> +                 // DFS avoids the intermediate allocations.

I think this should be "avoid" not "avoids"?
Or maybe "but for DFS it avoids the ..."

> +                 for (; __next != _S_invalid_state_id;)
> +                   __next = _M_dfs_next(__match_mode, __next);
> +               else if (__next != _S_invalid_state_id)
> +                 _M_frames.emplace_back(_S_fopcode_next, __next);
> +             }
>               break;
>
>             case _S_fopcode_posix_alternative:
>
>
> --
  

On Thu, 16 Jul 2026, Tamar Christina wrote:

> The change in r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20 changed
> the recursive implementation with an iterative one using an explicit heap.
> 
> However one benefit of the previous implementation is that the frame did
> not have to be saved and popped when the match is supposed to continue.
> 
> This means that on hot paths we now have additional memory accesses and
> need additional instructions to calculate the memref addresses.
> 
> For DFS matching this is clearly suboptimal since when _M_rep_once_more
> then we push and pop the same state but there is enough other acceses
> in between the push and pop that we get a lot of cache misses.
> 
> This patch keeps the new frame based executor, however adds a fast path
> for _M_rep_once_more cases.  This is done by having _M_rep_once_more
> return the state as return value, and have the caller decide what to
> do with it.  BFS does not change and immediately stores the frame.
> 
> For DFS we try to consume the state immediately until we're told to
> stop.
> 
> The patch also reserves some frames in the initial vector to avoid having
> resizes on the hot path.  To avoid large RSS before matching even starts
> we provide a cap to the initial reservations.
> 
> Benchmark improvements vs GCC 16:
>   email: 53.7%
>   URI:   52.8%
>   IPv4:  44.4%
> 
> 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.h (_Executor): Reserve frame space.
> 	(_M_rep_once_more): Return state.
> 	(_M_dfs_next): New.
> 	* include/bits/regex_executor.tcc (_M_rep_once_more): Return state.
> 	(_M_dfs_next): New.
> 	(_M_dfs): Traverse states iteratively for _S_fopcode_next,
> 	_S_fopcode_fallback_next, _S_fopcode_fallback_rep_once_more
> 	and _S_fopcode_rep_once_more.
> 
> ---
> diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
> index f6e55f2f4aaa8fb3fa8d963b04d5bcf0b3b191d3..0a63b9b83789a700de63081ee61a7857028548e0 100644
> --- a/libstdc++-v3/include/bits/regex_executor.h
> +++ b/libstdc++-v3/include/bits/regex_executor.h
> @@ -87,6 +87,11 @@ namespace __detail
>  	using namespace regex_constants;
>  	if (__flags & match_prev_avail) // ignore not_bol and not_bow
>  	  _M_flags &= ~(match_not_bol | match_not_bow);
> +	// Reserve NFA sized frames up front to prevent having to constantly
> +	// reallocate frames.  To avoid an explosion in state with large regexp
> +	// before any matching is every done limit the reservation to 256.
> +	// This should cover a large class of regexp.
> +	_M_frames.reserve(std::min<size_t>(_M_nfa.size(), 256));
>  	if (_M_search_mode == _Search_mode::_BFS)
>  	  _M_visited_states = new bool[_M_nfa.size()];
>        }
> @@ -114,7 +119,7 @@ namespace __detail
>        _M_search();
>  
>      private:
> -      void
> +      _StateIdT
>        _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
>  
>        template<_Search_mode __search_mode>
> @@ -157,6 +162,9 @@ namespace __detail
>  	void
>        _M_node(_Match_mode, _StateIdT);
>  
> +      _StateIdT
> +      _M_dfs_next(_Match_mode, _StateIdT);
> +
>        template<_Search_mode __search_mode>
>  	void
>        _M_dfs(_Match_mode __match_mode, _StateIdT __start);
> diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
> index 86f6c6240853d673f47099a5fd15fe84fc99316e..bf0594912688e0014a5928b6c6d600af6f80b31a 100644
> --- a/libstdc++-v3/include/bits/regex_executor.tcc
> +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> @@ -250,8 +250,14 @@ namespace __detail
>    // infinite loop by refusing to continue when it's already been
>    // visited more than twice. It's `twice` instead of `once` because
>    // we need to spare one more time for potential group capture.
> +  //
> +  // If the node cannot be re-entered anymore from the current state then return
> +  // _S_invalid_state_id otherwise return the current state without going
> +  // through a vector, allowing the caller to decide what to do with the state
> +  // This is beneficial for DFS since DFS can continue with the next state
> +  // immediately
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> -    void _Executor<_BiIter, _Alloc, _TraitsT>::
> +    _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_rep_once_more(_Match_mode, _StateIdT __i)
>      {
>        const auto& __state = _M_nfa[__i];
> @@ -263,7 +269,7 @@ namespace __detail
>  	  _M_frames.back()._M_count = __rep_count.second;
>  	  __rep_count.first = _M_current;
>  	  __rep_count.second = 1;
> -	  _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> +	  return __state._M_alt;
>  	}
>        else
>  	{
> @@ -271,9 +277,10 @@ namespace __detail
>  	    {
>  	      __rep_count.second++;
>  	      _M_frames.emplace_back(_S_fopcode_decrement_rep_count, __i);
> -	      _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> +	      return __state._M_alt;
>  	    }
>  	}
> +      return _S_invalid_state_id;
>      }
>  
>    // _M_alt branch is "match once more", while _M_next is "get me out
> @@ -611,6 +618,121 @@ namespace __detail
>  	}
>      }
>  
> +
> +  // Execute one DFS state in a form optimized for immediate progress.
> +  //
> +  // Returning a state id means "continue with this successor now".  Returning
> +  // _S_invalid_state_id means the helper either failed this path or delegated
> +  // to the generic frame-based handler, so the outer DFS loop should pop the
> +  // next pending frame.
> +  //
> +  // The helper is intentionally small and it's intended to cover states that
> +  // are common in scanning regexes and have an obvious preferred successor.
> +  // For example, in "[\w]+://" most successful work is: enter repeat, consume
> +  // a match state, repeat, then try the literal ':' path.
> +  // The key is to avoid a push/pop for each immediate _S_fopcode_next.   When
> +  // it sees a state whose behavior that's not an obvious direct match it calls
> +  // _M_node<_Search_mode::_DFS> and resumes the normal flow.

This helper seems to be just duplicating the logic of the existing
_M_handle_foo handlers.  Couldn't we just generally make _M_handle_foo
always return the next state rather than pushing a 'next' frame (when
possible, otherwise return _S_invalid_state_id, like this _M_dfs_next
does) and have a generic fast path near the top of the _M_dfs loop
that iteratively calls _M_node until _S_invalid_state_id is returned?

We could also get rid of the _S_fopcode_rep_once_more frame and have
_M_handle_repeat call _M_rep_once_more directly so that we can in turn
make _M_handle_repeat always return the 'next' state rather than pushing
another frame.

> +  template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +#ifdef __OPTIMIZE__
> +    [[__gnu__::__always_inline__]]
> +#endif
> +    inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> +    _M_dfs_next(_Match_mode __match_mode, _StateIdT __i)
> +    {
> +      const auto& __state = _M_nfa[__i];
> +
> +      switch (__state._M_opcode())
> +	{
> +	case _S_opcode_subexpr_begin:
> +	  // Capture group 0 is the whole match.  Without backreferences no
> +	  // later state can observe the old group-0 boundary during
> +	  // backtracking, so continue directly with the next state.
> +	  //
> +	  // Example: for regex_search with "[0-9]+", only the final group-0
> +	  // boundaries are reported; there is no backref that can read
> +	  // an intermediate group-0 value.
> +	  if (!_M_nfa._M_has_backref && __state._M_subexpr == 0)

This seems like an optimization that _M_handle_subexpr_begin/end could
also benefit from -- for capture group 0 we don't bother pushing a
restore_cur_results frame, IIUC?

> +	    {
> +	      _M_cur_results[0].first = _M_current;
> +	      return __state._M_next;
> +	    }
> +	  break;
> +
> +	case _S_opcode_subexpr_end:
> +	  // Same group-0 shortcut for the end boundary.  For other capture
> +	  // groups we delegate to _M_node so their old values are restored
> +	  // correctly when a later alternative fails.  For example, in
> +	  // "(a|ab)c" the capture for group 1 may need to roll back from "a"
> +	  // to try "ab" so the shortcut cannot be used.
> +	  if (!_M_nfa._M_has_backref && __state._M_subexpr == 0)
> +	    {
> +	      auto& __res = _M_cur_results[0];
> +	      __res.second = _M_current;
> +	      __res.matched = true;
> +	      return __state._M_next;
> +	    }
> +	  break;
> +
> +	case _S_opcode_match:
> +	  // Consume one character and return the next state instead of pushing
> +	  // _S_fopcode_next.  On a long input matched by e.g. "#+", this
> +	  // removes one frame round trip per consumed '#'.
> +	  if (_M_current != _M_end && __state._M_matches(*_M_current))
> +	    {
> +	      ++_M_current;
> +	      return __state._M_next;
> +	    }
> +	  return _S_invalid_state_id;
> +
> +	case _S_opcode_accept:
> +	  // Accept needs to store the frame, so call the generic handler and
> +	  // stop any linear consumptions in the optimized paths.
> +	  _M_handle_accept<_Search_mode::_DFS>(__match_mode, __i);
> +	  return _S_invalid_state_id;
> +
> +	case _S_opcode_repeat:
> +	  // For greedy repeats, DFS should try the body first and remember the
> +	  // exit as a fallback.  Example: for "[0-9]+" at "123x", keep the
> +	  // "exit repeat" state on the stack, but immediately continue into the
> +	  // digit-matching body.  When the body later fails at 'x', the
> +	  // fallback accepts the repeat at the position after '3'.
> +	  if (!__state._M_neg)
> +	    {
> +	      _M_frames.emplace_back(_S_fopcode_fallback_next,
> +				     __state._M_next, _M_current);
> +	      return _M_rep_once_more(__match_mode, __i);
> +	    }
> +	  else
> +	    {
> +	      _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> +				     __i, _M_current);
> +	      return __state._M_next;
> +	    }
> +
> +	case _S_opcode_alternative:
> +	  // ECMAScript alternatives are ordered.  Try _M_alt first and keep _M_next
> +	  // as a fallback, e.g. "foo|fo" should prefer "foo" if it succeeds.
> +	  // If the preferred arm fails, the fallback restores _M_current and
> +	  // tries the other arm.  POSIX alternatives require longest-match
> +	  // merging, so they stay on the generic path.
> +	  if (_M_nfa._M_flags & regex_constants::ECMAScript)
> +	    {
> +	      _M_frames.emplace_back(_S_fopcode_fallback_next,
> +				     __state._M_next, _M_current);
> +	      return __state._M_alt;
> +	    }
> +	  break;
> +
> +	default:
> +	  break;
> +	}
> +
> +      // Any opcode not handled above still uses the existing mechanism
> +      _M_node<_Search_mode::_DFS>(__match_mode, __i);
> +      return _S_invalid_state_id;
> +    }
> +
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
>    template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
> @@ -632,7 +754,15 @@ namespace __detail
>  		_M_current = __frame._M_pos;
>  	      [[__fallthrough__]];
>  	    case _S_fopcode_next:
> -	      _M_node<__search_mode>(__match_mode, __frame._M_state_id);
> +	      if constexpr (__search_mode == _Search_mode::_DFS)
> +		// Follow immediate successors without re-entering the frame
> +		// loop untill we fail.  This avoids the needless state save and
> +		// restore through memory.
> +		for (_StateIdT __next = __frame._M_state_id;
> +		     __next != _S_invalid_state_id;)
> +		  __next = _M_dfs_next(__match_mode, __next);
> +	      else
> +		_M_node<_Search_mode::_BFS>(__match_mode, __frame._M_state_id);
>  	      break;
>  
>  	    case _S_fopcode_fallback_rep_once_more:
> @@ -642,7 +772,21 @@ namespace __detail
>  		_M_current = __frame._M_pos;
>  	      [[__fallthrough__]];
>  	    case _S_fopcode_rep_once_more:
> -	      _M_rep_once_more(__match_mode, __frame._M_state_id);
> +	      {
> +		_StateIdT __next
> +		  = _M_rep_once_more(__match_mode, __frame._M_state_id);
> +		if constexpr (__search_mode == _Search_mode::_DFS)
> +		  // _M_rep_once_more returned the repeated body's start state.
> +		  // Continue directly in DFS; BFS must materialize the state as
> +		  // a queue/frame item because it advances by input position
> +		  // rather than by backtracking order.  Splittig this in a
> +		  // specialized path preserves the behavior for both but has
> +		  // DFS avoids the intermediate allocations.
> +		  for (; __next != _S_invalid_state_id;)
> +		    __next = _M_dfs_next(__match_mode, __next);
> +		else if (__next != _S_invalid_state_id)
> +		  _M_frames.emplace_back(_S_fopcode_next, __next);
> +	      }
>  	      break;
>  
>  	    case _S_fopcode_posix_alternative:
> 
> 
> -- 
>
  

> -----Original Message-----
> From: Jonathan Wakely <jwakely@redhat.com>
> Sent: 20 July 2026 17:06
> To: Tamar Christina <Tamar.Christina@arm.com>
> Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; libstdc++@gcc.gnu.org;
> tkaminsk@redhat.com; ppalka@redhat.com
> Subject: Re: [patch 2/4][libstdc++]: Continue with regex DFS traversals
> without next frames [PR126274]
> 
> On Thu, 16 Jul 2026 at 15:31, Tamar Christina <tamar.christina@arm.com>
> wrote:
> >
> > The change in r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20
> changed
> > the recursive implementation with an iterative one using an explicit heap.
> >
> > However one benefit of the previous implementation is that the frame did
> > not have to be saved and popped when the match is supposed to continue.
> >
> > This means that on hot paths we now have additional memory accesses and
> > need additional instructions to calculate the memref addresses.
> >
> > For DFS matching this is clearly suboptimal since when _M_rep_once_more
> > then we push and pop the same state but there is enough other acceses
> > in between the push and pop that we get a lot of cache misses.
> >
> > This patch keeps the new frame based executor, however adds a fast path
> > for _M_rep_once_more cases.  This is done by having _M_rep_once_more
> > return the state as return value, and have the caller decide what to
> > do with it.  BFS does not change and immediately stores the frame.
> >
> > For DFS we try to consume the state immediately until we're told to
> > stop.
> >
> > The patch also reserves some frames in the initial vector to avoid having
> > resizes on the hot path.  To avoid large RSS before matching even starts
> > we provide a cap to the initial reservations.
> >
> > Benchmark improvements vs GCC 16:
> >   email: 53.7%
> >   URI:   52.8%
> >   IPv4:  44.4%
> >
> > Bootstrapped Regtested on aarch64-none-linux-gnu,
> > arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
> > -m32, -m64 and no issues.
> >
> > Ok for master?
> 
> Some minor comments below while Patrick reviews this series and we
> confirm the benefits at -O2 ...
> 
> >
> > Thanks,
> > Tamar
> >
> > libstdc++-v3/ChangeLog:
> >
> >         PR libstdc++/126274
> >         * include/bits/regex_executor.h (_Executor): Reserve frame space.
> >         (_M_rep_once_more): Return state.
> >         (_M_dfs_next): New.
> >         * include/bits/regex_executor.tcc (_M_rep_once_more): Return state.
> >         (_M_dfs_next): New.
> >         (_M_dfs): Traverse states iteratively for _S_fopcode_next,
> >         _S_fopcode_fallback_next, _S_fopcode_fallback_rep_once_more
> >         and _S_fopcode_rep_once_more.
> >
> > ---
> > diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-
> v3/include/bits/regex_executor.h
> > index
> f6e55f2f4aaa8fb3fa8d963b04d5bcf0b3b191d3..0a63b9b83789a700de630
> 81ee61a7857028548e0 100644
> > --- a/libstdc++-v3/include/bits/regex_executor.h
> > +++ b/libstdc++-v3/include/bits/regex_executor.h
> > @@ -87,6 +87,11 @@ namespace __detail
> >         using namespace regex_constants;
> >         if (__flags & match_prev_avail) // ignore not_bol and not_bow
> >           _M_flags &= ~(match_not_bol | match_not_bow);
> > +       // Reserve NFA sized frames up front to prevent having to constantly
> > +       // reallocate frames.  To avoid an explosion in state with large regexp
> > +       // before any matching is every done limit the reservation to 256.
> 
> "is ever done" ?
> 
> > +       // This should cover a large class of regexp.
> > +       _M_frames.reserve(std::min<size_t>(_M_nfa.size(), 256));
> 
> Was 256 determined empirically? It seems quite high to me.
> The geometric growth policy of std::vector should mean it doesn't
> _constantly_ reallocate frames. We'll reallocate frequently while the
> number of frames is small, but as the size increases we'll end up
> allocating larger blocks and need to reallocate less often.
> 

No, this was completely arbitrary and was just that I didn't know how
big the typical nfa size is in practice. There's definitely the possibility
that this isn't that expensive.  Let me drop it and see if I see anything
meaningful.

I'm respinning the patches now with Patrick's review changes and will
try this at the same time.

Thanks,
Tamar

> 
> >         if (_M_search_mode == _Search_mode::_BFS)
> >           _M_visited_states = new bool[_M_nfa.size()];
> >        }
> > @@ -114,7 +119,7 @@ namespace __detail
> >        _M_search();
> >
> >      private:
> > -      void
> > +      _StateIdT
> >        _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
> >
> >        template<_Search_mode __search_mode>
> > @@ -157,6 +162,9 @@ namespace __detail
> >         void
> >        _M_node(_Match_mode, _StateIdT);
> >
> > +      _StateIdT
> > +      _M_dfs_next(_Match_mode, _StateIdT);
> > +
> >        template<_Search_mode __search_mode>
> >         void
> >        _M_dfs(_Match_mode __match_mode, _StateIdT __start);
> > diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-
> v3/include/bits/regex_executor.tcc
> > index
> 86f6c6240853d673f47099a5fd15fe84fc99316e..bf0594912688e0014a592
> 8b6c6d600af6f80b31a 100644
> > --- a/libstdc++-v3/include/bits/regex_executor.tcc
> > +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> > @@ -250,8 +250,14 @@ namespace __detail
> >    // infinite loop by refusing to continue when it's already been
> >    // visited more than twice. It's `twice` instead of `once` because
> >    // we need to spare one more time for potential group capture.
> > +  //
> > +  // If the node cannot be re-entered anymore from the current state then
> return
> > +  // _S_invalid_state_id otherwise return the current state without going
> > +  // through a vector, allowing the caller to decide what to do with the state
> > +  // This is beneficial for DFS since DFS can continue with the next state
> > +  // immediately
> >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > -    void _Executor<_BiIter, _Alloc, _TraitsT>::
> > +    _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >      _M_rep_once_more(_Match_mode, _StateIdT __i)
> >      {
> >        const auto& __state = _M_nfa[__i];
> > @@ -263,7 +269,7 @@ namespace __detail
> >           _M_frames.back()._M_count = __rep_count.second;
> >           __rep_count.first = _M_current;
> >           __rep_count.second = 1;
> > -         _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> > +         return __state._M_alt;
> >         }
> >        else
> >         {
> > @@ -271,9 +277,10 @@ namespace __detail
> >             {
> >               __rep_count.second++;
> >               _M_frames.emplace_back(_S_fopcode_decrement_rep_count, __i);
> > -             _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> > +             return __state._M_alt;
> >             }
> >         }
> > +      return _S_invalid_state_id;
> >      }
> >
> >    // _M_alt branch is "match once more", while _M_next is "get me out
> > @@ -611,6 +618,121 @@ namespace __detail
> >         }
> >      }
> >
> > +
> > +  // Execute one DFS state in a form optimized for immediate progress.
> > +  //
> > +  // Returning a state id means "continue with this successor now".
> Returning
> > +  // _S_invalid_state_id means the helper either failed this path or delegated
> > +  // to the generic frame-based handler, so the outer DFS loop should pop
> the
> > +  // next pending frame.
> > +  //
> > +  // The helper is intentionally small and it's intended to cover states that
> > +  // are common in scanning regexes and have an obvious preferred
> successor.
> > +  // For example, in "[\w]+://" most successful work is: enter repeat,
> consume
> > +  // a match state, repeat, then try the literal ':' path.
> > +  // The key is to avoid a push/pop for each immediate _S_fopcode_next.
> When
> > +  // it sees a state whose behavior that's not an obvious direct match it calls
> > +  // _M_node<_Search_mode::_DFS> and resumes the normal flow.
> > +  template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > +#ifdef __OPTIMIZE__
> > +    [[__gnu__::__always_inline__]]
> > +#endif
> > +    inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> > +    _M_dfs_next(_Match_mode __match_mode, _StateIdT __i)
> > +    {
> > +      const auto& __state = _M_nfa[__i];
> > +
> > +      switch (__state._M_opcode())
> > +       {
> > +       case _S_opcode_subexpr_begin:
> > +         // Capture group 0 is the whole match.  Without backreferences no
> > +         // later state can observe the old group-0 boundary during
> > +         // backtracking, so continue directly with the next state.
> > +         //
> > +         // Example: for regex_search with "[0-9]+", only the final group-0
> > +         // boundaries are reported; there is no backref that can read
> > +         // an intermediate group-0 value.
> > +         if (!_M_nfa._M_has_backref && __state._M_subexpr == 0)
> > +           {
> > +             _M_cur_results[0].first = _M_current;
> > +             return __state._M_next;
> > +           }
> > +         break;
> > +
> > +       case _S_opcode_subexpr_end:
> > +         // Same group-0 shortcut for the end boundary.  For other capture
> > +         // groups we delegate to _M_node so their old values are restored
> > +         // correctly when a later alternative fails.  For example, in
> > +         // "(a|ab)c" the capture for group 1 may need to roll back from "a"
> > +         // to try "ab" so the shortcut cannot be used.
> > +         if (!_M_nfa._M_has_backref && __state._M_subexpr == 0)
> > +           {
> > +             auto& __res = _M_cur_results[0];
> > +             __res.second = _M_current;
> > +             __res.matched = true;
> > +             return __state._M_next;
> > +           }
> > +         break;
> > +
> > +       case _S_opcode_match:
> > +         // Consume one character and return the next state instead of pushing
> > +         // _S_fopcode_next.  On a long input matched by e.g. "#+", this
> > +         // removes one frame round trip per consumed '#'.
> > +         if (_M_current != _M_end && __state._M_matches(*_M_current))
> > +           {
> > +             ++_M_current;
> > +             return __state._M_next;
> > +           }
> > +         return _S_invalid_state_id;
> > +
> > +       case _S_opcode_accept:
> > +         // Accept needs to store the frame, so call the generic handler and
> > +         // stop any linear consumptions in the optimized paths.
> > +         _M_handle_accept<_Search_mode::_DFS>(__match_mode, __i);
> > +         return _S_invalid_state_id;
> > +
> > +       case _S_opcode_repeat:
> > +         // For greedy repeats, DFS should try the body first and remember the
> > +         // exit as a fallback.  Example: for "[0-9]+" at "123x", keep the
> > +         // "exit repeat" state on the stack, but immediately continue into the
> > +         // digit-matching body.  When the body later fails at 'x', the
> > +         // fallback accepts the repeat at the position after '3'.
> > +         if (!__state._M_neg)
> > +           {
> > +             _M_frames.emplace_back(_S_fopcode_fallback_next,
> > +                                    __state._M_next, _M_current);
> > +             return _M_rep_once_more(__match_mode, __i);
> > +           }
> > +         else
> > +           {
> > +             _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> > +                                    __i, _M_current);
> > +             return __state._M_next;
> > +           }
> > +
> > +       case _S_opcode_alternative:
> > +         // ECMAScript alternatives are ordered.  Try _M_alt first and keep
> _M_next
> > +         // as a fallback, e.g. "foo|fo" should prefer "foo" if it succeeds.
> > +         // If the preferred arm fails, the fallback restores _M_current and
> > +         // tries the other arm.  POSIX alternatives require longest-match
> > +         // merging, so they stay on the generic path.
> > +         if (_M_nfa._M_flags & regex_constants::ECMAScript)
> > +           {
> > +             _M_frames.emplace_back(_S_fopcode_fallback_next,
> > +                                    __state._M_next, _M_current);
> > +             return __state._M_alt;
> > +           }
> > +         break;
> > +
> > +       default:
> > +         break;
> > +       }
> > +
> > +      // Any opcode not handled above still uses the existing mechanism
> > +      _M_node<_Search_mode::_DFS>(__match_mode, __i);
> > +      return _S_invalid_state_id;
> > +    }
> > +
> >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >    template<_Search_mode __search_mode>
> >      void _Executor<_BiIter, _Alloc, _TraitsT>::
> > @@ -632,7 +754,15 @@ namespace __detail
> >                 _M_current = __frame._M_pos;
> >               [[__fallthrough__]];
> >             case _S_fopcode_next:
> > -             _M_node<__search_mode>(__match_mode, __frame._M_state_id);
> > +             if constexpr (__search_mode == _Search_mode::_DFS)
> > +               // Follow immediate successors without re-entering the frame
> > +               // loop untill we fail.  This avoids the needless state save and
> 
> "until"
> 
> > +               // restore through memory.
> > +               for (_StateIdT __next = __frame._M_state_id;
> > +                    __next != _S_invalid_state_id;)
> > +                 __next = _M_dfs_next(__match_mode, __next);
> > +             else
> > +               _M_node<_Search_mode::_BFS>(__match_mode,
> __frame._M_state_id);
> >               break;
> >
> >             case _S_fopcode_fallback_rep_once_more:
> > @@ -642,7 +772,21 @@ namespace __detail
> >                 _M_current = __frame._M_pos;
> >               [[__fallthrough__]];
> >             case _S_fopcode_rep_once_more:
> > -             _M_rep_once_more(__match_mode, __frame._M_state_id);
> > +             {
> > +               _StateIdT __next
> > +                 = _M_rep_once_more(__match_mode, __frame._M_state_id);
> > +               if constexpr (__search_mode == _Search_mode::_DFS)
> > +                 // _M_rep_once_more returned the repeated body's start state.
> > +                 // Continue directly in DFS; BFS must materialize the state as
> > +                 // a queue/frame item because it advances by input position
> > +                 // rather than by backtracking order.  Splittig this in a
> 
> "Splitting"
> 
> > +                 // specialized path preserves the behavior for both but has
> > +                 // DFS avoids the intermediate allocations.
> 
> I think this should be "avoid" not "avoids"?
> Or maybe "but for DFS it avoids the ..."
> 
> > +                 for (; __next != _S_invalid_state_id;)
> > +                   __next = _M_dfs_next(__match_mode, __next);
> > +               else if (__next != _S_invalid_state_id)
> > +                 _M_frames.emplace_back(_S_fopcode_next, __next);
> > +             }
> >               break;
> >
> >             case _S_fopcode_posix_alternative:
> >
> >
> > --