Re: [PATCH] dfa: addition of new state on demand

[Norihiro Tanaka]

Thanks for the review.  I confirmed your changes, and I found no problem.

> CC'ing this to grep-devel since that's where the hardy band of dfa
> consumers hang out.

I will also do it in next post for dfa.

Re: [PATCH] dfa: addition of new state on demand

[Paul Eggert]

Jim Meyering wrote:

I see one typo in your 2nd change's log: s/cdalls/calls/

  Omit unnecessary cdalls to zeroset.


Thanks, I fixed that.

Re: [PATCH] dfa: addition of new state on demand

[Jim Meyering]

On Fri, Nov 25, 2016 at 11:03 AM, Paul Eggert  wrote:
> Norihiro Tanaka wrote:
>>
>> Can anyone review this change?
>
>
> Thanks for doing all that, and sorry about the late review. I reviewed it,
> tweaked its commit message and propagated that into ChangeLog (the gnulib
> practice), and installed the result into gnulib, with two followup patches
> that I hope are self-explanatory. All three patches are attached. Please let
> us know of any problems you see with the result.
>
> CC'ing this to grep-devel since that's where the hardy band of dfa consumers
> hang out.

Thanks to both of you.
I confirmed that with those, grep still passes all of its tests, even
with ASAN (and hence leak detection) enabled.

Paul, I see one typo in your 2nd change's log: s/cdalls/calls/

  Omit unnecessary cdalls to zeroset.

Re: [PATCH] dfa: addition of new state on demand

[Paul Eggert]

Norihiro Tanaka wrote:

Can anyone review this change?


Thanks for doing all that, and sorry about the late review. I reviewed it, 
tweaked its commit message and propagated that into ChangeLog (the gnulib 
practice), and installed the result into gnulib, with two followup patches that 
I hope are self-explanatory. All three patches are attached. Please let us know 
of any problems you see with the result.


CC'ing this to grep-devel since that's where the hardy band of dfa consumers 
hang out.
From 41ed6b2c88e9fa7c2ab7f29d1ec1bea20f095614 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka 
Date: Fri, 25 Nov 2016 10:43:38 -0800
Subject: [PATCH 1/3] dfa: addition of new state on demand

* src/dfa.c (dfastate): Add argument UC, the current input character.
Fill only a group including the character in transition table.
(realloc_trans_if_necessary): Add the dummy state which means that a
transition table is assigned but the next state is not assigned.
(build_state): Return the next state.  All callers updated.
(transit_state_singlebyte): If we get the dummy state,
fill the transition table.
(dfaexec_main): Handle the dummy state.
(free_mbdata, dfafree): Consider the dummy state.
---
 ChangeLog |  13 +++
 lib/dfa.c | 347 +-
 2 files changed, 155 insertions(+), 205 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index b8f4423..ef6d40e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+2016-11-25  Norihiro Tanaka  
+
+	dfa: addition of new state on demand
+	* src/dfa.c (dfastate): Add argument UC, the current input character.
+	Fill only a group including the character in transition table.
+	(realloc_trans_if_necessary): Add the dummy state which means that a
+	transition table is assigned but the next state is not assigned.
+	(build_state): Return the next state.  All callers updated.
+	(transit_state_singlebyte): If we get the dummy state,
+	fill the transition table.
+	(dfaexec_main): Handle the dummy state.
+	(free_mbdata, dfafree): Consider the dummy state.
+
 2016-11-24  Daiki Ueno  
 
 	srclist: sync with released gettext
diff --git a/lib/dfa.c b/lib/dfa.c
index 7b80a1a..a182b05 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -477,7 +477,8 @@ struct dfa
 
   /* Fields filled by dfaexec.  */
   state_num tralloc;/* Number of transition tables that have
-   slots so far, not counting trans[-1].  */
+   slots so far, not counting trans[-1] and
+   trans[-2].  */
   int trcount;  /* Number of transition tables that have
actually been built.  */
   int min_trcount;  /* Minimum of number of transition tables.
@@ -490,7 +491,8 @@ struct dfa
state could possibly accept, its entry in
this table is NULL.  This points to one
past the start of the allocated array,
-   and trans[-1] is always NULL.  */
+   and trans[-1] and trans[-2] are always
+   NULL.  */
   state_num **fails;/* Transition tables after failing to accept
on a state that potentially could do so.  */
   int *success; /* Table of acceptance conditions used in
@@ -507,7 +509,8 @@ struct dfa
do not distinguish between their contexts,
as not supported word.  */
   position_set mb_follows;  /* Follow set added by ANYCHAR on demand.  */
-  state_num **mb_trans;  /* Transition tables for states with ANYCHAR.  */
+  state_num **mb_trans; /* Transition tables for states with
+   ANYCHAR.  */
   state_num mb_trcount; /* Number of transition tables for states with
ANYCHAR that have actually been built.  */
 
@@ -2510,19 +2513,12 @@ dfaanalyze (struct dfa *d, bool searchflag)
If after comparing with every group there are characters remaining in C,
create a new group labeled with the characters of C and insert this
position in that group.  */
-static void
-dfastate (state_num s, struct dfa *d, state_num trans[])
+static state_num
+dfastate (state_num s, struct dfa *d, unsigned char uc, state_num trans[])
 {
-  leaf_set grps[NOTCHAR];   /* As many as will ever be needed.  */
-  charclass labels[NOTCHAR];/* Labels corresponding to the groups.  */
-  size_t ngrps = 0; /* Number of groups actually used.  */
-  position pos; /* Current position being considered.  */
+  leaf_set group;   /* As many as will ever be needed.  */
+  charclass labels; /* Labels corresponding to the group.  */
   

Re: [PATCH] dfa: addition of new state on demand

[Norihiro Tanaka]

On Mon, 17 Oct 2016 22:00:33 +0900
Norihiro Tanaka <nori...@kcn.ne.jp> wrote:

> 
> On Mon, 17 Oct 2016 11:45:43 +0900
> Norihiro Tanaka <nori...@kcn.ne.jp> wrote:
> 
> > When dfa builds a state, generates all next states.  However, I believe
> > most of them are not used.
> > 
> > This patch changes as that when dfa builds a state, generates a next
> > state including next input character only.
> > 
> > The following test was improved from 2.52s to 0.67s by the patch in my
> > machine.
> > 
> > $ seq -f '%g bottles of beer on the wall' 600 >600
> > $ time -p env LC_ALL=C src/grep -vf 600 600
> > 
> > $ env LC_ALL=C gcc -v
> > Reading specs from /usr/local/lib/gcc/x86_64-pc-linux-gnu/4.4.7/specs
> > Target: x86_64-pc-linux-gnu
> > Configured with: ./configure --with-as=/usr/local/bin/as 
> > --with-ld=/usr/local/bin/ld --with-system-zlib --enable-__cxa_atexit
> > Thread model: posix
> > gcc version 4.4.7 (GCC)
> > $ uname -a
> > Linux rhel6 2.6.32-642.el6.x86_64 #1 SMP Wed Apr 13 00:51:26 EDT 2016 
> > x86_64 x86_64 x86_64 GNU/Linux
> 
> Hi,
> 
> I updated comments in previous patch.
> 
> Thanks,
> Norihiro

Can anyone review this change?
From a2144547298fe31a93e6a65b2c4e7e2037c53980 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <nori...@kcn.ne.jp>
Date: Mon, 17 Oct 2016 11:27:47 +0900
Subject: [PATCH] dfa: addition of new state on demand

* src/dfa.c (dfastate): Add argument UC.  It is current input character.
fill only a group including the character in transition table.
(realloc_trans_if_necessary): Add the dummy state which means that a
transition table is assigned but next state is not assigned.
(build_state): Return next state.  All caller updated.
(transit_state_singlebyte): If get the dummy state, fill the transition
tble.
(dfaexec_main): Handle the dummy state.
(free_mbdata, dfafree): Consider the dummy state.
---
 lib/dfa.c |  347 +
 1 files changed, 142 insertions(+), 205 deletions(-)

diff --git a/lib/dfa.c b/lib/dfa.c
index 744a9f1..793f828 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -477,7 +477,8 @@ struct dfa
 
   /* Fields filled by dfaexec.  */
   state_num tralloc;/* Number of transition tables that have
-   slots so far, not counting trans[-1].  */
+   slots so far, not counting trans[-1] and
+   trans[-2].  */
   int trcount;  /* Number of transition tables that have
actually been built.  */
   int min_trcount;  /* Minimum of number of transition tables.
@@ -490,7 +491,8 @@ struct dfa
state could possibly accept, its entry in
this table is NULL.  This points to one
past the start of the allocated array,
-   and trans[-1] is always NULL.  */
+   and trans[-1] and trans[-2] are always
+   NULL.  */
   state_num **fails;/* Transition tables after failing to accept
on a state that potentially could do so.  */
   int *success; /* Table of acceptance conditions used in
@@ -507,7 +509,8 @@ struct dfa
do not distinguish between their contexts,
as not supported word.  */
   position_set mb_follows;  /* Follow set added by ANYCHAR on demand.  */
-  state_num **mb_trans;  /* Transition tables for states with ANYCHAR.  */
+  state_num **mb_trans; /* Transition tables for states with
+   ANYCHAR.  */
   state_num mb_trcount; /* Number of transition tables for states with
ANYCHAR that have actually been built.  */
 
@@ -2510,19 +2513,12 @@ dfaanalyze (struct dfa *d, bool searchflag)
If after comparing with every group there are characters remaining in C,
create a new group labeled with the characters of C and insert this
position in that group.  */
-static void
-dfastate (state_num s, struct dfa *d, state_num trans[])
+static state_num
+dfastate (state_num s, struct dfa *d, unsigned char uc, state_num trans[])
 {
-  leaf_set grps[NOTCHAR];   /* As many as will ever be needed.  */
-  charclass labels[NOTCHAR];/* Labels corresponding to the groups.  */
-  size_t ngrps = 0; /* Number of groups actually used.  */
-  position pos; /* Current position being considered.  */
+  leaf_set group;   /* As many as will ever be needed.  */
+  charclass labels; /* Labels corresponding to the group.  */
 

Re: [PATCH] dfa: addition of new state on demand

[Norihiro Tanaka]

On Mon, 17 Oct 2016 11:45:43 +0900
Norihiro Tanaka <nori...@kcn.ne.jp> wrote:

> When dfa builds a state, generates all next states.  However, I believe
> most of them are not used.
> 
> This patch changes as that when dfa builds a state, generates a next
> state including next input character only.
> 
> The following test was improved from 2.52s to 0.67s by the patch in my
> machine.
> 
> $ seq -f '%g bottles of beer on the wall' 600 >600
> $ time -p env LC_ALL=C src/grep -vf 600 600
> 
> $ env LC_ALL=C gcc -v
> Reading specs from /usr/local/lib/gcc/x86_64-pc-linux-gnu/4.4.7/specs
> Target: x86_64-pc-linux-gnu
> Configured with: ./configure --with-as=/usr/local/bin/as 
> --with-ld=/usr/local/bin/ld --with-system-zlib --enable-__cxa_atexit
> Thread model: posix
> gcc version 4.4.7 (GCC)
> $ uname -a
> Linux rhel6 2.6.32-642.el6.x86_64 #1 SMP Wed Apr 13 00:51:26 EDT 2016 x86_64 
> x86_64 x86_64 GNU/Linux

Hi,

I updated comments in previous patch.

Thanks,
Norihiro
From a2144547298fe31a93e6a65b2c4e7e2037c53980 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <nori...@kcn.ne.jp>
Date: Mon, 17 Oct 2016 11:27:47 +0900
Subject: [PATCH] dfa: addition of new state on demand

* src/dfa.c (dfastate): Add argument UC.  It is current input character.
fill only a group including the character in transition table.
(realloc_trans_if_necessary): Add the dummy state which means that a
transition table is assigned but next state is not assigned.
(build_state): Return next state.  All caller updated.
(transit_state_singlebyte): If get the dummy state, fill the transition
tble.
(dfaexec_main): Handle the dummy state.
(free_mbdata, dfafree): Consider the dummy state.
---
 lib/dfa.c |  347 +
 1 files changed, 142 insertions(+), 205 deletions(-)

diff --git a/lib/dfa.c b/lib/dfa.c
index 744a9f1..793f828 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -477,7 +477,8 @@ struct dfa
 
   /* Fields filled by dfaexec.  */
   state_num tralloc;/* Number of transition tables that have
-   slots so far, not counting trans[-1].  */
+   slots so far, not counting trans[-1] and
+   trans[-2].  */
   int trcount;  /* Number of transition tables that have
actually been built.  */
   int min_trcount;  /* Minimum of number of transition tables.
@@ -490,7 +491,8 @@ struct dfa
state could possibly accept, its entry in
this table is NULL.  This points to one
past the start of the allocated array,
-   and trans[-1] is always NULL.  */
+   and trans[-1] and trans[-2] are always
+   NULL.  */
   state_num **fails;/* Transition tables after failing to accept
on a state that potentially could do so.  */
   int *success; /* Table of acceptance conditions used in
@@ -507,7 +509,8 @@ struct dfa
do not distinguish between their contexts,
as not supported word.  */
   position_set mb_follows;  /* Follow set added by ANYCHAR on demand.  */
-  state_num **mb_trans;  /* Transition tables for states with ANYCHAR.  */
+  state_num **mb_trans; /* Transition tables for states with
+   ANYCHAR.  */
   state_num mb_trcount; /* Number of transition tables for states with
ANYCHAR that have actually been built.  */
 
@@ -2510,19 +2513,12 @@ dfaanalyze (struct dfa *d, bool searchflag)
If after comparing with every group there are characters remaining in C,
create a new group labeled with the characters of C and insert this
position in that group.  */
-static void
-dfastate (state_num s, struct dfa *d, state_num trans[])
+static state_num
+dfastate (state_num s, struct dfa *d, unsigned char uc, state_num trans[])
 {
-  leaf_set grps[NOTCHAR];   /* As many as will ever be needed.  */
-  charclass labels[NOTCHAR];/* Labels corresponding to the groups.  */
-  size_t ngrps = 0; /* Number of groups actually used.  */
-  position pos; /* Current position being considered.  */
+  leaf_set group;   /* As many as will ever be needed.  */
+  charclass labels; /* Labels corresponding to the group.  */
   charclass matches;/* Set of matching characters.  */
-  charclass_word matchesf; /* Nonzero if matches is nonempty.  */
-  charclass intersect;  /* Intersection with some label set.  */
-  charclass_word intersectf;   /* Nonzero if intersect is nonem

[PATCH] dfa: addition of new state on demand

[Norihiro Tanaka]

When dfa builds a state, generates all next states.  However, I believe
most of them are not used.

This patch changes as that when dfa builds a state, generates a next
state including next input character only.

The following test was improved from 2.52s to 0.67s by the patch in my
machine.

$ seq -f '%g bottles of beer on the wall' 600 >600
$ time -p env LC_ALL=C src/grep -vf 600 600

$ env LC_ALL=C gcc -v
Reading specs from /usr/local/lib/gcc/x86_64-pc-linux-gnu/4.4.7/specs
Target: x86_64-pc-linux-gnu
Configured with: ./configure --with-as=/usr/local/bin/as 
--with-ld=/usr/local/bin/ld --with-system-zlib --enable-__cxa_atexit
Thread model: posix
gcc version 4.4.7 (GCC)
$ uname -a
Linux rhel6 2.6.32-642.el6.x86_64 #1 SMP Wed Apr 13 00:51:26 EDT 2016 x86_64 
x86_64 x86_64 GNU/Linux
From 2d33060d77713bfefc3d82c031a7436dc205654b Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <nori...@kcn.ne.jp>
Date: Mon, 17 Oct 2016 11:27:47 +0900
Subject: [PATCH] dfa: addition of new state on demand

* src/dfa.c (dfastate): Add argument UC.  It is current input character.
fill only a group including the character in transition table.
(realloc_trans_if_necessary): Add the dummy state which means that a
transition table is assigned but next state is not assigned.
(build_state): Return next state.  All caller updated.
(transit_state_singlebyte): If get the dummy state, fill the transition
tble.
(dfaexec_main): Handle the dummy state.
(free_mbdata, dfafree): Consider the dummy state.
---
 lib/dfa.c |  336 -
 1 files changed, 134 insertions(+), 202 deletions(-)

diff --git a/lib/dfa.c b/lib/dfa.c
index 744a9f1..20ec872 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2510,19 +2510,12 @@ dfaanalyze (struct dfa *d, bool searchflag)
If after comparing with every group there are characters remaining in C,
create a new group labeled with the characters of C and insert this
position in that group.  */
-static void
-dfastate (state_num s, struct dfa *d, state_num trans[])
+static state_num
+dfastate (state_num s, struct dfa *d, unsigned char uc, state_num trans[])
 {
-  leaf_set grps[NOTCHAR];   /* As many as will ever be needed.  */
-  charclass labels[NOTCHAR];/* Labels corresponding to the groups.  */
-  size_t ngrps = 0; /* Number of groups actually used.  */
-  position pos; /* Current position being considered.  */
+  leaf_set group;   /* As many as will ever be needed.  */
+  charclass labels; /* Labels corresponding to the groups.  */
   charclass matches;/* Set of matching characters.  */
-  charclass_word matchesf; /* Nonzero if matches is nonempty.  */
-  charclass intersect;  /* Intersection with some label set.  */
-  charclass_word intersectf;   /* Nonzero if intersect is nonempty.  */
-  charclass leftovers;  /* Stuff in the label that didn't match.  */
-  charclass_word leftoversf;   /* Nonzero if leftovers is nonempty.  */
   position_set follows; /* Union of the follows of some group.  */
   position_set tmp; /* Temporary space for merging sets.  */
   int possible_contexts;/* Contexts that this group can match.  */
@@ -2537,18 +2530,36 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
   fprintf (stderr, "build state %td\n", s);
 #endif
 
-  zeroset (matches);
+  group.elems = xnmalloc (d->nleaves, sizeof *group.elems);
+  group.nelem = 0;
+
+  zeroset (labels);
+  notset (labels);
 
   for (i = 0; i < d->states[s].elems.nelem; ++i)
 {
-  pos = d->states[s].elems.elems[i];
+  position pos = d->states[s].elems.elems[i];
+  bool matched = false;
   if (d->tokens[pos.index] >= 0 && d->tokens[pos.index] < NOTCHAR)
-setbit (d->tokens[pos.index], matches);
+{
+  zeroset (matches);
+  setbit (d->tokens[pos.index], matches);
+  if (d->tokens[pos.index] == uc)
+matched = true;
+}
   else if (d->tokens[pos.index] >= CSET)
-copyset (d->charclasses[d->tokens[pos.index] - CSET], matches);
-  else if (d->tokens[pos.index] == ANYCHAR)
 {
+  zeroset (matches);
+  copyset (d->charclasses[d->tokens[pos.index] - CSET], matches);
+  if (tstbit (uc, d->charclasses[d->tokens[pos.index] - CSET]))
+matched = true;
+}
+   else if (d->tokens[pos.index] == ANYCHAR)
+ {
+  zeroset (matches);
   copyset (d->charclasses[d->canychar], matches);
+  if (tstbit (uc, d->charclasses[d->canychar]))
+matched = true;
 
   /* ANYCHAR must match with a single character, so we must put
  it to D->states[s].mbps which contains the positions which
@@ -2603,113 +2614,31 @@ dfastate (state_num s, struct dfa *d, state_