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..7b9f86ce315a11c2336aca3e17ca05001f1fc35d
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..6c7255ce6be17d8e2682e41cce67799fb9caf79a
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
{
--
diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index c2dce4e24d35807b311d5a3273297f72a74cc24d..7b9f86ce315a11c2336aca3e17ca05001f1fc35d 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..6c7255ce6be17d8e2682e41cce67799fb9caf79a 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
{
