https://gcc.gnu.org/bugzilla/show_bug.cgi?id=126274
--- Comment #7 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Tamar Christina <[email protected]>: https://gcc.gnu.org/g:dc65d88cdf15f3538fdcfd1d174c845474989533 commit r17-4552-gdc65d88cdf15f3538fdcfd1d174c845474989533 Author: Tamar Christina <[email protected]> Date: Tue Sep 22 07:19:56 2026 +0100 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 __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 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. * include/bits/regex.h (class _Executor): Move to V2 ABI.
