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

Previous Next

Full log

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

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 17230-done <at> debbugs.gnu.org
Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for
 case-insensitive matching
Date: Thu, 24 Apr 2014 02:51:35 +0900

Paul, thanks for a lot of reviews and commits.  However, it may be wrong.
I ran several tests for the worst case.

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k
$ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k

My version:
real 0.74
user 0.43
sys 0.30

Simplified version:
real 2.06
user 1.74
sys 0.31

It's slower than DFA.

$ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k
real 1.26
user 0.96
sys 0.30

I ran the test on Solaris 10 (SPARC) and HP-UX 11v2 (Itanium)


- On HP-UX 11v2

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k
$ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k

My version:
real        2.9
user        2.6
sys         0.2

Simplified version:
real        7.5
user        7.3
sys         0.2

Using DFA:

$ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k

real        3.2
user        3.0
sys         0.2

- On Solaris 10

$ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k

My version:
real 7.61
user 6.89
sys 0.71

Simplified version:
real 24.44
user 23.71
sys 0.72

Using DFA:

$ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k

real 8.03
user 7.31
sys 0.71

Norihiro

Previous Next

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