[1/4,libstdc++] : Templatize regex executor traversal mode [PR126274]

  In GCC 16 the commit r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20
caused a big regression in performance of regex in libstdc++.

This and other patches were tested using the CPP version of the benchmarks
at https://github.com/mariomka/regex-benchmark/

The benchmark uses regex_token_iterator over the input text with these patterns:

- email: [\w.+-]+@[\w.-]+\.[\w.-]+
- URI: [\w]+:\/\/[^\/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?
- IPv4: (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])

Where it tests various types of regexpr. "email" has no backtracking so it's the
simplest NFA possible which we should be able to handle quickly.

"uri" has optional matches and some non capturing groups and "ipv4" adds some
alternative matching to the equation.

The input string is a 6.52 mb test file "input-text.txt"

The regressions of each type of regexpr compared to GCC 15 are:

  email: 118.9%
  URI: 124.8%
  IPv4: 139.8%

So most matches became > 2x slower.

This patch series addresses the regressions and gets the new code to be
ultimately faster than the GCC 15 implementation.

Currently the _Executor class implements both a DFS and a BFS traveral mode
for the regex matching.  It has a parameter _M_search_mode which it uses
inside the _Executor functions to separate out the implementations.

However this parameter is rather opague to IPA and so for each implementation
the other branch is always dead but they haven't been folded away.

This increases the number of dynamic instructions and branches being executed
and the branches seem to be often mispredicted.

The patch fixes it by moving _Search_mode out of the class and making it a
template parameter instead so we can at compile time fold away the two
implementations.  This removes all the extra compare and branches from the
hot functions.

These changes improve the benchmarks compared with GCC 16 with

  email: 17.8%
  URI: 16.8%
  IPv4: 8.9%

On Neoverse-V1

So there is still a regression until the end of the series and each patch
will chip away at it.

Also note that with none of these changes do I see an increase heap or stack
usage that the original fix fixed.  RSS stays about the same.

PS. thanks for the link to the algorithm in the source, it was useful to
understand how the machinery works!

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 (_Search_mode): Move to top level.
	(_M_handle_repeat, _M_handle_match, _M_handle_accept, _M_node, _M_dfs):
	Add template parameter.
	(_M_visited): Add inline keyword.
	* include/bits/regex_executor.tcc (_M_handle_repeat, _M_handle_match,
	_M_handle_accept, _M_node, _M_dfs): Use template parameter.

---


--
  

On Thu, 16 Jul 2026, Tamar Christina wrote:

> In GCC 16 the commit r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20
> caused a big regression in performance of regex in libstdc++.
> 
> This and other patches were tested using the CPP version of the benchmarks
> at https://github.com/mariomka/regex-benchmark/
> 
> The benchmark uses regex_token_iterator over the input text with these patterns:
> 
> - email: [\w.+-]+@[\w.-]+\.[\w.-]+
> - URI: [\w]+:\/\/[^\/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?
> - IPv4: (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])
> 
> Where it tests various types of regexpr. "email" has no backtracking so it's the
> simplest NFA possible which we should be able to handle quickly.
> 
> "uri" has optional matches and some non capturing groups and "ipv4" adds some
> alternative matching to the equation.
> 
> The input string is a 6.52 mb test file "input-text.txt"
> 
> The regressions of each type of regexpr compared to GCC 15 are:
> 
>   email: 118.9%
>   URI: 124.8%
>   IPv4: 139.8%
> 
> So most matches became > 2x slower.
> 
> This patch series addresses the regressions and gets the new code to be
> ultimately faster than the GCC 15 implementation.
> 
> Currently the _Executor class implements both a DFS and a BFS traveral mode
> for the regex matching.  It has a parameter _M_search_mode which it uses
> inside the _Executor functions to separate out the implementations.
> 
> However this parameter is rather opague to IPA and so for each implementation
> the other branch is always dead but they haven't been folded away.
> 
> This increases the number of dynamic instructions and branches being executed
> and the branches seem to be often mispredicted.

Why are the branches often mispredicted if they never change?

> 
> The patch fixes it by moving _Search_mode out of the class and making it a
> template parameter instead so we can at compile time fold away the two
> implementations.  This removes all the extra compare and branches from the
> hot functions.
> 
> These changes improve the benchmarks compared with GCC 16 with
> 
>   email: 17.8%
>   URI: 16.8%
>   IPv4: 8.9%

These measurements are with -O3 right? Shouldn't we also consider -O2?
I ask because this patch partially undoes r16-7425-gc49ce07bf09504 which
changed the compile-time search mode to a run-time flag for sake of code
size, run time, and compile time/memory usage according to my crude
benchmarks using -O2.  I found that by eliminating the entire extra copy
of _Executor's implementation, its std::vector operations are more
likely to get inlined, which resulted in a 15% improvement in run time.

However, previously the entire _Executor template was parameterized on the
search mode and this patch does a more targeted approach of parameterizing
only the member functions that need it, which I hadn't considered doing.
This might be the best compromise, but I do wonder about performance
with -O2, since IIUC -O2 is less aggressive about inlining and we might
see again the performance degradation I saw when _Executor was fully
parameterized on the search mode, resulting in some hot std::vector
operations not getting inlined.

> 
> On Neoverse-V1
> 
> So there is still a regression until the end of the series and each patch
> will chip away at it.
> 
> Also note that with none of these changes do I see an increase heap or stack
> usage that the original fix fixed.  RSS stays about the same.
> 
> PS. thanks for the link to the algorithm in the source, it was useful to
> understand how the machinery works!
> 
> 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 (_Search_mode): Move to top level.
> 	(_M_handle_repeat, _M_handle_match, _M_handle_accept, _M_node, _M_dfs):
> 	Add template parameter.
> 	(_M_visited): Add inline keyword.
> 	* include/bits/regex_executor.tcc (_M_handle_repeat, _M_handle_match,
> 	_M_handle_accept, _M_node, _M_dfs): Use template parameter.
> 
> ---
> diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
> index 797ad702784b6d1bf07734d91683946d989630f5..f6e55f2f4aaa8fb3fa8d963b04d5bcf0b3b191d3 100644
> --- a/libstdc++-v3/include/bits/regex_executor.h
> +++ b/libstdc++-v3/include/bits/regex_executor.h
> @@ -50,10 +50,11 @@ namespace __detail
>     * The %_Executor class has two modes: DFS mode and BFS mode, controlled
>     * by the function parameter %__search_mode.
>     */
> +  enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
> +
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
>      class _Executor
>      {
> -      enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
>        enum class _Match_mode : unsigned char { _Exact, _Prefix };
>  
>      public:
> @@ -116,7 +117,8 @@ namespace __detail
>        void
>        _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
>  
> -      void
> +      template<_Search_mode __search_mode>
> +	void
>        _M_handle_repeat(_Match_mode, _StateIdT);
>  
>        void
> @@ -137,22 +139,26 @@ namespace __detail
>        void
>        _M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
>  
> -      void
> +      template<_Search_mode __search_mode>
> +	void
>        _M_handle_match(_Match_mode, _StateIdT);
>  
>        void
>        _M_handle_backref(_Match_mode, _StateIdT);
>  
> -      void
> +      template<_Search_mode __search_mode>
> +	void
>        _M_handle_accept(_Match_mode, _StateIdT);
>  
>        void
>        _M_handle_alternative(_Match_mode, _StateIdT);
>  
> -      void
> +      template<_Search_mode __search_mode>
> +	void
>        _M_node(_Match_mode, _StateIdT);
>  
> -      void
> +      template<_Search_mode __search_mode>
> +	void
>        _M_dfs(_Match_mode __match_mode, _StateIdT __start);
>  
>        bool
> @@ -247,7 +253,7 @@ namespace __detail
>  	return (_M_re._M_automaton->_M_options() & __m) == __m;
>        }
>  
> -      bool
> +      inline bool
>        _M_visited(_StateIdT __i)
>        {
>  	if (_M_visited_states)
> diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
> index 167a7a345300868ed5e0852e328569aec47e3d0d..86f6c6240853d673f47099a5fd15fe84fc99316e 100644
> --- a/libstdc++-v3/include/bits/regex_executor.tcc
> +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> @@ -165,7 +165,7 @@ namespace __detail
>        _M_has_sol = false;
>        *_M_get_sol_pos() = _BiIter();
>        _M_cur_results = _M_results;
> -      _M_dfs(__match_mode, _M_start);
> +      _M_dfs<_Search_mode::_DFS>(__match_mode, _M_start);
>        return _M_has_sol;
>      }
>  
> @@ -208,7 +208,7 @@ namespace __detail
>  	  for (auto& __task : __old_queue)
>  	    {
>  	      _M_cur_results = _ResultsVec(std::move(__task.second), __alloc);
> -	      _M_dfs(__match_mode, __task.first);
> +	      _M_dfs<_Search_mode::_BFS>(__match_mode, __task.first);
>  	    }
>  	  if (__match_mode == _Match_mode::_Prefix)
>  	    __ret |= _M_has_sol;
> @@ -281,6 +281,7 @@ namespace __detail
>    // mean the same thing, and we need to choose the correct order under
>    // given greedy mode.
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_handle_repeat(_Match_mode, _StateIdT __i)
>      {
> @@ -288,7 +289,7 @@ namespace __detail
>        // Greedy.
>        if (!__state._M_neg)
>  	{
> -	  if (_M_search_mode == _Search_mode::_DFS)
> +	  if constexpr (__search_mode == _Search_mode::_DFS)
>  	    // If it's DFS executor and already accepted, we're done.
>  	    _M_frames.emplace_back(_S_fopcode_fallback_next, __state._M_next,
>  				   _M_current);
> @@ -298,7 +299,7 @@ namespace __detail
>  	}
>        else // Non-greedy mode
>  	{
> -	  if (_M_search_mode == _Search_mode::_DFS)
> +	  if constexpr (__search_mode == _Search_mode::_DFS)
>  	    {
>  	      // vice-versa.
>  	      _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i,
> @@ -390,13 +391,14 @@ namespace __detail
>      }
>  
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_handle_match(_Match_mode, _StateIdT __i)
>      {
>        const auto& __state = _M_nfa[__i];
>        if (_M_current == _M_end)
>  	return;
> -      if (_M_search_mode == _Search_mode::_DFS)
> +      if constexpr (__search_mode == _Search_mode::_DFS)
>  	{
>  	  if (__state._M_matches(*_M_current))
>  	    {
> @@ -487,10 +489,11 @@ namespace __detail
>      }
>  
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_handle_accept(_Match_mode __match_mode, _StateIdT)
>      {
> -      if (_M_search_mode == _Search_mode::_DFS)
> +      if constexpr (__search_mode == _Search_mode::_DFS)
>  	{
>  	  __glibcxx_assert(!_M_has_sol);
>  	  if (__match_mode == _Match_mode::_Exact)
> @@ -562,19 +565,23 @@ namespace __detail
>      }
>  
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>  #ifdef __OPTIMIZE__
>      [[__gnu__::__always_inline__]]
>  #endif
>      inline void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_node(_Match_mode __match_mode, _StateIdT __i)
>      {
> -      if (_M_visited(__i))
> -	return;
> +      // DFS has no _M_visited implementation as such don't even have the branch
> +      // or the check in the call graph.
> +      if constexpr (__search_mode == _Search_mode::_BFS)
> +	if (_M_visited(__i))
> +	  return;
>  
>        switch (_M_nfa[__i]._M_opcode())
>  	{
>  	case _S_opcode_repeat:
> -	  _M_handle_repeat(__match_mode, __i); break;
> +	  _M_handle_repeat<__search_mode>(__match_mode, __i); break;
>  	case _S_opcode_subexpr_begin:
>  	  _M_handle_subexpr_begin(__match_mode, __i); break;
>  	case _S_opcode_subexpr_end:
> @@ -588,15 +595,15 @@ namespace __detail
>  	case _S_opcode_subexpr_lookahead:
>  	  _M_handle_subexpr_lookahead(__match_mode, __i); break;
>  	case _S_opcode_match:
> -	  _M_handle_match(__match_mode, __i); break;
> +	  _M_handle_match<__search_mode>(__match_mode, __i); break;
>  	case _S_opcode_backref:
> -	  if (_M_search_mode == _Search_mode::_DFS)
> +	  if constexpr (__search_mode == _Search_mode::_DFS)
>  	    _M_handle_backref(__match_mode, __i);
>  	  else
>  	    __builtin_unreachable();
>  	  break;
>  	case _S_opcode_accept:
> -	  _M_handle_accept(__match_mode, __i); break;
> +	  _M_handle_accept<__search_mode>(__match_mode, __i); break;
>  	case _S_opcode_alternative:
>  	  _M_handle_alternative(__match_mode, __i); break;
>  	default:
> @@ -605,10 +612,10 @@ namespace __detail
>      }
>  
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_dfs(_Match_mode __match_mode, _StateIdT __start)
>      {
> -      const bool __dfs_mode = (_M_search_mode == _Search_mode::_DFS);
>        _M_frames.emplace_back(_S_fopcode_next, __start);
>  
>        while (!_M_frames.empty())
> @@ -621,17 +628,17 @@ namespace __detail
>  	    case _S_fopcode_fallback_next:
>  	      if (_M_has_sol)
>  		break;
> -	      if (__dfs_mode)
> +	      if constexpr (__search_mode == _Search_mode::_DFS)
>  		_M_current = __frame._M_pos;
>  	      [[__fallthrough__]];
>  	    case _S_fopcode_next:
> -	      _M_node(__match_mode, __frame._M_state_id);
> +	      _M_node<__search_mode>(__match_mode, __frame._M_state_id);
>  	      break;
>  
>  	    case _S_fopcode_fallback_rep_once_more:
>  	      if (_M_has_sol)
>  		break;
> -	      if (__dfs_mode)
> +	      if constexpr (__search_mode == _Search_mode::_DFS)
>  		_M_current = __frame._M_pos;
>  	      [[__fallthrough__]];
>  	    case _S_fopcode_rep_once_more:
> @@ -641,7 +648,7 @@ namespace __detail
>  	    case _S_fopcode_posix_alternative:
>  	      _M_frames.emplace_back(_S_fopcode_merge_sol, 0, _M_has_sol);
>  	      _M_frames.emplace_back(_S_fopcode_next, __frame._M_state_id);
> -	      if (__dfs_mode)
> +	      if constexpr (__search_mode == _Search_mode::_DFS)
>  		_M_current = __frame._M_pos;
>  	      _M_has_sol = false;
>  	      break;
> 
> 
> -- 
>
  

On Thu, 16 Jul 2026, 15:37 Tamar Christina, <tamar.christina@arm.com> wrote:

> In GCC 16 the commit r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20
> caused a big regression in performance of regex in libstdc++.
>
> This and other patches were tested using the CPP version of the benchmarks
> at https://github.com/mariomka/regex-benchmark/
>
> The benchmark uses regex_token_iterator over the input text with these
> patterns:
>
> - email: [\w.+-]+@[\w.-]+\.[\w.-]+
> - URI: [\w]+:\/\/[^\/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?
> - IPv4:
> (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])
>
> Where it tests various types of regexpr. "email" has no backtracking so
> it's the
> simplest NFA possible which we should be able to handle quickly.
>
> "uri" has optional matches and some non capturing groups and "ipv4" adds
> some
> alternative matching to the equation.
>
> The input string is a 6.52 mb test file "input-text.txt"
>
> The regressions of each type of regexpr compared to GCC 15 are:
>
>   email: 118.9%
>   URI: 124.8%
>   IPv4: 139.8%
>
> So most matches became > 2x slower.
>
> This patch series addresses the regressions and gets the new code to be
> ultimately faster than the GCC 15 implementation.
>
> Currently the _Executor class implements both a DFS and a BFS traveral mode
> for the regex matching.  It has a parameter _M_search_mode which it uses
> inside the _Executor functions to separate out the implementations.
>
> However this parameter is rather opague to IPA and so for each
> implementation
> the other branch is always dead but they haven't been folded away.
>
> This increases the number of dynamic instructions and branches being
> executed
> and the branches seem to be often mispredicted.
>
> The patch fixes it by moving _Search_mode out of the class and making it a
> template parameter instead so we can at compile time fold away the two
> implementations.  This removes all the extra compare and branches from the
> hot functions.
>
> These changes improve the benchmarks compared with GCC 16 with
>
>   email: 17.8%
>   URI: 16.8%
>   IPv4: 8.9%
>
> On Neoverse-V1
>
> So there is still a regression until the end of the series and each patch
> will chip away at it.
>
> Also note that with none of these changes do I see an increase heap or
> stack
> usage that the original fix fixed.  RSS stays about the same.
>
> PS. thanks for the link to the algorithm in the source, it was useful to
> understand how the machinery works!
>
> 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 (_Search_mode): Move to top level.
>         (_M_handle_repeat, _M_handle_match, _M_handle_accept, _M_node,
> _M_dfs):
>         Add template parameter.
>         (_M_visited): Add inline keyword.
>         * include/bits/regex_executor.tcc (_M_handle_repeat,
> _M_handle_match,
>         _M_handle_accept, _M_node, _M_dfs): Use template parameter.
>
> ---
> diff --git a/libstdc++-v3/include/bits/regex_executor.h
> b/libstdc++-v3/include/bits/regex_executor.h
> index
> 797ad702784b6d1bf07734d91683946d989630f5..f6e55f2f4aaa8fb3fa8d963b04d5bcf0b3b191d3
> 100644
> --- a/libstdc++-v3/include/bits/regex_executor.h
> +++ b/libstdc++-v3/include/bits/regex_executor.h
> @@ -50,10 +50,11 @@ namespace __detail
>     * The %_Executor class has two modes: DFS mode and BFS mode, controlled
>     * by the function parameter %__search_mode.
>     */
> +  enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
>

Patrick's comments are the most relevant, I'll just say that these should
be _Bfs and _Dfs, not all-caps.


+
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
>      class _Executor
>      {
> -      enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
>        enum class _Match_mode : unsigned char { _Exact, _Prefix };
>
>      public:
> @@ -116,7 +117,8 @@ namespace __detail
>        void
>        _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
>
> -      void
> +      template<_Search_mode __search_mode>
> +       void
>        _M_handle_repeat(_Match_mode, _StateIdT);
>
>        void
> @@ -137,22 +139,26 @@ namespace __detail
>        void
>        _M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
>
> -      void
> +      template<_Search_mode __search_mode>
> +       void
>        _M_handle_match(_Match_mode, _StateIdT);
>
>        void
>        _M_handle_backref(_Match_mode, _StateIdT);
>
> -      void
> +      template<_Search_mode __search_mode>
> +       void
>        _M_handle_accept(_Match_mode, _StateIdT);
>
>        void
>        _M_handle_alternative(_Match_mode, _StateIdT);
>
> -      void
> +      template<_Search_mode __search_mode>
> +       void
>        _M_node(_Match_mode, _StateIdT);
>
> -      void
> +      template<_Search_mode __search_mode>
> +       void
>        _M_dfs(_Match_mode __match_mode, _StateIdT __start);
>
>        bool
> @@ -247,7 +253,7 @@ namespace __detail
>         return (_M_re._M_automaton->_M_options() & __m) == __m;
>        }
>
> -      bool
> +      inline bool
>        _M_visited(_StateIdT __i)
>        {
>         if (_M_visited_states)
> diff --git a/libstdc++-v3/include/bits/regex_executor.tcc
> b/libstdc++-v3/include/bits/regex_executor.tcc
> index
> 167a7a345300868ed5e0852e328569aec47e3d0d..86f6c6240853d673f47099a5fd15fe84fc99316e
> 100644
> --- a/libstdc++-v3/include/bits/regex_executor.tcc
> +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> @@ -165,7 +165,7 @@ namespace __detail
>        _M_has_sol = false;
>        *_M_get_sol_pos() = _BiIter();
>        _M_cur_results = _M_results;
> -      _M_dfs(__match_mode, _M_start);
> +      _M_dfs<_Search_mode::_DFS>(__match_mode, _M_start);
>        return _M_has_sol;
>      }
>
> @@ -208,7 +208,7 @@ namespace __detail
>           for (auto& __task : __old_queue)
>             {
>               _M_cur_results = _ResultsVec(std::move(__task.second),
> __alloc);
> -             _M_dfs(__match_mode, __task.first);
> +             _M_dfs<_Search_mode::_BFS>(__match_mode, __task.first);
>             }
>           if (__match_mode == _Match_mode::_Prefix)
>             __ret |= _M_has_sol;
> @@ -281,6 +281,7 @@ namespace __detail
>    // mean the same thing, and we need to choose the correct order under
>    // given greedy mode.
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_handle_repeat(_Match_mode, _StateIdT __i)
>      {
> @@ -288,7 +289,7 @@ namespace __detail
>        // Greedy.
>        if (!__state._M_neg)
>         {
> -         if (_M_search_mode == _Search_mode::_DFS)
> +         if constexpr (__search_mode == _Search_mode::_DFS)
>             // If it's DFS executor and already accepted, we're done.
>             _M_frames.emplace_back(_S_fopcode_fallback_next,
> __state._M_next,
>                                    _M_current);
> @@ -298,7 +299,7 @@ namespace __detail
>         }
>        else // Non-greedy mode
>         {
> -         if (_M_search_mode == _Search_mode::_DFS)
> +         if constexpr (__search_mode == _Search_mode::_DFS)
>             {
>               // vice-versa.
>               _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> __i,
> @@ -390,13 +391,14 @@ namespace __detail
>      }
>
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_handle_match(_Match_mode, _StateIdT __i)
>      {
>        const auto& __state = _M_nfa[__i];
>        if (_M_current == _M_end)
>         return;
> -      if (_M_search_mode == _Search_mode::_DFS)
> +      if constexpr (__search_mode == _Search_mode::_DFS)
>         {
>           if (__state._M_matches(*_M_current))
>             {
> @@ -487,10 +489,11 @@ namespace __detail
>      }
>
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_handle_accept(_Match_mode __match_mode, _StateIdT)
>      {
> -      if (_M_search_mode == _Search_mode::_DFS)
> +      if constexpr (__search_mode == _Search_mode::_DFS)
>         {
>           __glibcxx_assert(!_M_has_sol);
>           if (__match_mode == _Match_mode::_Exact)
> @@ -562,19 +565,23 @@ namespace __detail
>      }
>
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>  #ifdef __OPTIMIZE__
>      [[__gnu__::__always_inline__]]
>  #endif
>      inline void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_node(_Match_mode __match_mode, _StateIdT __i)
>      {
> -      if (_M_visited(__i))
> -       return;
> +      // DFS has no _M_visited implementation as such don't even have the
> branch
> +      // or the check in the call graph.
> +      if constexpr (__search_mode == _Search_mode::_BFS)
> +       if (_M_visited(__i))
> +         return;
>
>        switch (_M_nfa[__i]._M_opcode())
>         {
>         case _S_opcode_repeat:
> -         _M_handle_repeat(__match_mode, __i); break;
> +         _M_handle_repeat<__search_mode>(__match_mode, __i); break;
>         case _S_opcode_subexpr_begin:
>           _M_handle_subexpr_begin(__match_mode, __i); break;
>         case _S_opcode_subexpr_end:
> @@ -588,15 +595,15 @@ namespace __detail
>         case _S_opcode_subexpr_lookahead:
>           _M_handle_subexpr_lookahead(__match_mode, __i); break;
>         case _S_opcode_match:
> -         _M_handle_match(__match_mode, __i); break;
> +         _M_handle_match<__search_mode>(__match_mode, __i); break;
>         case _S_opcode_backref:
> -         if (_M_search_mode == _Search_mode::_DFS)
> +         if constexpr (__search_mode == _Search_mode::_DFS)
>             _M_handle_backref(__match_mode, __i);
>           else
>             __builtin_unreachable();
>           break;
>         case _S_opcode_accept:
> -         _M_handle_accept(__match_mode, __i); break;
> +         _M_handle_accept<__search_mode>(__match_mode, __i); break;
>         case _S_opcode_alternative:
>           _M_handle_alternative(__match_mode, __i); break;
>         default:
> @@ -605,10 +612,10 @@ namespace __detail
>      }
>
>    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +  template<_Search_mode __search_mode>
>      void _Executor<_BiIter, _Alloc, _TraitsT>::
>      _M_dfs(_Match_mode __match_mode, _StateIdT __start)
>      {
> -      const bool __dfs_mode = (_M_search_mode == _Search_mode::_DFS);
>        _M_frames.emplace_back(_S_fopcode_next, __start);
>
>        while (!_M_frames.empty())
> @@ -621,17 +628,17 @@ namespace __detail
>             case _S_fopcode_fallback_next:
>               if (_M_has_sol)
>                 break;
> -             if (__dfs_mode)
> +             if constexpr (__search_mode == _Search_mode::_DFS)
>                 _M_current = __frame._M_pos;
>               [[__fallthrough__]];
>             case _S_fopcode_next:
> -             _M_node(__match_mode, __frame._M_state_id);
> +             _M_node<__search_mode>(__match_mode, __frame._M_state_id);
>               break;
>
>             case _S_fopcode_fallback_rep_once_more:
>               if (_M_has_sol)
>                 break;
> -             if (__dfs_mode)
> +             if constexpr (__search_mode == _Search_mode::_DFS)
>                 _M_current = __frame._M_pos;
>               [[__fallthrough__]];
>             case _S_fopcode_rep_once_more:
> @@ -641,7 +648,7 @@ namespace __detail
>             case _S_fopcode_posix_alternative:
>               _M_frames.emplace_back(_S_fopcode_merge_sol, 0, _M_has_sol);
>               _M_frames.emplace_back(_S_fopcode_next, __frame._M_state_id);
> -             if (__dfs_mode)
> +             if constexpr (__search_mode == _Search_mode::_DFS)
>                 _M_current = __frame._M_pos;
>               _M_has_sol = false;
>               break;
>
>
> --
>
  

> -----Original Message-----
> From: Patrick Palka <ppalka@redhat.com>
> Sent: 16 July 2026 16:18
> To: Tamar Christina <Tamar.Christina@arm.com>
> Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; libstdc++@gcc.gnu.org;
> jwakely@redhat.com; tkaminsk@redhat.com; ppalka@redhat.com
> Subject: Re: [patch 1/4][libstdc++]: Templatize regex executor traversal mode
> [PR126274]
> 
> On Thu, 16 Jul 2026, Tamar Christina wrote:
> 
> > In GCC 16 the commit r16-7193-
> g158ad5f96954da5fa24d5c2a91ae92417fb62e20
> > caused a big regression in performance of regex in libstdc++.
> >
> > This and other patches were tested using the CPP version of the benchmarks
> > at https://github.com/mariomka/regex-benchmark/
> >
> > The benchmark uses regex_token_iterator over the input text with these
> patterns:
> >
> > - email: [\w.+-]+@[\w.-]+\.[\w.-]+
> > - URI: [\w]+:\/\/[^\/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?
> > - IPv4: (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}(?:25[0-5]|2[0-
> 4][0-9]|[01]?[0-9][0-9])
> >
> > Where it tests various types of regexpr. "email" has no backtracking so it's
> the
> > simplest NFA possible which we should be able to handle quickly.
> >
> > "uri" has optional matches and some non capturing groups and "ipv4" adds
> some
> > alternative matching to the equation.
> >
> > The input string is a 6.52 mb test file "input-text.txt"
> >
> > The regressions of each type of regexpr compared to GCC 15 are:
> >
> >   email: 118.9%
> >   URI: 124.8%
> >   IPv4: 139.8%
> >
> > So most matches became > 2x slower.
> >
> > This patch series addresses the regressions and gets the new code to be
> > ultimately faster than the GCC 15 implementation.
> >
> > Currently the _Executor class implements both a DFS and a BFS traveral
> mode
> > for the regex matching.  It has a parameter _M_search_mode which it uses
> > inside the _Executor functions to separate out the implementations.
> >
> > However this parameter is rather opague to IPA and so for each
> implementation
> > the other branch is always dead but they haven't been folded away.
> >
> > This increases the number of dynamic instructions and branches being
> executed
> > and the branches seem to be often mispredicted.
> 
> Why are the branches often mispredicted if they never change?

The branch mispredictions refer to the entire run, so not specifically this patch.
When I looked at the perf report it has quite a lot of new branches and quite
a few dependended on loaded values.

I didn't look deeper into it since the dynamic instructions increased a lot too
so I focused on those first.

> 
> >
> > The patch fixes it by moving _Search_mode out of the class and making it a
> > template parameter instead so we can at compile time fold away the two
> > implementations.  This removes all the extra compare and branches from the
> > hot functions.
> >
> > These changes improve the benchmarks compared with GCC 16 with
> >
> >   email: 17.8%
> >   URI: 16.8%
> >   IPv4: 8.9%
> 
> These measurements are with -O3 right? Shouldn't we also consider -O2?
> I ask because this patch partially undoes r16-7425-gc49ce07bf09504 which
> changed the compile-time search mode to a run-time flag for sake of code
> size, run time, and compile time/memory usage according to my crude
> benchmarks using -O2.  I found that by eliminating the entire extra copy
> of _Executor's implementation, its std::vector operations are more
> likely to get inlined, which resulted in a 15% improvement in run time.
> 
> However, previously the entire _Executor template was parameterized on the
> search mode and this patch does a more targeted approach of parameterizing
> only the member functions that need it, which I hadn't considered doing.
> This might be the best compromise, but I do wonder about performance
> with -O2, since IIUC -O2 is less aggressive about inlining and we might
> see again the performance degradation I saw when _Executor was fully
> parameterized on the search mode, resulting in some hot std::vector
> operations not getting inlined.

This is a fair point. I'm away until Tuesday but wanted to give you some numbers
before I go, these are relative to GCC 15 before the change.

+-------+-----------------+----------------+-----------------------------------------------+
  | case  | patched version | GCC 17 - Trunk | after commit 158ad5f96954da5fa24d5c2a91ae92417fb62e20 |
  +-------+-----------------+----------------+-----------------------------------------------+
  | email    | +6.1%           | +97.0%         | +112.3%                                       |
  | URI  | +11.3%          | +106.5%        | +121.2%                                       |
  | IPv4     | -20.4%          | +129.3%        | +132.1%                                       |
  +-------+-----------------+----------------+-----------------------------------------------+

So it looks like -O2 has similar losses, which are better in current trunk but still worse than before
the change, and at -O2 we don't fully recover it for all cases but get close.

These are again on Neoverse-V1 but I can try x86_64 when I come back if
you'd like.

Cheers,
Tamar

> 
> >
> > On Neoverse-V1
> >
> > So there is still a regression until the end of the series and each patch
> > will chip away at it.
> >
> > Also note that with none of these changes do I see an increase heap or stack
> > usage that the original fix fixed.  RSS stays about the same.
> >
> > PS. thanks for the link to the algorithm in the source, it was useful to
> > understand how the machinery works!
> >
> > 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 (_Search_mode): Move to top level.
> > 	(_M_handle_repeat, _M_handle_match, _M_handle_accept,
> _M_node, _M_dfs):
> > 	Add template parameter.
> > 	(_M_visited): Add inline keyword.
> > 	* include/bits/regex_executor.tcc (_M_handle_repeat,
> _M_handle_match,
> > 	_M_handle_accept, _M_node, _M_dfs): Use template parameter.
> >
> > ---
> > diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-
> v3/include/bits/regex_executor.h
> > index
> 797ad702784b6d1bf07734d91683946d989630f5..f6e55f2f4aaa8fb3fa8d9
> 63b04d5bcf0b3b191d3 100644
> > --- a/libstdc++-v3/include/bits/regex_executor.h
> > +++ b/libstdc++-v3/include/bits/regex_executor.h
> > @@ -50,10 +50,11 @@ namespace __detail
> >     * The %_Executor class has two modes: DFS mode and BFS mode,
> controlled
> >     * by the function parameter %__search_mode.
> >     */
> > +  enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
> > +
> >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >      class _Executor
> >      {
> > -      enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
> >        enum class _Match_mode : unsigned char { _Exact, _Prefix };
> >
> >      public:
> > @@ -116,7 +117,8 @@ namespace __detail
> >        void
> >        _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
> >
> > -      void
> > +      template<_Search_mode __search_mode>
> > +	void
> >        _M_handle_repeat(_Match_mode, _StateIdT);
> >
> >        void
> > @@ -137,22 +139,26 @@ namespace __detail
> >        void
> >        _M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
> >
> > -      void
> > +      template<_Search_mode __search_mode>
> > +	void
> >        _M_handle_match(_Match_mode, _StateIdT);
> >
> >        void
> >        _M_handle_backref(_Match_mode, _StateIdT);
> >
> > -      void
> > +      template<_Search_mode __search_mode>
> > +	void
> >        _M_handle_accept(_Match_mode, _StateIdT);
> >
> >        void
> >        _M_handle_alternative(_Match_mode, _StateIdT);
> >
> > -      void
> > +      template<_Search_mode __search_mode>
> > +	void
> >        _M_node(_Match_mode, _StateIdT);
> >
> > -      void
> > +      template<_Search_mode __search_mode>
> > +	void
> >        _M_dfs(_Match_mode __match_mode, _StateIdT __start);
> >
> >        bool
> > @@ -247,7 +253,7 @@ namespace __detail
> >  	return (_M_re._M_automaton->_M_options() & __m) == __m;
> >        }
> >
> > -      bool
> > +      inline bool
> >        _M_visited(_StateIdT __i)
> >        {
> >  	if (_M_visited_states)
> > diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-
> v3/include/bits/regex_executor.tcc
> > index
> 167a7a345300868ed5e0852e328569aec47e3d0d..86f6c6240853d673f470
> 99a5fd15fe84fc99316e 100644
> > --- a/libstdc++-v3/include/bits/regex_executor.tcc
> > +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> > @@ -165,7 +165,7 @@ namespace __detail
> >        _M_has_sol = false;
> >        *_M_get_sol_pos() = _BiIter();
> >        _M_cur_results = _M_results;
> > -      _M_dfs(__match_mode, _M_start);
> > +      _M_dfs<_Search_mode::_DFS>(__match_mode, _M_start);
> >        return _M_has_sol;
> >      }
> >
> > @@ -208,7 +208,7 @@ namespace __detail
> >  	  for (auto& __task : __old_queue)
> >  	    {
> >  	      _M_cur_results = _ResultsVec(std::move(__task.second), __alloc);
> > -	      _M_dfs(__match_mode, __task.first);
> > +	      _M_dfs<_Search_mode::_BFS>(__match_mode, __task.first);
> >  	    }
> >  	  if (__match_mode == _Match_mode::_Prefix)
> >  	    __ret |= _M_has_sol;
> > @@ -281,6 +281,7 @@ namespace __detail
> >    // mean the same thing, and we need to choose the correct order under
> >    // given greedy mode.
> >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > +  template<_Search_mode __search_mode>
> >      void _Executor<_BiIter, _Alloc, _TraitsT>::
> >      _M_handle_repeat(_Match_mode, _StateIdT __i)
> >      {
> > @@ -288,7 +289,7 @@ namespace __detail
> >        // Greedy.
> >        if (!__state._M_neg)
> >  	{
> > -	  if (_M_search_mode == _Search_mode::_DFS)
> > +	  if constexpr (__search_mode == _Search_mode::_DFS)
> >  	    // If it's DFS executor and already accepted, we're done.
> >  	    _M_frames.emplace_back(_S_fopcode_fallback_next,
> __state._M_next,
> >  				   _M_current);
> > @@ -298,7 +299,7 @@ namespace __detail
> >  	}
> >        else // Non-greedy mode
> >  	{
> > -	  if (_M_search_mode == _Search_mode::_DFS)
> > +	  if constexpr (__search_mode == _Search_mode::_DFS)
> >  	    {
> >  	      // vice-versa.
> >  	      _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> __i,
> > @@ -390,13 +391,14 @@ namespace __detail
> >      }
> >
> >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > +  template<_Search_mode __search_mode>
> >      void _Executor<_BiIter, _Alloc, _TraitsT>::
> >      _M_handle_match(_Match_mode, _StateIdT __i)
> >      {
> >        const auto& __state = _M_nfa[__i];
> >        if (_M_current == _M_end)
> >  	return;
> > -      if (_M_search_mode == _Search_mode::_DFS)
> > +      if constexpr (__search_mode == _Search_mode::_DFS)
> >  	{
> >  	  if (__state._M_matches(*_M_current))
> >  	    {
> > @@ -487,10 +489,11 @@ namespace __detail
> >      }
> >
> >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > +  template<_Search_mode __search_mode>
> >      void _Executor<_BiIter, _Alloc, _TraitsT>::
> >      _M_handle_accept(_Match_mode __match_mode, _StateIdT)
> >      {
> > -      if (_M_search_mode == _Search_mode::_DFS)
> > +      if constexpr (__search_mode == _Search_mode::_DFS)
> >  	{
> >  	  __glibcxx_assert(!_M_has_sol);
> >  	  if (__match_mode == _Match_mode::_Exact)
> > @@ -562,19 +565,23 @@ namespace __detail
> >      }
> >
> >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > +  template<_Search_mode __search_mode>
> >  #ifdef __OPTIMIZE__
> >      [[__gnu__::__always_inline__]]
> >  #endif
> >      inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >      _M_node(_Match_mode __match_mode, _StateIdT __i)
> >      {
> > -      if (_M_visited(__i))
> > -	return;
> > +      // DFS has no _M_visited implementation as such don't even have the
> branch
> > +      // or the check in the call graph.
> > +      if constexpr (__search_mode == _Search_mode::_BFS)
> > +	if (_M_visited(__i))
> > +	  return;
> >
> >        switch (_M_nfa[__i]._M_opcode())
> >  	{
> >  	case _S_opcode_repeat:
> > -	  _M_handle_repeat(__match_mode, __i); break;
> > +	  _M_handle_repeat<__search_mode>(__match_mode, __i); break;
> >  	case _S_opcode_subexpr_begin:
> >  	  _M_handle_subexpr_begin(__match_mode, __i); break;
> >  	case _S_opcode_subexpr_end:
> > @@ -588,15 +595,15 @@ namespace __detail
> >  	case _S_opcode_subexpr_lookahead:
> >  	  _M_handle_subexpr_lookahead(__match_mode, __i); break;
> >  	case _S_opcode_match:
> > -	  _M_handle_match(__match_mode, __i); break;
> > +	  _M_handle_match<__search_mode>(__match_mode, __i); break;
> >  	case _S_opcode_backref:
> > -	  if (_M_search_mode == _Search_mode::_DFS)
> > +	  if constexpr (__search_mode == _Search_mode::_DFS)
> >  	    _M_handle_backref(__match_mode, __i);
> >  	  else
> >  	    __builtin_unreachable();
> >  	  break;
> >  	case _S_opcode_accept:
> > -	  _M_handle_accept(__match_mode, __i); break;
> > +	  _M_handle_accept<__search_mode>(__match_mode, __i); break;
> >  	case _S_opcode_alternative:
> >  	  _M_handle_alternative(__match_mode, __i); break;
> >  	default:
> > @@ -605,10 +612,10 @@ namespace __detail
> >      }
> >
> >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > +  template<_Search_mode __search_mode>
> >      void _Executor<_BiIter, _Alloc, _TraitsT>::
> >      _M_dfs(_Match_mode __match_mode, _StateIdT __start)
> >      {
> > -      const bool __dfs_mode = (_M_search_mode == _Search_mode::_DFS);
> >        _M_frames.emplace_back(_S_fopcode_next, __start);
> >
> >        while (!_M_frames.empty())
> > @@ -621,17 +628,17 @@ namespace __detail
> >  	    case _S_fopcode_fallback_next:
> >  	      if (_M_has_sol)
> >  		break;
> > -	      if (__dfs_mode)
> > +	      if constexpr (__search_mode == _Search_mode::_DFS)
> >  		_M_current = __frame._M_pos;
> >  	      [[__fallthrough__]];
> >  	    case _S_fopcode_next:
> > -	      _M_node(__match_mode, __frame._M_state_id);
> > +	      _M_node<__search_mode>(__match_mode,
> __frame._M_state_id);
> >  	      break;
> >
> >  	    case _S_fopcode_fallback_rep_once_more:
> >  	      if (_M_has_sol)
> >  		break;
> > -	      if (__dfs_mode)
> > +	      if constexpr (__search_mode == _Search_mode::_DFS)
> >  		_M_current = __frame._M_pos;
> >  	      [[__fallthrough__]];
> >  	    case _S_fopcode_rep_once_more:
> > @@ -641,7 +648,7 @@ namespace __detail
> >  	    case _S_fopcode_posix_alternative:
> >  	      _M_frames.emplace_back(_S_fopcode_merge_sol, 0,
> _M_has_sol);
> >  	      _M_frames.emplace_back(_S_fopcode_next,
> __frame._M_state_id);
> > -	      if (__dfs_mode)
> > +	      if constexpr (__search_mode == _Search_mode::_DFS)
> >  		_M_current = __frame._M_pos;
> >  	      _M_has_sol = false;
> >  	      break;
> >
> >
> > --
> >
  

On Thu, 16 Jul 2026, Tamar Christina wrote:

> > -----Original Message-----
> > From: Patrick Palka <ppalka@redhat.com>
> > Sent: 16 July 2026 16:18
> > To: Tamar Christina <Tamar.Christina@arm.com>
> > Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; libstdc++@gcc.gnu.org;
> > jwakely@redhat.com; tkaminsk@redhat.com; ppalka@redhat.com
> > Subject: Re: [patch 1/4][libstdc++]: Templatize regex executor traversal mode
> > [PR126274]
> > 
> > On Thu, 16 Jul 2026, Tamar Christina wrote:
> > 
> > > In GCC 16 the commit r16-7193-
> > g158ad5f96954da5fa24d5c2a91ae92417fb62e20
> > > caused a big regression in performance of regex in libstdc++.
> > >
> > > This and other patches were tested using the CPP version of the benchmarks
> > > at https://github.com/mariomka/regex-benchmark/
> > >
> > > The benchmark uses regex_token_iterator over the input text with these
> > patterns:
> > >
> > > - email: [\w.+-]+@[\w.-]+\.[\w.-]+
> > > - URI: [\w]+:\/\/[^\/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?
> > > - IPv4: (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}(?:25[0-5]|2[0-
> > 4][0-9]|[01]?[0-9][0-9])
> > >
> > > Where it tests various types of regexpr. "email" has no backtracking so it's
> > the
> > > simplest NFA possible which we should be able to handle quickly.
> > >
> > > "uri" has optional matches and some non capturing groups and "ipv4" adds
> > some
> > > alternative matching to the equation.
> > >
> > > The input string is a 6.52 mb test file "input-text.txt"
> > >
> > > The regressions of each type of regexpr compared to GCC 15 are:
> > >
> > >   email: 118.9%
> > >   URI: 124.8%
> > >   IPv4: 139.8%
> > >
> > > So most matches became > 2x slower.
> > >
> > > This patch series addresses the regressions and gets the new code to be
> > > ultimately faster than the GCC 15 implementation.
> > >
> > > Currently the _Executor class implements both a DFS and a BFS traveral
> > mode
> > > for the regex matching.  It has a parameter _M_search_mode which it uses
> > > inside the _Executor functions to separate out the implementations.
> > >
> > > However this parameter is rather opague to IPA and so for each
> > implementation
> > > the other branch is always dead but they haven't been folded away.
> > >
> > > This increases the number of dynamic instructions and branches being
> > executed
> > > and the branches seem to be often mispredicted.
> > 
> > Why are the branches often mispredicted if they never change?
> 
> The branch mispredictions refer to the entire run, so not specifically this patch.
> When I looked at the perf report it has quite a lot of new branches and quite
> a few dependended on loaded values.
> 
> I didn't look deeper into it since the dynamic instructions increased a lot too
> so I focused on those first.
> 
> > 
> > >
> > > The patch fixes it by moving _Search_mode out of the class and making it a
> > > template parameter instead so we can at compile time fold away the two
> > > implementations.  This removes all the extra compare and branches from the
> > > hot functions.
> > >
> > > These changes improve the benchmarks compared with GCC 16 with
> > >
> > >   email: 17.8%
> > >   URI: 16.8%
> > >   IPv4: 8.9%
> > 
> > These measurements are with -O3 right? Shouldn't we also consider -O2?
> > I ask because this patch partially undoes r16-7425-gc49ce07bf09504 which
> > changed the compile-time search mode to a run-time flag for sake of code
> > size, run time, and compile time/memory usage according to my crude
> > benchmarks using -O2.  I found that by eliminating the entire extra copy
> > of _Executor's implementation, its std::vector operations are more
> > likely to get inlined, which resulted in a 15% improvement in run time.
> > 
> > However, previously the entire _Executor template was parameterized on the
> > search mode and this patch does a more targeted approach of parameterizing
> > only the member functions that need it, which I hadn't considered doing.
> > This might be the best compromise, but I do wonder about performance
> > with -O2, since IIUC -O2 is less aggressive about inlining and we might
> > see again the performance degradation I saw when _Executor was fully
> > parameterized on the search mode, resulting in some hot std::vector
> > operations not getting inlined.
> 
> This is a fair point. I'm away until Tuesday but wanted to give you some numbers
> before I go, these are relative to GCC 15 before the change.
> 
> +-------+-----------------+----------------+-----------------------------------------------+
>   | case  | patched version | GCC 17 - Trunk | after commit 158ad5f96954da5fa24d5c2a91ae92417fb62e20 |
>   +-------+-----------------+----------------+-----------------------------------------------+
>   | email    | +6.1%           | +97.0%         | +112.3%                                       |
>   | URI  | +11.3%          | +106.5%        | +121.2%                                       |
>   | IPv4     | -20.4%          | +129.3%        | +132.1%                                       |
>   +-------+-----------------+----------------+-----------------------------------------------+
> 
> So it looks like -O2 has similar losses, which are better in current trunk but still worse than before
> the change, and at -O2 we don't fully recover it for all cases but get close.
> 
> These are again on Neoverse-V1 but I can try x86_64 when I come back if
> you'd like.

I was able to reproduce similar benchmark improvements with this patch
locally on my x86 machine with both -O2 and -O3.  I'm surprised that
this change has such a large effect on performance really.

The patch doesn't remove the _M_search_mode data member, and not
all existing _M_search_mode uses are replaced by a corresponding
template parameter.  Which is good for ABI compatibility and code size
I suppose, but kind of messy.

Since it seems that the 2/4 patch provides the bulk of the speedup,
could you reverse the order of 1/4 and 2/4 so that the 2/4 patch is the
first in the series (with my suggested changes to the _M_handle_foo
return values + fast path)?  It'd be easier to review, and I'm curious
to see what the marginal benefit of templatizing _M_search_mode is once
we get rid of the biggest source of slowdown.


> 
> Cheers,
> Tamar
> 
> > 
> > >
> > > On Neoverse-V1
> > >
> > > So there is still a regression until the end of the series and each patch
> > > will chip away at it.
> > >
> > > Also note that with none of these changes do I see an increase heap or stack
> > > usage that the original fix fixed.  RSS stays about the same.
> > >
> > > PS. thanks for the link to the algorithm in the source, it was useful to
> > > understand how the machinery works!
> > >
> > > 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 (_Search_mode): Move to top level.
> > > 	(_M_handle_repeat, _M_handle_match, _M_handle_accept,
> > _M_node, _M_dfs):
> > > 	Add template parameter.
> > > 	(_M_visited): Add inline keyword.
> > > 	* include/bits/regex_executor.tcc (_M_handle_repeat,
> > _M_handle_match,
> > > 	_M_handle_accept, _M_node, _M_dfs): Use template parameter.
> > >
> > > ---
> > > diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-
> > v3/include/bits/regex_executor.h
> > > index
> > 797ad702784b6d1bf07734d91683946d989630f5..f6e55f2f4aaa8fb3fa8d9
> > 63b04d5bcf0b3b191d3 100644
> > > --- a/libstdc++-v3/include/bits/regex_executor.h
> > > +++ b/libstdc++-v3/include/bits/regex_executor.h
> > > @@ -50,10 +50,11 @@ namespace __detail
> > >     * The %_Executor class has two modes: DFS mode and BFS mode,
> > controlled
> > >     * by the function parameter %__search_mode.
> > >     */
> > > +  enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
> > > +
> > >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > >      class _Executor
> > >      {
> > > -      enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
> > >        enum class _Match_mode : unsigned char { _Exact, _Prefix };
> > >
> > >      public:
> > > @@ -116,7 +117,8 @@ namespace __detail
> > >        void
> > >        _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
> > >
> > > -      void
> > > +      template<_Search_mode __search_mode>
> > > +	void
> > >        _M_handle_repeat(_Match_mode, _StateIdT);
> > >
> > >        void
> > > @@ -137,22 +139,26 @@ namespace __detail
> > >        void
> > >        _M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
> > >
> > > -      void
> > > +      template<_Search_mode __search_mode>
> > > +	void
> > >        _M_handle_match(_Match_mode, _StateIdT);
> > >
> > >        void
> > >        _M_handle_backref(_Match_mode, _StateIdT);
> > >
> > > -      void
> > > +      template<_Search_mode __search_mode>
> > > +	void
> > >        _M_handle_accept(_Match_mode, _StateIdT);
> > >
> > >        void
> > >        _M_handle_alternative(_Match_mode, _StateIdT);
> > >
> > > -      void
> > > +      template<_Search_mode __search_mode>
> > > +	void
> > >        _M_node(_Match_mode, _StateIdT);
> > >
> > > -      void
> > > +      template<_Search_mode __search_mode>
> > > +	void
> > >        _M_dfs(_Match_mode __match_mode, _StateIdT __start);
> > >
> > >        bool
> > > @@ -247,7 +253,7 @@ namespace __detail
> > >  	return (_M_re._M_automaton->_M_options() & __m) == __m;
> > >        }
> > >
> > > -      bool
> > > +      inline bool
> > >        _M_visited(_StateIdT __i)
> > >        {
> > >  	if (_M_visited_states)
> > > diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-
> > v3/include/bits/regex_executor.tcc
> > > index
> > 167a7a345300868ed5e0852e328569aec47e3d0d..86f6c6240853d673f470
> > 99a5fd15fe84fc99316e 100644
> > > --- a/libstdc++-v3/include/bits/regex_executor.tcc
> > > +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> > > @@ -165,7 +165,7 @@ namespace __detail
> > >        _M_has_sol = false;
> > >        *_M_get_sol_pos() = _BiIter();
> > >        _M_cur_results = _M_results;
> > > -      _M_dfs(__match_mode, _M_start);
> > > +      _M_dfs<_Search_mode::_DFS>(__match_mode, _M_start);
> > >        return _M_has_sol;
> > >      }
> > >
> > > @@ -208,7 +208,7 @@ namespace __detail
> > >  	  for (auto& __task : __old_queue)
> > >  	    {
> > >  	      _M_cur_results = _ResultsVec(std::move(__task.second), __alloc);
> > > -	      _M_dfs(__match_mode, __task.first);
> > > +	      _M_dfs<_Search_mode::_BFS>(__match_mode, __task.first);
> > >  	    }
> > >  	  if (__match_mode == _Match_mode::_Prefix)
> > >  	    __ret |= _M_has_sol;
> > > @@ -281,6 +281,7 @@ namespace __detail
> > >    // mean the same thing, and we need to choose the correct order under
> > >    // given greedy mode.
> > >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > > +  template<_Search_mode __search_mode>
> > >      void _Executor<_BiIter, _Alloc, _TraitsT>::
> > >      _M_handle_repeat(_Match_mode, _StateIdT __i)
> > >      {
> > > @@ -288,7 +289,7 @@ namespace __detail
> > >        // Greedy.
> > >        if (!__state._M_neg)
> > >  	{
> > > -	  if (_M_search_mode == _Search_mode::_DFS)
> > > +	  if constexpr (__search_mode == _Search_mode::_DFS)
> > >  	    // If it's DFS executor and already accepted, we're done.
> > >  	    _M_frames.emplace_back(_S_fopcode_fallback_next,
> > __state._M_next,
> > >  				   _M_current);
> > > @@ -298,7 +299,7 @@ namespace __detail
> > >  	}
> > >        else // Non-greedy mode
> > >  	{
> > > -	  if (_M_search_mode == _Search_mode::_DFS)
> > > +	  if constexpr (__search_mode == _Search_mode::_DFS)
> > >  	    {
> > >  	      // vice-versa.
> > >  	      _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> > __i,
> > > @@ -390,13 +391,14 @@ namespace __detail
> > >      }
> > >
> > >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > > +  template<_Search_mode __search_mode>
> > >      void _Executor<_BiIter, _Alloc, _TraitsT>::
> > >      _M_handle_match(_Match_mode, _StateIdT __i)
> > >      {
> > >        const auto& __state = _M_nfa[__i];
> > >        if (_M_current == _M_end)
> > >  	return;
> > > -      if (_M_search_mode == _Search_mode::_DFS)
> > > +      if constexpr (__search_mode == _Search_mode::_DFS)
> > >  	{
> > >  	  if (__state._M_matches(*_M_current))
> > >  	    {
> > > @@ -487,10 +489,11 @@ namespace __detail
> > >      }
> > >
> > >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > > +  template<_Search_mode __search_mode>
> > >      void _Executor<_BiIter, _Alloc, _TraitsT>::
> > >      _M_handle_accept(_Match_mode __match_mode, _StateIdT)
> > >      {
> > > -      if (_M_search_mode == _Search_mode::_DFS)
> > > +      if constexpr (__search_mode == _Search_mode::_DFS)
> > >  	{
> > >  	  __glibcxx_assert(!_M_has_sol);
> > >  	  if (__match_mode == _Match_mode::_Exact)
> > > @@ -562,19 +565,23 @@ namespace __detail
> > >      }
> > >
> > >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > > +  template<_Search_mode __search_mode>
> > >  #ifdef __OPTIMIZE__
> > >      [[__gnu__::__always_inline__]]
> > >  #endif
> > >      inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> > >      _M_node(_Match_mode __match_mode, _StateIdT __i)
> > >      {
> > > -      if (_M_visited(__i))
> > > -	return;
> > > +      // DFS has no _M_visited implementation as such don't even have the
> > branch
> > > +      // or the check in the call graph.
> > > +      if constexpr (__search_mode == _Search_mode::_BFS)
> > > +	if (_M_visited(__i))
> > > +	  return;
> > >
> > >        switch (_M_nfa[__i]._M_opcode())
> > >  	{
> > >  	case _S_opcode_repeat:
> > > -	  _M_handle_repeat(__match_mode, __i); break;
> > > +	  _M_handle_repeat<__search_mode>(__match_mode, __i); break;
> > >  	case _S_opcode_subexpr_begin:
> > >  	  _M_handle_subexpr_begin(__match_mode, __i); break;
> > >  	case _S_opcode_subexpr_end:
> > > @@ -588,15 +595,15 @@ namespace __detail
> > >  	case _S_opcode_subexpr_lookahead:
> > >  	  _M_handle_subexpr_lookahead(__match_mode, __i); break;
> > >  	case _S_opcode_match:
> > > -	  _M_handle_match(__match_mode, __i); break;
> > > +	  _M_handle_match<__search_mode>(__match_mode, __i); break;
> > >  	case _S_opcode_backref:
> > > -	  if (_M_search_mode == _Search_mode::_DFS)
> > > +	  if constexpr (__search_mode == _Search_mode::_DFS)
> > >  	    _M_handle_backref(__match_mode, __i);
> > >  	  else
> > >  	    __builtin_unreachable();
> > >  	  break;
> > >  	case _S_opcode_accept:
> > > -	  _M_handle_accept(__match_mode, __i); break;
> > > +	  _M_handle_accept<__search_mode>(__match_mode, __i); break;
> > >  	case _S_opcode_alternative:
> > >  	  _M_handle_alternative(__match_mode, __i); break;
> > >  	default:
> > > @@ -605,10 +612,10 @@ namespace __detail
> > >      }
> > >
> > >    template<typename _BiIter, typename _Alloc, typename _TraitsT>
> > > +  template<_Search_mode __search_mode>
> > >      void _Executor<_BiIter, _Alloc, _TraitsT>::
> > >      _M_dfs(_Match_mode __match_mode, _StateIdT __start)
> > >      {
> > > -      const bool __dfs_mode = (_M_search_mode == _Search_mode::_DFS);
> > >        _M_frames.emplace_back(_S_fopcode_next, __start);
> > >
> > >        while (!_M_frames.empty())
> > > @@ -621,17 +628,17 @@ namespace __detail
> > >  	    case _S_fopcode_fallback_next:
> > >  	      if (_M_has_sol)
> > >  		break;
> > > -	      if (__dfs_mode)
> > > +	      if constexpr (__search_mode == _Search_mode::_DFS)
> > >  		_M_current = __frame._M_pos;
> > >  	      [[__fallthrough__]];
> > >  	    case _S_fopcode_next:
> > > -	      _M_node(__match_mode, __frame._M_state_id);
> > > +	      _M_node<__search_mode>(__match_mode,
> > __frame._M_state_id);
> > >  	      break;
> > >
> > >  	    case _S_fopcode_fallback_rep_once_more:
> > >  	      if (_M_has_sol)
> > >  		break;
> > > -	      if (__dfs_mode)
> > > +	      if constexpr (__search_mode == _Search_mode::_DFS)
> > >  		_M_current = __frame._M_pos;
> > >  	      [[__fallthrough__]];
> > >  	    case _S_fopcode_rep_once_more:
> > > @@ -641,7 +648,7 @@ namespace __detail
> > >  	    case _S_fopcode_posix_alternative:
> > >  	      _M_frames.emplace_back(_S_fopcode_merge_sol, 0,
> > _M_has_sol);
> > >  	      _M_frames.emplace_back(_S_fopcode_next,
> > __frame._M_state_id);
> > > -	      if (__dfs_mode)
> > > +	      if constexpr (__search_mode == _Search_mode::_DFS)
> > >  		_M_current = __frame._M_pos;
> > >  	      _M_has_sol = false;
> > >  	      break;
> > >
> > >
> > > --
> > >
> 
>