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

Previous Next

Full log

View this message in rfc822 format

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 17230 <at> debbugs.gnu.org
Subject: bug#17230: [PATCH 1/2] grep: may also use Boyer-Moore algorithm for case-insensitive matching
Date: Wed, 23 Apr 2014 18:49:16 -0700

Norihiro Tanaka wrote:
> Could you also
> consider them, and run (A) instead of (B)?  It means that overheads by
> `yes' and `head' should be ignored.

Sure, I did that, using the updated 17230.diff patch, and found that the 
patch slowed grep down on my machine.  Your benchmark took about 0.58s 
real-time with grep master, and about about 0.89s real-time with the 
updated patch.

I normally time with an AMD Phenom II X4 910e; this is a 65W Deneb 
processor released January 2010.  I just now tried a different 
processor, an Intel Xeon E5620 under RHEL 6.5; this is an 80W 
Westmere-EP processor released March 2010.  As with the AMD machine, I 
compiled with GCC 4.9.0 with default (-O2) optimizations.  The same 
benchmark took about 0.40s real-time with the master, and about 0.83s 
real-time with the updated patch.

> Though I don't analyze detail still, don't seem that overhead by check
> for `trans' in `tr' function, which is called each time the comparison
> of a character, can be ignorable.

I haven't looked into the details either, but I'd guess that the 
compiler and/or branch prediction optimizes most of that stuff away. 
Even if it didn't, we could use inlining rather than macroexpansion to 
optimize it away by hand, though I'd rather not bother unless the 
performance improvement is worthwhile.

By the way, the updated patch does pass 'make check', so my earlier 
version of the patch was incorrect and its timings should be ignored.

Previous Next

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