Re: [PATCH] grep: do not do external grep on skip-worktree entries

On Mon, 11 Jan 2010, Fredrik Kuivinen wrote:

Any ideas on how this can be explained?

Could it be a bad 'strstr()' implementation? 

Try a complex pattern ("qwerty.*as" finds the same line), and see if that 
too is slower than before. If that is faster than it used to be (with 
--no-ext-grep, of course), then it's strstr() that is badly implemented.

For me, on x86-64 (Fedora-12), strstr() seems to do pretty well. But it's 
easy to do a stupid implementation of strstr that does a 'strlen()' first, 
for example, and thus always traverses all data _twice_ etc. Depending on 
cache sizes etc, that can end up killing performance (or not mattering 
much at all..)

		Linus

On Mon, Jan 11, 2010 at 20:29, Linus Torvalds
[off-list ref] wrote:

On Mon, 11 Jan 2010, Fredrik Kuivinen wrote:

quoted

Any ideas on how this can be explained?

Could it be a bad 'strstr()' implementation?

Try a complex pattern ("qwerty.*as" finds the same line), and see if that
too is slower than before. If that is faster than it used to be (with
--no-ext-grep, of course), then it's strstr() that is badly implemented.

Ah, yes, that's it. With the pattern "qwerty.*as" I get 2.5s with the
patch and 6s without.

Thanks.

- Fredrik

On Mon, 11 Jan 2010, Fredrik Kuivinen wrote:

quoted

Try a complex pattern ("qwerty.*as" finds the same line), and see if that
too is slower than before. If that is faster than it used to be (with
--no-ext-grep, of course), then it's strstr() that is badly implemented.

Ah, yes, that's it. With the pattern "qwerty.*as" I get 2.5s with the
patch and 6s without.

Ok, so on your machine, regcomp() is basically twice as fast as strstr().

Which is not entirely unexpected: I was actually surprised by strstr() 
being apparently so good on my machine. I do not generally expect things 
like that to be at all optimized for bigger working sets. Most common uses 
of strstr() are in short strings - not "strings" that are many kilobytes 
in size (the whole file).

In fact, I suspect it works so well for me because in my version of glibc 
it's not just SSE-optimized: judging by the naming it's SSE4.2 optimized - 
so the case I see on my machine will _only_ happen on Nehalem-based cores 
(ie the new "Core i[357]" cpu's).

It is entirely possible that strstr in general is a disaster.

		Linus

On Mon, Jan 11, 2010 at 21:07, Linus Torvalds
[off-list ref] wrote:

On Mon, 11 Jan 2010, Fredrik Kuivinen wrote:

quoted

quoted

Try a complex pattern ("qwerty.*as" finds the same line), and see if that
too is slower than before. If that is faster than it used to be (with
--no-ext-grep, of course), then it's strstr() that is badly implemented.

Ah, yes, that's it. With the pattern "qwerty.*as" I get 2.5s with the
patch and 6s without.

Ok, so on your machine, regcomp() is basically twice as fast as strstr().

Yes.

Which is not entirely unexpected: I was actually surprised by strstr()
being apparently so good on my machine. I do not generally expect things
like that to be at all optimized for bigger working sets. Most common uses
of strstr() are in short strings - not "strings" that are many kilobytes
in size (the whole file).

In fact, I suspect it works so well for me because in my version of glibc
it's not just SSE-optimized: judging by the naming it's SSE4.2 optimized -
so the case I see on my machine will _only_ happen on Nehalem-based cores
(ie the new "Core i[357]" cpu's).

It is entirely possible that strstr in general is a disaster.

Another option is to use memmem instead. As we know the length of the
buffer already it should be a slight improvement over strstr for
everyone. memmem may cause some portability problems though as it is a
GNU extension.

I get these results: (git-grep --no-ext-grep qwerty, best of five)

Junio's patch: 0:04.84
memmem (attached patch on top of Junio's): 0:02.91
regcomp/regexec (I changed is_fixed to always return 0, also on top of
Junio's): 0:02.02

- Fredrik

On Mon, 11 Jan 2010, Fredrik Kuivinen wrote:

Another option is to use memmem instead. As we know the length of the
buffer already it should be a slight improvement over strstr for
everyone. memmem may cause some portability problems though as it is a
GNU extension.

I'd almost prefer to just drop the strstr entirely.

It's not actually all *that* big a win, even on my machine. I get

 - strstr:

        real    0m0.309s
        user    0m0.168s
        sys     0m0.136s

 - regexec:

	real	0m0.410s
	user	0m0.220s
	sys	0m0.116s

so yeah, it's slower, but not by a huge degree. With strstr, "git grep" 
actually beats the external grep for me, but I don't really care. It's 
already way better than it used to be - and clearly strstr has a lot of 
potential problems.

Sure memmem() might be better for you than strstr, but on the other hand, 
it might easily be worse than strstr for others - and not just from a 
portability standpoint. Is memmem() optimized to take advantage of SSE4.2? 
I suspect it is not, exactly _because_ it's a GNU extension, so Intel 
hasn't published optimized sample code for people to use.

So I would argue against even bothering to try memmem. Especially since	in 
your case, regexec() is apparently faster than memmem _anyway_. I expect 
that it is for me too, but I'm too lazy to check.

			Linus