[Top][All Lists]

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

Re: how is grep so fast?

From: Tony Abou-Assaleh
Subject: Re: how is grep so fast?
Date: Mon, 08 Jun 2009 00:41:43 -0300
User-agent: Thunderbird (Macintosh/20090302)

Hi Edward,

GNU grep uses many of the latest state-of-the-art algorithms in string
and pattern matching. The source code has it all, and you are free to
reuse it under the GPL licence. Not that fgrep is even faster than grep
if you're matching only a fixed string and not a regular expression.

>From the README file:

GNU grep is based on a fast lazy-state deterministic matcher (about
twice as fast as stock Unix egrep) hybridized with a Boyer-Moore-Gosper
search for a fixed string that eliminates impossible text from being
considered by the full regexp matcher without necessarily having to
look at every character.  The result is typically many times faster
than Unix grep or egrep.  (Regular expressions containing backreferencing
will run more slowly, however.)

GNU grep also provides a library that you could use in your program, so
yes, there is API.



Tony Abou-Assaleh, PhD
Email:    address@hidden
Web site: http://tony.abou-assaleh.net
LinkedIn: http://www.linkedin.com/in/tabouasssaleh
Twitter:  http://twitter.com/tony_aa

Edward Peschko wrote:
> All,
> I was writing my own, 'grep-like' program, and while doing so, I noticed that
> grep is exceedingly fast.
> This simple loop on linux takes about 3 seconds, vs a whole grep run
> which took 1.
> while (fgets(buf, 32768, fp) { }
> Adding pcre made my equivalent 'grep' command come out to about 8 seconds.
> So how does grep manage to be so fast? I'm really curious about this; I'd like
> to emulate this behavior if possible, or maybe use grep as an API if possible.
> Thanks much,
> Ed

reply via email to

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