GNU bug report logs - #32750
[PATCH 2/2] dfa: optmization of alternation in NFA

Previous Next

Full log

Message #22 received at 32750-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 32750-done <at> debbugs.gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Tue, 18 Sep 2018 21:12:18 -0700

[Message part 1 (text/plain, inline)]

Norihiro Tanaka wrote:
> I thought of various things for the name of the function, but I could
> not think of a good name.

Yes, that's a tough one. I eventually came up with maybe_disable_superset_dfa. 
Perhaps we can think of an ever better one.

I installed your patches into Gnulib, along with the attached relatively-minor 
fixups, and then propagated the result into grep by updating the Gnulib version 
that the grep master points to.

As you may notice, nowadays I prefer using signed types like ptrdiff_t to 
unsigned ones like size_t, as the signed types have a significant advantage in 
overflow checking with gcc -fsanitize=undefined. Perhaps at some point we should 
change the other instances of size_t in dfa.c, but one step at a time.

Thanks again for the performance improvement.

[0001-dfa-reorder-enum-for-efficiency.patch (text/x-patch, attachment)]

[0002-dfa-prune-states-as-we-go.patch (text/x-patch, attachment)]

[0003-dfa-tweak-allocation-performance.patch (text/x-patch, attachment)]

[0004-dfa-use-more-informative-function-name.patch (text/x-patch, attachment)]

Previous Next

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