In GCC 16 the commit r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20
caused a big regression in performance of regex in libstdc++.
This and other patches were tested using the CPP version of the benchmarks
at https://github.com/mariomka/regex-benchmark/
The benchmark uses regex_token_iterator over the input text with these patterns:
- email: [\w.+-]+@[\w.-]+\.[\w.-]+
- URI: [\w]+:\/\/[^\/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?
- IPv4:
(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])
Where it tests various types of regexpr. "email" has no backtracking so it's the
simplest NFA possible which we should be able to handle quickly.
"uri" has optional matches and some non capturing groups and "ipv4" adds some
alternative matching to the equation.
The input string is a 6.52 mb test file "input-text.txt"
The regressions of each type of regexpr compared to GCC 15 are:
email: 118.9%
URI: 124.8%
IPv4: 139.8%
So most matches became > 2x slower.
This patch series addresses the regressions and gets the new code to be
ultimately faster than the GCC 15 implementation.
Currently the _Executor class implements both a DFS and a BFS traveral mode
for the regex matching. It has a parameter _M_search_mode which it uses
inside the _Executor functions to separate out the implementations.
However this parameter is rather opague to IPA and so for each implementation
the other branch is always dead but they haven't been folded away.
This increases the number of dynamic instructions and branches being executed
and the branches seem to be often mispredicted.
The patch fixes it by moving _Search_mode out of the class and making it a
template parameter instead so we can at compile time fold away the two
implementations. This removes all the extra compare and branches from the
hot functions.
These changes improve the benchmarks compared with GCC 16 with
email: 17.8%
URI: 16.8%
IPv4: 8.9%
On Neoverse-V1
So 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!
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 (_Search_mode): Move to top level.
(_M_handle_repeat, _M_handle_match, _M_handle_accept, _M_node, _M_dfs):
Add template parameter.
(_M_visited): Add inline keyword.
* include/bits/regex_executor.tcc (_M_handle_repeat, _M_handle_match,
_M_handle_accept, _M_node, _M_dfs): Use template parameter.
---
diff --git a/libstdc++-v3/include/bits/regex_executor.h
b/libstdc++-v3/include/bits/regex_executor.h
index
797ad702784b6d1bf07734d91683946d989630f5..f6e55f2f4aaa8fb3fa8d963b04d5bcf0b3b191d3
100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -50,10 +50,11 @@ namespace __detail
* The %_Executor class has two modes: DFS mode and BFS mode, controlled
* by the function parameter %__search_mode.
*/
+ enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
+
template<typename _BiIter, typename _Alloc, typename _TraitsT>
class _Executor
{
- enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
enum class _Match_mode : unsigned char { _Exact, _Prefix };
public:
@@ -116,7 +117,8 @@ namespace __detail
void
_M_rep_once_more(_Match_mode __match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_handle_repeat(_Match_mode, _StateIdT);
void
@@ -137,22 +139,26 @@ namespace __detail
void
_M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_handle_match(_Match_mode, _StateIdT);
void
_M_handle_backref(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_handle_accept(_Match_mode, _StateIdT);
void
_M_handle_alternative(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_node(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_dfs(_Match_mode __match_mode, _StateIdT __start);
bool
@@ -247,7 +253,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..86f6c6240853d673f47099a5fd15fe84fc99316e
100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -165,7 +165,7 @@ namespace __detail
_M_has_sol = false;
*_M_get_sol_pos() = _BiIter();
_M_cur_results = _M_results;
- _M_dfs(__match_mode, _M_start);
+ _M_dfs<_Search_mode::_DFS>(__match_mode, _M_start);
return _M_has_sol;
}
@@ -208,7 +208,7 @@ namespace __detail
for (auto& __task : __old_queue)
{
_M_cur_results = _ResultsVec(std::move(__task.second), __alloc);
- _M_dfs(__match_mode, __task.first);
+ _M_dfs<_Search_mode::_BFS>(__match_mode, __task.first);
}
if (__match_mode == _Match_mode::_Prefix)
__ret |= _M_has_sol;
@@ -281,6 +281,7 @@ 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>
+ template<_Search_mode __search_mode>
void _Executor<_BiIter, _Alloc, _TraitsT>::
_M_handle_repeat(_Match_mode, _StateIdT __i)
{
@@ -288,7 +289,7 @@ namespace __detail
// Greedy.
if (!__state._M_neg)
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
// If it's DFS executor and already accepted, we're done.
_M_frames.emplace_back(_S_fopcode_fallback_next, __state._M_next,
_M_current);
@@ -298,7 +299,7 @@ namespace __detail
}
else // Non-greedy mode
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
{
// vice-versa.
_M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i,
@@ -390,13 +391,14 @@ namespace __detail
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
void _Executor<_BiIter, _Alloc, _TraitsT>::
_M_handle_match(_Match_mode, _StateIdT __i)
{
const auto& __state = _M_nfa[__i];
if (_M_current == _M_end)
return;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
{
if (__state._M_matches(*_M_current))
{
@@ -487,10 +489,11 @@ namespace __detail
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
void _Executor<_BiIter, _Alloc, _TraitsT>::
_M_handle_accept(_Match_mode __match_mode, _StateIdT)
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
{
__glibcxx_assert(!_M_has_sol);
if (__match_mode == _Match_mode::_Exact)
@@ -562,19 +565,23 @@ namespace __detail
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
inline void _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 constexpr (__search_mode == _Search_mode::_BFS)
+ if (_M_visited(__i))
+ return;
switch (_M_nfa[__i]._M_opcode())
{
case _S_opcode_repeat:
- _M_handle_repeat(__match_mode, __i); break;
+ _M_handle_repeat<__search_mode>(__match_mode, __i); break;
case _S_opcode_subexpr_begin:
_M_handle_subexpr_begin(__match_mode, __i); break;
case _S_opcode_subexpr_end:
@@ -588,15 +595,15 @@ namespace __detail
case _S_opcode_subexpr_lookahead:
_M_handle_subexpr_lookahead(__match_mode, __i); break;
case _S_opcode_match:
- _M_handle_match(__match_mode, __i); break;
+ _M_handle_match<__search_mode>(__match_mode, __i); break;
case _S_opcode_backref:
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
_M_handle_backref(__match_mode, __i);
else
__builtin_unreachable();
break;
case _S_opcode_accept:
- _M_handle_accept(__match_mode, __i); break;
+ _M_handle_accept<__search_mode>(__match_mode, __i); break;
case _S_opcode_alternative:
_M_handle_alternative(__match_mode, __i); break;
default:
@@ -605,10 +612,10 @@ namespace __detail
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
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,17 +628,17 @@ namespace __detail
case _S_fopcode_fallback_next:
if (_M_has_sol)
break;
- if (__dfs_mode)
+ if constexpr (__search_mode == _Search_mode::_DFS)
_M_current = __frame._M_pos;
[[__fallthrough__]];
case _S_fopcode_next:
- _M_node(__match_mode, __frame._M_state_id);
+ _M_node<__search_mode>(__match_mode, __frame._M_state_id);
break;
case _S_fopcode_fallback_rep_once_more:
if (_M_has_sol)
break;
- if (__dfs_mode)
+ if constexpr (__search_mode == _Search_mode::_DFS)
_M_current = __frame._M_pos;
[[__fallthrough__]];
case _S_fopcode_rep_once_more:
@@ -641,7 +648,7 @@ namespace __detail
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 constexpr (__search_mode == _Search_mode::_DFS)
_M_current = __frame._M_pos;
_M_has_sol = false;
break;
--
diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index 797ad702784b6d1bf07734d91683946d989630f5..f6e55f2f4aaa8fb3fa8d963b04d5bcf0b3b191d3 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -50,10 +50,11 @@ namespace __detail
* The %_Executor class has two modes: DFS mode and BFS mode, controlled
* by the function parameter %__search_mode.
*/
+ enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
+
template<typename _BiIter, typename _Alloc, typename _TraitsT>
class _Executor
{
- enum class _Search_mode : unsigned char { _BFS = 0, _DFS = 1 };
enum class _Match_mode : unsigned char { _Exact, _Prefix };
public:
@@ -116,7 +117,8 @@ namespace __detail
void
_M_rep_once_more(_Match_mode __match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_handle_repeat(_Match_mode, _StateIdT);
void
@@ -137,22 +139,26 @@ namespace __detail
void
_M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_handle_match(_Match_mode, _StateIdT);
void
_M_handle_backref(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_handle_accept(_Match_mode, _StateIdT);
void
_M_handle_alternative(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_node(_Match_mode, _StateIdT);
- void
+ template<_Search_mode __search_mode>
+ void
_M_dfs(_Match_mode __match_mode, _StateIdT __start);
bool
@@ -247,7 +253,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..86f6c6240853d673f47099a5fd15fe84fc99316e 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -165,7 +165,7 @@ namespace __detail
_M_has_sol = false;
*_M_get_sol_pos() = _BiIter();
_M_cur_results = _M_results;
- _M_dfs(__match_mode, _M_start);
+ _M_dfs<_Search_mode::_DFS>(__match_mode, _M_start);
return _M_has_sol;
}
@@ -208,7 +208,7 @@ namespace __detail
for (auto& __task : __old_queue)
{
_M_cur_results = _ResultsVec(std::move(__task.second), __alloc);
- _M_dfs(__match_mode, __task.first);
+ _M_dfs<_Search_mode::_BFS>(__match_mode, __task.first);
}
if (__match_mode == _Match_mode::_Prefix)
__ret |= _M_has_sol;
@@ -281,6 +281,7 @@ 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>
+ template<_Search_mode __search_mode>
void _Executor<_BiIter, _Alloc, _TraitsT>::
_M_handle_repeat(_Match_mode, _StateIdT __i)
{
@@ -288,7 +289,7 @@ namespace __detail
// Greedy.
if (!__state._M_neg)
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
// If it's DFS executor and already accepted, we're done.
_M_frames.emplace_back(_S_fopcode_fallback_next, __state._M_next,
_M_current);
@@ -298,7 +299,7 @@ namespace __detail
}
else // Non-greedy mode
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
{
// vice-versa.
_M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i,
@@ -390,13 +391,14 @@ namespace __detail
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
void _Executor<_BiIter, _Alloc, _TraitsT>::
_M_handle_match(_Match_mode, _StateIdT __i)
{
const auto& __state = _M_nfa[__i];
if (_M_current == _M_end)
return;
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
{
if (__state._M_matches(*_M_current))
{
@@ -487,10 +489,11 @@ namespace __detail
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
void _Executor<_BiIter, _Alloc, _TraitsT>::
_M_handle_accept(_Match_mode __match_mode, _StateIdT)
{
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
{
__glibcxx_assert(!_M_has_sol);
if (__match_mode == _Match_mode::_Exact)
@@ -562,19 +565,23 @@ namespace __detail
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
#ifdef __OPTIMIZE__
[[__gnu__::__always_inline__]]
#endif
inline void _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 constexpr (__search_mode == _Search_mode::_BFS)
+ if (_M_visited(__i))
+ return;
switch (_M_nfa[__i]._M_opcode())
{
case _S_opcode_repeat:
- _M_handle_repeat(__match_mode, __i); break;
+ _M_handle_repeat<__search_mode>(__match_mode, __i); break;
case _S_opcode_subexpr_begin:
_M_handle_subexpr_begin(__match_mode, __i); break;
case _S_opcode_subexpr_end:
@@ -588,15 +595,15 @@ namespace __detail
case _S_opcode_subexpr_lookahead:
_M_handle_subexpr_lookahead(__match_mode, __i); break;
case _S_opcode_match:
- _M_handle_match(__match_mode, __i); break;
+ _M_handle_match<__search_mode>(__match_mode, __i); break;
case _S_opcode_backref:
- if (_M_search_mode == _Search_mode::_DFS)
+ if constexpr (__search_mode == _Search_mode::_DFS)
_M_handle_backref(__match_mode, __i);
else
__builtin_unreachable();
break;
case _S_opcode_accept:
- _M_handle_accept(__match_mode, __i); break;
+ _M_handle_accept<__search_mode>(__match_mode, __i); break;
case _S_opcode_alternative:
_M_handle_alternative(__match_mode, __i); break;
default:
@@ -605,10 +612,10 @@ namespace __detail
}
template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ template<_Search_mode __search_mode>
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,17 +628,17 @@ namespace __detail
case _S_fopcode_fallback_next:
if (_M_has_sol)
break;
- if (__dfs_mode)
+ if constexpr (__search_mode == _Search_mode::_DFS)
_M_current = __frame._M_pos;
[[__fallthrough__]];
case _S_fopcode_next:
- _M_node(__match_mode, __frame._M_state_id);
+ _M_node<__search_mode>(__match_mode, __frame._M_state_id);
break;
case _S_fopcode_fallback_rep_once_more:
if (_M_has_sol)
break;
- if (__dfs_mode)
+ if constexpr (__search_mode == _Search_mode::_DFS)
_M_current = __frame._M_pos;
[[__fallthrough__]];
case _S_fopcode_rep_once_more:
@@ -641,7 +648,7 @@ namespace __detail
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 constexpr (__search_mode == _Search_mode::_DFS)
_M_current = __frame._M_pos;
_M_has_sol = false;
break;
