From: Jeff King <peff@peff.net>
Date: Tue, 12 Jan 2010 16:21:54 GMT
Subject: Re: [PATCH] grep: do not do external grep on skip-worktree entries
Message-ID: <20100112162154.GA25092@coredump.intra.peff.net>
In-Reply-To: <alpine.LFD.2.00.1001110748560.13040@localhost.localdomain>

On Mon, Jan 11, 2010 at 07:59:18AM -0800, Linus Torvalds wrote:

> The meh news: this shows how grep is faster than regexec() due to being a 
> smarter algorithm. For the non-fixed case (I used "qwerty.*as"), the 
> numbers are
> 
>  - built-in:
> 	real	0m0.548s
> 	user	0m0.384s
> 	sys	0m0.152s
> 
>  - external:
> 	real	0m0.415s
> 	user	0m0.176s
> 	sys	0m0.160s
> 
> so it really is just 'strstr()' that is faster. But This is a 'meh', 
> because I don't really care, and the new code is still way faster than the 
> old one. And I'd be personally willing to just drop the external grep if 
> this is the worst problem.

Just for fun, I repeated my pcre tests on what's in pu (which has
Junio's lookahead patch now). Before they didn't show any improvement
because we wasted all of our time in non-regex code. There is some
improvement in just using pcre, but I didn't get any improvement by
tweaking it:

[pu]
$ time git grep 'qwerty.*as' >/dev/null
real    0m1.007s
user    0m0.752s
sys     0m0.252s

[pu + pcre]
$ time git grep --no-ext-grep 'qwerty.*as' >/dev/null
real    0m0.864s
user    0m0.648s
sys     0m0.212s

[pu + pcre_study]
$ time git grep --no-ext-grep 'qwerty.*as' >/dev/null
real    0m0.866s
user    0m0.628s
sys     0m0.200s

[pu + pcre_dfa_exec]
$ time git grep --no-ext-grep 'qwerty.*as' >/dev/null
real    0m0.868s
user    0m0.608s
sys     0m0.256s

So pcre seems to buy us about 15%, and tweaking it gets lost in the
noise (or I am tweaking it badly, which is entirely possible). I doubt
it's worth the trouble of supporting pcre for that much.

And let me add an additional vote against strstr:

$ time git grep --no-ext-grep qwerty >/dev/null
real    0m3.285s
user    0m3.032s
sys     0m0.252s

-Peff