Date: Wed, 25 Jun 2003 12:28:37 -0400 From: Christopher Weimann <csw@k12hq.com> To: freebsd-hackers@freebsd.org Subject: Re: Replacing GNU grep revisited Message-ID: <20030625000344.A54424@smtp.k12us.com> Resent-Message-ID: <20030625165947.91894.qmail@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
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>