This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [Patch 1/3] Use manual regex algorithm switching
- From: Jonathan Wakely <jwakely at redhat dot com>
- To: Tim Shen <timshen91 at gmail dot com>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 25 Apr 2014 22:14:17 +0100
- Subject: Re: [Patch 1/3] Use manual regex algorithm switching
- Authentication-results: sourceware.org; auth=none
- References: <CAPrifDm8MwcHY8XSnW_z6Z_hLVS+Lw4huqWEF3_eNT=fw3mkRg at mail dot gmail dot com>
--- a/libstdc++-v3/include/bits/regex.tcc
+++ b/libstdc++-v3/include/bits/regex.tcc
@@ -28,12 +28,12 @@
* Do not attempt to use it directly. @headername{regex}
*/
-// See below __regex_algo_impl to get what this is talking about. The default
-// value 1 indicated a conservative optimization without giving up worst case
-// performance.
-#ifndef _GLIBCXX_REGEX_DFS_QUANTIFIERS_LIMIT
-#define _GLIBCXX_REGEX_DFS_QUANTIFIERS_LIMIT 1
-#endif
+// A non-standard switch to let the user pick the matching algorithm.
+// If _GLIBCXX_REGEX_USE_THOMPSON_NFA is defined, the thompson NFA
+// algorithm will be used. This algorithm is not by default, and cannot
This should say "not enabled by default" or "not used by default".
+// be used if the regex contains back-references, but has better
+// (polynomial instead of exponential) worst case performace.
+// See __regex_algo_impl below.
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -68,7 +68,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// This function decide which executor to use under given circumstances.
// The _S_auto policy now is the following: if a NFA has no
- // back-references and has more than _GLIBCXX_REGEX_DFS_QUANTIFIERS_LIMIT
+ // back-references and has more than _GLIBCXX_REGEX_USE_THOMPSON_NFA
This comment needs more than just a simple replacement, as the way the
macro is used changed, not just its name.
// quantifiers (*, +, ?), the BFS executor will be used, other wise
// DFS executor. This is because DFS executor has a exponential upper
// bound, but better best-case performace. Meanwhile, BFS executor can
@@ -82,8 +82,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool __ret;
if (!__re._M_automaton->_M_has_backref
&& (__policy == _RegexExecutorPolicy::_S_alternate
- || __re._M_automaton->_M_quant_count
- > _GLIBCXX_REGEX_DFS_QUANTIFIERS_LIMIT))
+#ifdef _GLIBCXX_REGEX_USE_THOMPSON_NFA
+ || true
+#endif
+ ))
I wonder if this would be simpler to read like this:
if (!__re._M_automaton->_M_has_backref
#ifndef _GLIBCXX_REGEX_USE_THOMPSON_NFA
&& __policy == _RegexExecutorPolicy::_S_alternate
#endif
)
What do you think?