GNU bug report logs - #16966
[PATCH] grep: optimization with the superset of DFA

Previous Next

Full log

Message #24 received at 16966 <at> debbugs.gnu.org (full text, mbox):

From: Paolo Bonzini <bonzini <at> gnu.org>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, 16966 <at> debbugs.gnu.org
Subject: Re: bug#16966: [PATCH] grep: optimization with the superset of DFA
Date: Tue, 01 Apr 2014 10:16:32 +0200

Il 28/03/2014 18:20, Norihiro Tanaka ha scritto:
> I rebased this patch, and added four fixes to it.
>
>  1. Fix for the conditions that the superset is used.  No longer use it
>     when don't include any normal chars and CSETs. (dfasuperset)
>
>  2. Ignore any letter constrations.  Otherwise, it mayn't be able to be
>     a superset of the original dfa. (dfasuperset)
>
>  3. Change return type of dfahint().  It can check whether used or not
>     from caller.(dfahint)
>
>  4. If both kwset and dfahint() aren't used, run DFA matcher in whole
>     range still.

For ANYCHAR, you can convert it to CSET{1,mb_cur_max} or, even better, 
(single-CSET | lead-CSET full-CSET{0,mb_cur_max-1}).

Single-CSET and lead-CSET can be computed by looping over the 256 
characters with mbrtowc and looking respectively for non-negative or -2 
return values.

Paolo

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.