On Thu, 16 Jul 2026, 15:37 Tamar Christina, <[email protected]> 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; > > > -- >
