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 16:
email: 55.5%
URI: 55.2%
IPv4: 68.0%
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_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
0a63b9b83789a700de63081ee61a7857028548e0..28dac152b6241ee44fd120528b9d1ebdbdf1aafa
100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -112,6 +112,28 @@ namespace __detail
_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);
}
@@ -181,6 +203,9 @@ namespace __detail
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
bf0594912688e0014a5928b6c6d600af6f80b31a..3a3bad8ecac485d452970c0aa26e6db34cabd1e5
100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -169,6 +169,101 @@ namespace __detail
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 0a63b9b83789a700de63081ee61a7857028548e0..28dac152b6241ee44fd120528b9d1ebdbdf1aafa 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -112,6 +112,28 @@ namespace __detail
_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);
}
@@ -181,6 +203,9 @@ namespace __detail
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 bf0594912688e0014a5928b6c6d600af6f80b31a..3a3bad8ecac485d452970c0aa26e6db34cabd1e5 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -169,6 +169,101 @@ namespace __detail
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:
