Ping
> -----Original Message----- > From: Tamar Christina > Sent: 20 August 2026 18:14 > To: [email protected] > Cc: nd <[email protected]>; [email protected]; [email protected]; > [email protected]; [email protected] > Subject: [patch v3 4/4][libstdc++]: Inline simple regex repeating matches in > DFS [PR126274] > > Optimize the common DFS NFA shape repeat -> match -> repeat, which is > produced > by repeated character classes such as [\w]+, [^\s?#]+, and #+. > > Since the second patch the DFS continuation already avoids pushing a > separate > _S_fopcode_next frame for many states. This patch adds a small > improvement > for greedy repeats. > > After creating the same fallback and repeat bookkeeping frames as before, if > the repeated body is a single match state that returns to the repeat state, > consume that match state immediately and continue at the repeat. > > Backtracking behavior is unchanged. _M_rep_once_more still creates the > restore/decrement frames, and the repeat exit fallback is still saved before > trying the body. If the body match fails, the helper returns > _S_invalid_state_id so the normal frame loop restores repeat state and tries > pending fallbacks. > > Benchmarks improvements compared to GCC previous patch in series: > > at -O2: > > email: +4.7% > URI: +5.1% > IPv4 -1.1% > > at -O3: > > email: +4.5%, > URI: +4.1% > IPv4: -0.2% > > And finally gets us better than GCC 15. > > I outlined the helper into _M_match_simple_repeat_body since that > looks more readable. > > 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 (_M_match_simple_repeat_body): > New. > * include/bits/regex_executor.tcc (_M_dfs_next): Inline consume > matches > on _S_opcode_repeat. > (_M_match_simple_repeat_body): New. > > --- > diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++- > v3/include/bits/regex_executor.h > index > c2dce4e24d35807b311d5a3273297f72a74cc24d..7b9f86ce315a11c2336ac > a3e17ca05001f1fc35d 100644 > --- a/libstdc++-v3/include/bits/regex_executor.h > +++ b/libstdc++-v3/include/bits/regex_executor.h > @@ -140,6 +140,9 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > _StateIdT > _M_rep_once_more(_Match_mode __match_mode, _StateIdT); > > + _StateIdT > + _M_match_simple_repeat_body(_StateIdT, _StateIdT); > + > template<_Search_mode __search_mode> > _StateIdT > _M_handle_repeat(_Match_mode, _StateIdT); > diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++- > v3/include/bits/regex_executor.tcc > index > 2c03c6bfe9377ac66bffc0f3d9350d5d5cc35468..6c7255ce6be17d8e2682e4 > 1cce67799fb9caf79a 100644 > --- a/libstdc++-v3/include/bits/regex_executor.tcc > +++ b/libstdc++-v3/include/bits/regex_executor.tcc > @@ -379,6 +379,31 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > return _S_invalid_state_id; > } > > + // Try to consume the common repeat body shape > + // repeat -> match -> repeat > + // without going through the generic state dispatch again. > + template<typename _BiIter, typename _Alloc, typename _TraitsT> > +#ifdef __OPTIMIZE__ > + [[__gnu__::__always_inline__]] > +#endif > + inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>:: > + _M_match_simple_repeat_body(_StateIdT __next, _StateIdT __repeat) > + { > + if (__next == _S_invalid_state_id) > + return _S_invalid_state_id; > + > + const auto& __state = _M_nfa[__next]; > + if (__state._M_opcode() != _S_opcode_match > + || __state._M_next != __repeat) > + return __next; > + > + if (_M_current == _M_end || !__state._M_matches(*_M_current)) > + return _S_invalid_state_id; > + > + ++_M_current; > + return __repeat; > + } > + > // _M_alt branch is "match once more", while _M_next is "get me out > // of this quantifier". Executing _M_next first or _M_alt first don't > // mean the same thing, and we need to choose the correct order under > @@ -401,7 +426,11 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > _M_current); > else > _M_frames.emplace_back(_S_fopcode_next, __state._M_next); > - return _M_rep_once_more(__match_mode, __i); > + _StateIdT __next = _M_rep_once_more(__match_mode, __i); > + if constexpr (__search_mode == _Search_mode::_Dfs) > + return _M_match_simple_repeat_body(__next, __i); > + else > + return __next; > } > else // Non-greedy mode > { > > > --
