[patch 2/4][libstdc++]: Continue with regex DFS traversals without next frames [PR126274]
Patrick Palka
ppalka@redhat.com
Tue Jul 21 03:05:18 GMT 2026
On Thu, 16 Jul 2026, Tamar Christina wrote:
> 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 patch keeps the new frame based executor, however adds a fast path
> for _M_rep_once_more cases. This is done by having _M_rep_once_more
> return the state as return value, and have the caller decide what to
> do with it. BFS does not change and immediately stores the frame.
>
> For DFS we try to consume the state immediately until we're told to
> stop.
>
> 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.
>
> Benchmark improvements vs GCC 16:
> email: 53.7%
> URI: 52.8%
> IPv4: 44.4%
>
> 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): Return state.
> (_M_dfs_next): New.
> * include/bits/regex_executor.tcc (_M_rep_once_more): Return state.
> (_M_dfs_next): New.
> (_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_executor.h b/libstdc++-v3/include/bits/regex_executor.h
> index f6e55f2f4aaa8fb3fa8d963b04d5bcf0b3b191d3..0a63b9b83789a700de63081ee61a7857028548e0 100644
> --- a/libstdc++-v3/include/bits/regex_executor.h
> +++ b/libstdc++-v3/include/bits/regex_executor.h
> @@ -87,6 +87,11 @@ namespace __detail
> using namespace regex_constants;
> if (__flags & match_prev_avail) // ignore not_bol and not_bow
> _M_flags &= ~(match_not_bol | match_not_bow);
> + // Reserve NFA sized frames up front to prevent having to constantly
> + // reallocate frames. To avoid an explosion in state with large regexp
> + // before any matching is every done limit the reservation to 256.
> + // This should cover a large class of regexp.
> + _M_frames.reserve(std::min<size_t>(_M_nfa.size(), 256));
> if (_M_search_mode == _Search_mode::_BFS)
> _M_visited_states = new bool[_M_nfa.size()];
> }
> @@ -114,7 +119,7 @@ namespace __detail
> _M_search();
>
> private:
> - void
> + _StateIdT
> _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
>
> template<_Search_mode __search_mode>
> @@ -157,6 +162,9 @@ namespace __detail
> void
> _M_node(_Match_mode, _StateIdT);
>
> + _StateIdT
> + _M_dfs_next(_Match_mode, _StateIdT);
> +
> template<_Search_mode __search_mode>
> void
> _M_dfs(_Match_mode __match_mode, _StateIdT __start);
> diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
> index 86f6c6240853d673f47099a5fd15fe84fc99316e..bf0594912688e0014a5928b6c6d600af6f80b31a 100644
> --- a/libstdc++-v3/include/bits/regex_executor.tcc
> +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> @@ -250,8 +250,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 +269,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 +277,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
> @@ -611,6 +618,121 @@ namespace __detail
> }
> }
>
> +
> + // Execute one DFS state in a form optimized for immediate progress.
> + //
> + // Returning a state id means "continue with this successor now". Returning
> + // _S_invalid_state_id means the helper either failed this path or delegated
> + // to the generic frame-based handler, so the outer DFS loop should pop the
> + // next pending frame.
> + //
> + // The helper is intentionally small and it's intended to cover states that
> + // are common in scanning regexes and have an obvious preferred successor.
> + // For example, in "[\w]+://" most successful work is: enter repeat, consume
> + // a match state, repeat, then try the literal ':' path.
> + // The key is to avoid a push/pop for each immediate _S_fopcode_next. When
> + // it sees a state whose behavior that's not an obvious direct match it calls
> + // _M_node<_Search_mode::_DFS> and resumes the normal flow.
This helper seems to be just duplicating the logic of the existing
_M_handle_foo handlers. Couldn't we just generally make _M_handle_foo
always return the next state rather than pushing a 'next' frame (when
possible, otherwise return _S_invalid_state_id, like this _M_dfs_next
does) and have a generic fast path near the top of the _M_dfs loop
that iteratively calls _M_node until _S_invalid_state_id is returned?
We could also get rid of the _S_fopcode_rep_once_more frame and have
_M_handle_repeat call _M_rep_once_more directly so that we can in turn
make _M_handle_repeat always return the 'next' state rather than pushing
another frame.
> + template<typename _BiIter, typename _Alloc, typename _TraitsT>
> +#ifdef __OPTIMIZE__
> + [[__gnu__::__always_inline__]]
> +#endif
> + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> + _M_dfs_next(_Match_mode __match_mode, _StateIdT __i)
> + {
> + const auto& __state = _M_nfa[__i];
> +
> + switch (__state._M_opcode())
> + {
> + case _S_opcode_subexpr_begin:
> + // Capture group 0 is the whole match. Without backreferences no
> + // later state can observe the old group-0 boundary during
> + // backtracking, so continue directly with the next state.
> + //
> + // Example: for regex_search with "[0-9]+", only the final group-0
> + // boundaries are reported; there is no backref that can read
> + // an intermediate group-0 value.
> + if (!_M_nfa._M_has_backref && __state._M_subexpr == 0)
This seems like an optimization that _M_handle_subexpr_begin/end could
also benefit from -- for capture group 0 we don't bother pushing a
restore_cur_results frame, IIUC?
> + {
> + _M_cur_results[0].first = _M_current;
> + return __state._M_next;
> + }
> + break;
> +
> + case _S_opcode_subexpr_end:
> + // Same group-0 shortcut for the end boundary. For other capture
> + // groups we delegate to _M_node so their old values are restored
> + // correctly when a later alternative fails. For example, in
> + // "(a|ab)c" the capture for group 1 may need to roll back from "a"
> + // to try "ab" so the shortcut cannot be used.
> + if (!_M_nfa._M_has_backref && __state._M_subexpr == 0)
> + {
> + auto& __res = _M_cur_results[0];
> + __res.second = _M_current;
> + __res.matched = true;
> + return __state._M_next;
> + }
> + break;
> +
> + case _S_opcode_match:
> + // Consume one character and return the next state instead of pushing
> + // _S_fopcode_next. On a long input matched by e.g. "#+", this
> + // removes one frame round trip per consumed '#'.
> + if (_M_current != _M_end && __state._M_matches(*_M_current))
> + {
> + ++_M_current;
> + return __state._M_next;
> + }
> + return _S_invalid_state_id;
> +
> + case _S_opcode_accept:
> + // Accept needs to store the frame, so call the generic handler and
> + // stop any linear consumptions in the optimized paths.
> + _M_handle_accept<_Search_mode::_DFS>(__match_mode, __i);
> + return _S_invalid_state_id;
> +
> + case _S_opcode_repeat:
> + // For greedy repeats, DFS should try the body first and remember the
> + // exit as a fallback. Example: for "[0-9]+" at "123x", keep the
> + // "exit repeat" state on the stack, but immediately continue into the
> + // digit-matching body. When the body later fails at 'x', the
> + // fallback accepts the repeat at the position after '3'.
> + if (!__state._M_neg)
> + {
> + _M_frames.emplace_back(_S_fopcode_fallback_next,
> + __state._M_next, _M_current);
> + return _M_rep_once_more(__match_mode, __i);
> + }
> + else
> + {
> + _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> + __i, _M_current);
> + return __state._M_next;
> + }
> +
> + case _S_opcode_alternative:
> + // ECMAScript alternatives are ordered. Try _M_alt first and keep _M_next
> + // as a fallback, e.g. "foo|fo" should prefer "foo" if it succeeds.
> + // If the preferred arm fails, the fallback restores _M_current and
> + // tries the other arm. POSIX alternatives require longest-match
> + // merging, so they stay on the generic path.
> + if (_M_nfa._M_flags & regex_constants::ECMAScript)
> + {
> + _M_frames.emplace_back(_S_fopcode_fallback_next,
> + __state._M_next, _M_current);
> + return __state._M_alt;
> + }
> + break;
> +
> + default:
> + break;
> + }
> +
> + // Any opcode not handled above still uses the existing mechanism
> + _M_node<_Search_mode::_DFS>(__match_mode, __i);
> + return _S_invalid_state_id;
> + }
> +
> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> template<_Search_mode __search_mode>
> void _Executor<_BiIter, _Alloc, _TraitsT>::
> @@ -632,7 +754,15 @@ namespace __detail
> _M_current = __frame._M_pos;
> [[__fallthrough__]];
> case _S_fopcode_next:
> - _M_node<__search_mode>(__match_mode, __frame._M_state_id);
> + if constexpr (__search_mode == _Search_mode::_DFS)
> + // Follow immediate successors without re-entering the frame
> + // loop untill we fail. This avoids the needless state save and
> + // restore through memory.
> + for (_StateIdT __next = __frame._M_state_id;
> + __next != _S_invalid_state_id;)
> + __next = _M_dfs_next(__match_mode, __next);
> + else
> + _M_node<_Search_mode::_BFS>(__match_mode, __frame._M_state_id);
> break;
>
> case _S_fopcode_fallback_rep_once_more:
> @@ -642,7 +772,21 @@ namespace __detail
> _M_current = __frame._M_pos;
> [[__fallthrough__]];
> case _S_fopcode_rep_once_more:
> - _M_rep_once_more(__match_mode, __frame._M_state_id);
> + {
> + _StateIdT __next
> + = _M_rep_once_more(__match_mode, __frame._M_state_id);
> + if constexpr (__search_mode == _Search_mode::_DFS)
> + // _M_rep_once_more returned the repeated body's start state.
> + // Continue directly in DFS; BFS must materialize the state as
> + // a queue/frame item because it advances by input position
> + // rather than by backtracking order. Splittig this in a
> + // specialized path preserves the behavior for both but has
> + // DFS avoids the intermediate allocations.
> + for (; __next != _S_invalid_state_id;)
> + __next = _M_dfs_next(__match_mode, __next);
> + else if (__next != _S_invalid_state_id)
> + _M_frames.emplace_back(_S_fopcode_next, __next);
> + }
> break;
>
> case _S_fopcode_posix_alternative:
>
>
> --
>
More information about the Libstdc++
mailing list