On Thu, 16 Jul 2026, Tamar Christina wrote:
> > -----Original Message-----
> > From: Patrick Palka <[email protected]>
> > Sent: 16 July 2026 16:18
> > To: Tamar Christina <[email protected]>
> > Cc: [email protected]; nd <[email protected]>; [email protected];
> > [email protected]; [email protected]; [email protected]
> > 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;
> > >
> > >
> > > --
> > >
>
>
