> -----Original Message-----
> From: Jonathan Wakely <[email protected]>
> Sent: 20 July 2026 17:06
> To: Tamar Christina <[email protected]>
> Cc: [email protected]; nd <[email protected]>; [email protected];
> [email protected]; [email protected]
> Subject: Re: [patch 2/4][libstdc++]: Continue with regex DFS traversals
> without next frames [PR126274]
>
> On Thu, 16 Jul 2026 at 15:31, Tamar Christina <[email protected]>
> 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?
>
> Some minor comments below while Patrick reviews this series and we
> confirm the benefits at -O2 ...
>
> >
> > 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..0a63b9b83789a700de630
> 81ee61a7857028548e0 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.
>
> "is ever done" ?
>
> > + // This should cover a large class of regexp.
> > + _M_frames.reserve(std::min<size_t>(_M_nfa.size(), 256));
>
> Was 256 determined empirically? It seems quite high to me.
> The geometric growth policy of std::vector should mean it doesn't
> _constantly_ reallocate frames. We'll reallocate frequently while the
> number of frames is small, but as the size increases we'll end up
> allocating larger blocks and need to reallocate less often.
>
No, this was completely arbitrary and was just that I didn't know how
big the typical nfa size is in practice. There's definitely the possibility
that this isn't that expensive. Let me drop it and see if I see anything
meaningful.
I'm respinning the patches now with Patrick's review changes and will
try this at the same time.
Thanks,
Tamar
>
> > 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..bf0594912688e0014a592
> 8b6c6d600af6f80b31a 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.
> > + 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)
> > + {
> > + _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
>
> "until"
>
> > + // 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
>
> "Splitting"
>
> > + // specialized path preserves the behavior for both but
> > has
> > + // DFS avoids the intermediate allocations.
>
> I think this should be "avoid" not "avoids"?
> Or maybe "but for DFS it avoids the ..."
>
> > + 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:
> >
> >
> > --
