Date: Wed, 25 Jun 2003 00:03:45 -0400 From: Christopher Weimann <csw@k12hq.com> To: Sean Farley <sean-freebsd@farley.org> Cc: freebsd-hackers@freebsd.org Subject: Re: Replacing GNU grep revisited Message-ID: <20030625000344.A54424@smtp.k12us.com> In-Reply-To: <20030621103502.K18572@thor.farley.org>; from sean-freebsd@farley.org on Sat, Jun 21, 2003 at 10:55:59AM -0500 References: <20030621103502.K18572@thor.farley.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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!
------------------------------------------------------------
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030625000344.A54424>