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

Previous Next

Full log

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: Aharon Robbins <arnold <at> skeeve.com>, 17700 <at> debbugs.gnu.org
Subject: Re: bug#17700: [PATCH] dfa: speed-up for a pattern that many atoms
 are catenated
Date: Thu, 05 Jun 2014 17:49:23 -0700

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.