RE: [patch v2 1/4][libstdc++]: Continue with regex DFS traversals without next frames [PR126274]

> -----Original Message-----
> From: Patrick Palka <[email protected]>
> Sent: 20 August 2026 15:31
> To: Tamar Christina <[email protected]>
> Cc: [email protected]; nd <[email protected]>; [email protected];
> [email protected]; [email protected]
> Subject: Re: [patch v2 1/4][libstdc++]: Continue with regex DFS traversals
> without next frames [PR126274]
> 
> On Tue, Aug 18, 2026 at 3:35 AM Tamar Christina
> <[email protected]> wrote:
> >
> > > -----Original Message-----
> > > From: Patrick Palka <[email protected]>
> > > Sent: 30 July 2026 05:28
> > > To: Tamar Christina <[email protected]>
> > > Cc: [email protected]; nd <[email protected]>; [email protected];
> > > [email protected]; [email protected]; [email protected]
> > > Subject: Re: [patch v2 1/4][libstdc++]: Continue with regex DFS traversals
> > > without next frames [PR126274]
> > >
> > > On Wed, 29 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 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_executor.h b/libstdc++-
> > > v3/include/bits/regex_executor.h
> > > > index
> > >
> 797ad702784b6d1bf07734d91683946d989630f5..23fe828078a32194d99
> > > 6aeb3bfc37e2c46513c41 100644
> > > > --- a/libstdc++-v3/include/bits/regex_executor.h
> > > > +++ b/libstdc++-v3/include/bits/regex_executor.h
> > > > @@ -86,6 +86,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 ever 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()];
> > > >        }
> > > > @@ -113,43 +118,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 +252,7 @@ namespace __detail
> > > >     return (_M_re._M_automaton->_M_options() & __m) == __m;
> > > >        }
> > > >
> > > > -      bool
> > > > +      inline bool
> > > >        _M_visited(_StateIdT __i)
> > > >        {
> > > >     if (_M_visited_states)
> > > > diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-
> > > v3/include/bits/regex_executor.tcc
> > > > index
> > >
> 167a7a345300868ed5e0852e328569aec47e3d0d..ed53df63a5a304f1db04
> > > c3519b986f0e5750e3f5 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
> > > > @@ -281,8 +288,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 +304,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 +313,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 +326,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);
> > >
> > > On second thought is this certainly a win?  I worry this optimization is
> > > not worth the overhead, it avoids just two restore_cur_results frames
> > > (for the implicit outermost capture group) at the expense of additional
> > > memory accesses and instructions every time we enter any capture group.
> > >
> >
> > It looks like it's giving 5% on both the email and URI test at both -O2 and -
> O3.
> > So It does seem worth having.
> >
> > > >        __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 +497,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 +505,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 +517,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 +568,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 +576,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 +593,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 +601,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,50 +609,63 @@ 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);
> > > >     }
> > > > +      if (_M_search_mode == _Search_mode::_BFS)
> > > > +   {
> > > > +     if (__next != _S_invalid_state_id)
> > > > +       _M_frames.emplace_back(_S_fopcode_next, __next);
> > > > +     return _S_invalid_state_id;
> > >
> > > I don't see why we can't also return the next state when in BFS mode?
> > > As long as _M_dfs continues to handle a returned state id as if a next
> > > frame was pushed to the top of the stack it shouldn't matter whether
> > > we're in BFS or DFS mode.
> >
> > That's fair. I've refactored this now.
> >
> > >
> > > > +   }
> > > > +      else
> > > > +   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);
> > > >
> > > >        while (!_M_frames.empty())
> > > > @@ -621,27 +678,49 @@ 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);
> > > > +         if (_M_search_mode == _Search_mode::_DFS)
> > > > +           // Follow immediate successors without re-entering the frame
> > > > +           // loop until 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_node(__match_mode, __next);
> > > > +         else
> > > > +           _M_node(__match_mode, __frame._M_state_id);
> > >
> > > I don't see why we can't do the loop in BFS mode.  BFS mode handles a
> > > next frame on the top of the stack the same as DFS does -- it
> > > immediately pops it and evaluates it via _M_node.  We should be able to
> > > do the fast path in BFS mode unless I'm missing something.
> > >
> > > >           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);
> > > > +         {
> > > > +           _StateIdT __next
> > > > +             = _M_rep_once_more(__match_mode,
> > > __frame._M_state_id);
> > > > +           if (_M_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.  Splitting this in a
> > > > +             // specialized path preserves the behavior for both but for
> > > > +             // DFS it avoids the intermediate allocations.
> > > > +             for (; __next != _S_invalid_state_id;)
> > > > +               __next = _M_node(__match_mode, __next);
> > > > +           else if (__next != _S_invalid_state_id)
> > > > +             _M_frames.emplace_back(_S_fopcode_next, __next);
> > >
> > > Ditto.
> > >
> > > Rather than having two such fast paths, we could just have a single one
> > > at the top of _M_dfs so that _M_dfs looks like:
> >
> > Ack.
> >
> > Done, sending v3.
> 
> Has v3 been sent already? I don't see it in my inbox or on the ML

Ah no, let me finish the cover letter updates and send it out.

Thanks,
Tamar
> 
> >
> > Thanks for the reviews!
> >
> > Tamar
> > >
> > >     _M_dfs(_Match_mode __match_mode, _StateIdT __start)
> > >     {
> > >        _StateIdT __next = __start;
> > >
> > >        while (true)
> > >         {
> > >           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();
> > >
> > >           switch (__frame._M_op)
> > >             {
> > >               case _S_fopcode_rep_once_more:
> > >                 ...
> > >                 __next = _M_rep_once_more(...);
> > >                 ...
> > >                 break;
> > >
> > >               case _S_fopcode_posix_alternative:
> > >                 ...
> > >                 __next = __frame._M_state_id;
> > >                 ...
> > >                 break;
> > >
> > >               ...
> > >             }
> > >          }
> > >     }
> > >
> > > This way, we also avoid needing to push a frame for the start state.
> > >
> > > For the ABI issue we probably should just wrap the entirety of _Executor
> > > in regex.h, regex_executor.{h,tcc} with
> > >
> > > _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
> > > ...
> > > _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> > >
> > > to give all its member functions different manglings (even if not all of
> > > them need it).
> > >
> > > > +         }
> > > >           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)
> > > > +         if (_M_search_mode == _Search_mode::_DFS)
> > > >             _M_current = __frame._M_pos;
> > > >           _M_has_sol = false;
> > > >           break;
> > > >
> > > >
> > > > --
> > > >
> >