[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Paul Eggert
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
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0

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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]