Re: grep -f scales extremely poorly with number of lines in pattern file

[Stepan Kasal]

Hello,

On Sun, Mar 19, 2006 at 11:28:48PM -0500, Narfi Stefansson wrote:
> I was expecting it to take order n time to match against n patterns, where n 
> is the number of lines in the pattern file.
> 
> What I am experiencing:  The execution time of grep -f behaves like n^a, with 
> a somewhere in the range [2.5, 3.0]. 

yes, that is the expected behaviour: the goal of grep is to scan files which
are much bigger than the total size of all the given patterns.

So it is OK that the time required to build the ``compiled structure'' from
the pattern list is huge.  fgrep compiles all the strings to one huge structure
and grep/egrep should treat all the patterns as if it were one huge regular
expression.

Hope this explains it,
        Stepan Kasal