From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Mon, 04 Jan 2010 16:03:04 GMT
Subject: Re: [PATCH] grep: do not do external grep on skip-worktree entries
Message-ID: <alpine.LFD.2.00.1001040801290.3630@localhost.localdomain>
In-Reply-To: <fc339e4a1001040757n31298f3h724eacfafb68c63e@mail.gmail.com>



On Tue, 5 Jan 2010, Miles Bader wrote:

> On Tue, Jan 5, 2010 at 12:54 AM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> > And "perf record" followed by "perf report" on the internal one shows
> > that it's not even regexec() - we use strstr() for the trivial case:
> 
> Does strstr use e.g. boyer-moore?  I imagine grep does...

It doesn't matter. Since we do the line-by-line thing, the input is always 
so short that DFA vs NFA vs BM vs other-clever-search doesn't matter. 
There is no scaling - the grep buffer tends to be too small for the 
algorithm to matter.

And the reason we do things line-by-line is that we need to then output 
things line-per-line.

			Linus