https://gcc.gnu.org/g:24570c4a1b2805fc375c5f0fb9881eb3d1f24bc7
commit r17-4553-g24570c4a1b2805fc375c5f0fb9881eb3d1f24bc7 Author: Tamar Christina <[email protected]> Date: Tue Sep 22 07:21:49 2026 +0100 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% 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: --- libstdc++-v3/include/bits/regex_executor.h | 28 +++++++++++------ libstdc++-v3/include/bits/regex_executor.tcc | 47 ++++++++++++++++------------ 2 files changed, 45 insertions(+), 30 deletions(-) diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h index eccf12c5a087..0cafc26a15b5 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 9361c27d4c5b..a4cce445e350 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; @@ -288,6 +288,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> #ifdef __OPTIMIZE__ [[__gnu__::__always_inline__]] #endif @@ -298,7 +299,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); @@ -308,7 +309,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, @@ -334,6 +335,7 @@ namespace __detail } template<typename _BiIter, typename _Alloc, typename _TraitsT> + template<_Search_mode __search_mode> #ifdef __OPTIMIZE__ [[__gnu__::__always_inline__]] #endif @@ -344,7 +346,7 @@ namespace __detail 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); @@ -353,6 +355,7 @@ namespace __detail } template<typename _BiIter, typename _Alloc, typename _TraitsT> + template<_Search_mode __search_mode> #ifdef __OPTIMIZE__ [[__gnu__::__always_inline__]] #endif @@ -363,7 +366,7 @@ namespace __detail 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), @@ -420,6 +423,7 @@ namespace __detail } template<typename _BiIter, typename _Alloc, typename _TraitsT> + template<_Search_mode __search_mode> #ifdef __OPTIMIZE__ [[__gnu__::__always_inline__]] #endif @@ -429,7 +433,7 @@ namespace __detail 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)) { @@ -500,7 +504,7 @@ namespace __detail _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]; @@ -524,13 +528,14 @@ namespace __detail } 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) @@ -606,6 +611,7 @@ namespace __detail } template<typename _BiIter, typename _Alloc, typename _TraitsT> + template<_Search_mode __search_mode> #ifdef __OPTIMIZE__ [[__gnu__::__always_inline__]] #endif @@ -614,7 +620,7 @@ namespace __detail { // 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; @@ -622,12 +628,12 @@ namespace __detail 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; @@ -638,15 +644,15 @@ namespace __detail 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: @@ -656,6 +662,7 @@ 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) { @@ -667,7 +674,7 @@ namespace __detail // 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; @@ -680,7 +687,7 @@ namespace __detail 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: @@ -690,7 +697,7 @@ namespace __detail 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: @@ -700,7 +707,7 @@ namespace __detail 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;
