GNU bug report logs - #17700
[PATCH] dfa: speed-up for a pattern that many atoms are catenated

Previous Next

Full log

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

From: arnold <at> skeeve.com
To: noritnk <at> kcn.ne.jp, eggert <at> cs.ucla.edu
Cc: 17700 <at> debbugs.gnu.org
Subject: Re: bug#17700: [PATCH] dfa: speed-up for a pattern that many atoms
 are catenated
Date: Fri, 06 Jun 2014 00:42:45 -0600

Is strstr() even a good idea? dfa needs to be able to match NUL
bytes in the data.  If this prevents that, then it's a problem.

I'm merely asking - I didn't look hard at where the change was made.
If it matching NUL bytes isn't affected then, no problem.

Thanks,

Arnold

Paul Eggert <eggert <at> cs.ucla.edu> wrote:

> Norihiro Tanaka wrote:
> > after `grep: undo part of previous change', no longer faster.
> >
> > $ printf '%02048d\n' 0 | time -p src/grep -f - /dev/null
> >
> > master  : real 5.74  user 5.40  sys 0.17
> > my patch: real 0.08  user 0.04  sys 0.04
>
> This isn't matching the results I get on my platform.  If 
> src/d5dfa69/grep is the old version, src/709e7e5/grep the current master 
> (i.e., just use system strstr), and src/grep is the old version with 
> your patch, I get:
>
> $ printf '%02048d\n' 0 | time -p src/d5dfa69/grep -f - /dev/null
> real 0.33
> user 0.33
> sys 0.00
> $ printf '%02048d\n' 0 | time -p src/709e7e5/grep -f - /dev/null
> real 0.04
> user 0.04
> sys 0.00
> $ printf '%02048d\n' 0 | time -p src/grep -f - /dev/null
> real 0.03
> user 0.03
> sys 0.00
>
> So it looks like your patch confers some advantage, but on my platform 
> almost all the speedup is achieved simply by switching to the system strstr.
>
> > `lookfor' isn't terminated by `\-'\0' in istrstr(), but strstr() requires it.
>
> Yes, that's why I needed to make the most recent change in the current 
> master; it arranges for strstr's 2nd arg to be null-terminated.

Previous Next

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