Replacing GNU grep revisited

[Christopher Weimann]

On Sat 06/21/2003-10:55:59AM -0500, Sean Farley wrote:
> 
> I have placed the patches up on Geocities¹ for others to try out.  They
> get freegrep fairly close to the performance of GNU's grep.  Also
> included is a small patch to regex to squeak a bit more performance out
> of it, but I am not certain if it actually helps or not.
> 

There is at least one aspect of freegrep that doesn't even come 
close to GNU grep, fgrep.  

I'll grant that this is a pretty extreeme example and perhaps not 
many people are making use of fgrep but...

GNU grep
%/usr/bin/time /usr/bin/fgrep -f /usr/share/dict/words /usr/share/games/fortune/fortunes2 > /dev/null
        5.40 real         4.98 user         0.41 sys
   42743  359388 2034033

freegrep
%/usr/bin/time /usr/local/bin/fgrep -f /usr/share/dict/words /usr/share/games/fortune/fortunes2 > /dev/null
      990.43 real       988.61 user         1.99 sys
   42743  359388 2034033

I ran both of these more than once so it is not a fluke.  After 
looking at it further it seems that freegrep does not use the 
Aho-Corasick algorithim for fgrep but just uses brute force.

Just for giggles I downloaded the V7 fgrep from 
http://www.tuhs.org/Archive/PDP-11/Trees/V7/usr/src/cmd/fgrep.c
to see what I'm guessing is Aho's version would do.

%/usr/bin/time ./fgrep -f /usr/share/dict/words /usr/share/games/fortune/fortunes2  | wc
        0.98 real         0.71 user         0.25 sys
   42743  359388 2034033

Which pretty much squashes GNU grep.  

I wonder how many of the other old utils outrun our modern ones.
I guess it must be all those gotos. :)

-- 
------------------------------------------------------------
Christopher Weimann
http://www.k12usa.com
K12USA.com Cool Tools for Schools!
------------------------------------------------------------