This patch add a conservative first-character precheck for DFS prefix search.
regex_search and regex_token_iterator try the pattern at each possible input
position. However for many regexp some of those positions can be rejected by
looking through the front (without consuming state) before building th full
DFS state which can be expensive to build only to realize that nothing matches.
The pre-check only returns false when every inspected path reaches a first
consuming match state that rejects *_M_current, or reaches a dead end. It
returns true for unsupported or context-sensitive states such as backrefs
and lookahead, so true means "run the normal executor" and false means
"this start position cannot match".
This mainly helps IPv4-style scans where most positions are non-digits and
only a few positions can start a match.
Benchmarks improvements compared to GCC previous patch in series:
at -O2:
email: +2.4%
URI: +3.6%
IPv4 +43.9%
at -O3:
email: +0.1%,
URI: +1.4%
IPv4: +42.7%
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
PR libstdc++/88947
* include/bits/regex_executor.h (_M_search_from_first): Avoid needless
recursions.
(_M_maybe_start_match): New.
* include/bits/regex_executor.tcc (_M_maybe_start_match): New.
---
diff --git a/libstdc++-v3/include/bits/regex_executor.h
b/libstdc++-v3/include/bits/regex_executor.h
index
2a9c87af59489f5202554d1052ec8355b7c5646b..c2dce4e24d35807b311d5a3273297f72a74cc24d
100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -108,6 +108,28 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_M_search_from_first()
{
_M_current = _M_begin;
+ // Fast reject for DFS prefix search. regex_search and
+ // regex_token_iterator try the pattern at each possible starting
+ // position. If the regex can only start with a digit, running the full
+ // DFS executor at a space, letter, or punctuation character only builds
+ // frames to discover the first match state rejects that character.
+ //
+ // Example: for the IPv4 pattern
+ // (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}...
+ // a current input character of 'x' cannot match any first consuming
+ // state. _M_maybe_start_match returns false and this starting position
+ // is skipped. At '2' it returns true, because at least one branch
+ // might match, so the normal executor still decides the complete
+ // result.
+ //
+ // This is intentionally disabled for backreferences. Pruning the
+ // search space for DFS reduces the number of frames we build and the
+ // time to find an actual match.
+ if (_M_search_mode == _Search_mode::_Dfs
+ && !_M_nfa._M_has_backref
+ && _M_current != _M_end
+ && !_M_maybe_start_match(_M_start, 0))
+ return false;
return _M_main(_Match_mode::_Prefix);
}
@@ -176,6 +198,9 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
bool
_M_main_dfs(_Match_mode __match_mode);
+ bool
+ _M_maybe_start_match(_StateIdT, size_t);
+
bool
_M_main_bfs(_Match_mode __match_mode);
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc
b/libstdc++-v3/include/bits/regex_executor.tcc
index
6e4c2a238cf8e393c8ae561edb88f94bf35331c0..2c03c6bfe9377ac66bffc0f3d9350d5d5cc35468
100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -170,6 +170,101 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
return _M_has_sol;
}
+ // Return whether a prefix search at _M_current might still match after
+ // looking only through the non-consuming front of the NFA.
+ //
+ // This is not a general implementation. It is deliberately small and
+ // conservative: when it reaches a construct whose first consuming character
+ // is hard to know cheaply, it returns true and lets the normal executor run.
+ // The important fast paths are the common negative cases.
+ //
+ // Examples:
+ // * Pattern "[0-9]+" at input 'x': the first _S_opcode_match rejects 'x',
+ // so a full DFS search would only allocate/pop frames to fail. Return
+ // false and let regex_search advance the starting position.
+ //
+ // * Pattern "[01]?[0-9]" at input '9': the optional [01] branch rejects,
+ // but the skip branch can consume '9'. Return true and let DFS decide
+ // the full match.
+ //
+ // * Pattern "foo|bar" at input 'b': one alternative rejects, the other can
+ // start with 'b'. Return true.
+ template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ bool _Executor<_BiIter, _Alloc, _TraitsT>::
+ _M_maybe_start_match(_StateIdT __i, size_t __depth)
+ {
+ // Depth is bounded by the NFA size so epsilon cycles cannot make the
+ // precheck recurse forever. Hitting the bound means "unknown", not
+ // "no match", so stay conservative and run the real executor. This is
+ // important for patterns such as "(a*)*" where epsilon paths can cycle
+ // before a consuming state is reached.
+ if (__depth > _M_nfa.size())
+ return true;
+
+ // An invalid edge is a real dead end for the explored path.
+ if (__i == _S_invalid_state_id)
+ return false;
+
+ const auto& __state = _M_nfa[__i];
+ switch (__state._M_opcode())
+ {
+ case _S_opcode_match:
+ return __state._M_matches(*_M_current);
+
+ case _S_opcode_accept:
+ // Empty matches are possible, so the full executor must decide.
+ return true;
+
+ case _S_opcode_subexpr_begin:
+ case _S_opcode_subexpr_end:
+ case _S_opcode_dummy:
+ // Captures and dummy states do not consume input, so they cannot
+ // affect the first-character decision. Continue along the only
+ // successor.
+ return _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_line_begin_assertion:
+ // Assertions do not consume characters, but they can reject the
+ // current position. For "^abc" at a non-begin position, there is no
+ // need to run DFS merely to discover that ^ fails.
+ return _M_at_begin()
+ && _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_line_end_assertion:
+ // Same idea for "$": if the assertion does not hold here, this
+ // starting position cannot match via this path.
+ return _M_at_end()
+ && _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_word_boundary:
+ // Word-boundary assertions are also checked before the first
+ // consuming state. For "\bfoo" in the middle of "xfoo", this path
+ // rejects before testing 'f'.
+ return _M_word_boundary() == !__state._M_neg
+ && _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_alternative:
+ // A branch might match if either arm can start with *_M_current.
+ // Example: "foo|bar" at 'b' rejects the "foo" arm but keeps the
+ // search because the "bar" arm is viable.
+ return _M_maybe_start_match(__state._M_alt, __depth + 1)
+ || _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_repeat:
+ // Repeats can either enter the body or skip to the exit, so inspect
+ // both paths. This matters for constructs such as "[01]?[0-9]": at
+ // '9' the optional first digit can be skipped, while at 'x' both
+ // paths reject.
+ return _M_maybe_start_match(__state._M_alt, __depth + 1)
+ || _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_backref:
+ case _S_opcode_subexpr_lookahead:
+ default:
+ return true;
+ }
+ }
+
// ------------------------------------------------------------
//
// BFS mode:
--
diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index 2a9c87af59489f5202554d1052ec8355b7c5646b..c2dce4e24d35807b311d5a3273297f72a74cc24d 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -108,6 +108,28 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
_M_search_from_first()
{
_M_current = _M_begin;
+ // Fast reject for DFS prefix search. regex_search and
+ // regex_token_iterator try the pattern at each possible starting
+ // position. If the regex can only start with a digit, running the full
+ // DFS executor at a space, letter, or punctuation character only builds
+ // frames to discover the first match state rejects that character.
+ //
+ // Example: for the IPv4 pattern
+ // (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}...
+ // a current input character of 'x' cannot match any first consuming
+ // state. _M_maybe_start_match returns false and this starting position
+ // is skipped. At '2' it returns true, because at least one branch
+ // might match, so the normal executor still decides the complete
+ // result.
+ //
+ // This is intentionally disabled for backreferences. Pruning the
+ // search space for DFS reduces the number of frames we build and the
+ // time to find an actual match.
+ if (_M_search_mode == _Search_mode::_Dfs
+ && !_M_nfa._M_has_backref
+ && _M_current != _M_end
+ && !_M_maybe_start_match(_M_start, 0))
+ return false;
return _M_main(_Match_mode::_Prefix);
}
@@ -176,6 +198,9 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
bool
_M_main_dfs(_Match_mode __match_mode);
+ bool
+ _M_maybe_start_match(_StateIdT, size_t);
+
bool
_M_main_bfs(_Match_mode __match_mode);
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 6e4c2a238cf8e393c8ae561edb88f94bf35331c0..2c03c6bfe9377ac66bffc0f3d9350d5d5cc35468 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -170,6 +170,101 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
return _M_has_sol;
}
+ // Return whether a prefix search at _M_current might still match after
+ // looking only through the non-consuming front of the NFA.
+ //
+ // This is not a general implementation. It is deliberately small and
+ // conservative: when it reaches a construct whose first consuming character
+ // is hard to know cheaply, it returns true and lets the normal executor run.
+ // The important fast paths are the common negative cases.
+ //
+ // Examples:
+ // * Pattern "[0-9]+" at input 'x': the first _S_opcode_match rejects 'x',
+ // so a full DFS search would only allocate/pop frames to fail. Return
+ // false and let regex_search advance the starting position.
+ //
+ // * Pattern "[01]?[0-9]" at input '9': the optional [01] branch rejects,
+ // but the skip branch can consume '9'. Return true and let DFS decide
+ // the full match.
+ //
+ // * Pattern "foo|bar" at input 'b': one alternative rejects, the other can
+ // start with 'b'. Return true.
+ template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ bool _Executor<_BiIter, _Alloc, _TraitsT>::
+ _M_maybe_start_match(_StateIdT __i, size_t __depth)
+ {
+ // Depth is bounded by the NFA size so epsilon cycles cannot make the
+ // precheck recurse forever. Hitting the bound means "unknown", not
+ // "no match", so stay conservative and run the real executor. This is
+ // important for patterns such as "(a*)*" where epsilon paths can cycle
+ // before a consuming state is reached.
+ if (__depth > _M_nfa.size())
+ return true;
+
+ // An invalid edge is a real dead end for the explored path.
+ if (__i == _S_invalid_state_id)
+ return false;
+
+ const auto& __state = _M_nfa[__i];
+ switch (__state._M_opcode())
+ {
+ case _S_opcode_match:
+ return __state._M_matches(*_M_current);
+
+ case _S_opcode_accept:
+ // Empty matches are possible, so the full executor must decide.
+ return true;
+
+ case _S_opcode_subexpr_begin:
+ case _S_opcode_subexpr_end:
+ case _S_opcode_dummy:
+ // Captures and dummy states do not consume input, so they cannot
+ // affect the first-character decision. Continue along the only
+ // successor.
+ return _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_line_begin_assertion:
+ // Assertions do not consume characters, but they can reject the
+ // current position. For "^abc" at a non-begin position, there is no
+ // need to run DFS merely to discover that ^ fails.
+ return _M_at_begin()
+ && _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_line_end_assertion:
+ // Same idea for "$": if the assertion does not hold here, this
+ // starting position cannot match via this path.
+ return _M_at_end()
+ && _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_word_boundary:
+ // Word-boundary assertions are also checked before the first
+ // consuming state. For "\bfoo" in the middle of "xfoo", this path
+ // rejects before testing 'f'.
+ return _M_word_boundary() == !__state._M_neg
+ && _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_alternative:
+ // A branch might match if either arm can start with *_M_current.
+ // Example: "foo|bar" at 'b' rejects the "foo" arm but keeps the
+ // search because the "bar" arm is viable.
+ return _M_maybe_start_match(__state._M_alt, __depth + 1)
+ || _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_repeat:
+ // Repeats can either enter the body or skip to the exit, so inspect
+ // both paths. This matters for constructs such as "[01]?[0-9]": at
+ // '9' the optional first digit can be skipped, while at 'x' both
+ // paths reject.
+ return _M_maybe_start_match(__state._M_alt, __depth + 1)
+ || _M_maybe_start_match(__state._M_next, __depth + 1);
+
+ case _S_opcode_backref:
+ case _S_opcode_subexpr_lookahead:
+ default:
+ return true;
+ }
+ }
+
// ------------------------------------------------------------
//
// BFS mode:
