GNU bug report logs - #17229
[PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching

Previous Next

Full log

View this message in rfc822 format

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 17229 <at> debbugs.gnu.org
Subject: bug#17229: [PATCH 2/2] grep: speed-up by using memchr() in Boyer-Moore searching
Date: Thu, 10 Apr 2014 20:37:45 +0900

Hi Paul,
Hi Paul,

Thanks for the review for the patch.

> What benchmark did you use to time this?

I measured below.

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k

Before:
$ time -p env LANG=C src/grep jk k
real 1.53
user 1.21
sys 0.31

After:
$ time -p env LANG=C src/grep jk k
real 0.33
user 0.03
sys 0.29

> Is there some other patch that establishes this variable, a patch that
> is a prerequisite for this one?

The patch requires below.

bug#17230
[PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching

> What is delta1?  It's mentioned in a comment but not in the code.

It means `d1' in kwset.c:bmexec.

> It'd be simpler to use memchr on all platforms;
> is there a major performance downside to that?

Yes.  As far as I was confirmed, it's slow in HP-UX on Itanium and
Solaris on SPARC.  I think that that it depends on the implementation of
memchr() and the rate of the increment instruction for the `add'
instruction on the platform.

Norihiro

Previous Next

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