This is the mail archive of the
mailing list for the GCC project.
Re: [Patch] Change default executor to DFS in regex
- From: Paolo Carlini <paolo dot carlini at oracle dot com>
- To: Tim Shen <timshen91 at gmail dot com>, libstdc++ <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Sat, 19 Oct 2013 10:03:18 +0200
- Subject: Re: [Patch] Change default executor to DFS in regex
- Authentication-results: sourceware.org; auth=none
- References: <CAPrifD=xODhzMevpww0BnkQh1Ju2btXxd-fFde=fN7nKzWmgBQ at mail dot gmail dot com> <CAPrifDn8QqtPm6T6qr-=2VNr0zh2XgQ7xPPdFRbKZQSJ16AHDg at mail dot gmail dot com>
On 10/19/2013 05:53 AM, Tim Shen wrote:
The idea of course makes sense to me, but I think it needs a few small
tweaks. First, I don't like much the name _S_anti_auto, sounds like
something which goes against auto (?). What about _S_alternate?
On Fri, Oct 18, 2013 at 9:13 PM, Tim Shen <firstname.lastname@example.org> wrote:
As the comment in this patch said, DFS approach is faster in simple
regex, but exponentially slower in complex(many quantifier) cases.
Actually I suggest to use DFS where number of quantifiers < 2, to make
this 'optimization' more conservative. Now `split regex`, say "\s+"
can be optimized.
The _S_auto policy now is as coded,
should probably be:
The _S_auto policy is the following:
In the text, remember to always put a space before open parentheses, it
About the < 2, in general hardcoding a parameter value in the code isn't
a nice idea. Why don't we take it out to a macro, say
_GLIBCXX_REGEX_NFA_QUANTIFIERS_LIMIT? In stl_deque.h we have something
similar and in the present case it would be even safe from the ABI point
of view, if I'm not mistaken.
Finally, you mentioned the DFA optimization: I would like to see some
details about it. Would it be a big win in all cases? Before we freeze
the next ABI we should keep open all the possibilities...