Ping
> -----Original Message----- > From: Tamar Christina > Sent: 20 August 2026 18:14 > To: [email protected] > Cc: nd <[email protected]>; [email protected]; [email protected]; > [email protected]; [email protected] > Subject: [patch v3 2/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 previous patch in > series > > at -O2: > > email: +11.1% > URI: +10.3% > IPv4 +7.3% > > at -O3: > > email: +8.6%, > URI: +7.9% > IPv4: +3.6% > > 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 > c2d1d5f0bfeee279fbd1fb138c58f45f9cdbe60e..2a9c87af59489f5202554d1 > 052ec8355b7c5646b 100644 > --- a/libstdc++-v3/include/bits/regex_executor.h > +++ b/libstdc++-v3/include/bits/regex_executor.h > @@ -51,10 +51,11 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > * 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: > @@ -82,12 +83,12 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > _M_start(_M_nfa._M_start()), > _M_visited_states(nullptr), > _M_flags(__flags), > - _M_search_mode(__use_dfs ? _Search_mode::_DFS : > _Search_mode::_BFS) > + _M_search_mode(__use_dfs ? _Search_mode::_Dfs : > _Search_mode::_Bfs) > { > using namespace regex_constants; > if (__flags & match_prev_avail) // ignore not_bol and not_bow > _M_flags &= ~(match_not_bol | match_not_bow); > - if (_M_search_mode == _Search_mode::_BFS) > + if (_M_search_mode == _Search_mode::_Bfs) > _M_visited_states = new bool[_M_nfa.size()]; > } > > @@ -117,13 +118,16 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > _StateIdT > _M_rep_once_more(_Match_mode __match_mode, _StateIdT); > > + template<_Search_mode __search_mode> > _StateIdT > _M_handle_repeat(_Match_mode, _StateIdT); > > - _StateIdT > + template<_Search_mode __search_mode> > + _StateIdT > _M_handle_subexpr_begin(_Match_mode, _StateIdT); > > - _StateIdT > + template<_Search_mode __search_mode> > + _StateIdT > _M_handle_subexpr_end(_Match_mode, _StateIdT); > > _StateIdT > @@ -138,28 +142,32 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > _StateIdT > _M_handle_subexpr_lookahead(_Match_mode, _StateIdT); > > - _StateIdT > + template<_Search_mode __search_mode> > + _StateIdT > _M_handle_match(_Match_mode, _StateIdT); > > _StateIdT > _M_handle_backref(_Match_mode, _StateIdT); > > - _StateIdT > + template<_Search_mode __search_mode> > + _StateIdT > _M_handle_accept(_Match_mode, _StateIdT); > > _StateIdT > _M_handle_alternative(_Match_mode, _StateIdT); > > - _StateIdT > + template<_Search_mode __search_mode> > + _StateIdT > _M_node(_Match_mode, _StateIdT); > > - void > + template<_Search_mode __search_mode> > + void > _M_dfs(_Match_mode __match_mode, _StateIdT __start); > > bool > _M_main(_Match_mode __match_mode) > { > - if (_M_search_mode == _Search_mode::_DFS) > + if (_M_search_mode == _Search_mode::_Dfs) > return _M_main_dfs(__match_mode); > else > return _M_main_bfs(__match_mode); > diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++- > v3/include/bits/regex_executor.tcc > index > 87d5ac68685c22bbedcf9e67f96b50b61392a701..6e4c2a238cf8e393c8ae5 > 61edb88f94bf35331c0 100644 > --- a/libstdc++-v3/include/bits/regex_executor.tcc > +++ b/libstdc++-v3/include/bits/regex_executor.tcc > @@ -166,7 +166,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > _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; > } > > @@ -209,7 +209,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > 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; > @@ -289,6 +289,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > // 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> > #ifdef __OPTIMIZE__ > [[__gnu__::__always_inline__]] > #endif > @@ -299,7 +300,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > // 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); > @@ -309,7 +310,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > } > 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, > @@ -335,6 +336,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > + template<_Search_mode __search_mode> > #ifdef __OPTIMIZE__ > [[__gnu__::__always_inline__]] > #endif > @@ -345,7 +347,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > auto& __res = _M_cur_results[__state._M_subexpr]; > if (_M_nfa._M_has_backref > || __state._M_subexpr != 0 > - || _M_search_mode != _Search_mode::_DFS) > + || __search_mode != _Search_mode::_Dfs) > _M_frames.emplace_back(_S_fopcode_restore_cur_results, > static_cast<_StateIdT>(__state._M_subexpr), > __res.first); > @@ -354,6 +356,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > + template<_Search_mode __search_mode> > #ifdef __OPTIMIZE__ > [[__gnu__::__always_inline__]] > #endif > @@ -364,7 +367,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > auto& __res = _M_cur_results[__state._M_subexpr]; > if (_M_nfa._M_has_backref > || __state._M_subexpr != 0 > - || _M_search_mode != _Search_mode::_DFS) > + || __search_mode != _Search_mode::_Dfs) > { > _M_frames.emplace_back(_S_fopcode_restore_cur_results, > static_cast<_StateIdT>(__state._M_subexpr), > @@ -421,6 +424,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > + template<_Search_mode __search_mode> > #ifdef __OPTIMIZE__ > [[__gnu__::__always_inline__]] > #endif > @@ -430,7 +434,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > const auto& __state = _M_nfa[__i]; > if (_M_current == _M_end) > return _S_invalid_state_id; > - if (_M_search_mode == _Search_mode::_DFS) > + if constexpr (__search_mode == _Search_mode::_Dfs) > { > if (__state._M_matches(*_M_current)) > { > @@ -501,7 +505,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_backref(_Match_mode, _StateIdT __i) > { > - __glibcxx_assert(_M_search_mode == _Search_mode::_DFS); > + __glibcxx_assert(_M_search_mode == _Search_mode::_Dfs); > > const auto& __state = _M_nfa[__i]; > auto& __submatch = _M_cur_results[__state._M_backref_index]; > @@ -525,13 +529,14 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > + template<_Search_mode __search_mode> > #ifdef __OPTIMIZE__ > [[__gnu__::__always_inline__]] > #endif > inline _StateIdT _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) > @@ -607,6 +612,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > + template<_Search_mode __search_mode> > #ifdef __OPTIMIZE__ > [[__gnu__::__always_inline__]] > #endif > @@ -615,7 +621,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > { > // DFS has no _M_visited implementation as such don't even have the > branch > // or the check in the call graph. > - if (_M_search_mode == _Search_mode::_BFS) > + if constexpr (__search_mode == _Search_mode::_Bfs) > if (_M_visited(__i)) > return _S_invalid_state_id; > > @@ -623,12 +629,12 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > switch (_M_nfa[__i]._M_opcode()) > { > case _S_opcode_repeat: > - __next = _M_handle_repeat(__match_mode, __i); break; > + __next = _M_handle_repeat<__search_mode>(__match_mode, __i); > break; > case _S_opcode_subexpr_begin: > - __next = _M_handle_subexpr_begin(__match_mode, __i); > + __next = > _M_handle_subexpr_begin<__search_mode>(__match_mode, __i); > break; > case _S_opcode_subexpr_end: > - __next = _M_handle_subexpr_end(__match_mode, __i); > + __next = > _M_handle_subexpr_end<__search_mode>(__match_mode, __i); > break; > case _S_opcode_line_begin_assertion: > __next = _M_handle_line_begin_assertion(__match_mode, __i); > break; > @@ -639,15 +645,15 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > case _S_opcode_subexpr_lookahead: > __next = _M_handle_subexpr_lookahead(__match_mode, __i); > break; > case _S_opcode_match: > - __next = _M_handle_match(__match_mode, __i); break; > + __next = _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) > __next = _M_handle_backref(__match_mode, __i); > else > __builtin_unreachable(); > break; > case _S_opcode_accept: > - __next = _M_handle_accept(__match_mode, __i); break; > + __next = _M_handle_accept<__search_mode>(__match_mode, __i); > break; > case _S_opcode_alternative: > __next = _M_handle_alternative(__match_mode, __i); break; > default: > @@ -657,6 +663,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > } > > 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) > { > @@ -668,7 +675,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > // loop until we fail. This avoids the needless state save and > // restore through memory. > while (__next != _S_invalid_state_id) > - __next = _M_node(__match_mode, __next); > + __next = _M_node<__search_mode>(__match_mode, __next); > > if (_M_frames.empty()) > break; > @@ -681,7 +688,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > case _S_fopcode_fallback_next: > if (_M_has_sol) > break; > - if (_M_search_mode == _Search_mode::_DFS) > + if constexpr (__search_mode == _Search_mode::_Dfs) > _M_current = __frame._M_pos; > [[__fallthrough__]]; > case _S_fopcode_next: > @@ -691,7 +698,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > case _S_fopcode_fallback_rep_once_more: > if (_M_has_sol) > break; > - if (_M_search_mode == _Search_mode::_DFS) > + if constexpr (__search_mode == _Search_mode::_Dfs) > _M_current = __frame._M_pos; > [[__fallthrough__]]; > case _S_fopcode_rep_once_more: > @@ -701,7 +708,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > case _S_fopcode_posix_alternative: > _M_frames.emplace_back(_S_fopcode_merge_sol, 0, > _M_has_sol); > __next = __frame._M_state_id; > - if (_M_search_mode == _Search_mode::_DFS) > + if constexpr (__search_mode == _Search_mode::_Dfs) > _M_current = __frame._M_pos; > _M_has_sol = false; > break; > > > --
