Ping
> -----Original Message----- > From: Tamar Christina <[email protected]> > Sent: 20 August 2026 18:13 > To: [email protected] > Cc: nd <[email protected]>; [email protected]; [email protected]; > [email protected]; [email protected] > Subject: [patch v3 1/4][libstdc++]: Continue with regex DFS traversals without > next frames [PR126274] > > The change in r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20 > changed > the recursive implementation with an iterative one using an explicit heap. > > However one benefit of the previous implementation is that the frame did > not have to be saved and popped when the match is supposed to continue. > > This means that on hot paths we now have additional memory accesses and > need additional instructions to calculate the memref addresses. > > For DFS matching this is clearly suboptimal since when _M_rep_once_more > then we push and pop the same state but there is enough other acceses > in between the push and pop that we get a lot of cache misses. > > This makes all the private _m_handle_* methods return a _StateIdT which > allows > the caller to deal with the value, so that for DFS we can avoid pushing the > frame if needed. > > For DFS we try to consume the state immediately until we're told to > stop. > > For this to work the methods have to me marked always inline, because a key > part > of the optimization is to keep the values in registers rather than passing > through stack and the function call overheads and AAPCS requirements would > negate the benefits. > > The patch also reserves some frames in the initial vector to avoid having > resizes on the hot path. To avoid large RSS before matching even starts > we provide a cap to the initial reservations. However I have not yet > addressed > > Jakub's comment that the cap at 255 is likely to big. I need to do more > experiments here to figure out if it's even needed. For now I left it since I > am expecting another respin here. > > The __dfs_mode changes are because the constexpr patch still gave a big boost > so > it prepares to apply it. > > 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! > > Benchmark improvements vs GCC 16: > > at -O2: > > email: +36.1% > URI: +36.5% > IPv4 +33.0% > > at -O3: > > email: +45.5%, > URI: +44.9% > IPv4: +43.0% > > On Neoverse-V1 > > 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 (_Executor): Reserve frame space. > (_M_rep_once_more, _M_handle_repeat, _M_handle_subexpr_begin, > _M_handle_subexpr_end, _M_handle_line_begin_assertion, > _M_handle_line_end_assertion, _M_handle_word_boundary, > _M_handle_subexpr_lookahead, _M_handle_match, > _M_handle_backref, > _M_node): return StateIdT. > (_M_visited): Mark inline. > * include/bits/regex_executor.tcc (_M_rep_once_more, > _M_handle_repeat, > _M_handle_subexpr_begin, _M_handle_subexpr_end, > _M_handle_line_begin_assertion, _M_handle_line_end_assertion, > _M_handle_word_boundary, _M_handle_subexpr_lookahead, > _M_handle_match, > _M_handle_backref): Return state, mark always inline. > (_M_node): Return StateIdT and also decide what to do with the value > after return. > (_M_dfs): Traverse states iteratively for _S_fopcode_next, > _S_fopcode_fallback_next, _S_fopcode_fallback_rep_once_more > and _S_fopcode_rep_once_more. > > --- > diff --git a/libstdc++-v3/include/bits/regex.h b/libstdc++- > v3/include/bits/regex.h > index > 0e815ca086eb33975dd3ac66841c6eaf4a54b2ad..dce420251db0817fa05ab > 79d7ca0838f214fdc33 100644 > --- a/libstdc++-v3/include/bits/regex.h > +++ b/libstdc++-v3/include/bits/regex.h > @@ -61,8 +61,10 @@ namespace __detail > _RegexExecutorPolicy __policy, > bool __match_mode); > > +_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > template<typename, typename, typename> > class _Executor; > +_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) > > template<typename _Tp> > struct __is_contiguous_iter : false_type { }; > diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++- > v3/include/bits/regex_executor.h > index > 797ad702784b6d1bf07734d91683946d989630f5..c2d1d5f0bfeee279fbd1 > fb138c58f45f9cdbe60e 100644 > --- a/libstdc++-v3/include/bits/regex_executor.h > +++ b/libstdc++-v3/include/bits/regex_executor.h > @@ -41,6 +41,7 @@ namespace __detail > * @{ > */ > > +_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > template<typename _BiIter, bool _Trivial = > is_trivially_copyable<_BiIter>::value> > struct _ExecutorFrame; > > @@ -113,43 +114,43 @@ namespace __detail > _M_search(); > > private: > - void > + _StateIdT > _M_rep_once_more(_Match_mode __match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_repeat(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_subexpr_begin(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_subexpr_end(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_line_begin_assertion(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_line_end_assertion(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_word_boundary(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_subexpr_lookahead(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_match(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_backref(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_accept(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_handle_alternative(_Match_mode, _StateIdT); > > - void > + _StateIdT > _M_node(_Match_mode, _StateIdT); > > void > @@ -247,7 +248,7 @@ namespace __detail > return (_M_re._M_automaton->_M_options() & __m) == __m; > } > > - bool > + inline bool > _M_visited(_StateIdT __i) > { > if (_M_visited_states) > @@ -284,6 +285,7 @@ namespace __detail > bool _M_has_sol; > }; > > +_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) > ///@} regex-detail > } // namespace __detail > _GLIBCXX_END_NAMESPACE_VERSION > diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++- > v3/include/bits/regex_executor.tcc > index > 167a7a345300868ed5e0852e328569aec47e3d0d..87d5ac68685c22bbedcf > 9e67f96b50b61392a701 100644 > --- a/libstdc++-v3/include/bits/regex_executor.tcc > +++ b/libstdc++-v3/include/bits/regex_executor.tcc > @@ -36,6 +36,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr > namespace __detail > { > +_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > template<typename _BiIter, typename _Alloc, typename _TraitsT> > bool _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_search() > @@ -250,8 +251,14 @@ namespace __detail > // infinite loop by refusing to continue when it's already been > // visited more than twice. It's `twice` instead of `once` because > // we need to spare one more time for potential group capture. > + // > + // If the node cannot be re-entered anymore from the current state then > return > + // _S_invalid_state_id otherwise return the current state without going > + // through a vector, allowing the caller to decide what to do with the > state > + // This is beneficial for DFS since DFS can continue with the next state > + // immediately > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - void _Executor<_BiIter, _Alloc, _TraitsT>:: > + _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_rep_once_more(_Match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > @@ -263,7 +270,7 @@ namespace __detail > _M_frames.back()._M_count = __rep_count.second; > __rep_count.first = _M_current; > __rep_count.second = 1; > - _M_frames.emplace_back(_S_fopcode_next, __state._M_alt); > + return __state._M_alt; > } > else > { > @@ -271,9 +278,10 @@ namespace __detail > { > __rep_count.second++; > _M_frames.emplace_back(_S_fopcode_decrement_rep_count, > __i); > - _M_frames.emplace_back(_S_fopcode_next, __state._M_alt); > + return __state._M_alt; > } > } > + return _S_invalid_state_id; > } > > // _M_alt branch is "match once more", while _M_next is "get me out > @@ -281,8 +289,11 @@ 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> > - void _Executor<_BiIter, _Alloc, _TraitsT>:: > - _M_handle_repeat(_Match_mode, _StateIdT __i) > +#ifdef __OPTIMIZE__ > + [[__gnu__::__always_inline__]] > +#endif > + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > + _M_handle_repeat(_Match_mode __match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > // Greedy. > @@ -294,7 +305,7 @@ namespace __detail > _M_current); > else > _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > - _M_frames.emplace_back(_S_fopcode_rep_once_more, __i); > + return _M_rep_once_more(__match_mode, __i); > } > else // Non-greedy mode > { > @@ -303,7 +314,7 @@ namespace __detail > // vice-versa. > _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, > __i, > _M_current); > - _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > + return __state._M_next; > } > else > { > @@ -316,97 +327,122 @@ namespace __detail > // accepted state *must* be better than a solution that > // matches a non-greedy quantifier one more time. > > _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i); > - _M_frames.emplace_back(_S_fopcode_next, > __state._M_next); > + return __state._M_next; > } > } > } > + return _S_invalid_state_id; > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - void _Executor<_BiIter, _Alloc, _TraitsT>:: > +#ifdef __OPTIMIZE__ > + [[__gnu__::__always_inline__]] > +#endif > + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_subexpr_begin(_Match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > auto& __res = _M_cur_results[__state._M_subexpr]; > - _M_frames.emplace_back(_S_fopcode_restore_cur_results, > - static_cast<_StateIdT>(__state._M_subexpr), > - __res.first); > + if (_M_nfa._M_has_backref > + || __state._M_subexpr != 0 > + || _M_search_mode != _Search_mode::_DFS) > + _M_frames.emplace_back(_S_fopcode_restore_cur_results, > + static_cast<_StateIdT>(__state._M_subexpr), > + __res.first); > __res.first = _M_current; > - _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > + return __state._M_next; > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - void _Executor<_BiIter, _Alloc, _TraitsT>:: > +#ifdef __OPTIMIZE__ > + [[__gnu__::__always_inline__]] > +#endif > + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_subexpr_end(_Match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > auto& __res = _M_cur_results[__state._M_subexpr]; > - _M_frames.emplace_back(_S_fopcode_restore_cur_results, > - static_cast<_StateIdT>(__state._M_subexpr), > - __res.second); > - _M_frames.back()._M_subexpr_end = true; > - _M_frames.back()._M_matched = __res.matched; > + if (_M_nfa._M_has_backref > + || __state._M_subexpr != 0 > + || _M_search_mode != _Search_mode::_DFS) > + { > + _M_frames.emplace_back(_S_fopcode_restore_cur_results, > + static_cast<_StateIdT>(__state._M_subexpr), > + __res.second); > + _M_frames.back()._M_subexpr_end = true; > + _M_frames.back()._M_matched = __res.matched; > + } > + > __res.second = _M_current; > __res.matched = true; > - _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > + return __state._M_next; > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - inline void _Executor<_BiIter, _Alloc, _TraitsT>:: > + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_line_begin_assertion(_Match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > if (_M_at_begin()) > - _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > + return __state._M_next; > + return _S_invalid_state_id; > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - inline void _Executor<_BiIter, _Alloc, _TraitsT>:: > + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_line_end_assertion(_Match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > if (_M_at_end()) > - _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > + return __state._M_next; > + return _S_invalid_state_id; > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - inline void _Executor<_BiIter, _Alloc, _TraitsT>:: > + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_word_boundary(_Match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > if (_M_word_boundary() == !__state._M_neg) > - _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > + return __state._M_next; > + return _S_invalid_state_id; > } > > // Here __state._M_alt offers a single start node for a sub-NFA. > // We recursively invoke our algorithm to match the sub-NFA. > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - void _Executor<_BiIter, _Alloc, _TraitsT>:: > + _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_subexpr_lookahead(_Match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > if (_M_lookahead(__state._M_alt) == !__state._M_neg) > - _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > + return __state._M_next; > + return _S_invalid_state_id; > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - void _Executor<_BiIter, _Alloc, _TraitsT>:: > +#ifdef __OPTIMIZE__ > + [[__gnu__::__always_inline__]] > +#endif > + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_match(_Match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > if (_M_current == _M_end) > - return; > + return _S_invalid_state_id; > if (_M_search_mode == _Search_mode::_DFS) > { > if (__state._M_matches(*_M_current)) > { > ++_M_current; > - _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > + return __state._M_next; > } > } > else > if (__state._M_matches(*_M_current)) > _M_match_queue.emplace_back(__state._M_next, _M_cur_results); > + > + return _S_invalid_state_id; > } > > template<typename _BiIter, typename _TraitsT> > @@ -462,7 +498,7 @@ namespace __detail > // (_M_current, _M_current + (__submatch.second - __submatch.first)). > // If matched, keep going; else just return and try another state. > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - void _Executor<_BiIter, _Alloc, _TraitsT>:: > + _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_backref(_Match_mode, _StateIdT __i) > { > __glibcxx_assert(_M_search_mode == _Search_mode::_DFS); > @@ -470,7 +506,7 @@ namespace __detail > const auto& __state = _M_nfa[__i]; > auto& __submatch = _M_cur_results[__state._M_backref_index]; > if (!__submatch.matched) > - return; > + return _S_invalid_state_id; > auto __last = _M_current; > for (auto __tmp = __submatch.first; > __last != _M_end && __tmp != __submatch.second; > @@ -482,12 +518,17 @@ namespace __detail > __submatch.first, __submatch.second, _M_current, __last)) > { > _M_current = __last; > - _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > + return __state._M_next; > } > + > + return _S_invalid_state_id; > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - void _Executor<_BiIter, _Alloc, _TraitsT>:: > +#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) > @@ -528,7 +569,7 @@ namespace __detail > { > if (_M_current == _M_begin > && (_M_flags & regex_constants::match_not_null)) > - return; > + return _S_invalid_state_id; > if (__match_mode == _Match_mode::_Prefix || _M_current == > _M_end) > if (!_M_has_sol) > { > @@ -536,10 +577,14 @@ namespace __detail > _M_results = _M_cur_results; > } > } > + return _S_invalid_state_id; > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > - void _Executor<_BiIter, _Alloc, _TraitsT>:: > +#ifdef __OPTIMIZE__ > + [[__gnu__::__always_inline__]] > +#endif > + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > _M_handle_alternative(_Match_mode, _StateIdT __i) > { > const auto& __state = _M_nfa[__i]; > @@ -549,7 +594,7 @@ namespace __detail > // Pick lhs if it matches. Only try rhs if it doesn't. > _M_frames.emplace_back(_S_fopcode_fallback_next, > __state._M_next, > _M_current); > - _M_frames.emplace_back(_S_fopcode_next, __state._M_alt); > + return __state._M_alt; > } > else > { > @@ -557,7 +602,7 @@ namespace __detail > // See "case _S_opcode_accept:" handling above. > _M_frames.emplace_back(_S_fopcode_posix_alternative, > __state._M_next, > _M_current); > - _M_frames.emplace_back(_S_fopcode_next, __state._M_alt); > + return __state._M_alt; > } > } > > @@ -565,54 +610,69 @@ namespace __detail > #ifdef __OPTIMIZE__ > [[__gnu__::__always_inline__]] > #endif > - inline void _Executor<_BiIter, _Alloc, _TraitsT>:: > + inline _StateIdT _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 (_M_search_mode == _Search_mode::_BFS) > + if (_M_visited(__i)) > + return _S_invalid_state_id; > > + _StateIdT __next = _S_invalid_state_id; > switch (_M_nfa[__i]._M_opcode()) > { > case _S_opcode_repeat: > - _M_handle_repeat(__match_mode, __i); break; > + __next = _M_handle_repeat(__match_mode, __i); break; > case _S_opcode_subexpr_begin: > - _M_handle_subexpr_begin(__match_mode, __i); break; > + __next = _M_handle_subexpr_begin(__match_mode, __i); > + break; > case _S_opcode_subexpr_end: > - _M_handle_subexpr_end(__match_mode, __i); break; > + __next = _M_handle_subexpr_end(__match_mode, __i); > + break; > case _S_opcode_line_begin_assertion: > - _M_handle_line_begin_assertion(__match_mode, __i); break; > + __next = _M_handle_line_begin_assertion(__match_mode, __i); > break; > case _S_opcode_line_end_assertion: > - _M_handle_line_end_assertion(__match_mode, __i); break; > + __next = _M_handle_line_end_assertion(__match_mode, __i); break; > case _S_opcode_word_boundary: > - _M_handle_word_boundary(__match_mode, __i); break; > + __next = _M_handle_word_boundary(__match_mode, __i); break; > case _S_opcode_subexpr_lookahead: > - _M_handle_subexpr_lookahead(__match_mode, __i); break; > + __next = _M_handle_subexpr_lookahead(__match_mode, __i); > break; > case _S_opcode_match: > - _M_handle_match(__match_mode, __i); break; > + __next = _M_handle_match(__match_mode, __i); break; > case _S_opcode_backref: > if (_M_search_mode == _Search_mode::_DFS) > - _M_handle_backref(__match_mode, __i); > + __next = _M_handle_backref(__match_mode, __i); > else > __builtin_unreachable(); > break; > case _S_opcode_accept: > - _M_handle_accept(__match_mode, __i); break; > + __next = _M_handle_accept(__match_mode, __i); break; > case _S_opcode_alternative: > - _M_handle_alternative(__match_mode, __i); break; > + __next = _M_handle_alternative(__match_mode, __i); break; > default: > __glibcxx_assert(false); > } > + return __next; > } > > template<typename _BiIter, typename _Alloc, typename _TraitsT> > 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); > + _StateIdT __next = __start; > > - while (!_M_frames.empty()) > + while (true) > { > + // Follow immediate successors without re-entering the frame > + // 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); > + > + if (_M_frames.empty()) > + break; > + > _ExecutorFrame<_BiIter> __frame = std::move(_M_frames.back()); > _M_frames.pop_back(); > > @@ -621,27 +681,27 @@ namespace __detail > case _S_fopcode_fallback_next: > if (_M_has_sol) > break; > - if (__dfs_mode) > + if (_M_search_mode == _Search_mode::_DFS) > _M_current = __frame._M_pos; > [[__fallthrough__]]; > case _S_fopcode_next: > - _M_node(__match_mode, __frame._M_state_id); > + __next = __frame._M_state_id; > break; > > case _S_fopcode_fallback_rep_once_more: > if (_M_has_sol) > break; > - if (__dfs_mode) > + if (_M_search_mode == _Search_mode::_DFS) > _M_current = __frame._M_pos; > [[__fallthrough__]]; > case _S_fopcode_rep_once_more: > - _M_rep_once_more(__match_mode, __frame._M_state_id); > + __next = _M_rep_once_more(__match_mode, > __frame._M_state_id); > break; > > 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) > + __next = __frame._M_state_id; > + if (_M_search_mode == _Search_mode::_DFS) > _M_current = __frame._M_pos; > _M_has_sol = false; > break; > @@ -695,6 +755,7 @@ namespace __detail > > return __left_is_word != __right_is_word; > } > +_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) > } // namespace __detail > #pragma GCC diagnostic pop > > > > --
