grep vs git grep performance?

grep vs git grep performance?

[Joe Perches]

Comparing a cache warm git grep vs command line grep
shows significant differences in cpu & wall clock.

Any ideas how to improve this?

$ time git grep "\bseq_.*%p\W" | wc -l
112

real	0m4.271s
user	0m15.520s
sys	0m0.395s

$ time grep -r --include=*.[ch] "\bseq_.*%p\W" * | wc -l
112

real	0m1.164s
user	0m0.847s
sys	0m0.314s

Re: grep vs git grep performance?

[Han-Wen Nienhuys]

On Thu, Oct 26, 2017 at 5:02 PM, Joe Perches <joe@perches.com> wrote:
> Comparing a cache warm git grep vs command line grep
> shows significant differences in cpu & wall clock.
>
> Any ideas how to improve this?

Is git-grep multithreaded? IIRC, grep -r uses multiple threads. (Do
you have a 4-core machine?)

--

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado

Re: grep vs git grep performance?

[Joe Perches]

On Thu, 2017-10-26 at 17:11 +0200, Han-Wen Nienhuys wrote:
> On Thu, Oct 26, 2017 at 5:02 PM, Joe Perches <joe@perches.com> wrote:
> > Comparing a cache warm git grep vs command line grep
> > shows significant differences in cpu & wall clock.
> > 
> > Any ideas how to improve this?
> 
> Is git-grep multithreaded?

Yes, at least according to the documentation

$ git grep --help
[]
       grep.threads
           Number of grep worker threads to use. If unset (or set to 0), 8
           threads are used by default (for now).

> IIRC, grep -r uses multiple threads. (Do
> you have a 4-core machine?)

I have a 2 core machine with hyperthreading

$ cat /proc/cpuinfo
[]
model name	: Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
stepping	: 3
microcode	: 0xba
cpu MHz		: 2400.000
cache size	: 3072 KB
physical id	: 0
siblings	: 4
core id		: 0
cpu cores	: 2

Re: grep vs git grep performance?

[SZEDER Gábor]

> Comparing a cache warm git grep vs command line grep
> shows significant differences in cpu & wall clock.
> 
> Any ideas how to improve this?
> 
> $ time git grep "\bseq_.*%p\W" | wc -l
> 112
> 
> real	0m4.271s
> user	0m15.520s
> sys	0m0.395s
> 
> $ time grep -r --include=*.[ch] "\bseq_.*%p\W" * | wc -l
> 112
> 
> real	0m1.164s
> user	0m0.847s
> sys	0m0.314s

Note that this "regular" grep is limited to *.c and *.h files, while
the above git grep invocation isn't and has to look at all tracked
files.  How does

  git grep "\bseq_.*%p\W" "*.[ch]"

fare?

Re: grep vs git grep performance?

[Joe Perches]

On Thu, 2017-10-26 at 18:13 +0200, SZEDER Gábor wrote:
> > Comparing a cache warm git grep vs command line grep
> > shows significant differences in cpu & wall clock.
> > 
> > Any ideas how to improve this?
> > 
> > $ time git grep "\bseq_.*%p\W" | wc -l
> > 112
> > 
> > real	0m4.271s
> > user	0m15.520s
> > sys	0m0.395s
> > 
> > $ time grep -r --include=*.[ch] "\bseq_.*%p\W" * | wc -l
> > 112
> > 
> > real	0m1.164s
> > user	0m0.847s
> > sys	0m0.314s
> 
> Note that this "regular" grep is limited to *.c and *.h files, while
> the above git grep invocation isn't and has to look at all tracked
> files.  How does
> 
>   git grep "\bseq_.*%p\W" "*.[ch]"
> 
> fare?

Same-ish

$ time git grep "\bseq_.*%p\W" -- "*.[ch]" | wc -l
112

real	0m4.225s
user	0m14.485s
sys	0m0.413s

Re: grep vs git grep performance?

[Stefan Beller]

+ Avar who knows a thing about pcre (I assume the regex compilation
has impact on grep speed)

On Thu, Oct 26, 2017 at 8:02 AM, Joe Perches <joe@perches.com> wrote:
> Comparing a cache warm git grep vs command line grep
> shows significant differences in cpu & wall clock.
>
> Any ideas how to improve this?
>
> $ time git grep "\bseq_.*%p\W" | wc -l
> 112
>
> real    0m4.271s
> user    0m15.520s
> sys     0m0.395s
>
> $ time grep -r --include=*.[ch] "\bseq_.*%p\W" * | wc -l
> 112
>
> real    0m1.164s
> user    0m0.847s
> sys     0m0.314s
>

I wonder how much is algorithmic advantage vs coding/micro
optimization that we can do.

Re: grep vs git grep performance?

[Joe Perches]

On Thu, 2017-10-26 at 09:58 -0700, Stefan Beller wrote:
> + Avar who knows a thing about pcre (I assume the regex compilation
> has impact on grep speed)
> 
> On Thu, Oct 26, 2017 at 8:02 AM, Joe Perches <joe@perches.com> wrote:
> > Comparing a cache warm git grep vs command line grep
> > shows significant differences in cpu & wall clock.
> > 
> > Any ideas how to improve this?
> > 
> > $ time git grep "\bseq_.*%p\W" | wc -l
> > 112
> > 
> > real    0m4.271s
> > user    0m15.520s
> > sys     0m0.395s
> > 
> > $ time grep -r --include=*.[ch] "\bseq_.*%p\W" * | wc -l
> > 112
> > 
> > real    0m1.164s
> > user    0m0.847s
> > sys     0m0.314s
> > 
> 
> I wonder how much is algorithmic advantage vs coding/micro
> optimization that we can do.

As do I.  I presume this is libpcre related.

For instance, git grep performance is better than grep for:

$ time git grep -w "seq_printf" -- "*.[ch]" | wc -l
8609

real	0m0.301s
user	0m0.548s
sys	0m0.372s

$ time grep -w -r --include=*.[ch] "seq_printf" * | wc -l
8609

real	0m0.706s
user	0m0.396s
sys	0m0.309s

Re: grep vs git grep performance?

[Stefan Beller]

On Thu, Oct 26, 2017 at 10:41 AM, Joe Perches <joe@perches.com> wrote:
> On Thu, 2017-10-26 at 09:58 -0700, Stefan Beller wrote:
>> + Avar who knows a thing about pcre (I assume the regex compilation
>> has impact on grep speed)
>>
>> On Thu, Oct 26, 2017 at 8:02 AM, Joe Perches <joe@perches.com> wrote:
>> > Comparing a cache warm git grep vs command line grep
>> > shows significant differences in cpu & wall clock.
>> >
>> > Any ideas how to improve this?
>> >
>> > $ time git grep "\bseq_.*%p\W" | wc -l
>> > 112
>> >
>> > real    0m4.271s
>> > user    0m15.520s
>> > sys     0m0.395s
>> >
>> > $ time grep -r --include=*.[ch] "\bseq_.*%p\W" * | wc -l
>> > 112
>> >
>> > real    0m1.164s
>> > user    0m0.847s
>> > sys     0m0.314s
>> >
>>
>> I wonder how much is algorithmic advantage vs coding/micro
>> optimization that we can do.
>
> As do I.  I presume this is libpcre related.
>
> For instance, git grep performance is better than grep for:
>
> $ time git grep -w "seq_printf" -- "*.[ch]" | wc -l
> 8609
>
> real    0m0.301s
> user    0m0.548s
> sys     0m0.372s
>
> $ time grep -w -r --include=*.[ch] "seq_printf" * | wc -l
> 8609
>
> real    0m0.706s
> user    0m0.396s
> sys     0m0.309s
>

One important piece of information is what version of Git you are running,


$ git tag --contains origin/ab/pcre-v2
v2.14.0
...

(and the version of pcre, see the numbers)
https://git.kernel.org/pub/scm/git/git.git/commit/?id=94da9193a6eb8f1085d611c04ff8bbb4f5ae1e0a

Re: grep vs git grep performance?

[Joe Perches]

On Thu, 2017-10-26 at 10:45 -0700, Stefan Beller wrote:
> On Thu, Oct 26, 2017 at 10:41 AM, Joe Perches <joe@perches.com> wrote:
> > On Thu, 2017-10-26 at 09:58 -0700, Stefan Beller wrote:
> > > + Avar who knows a thing about pcre (I assume the regex compilation
> > > has impact on grep speed)
> > > 
> > > On Thu, Oct 26, 2017 at 8:02 AM, Joe Perches <joe@perches.com> wrote:
> > > > Comparing a cache warm git grep vs command line grep
> > > > shows significant differences in cpu & wall clock.
> > > > 
> > > > Any ideas how to improve this?
> > > > 
> > > > $ time git grep "\bseq_.*%p\W" | wc -l
> > > > 112
> > > > 
> > > > real    0m4.271s
> > > > user    0m15.520s
> > > > sys     0m0.395s
> > > > 
> > > > $ time grep -r --include=*.[ch] "\bseq_.*%p\W" * | wc -l
> > > > 112
> > > > 
> > > > real    0m1.164s
> > > > user    0m0.847s
> > > > sys     0m0.314s
> > > > 
> > > 
> > > I wonder how much is algorithmic advantage vs coding/micro
> > > optimization that we can do.
> > 
> > As do I.  I presume this is libpcre related.
> > 
> > For instance, git grep performance is better than grep for:
> > 
> > $ time git grep -w "seq_printf" -- "*.[ch]" | wc -l
> > 8609
> > 
> > real    0m0.301s
> > user    0m0.548s
> > sys     0m0.372s
> > 
> > $ time grep -w -r --include=*.[ch] "seq_printf" * | wc -l
> > 8609
> > 
> > real    0m0.706s
> > user    0m0.396s
> > sys     0m0.309s
> > 
> 
> One important piece of information is what version of Git you are running,
> 
> 
> $ git tag --contains origin/ab/pcre-v2
> v2.14.0

v2.10

> ...
> 
> (and the version of pcre, see the numbers)
> https://git.kernel.org/pub/scm/git/git.git/commit/?id=94da9193a6eb8f1085d611c04ff8bbb4f5ae1e0a

I definitely didn't have that one.

I recompiled git latest (with USE_LIBPCRE2) and reran.

Here are the results

$ git --version
git version 2.15.0.rc2.48.g4e40fb3

$ time git grep -P "\bseq_.*%p\W" -- "*.[ch]" | wc -l
112

real	0m0.437s
user	0m1.008s
sys	0m0.381s

So, git grep performance has already been
quite successfully improved.

Thanks.

Re: grep vs git grep performance?

[Ævar Arnfjörð Bjarmason]

On Fri, Oct 27 2017, Joe Perches jotted:

> On Thu, 2017-10-26 at 10:45 -0700, Stefan Beller wrote:
>> On Thu, Oct 26, 2017 at 10:41 AM, Joe Perches <joe@perches.com> wrote:
>> > On Thu, 2017-10-26 at 09:58 -0700, Stefan Beller wrote:
>> > > + Avar who knows a thing about pcre (I assume the regex compilation
>> > > has impact on grep speed)
>> > >
>> > > On Thu, Oct 26, 2017 at 8:02 AM, Joe Perches <joe@perches.com> wrote:
>> > > > Comparing a cache warm git grep vs command line grep
>> > > > shows significant differences in cpu & wall clock.
>> > > >
>> > > > Any ideas how to improve this?
>> > > >
>> > > > $ time git grep "\bseq_.*%p\W" | wc -l
>> > > > 112
>> > > >
>> > > > real    0m4.271s
>> > > > user    0m15.520s
>> > > > sys     0m0.395s
>> > > >
>> > > > $ time grep -r --include=*.[ch] "\bseq_.*%p\W" * | wc -l
>> > > > 112
>> > > >
>> > > > real    0m1.164s
>> > > > user    0m0.847s
>> > > > sys     0m0.314s
>> > > >
>> > >
>> > > I wonder how much is algorithmic advantage vs coding/micro
>> > > optimization that we can do.
>> >
>> > As do I.  I presume this is libpcre related.
>> >
>> > For instance, git grep performance is better than grep for:
>> >
>> > $ time git grep -w "seq_printf" -- "*.[ch]" | wc -l
>> > 8609
>> >
>> > real    0m0.301s
>> > user    0m0.548s
>> > sys     0m0.372s
>> >
>> > $ time grep -w -r --include=*.[ch] "seq_printf" * | wc -l
>> > 8609
>> >
>> > real    0m0.706s
>> > user    0m0.396s
>> > sys     0m0.309s
>> >
>>
>> One important piece of information is what version of Git you are running,
>>
>>
>> $ git tag --contains origin/ab/pcre-v2
>> v2.14.0
>
> v2.10
>
>> ...
>>
>> (and the version of pcre, see the numbers)
>> https://git.kernel.org/pub/scm/git/git.git/commit/?id=94da9193a6eb8f1085d611c04ff8bbb4f5ae1e0a
>
> I definitely didn't have that one.
>
> I recompiled git latest (with USE_LIBPCRE2) and reran.
>
> Here are the results
>
> $ git --version
> git version 2.15.0.rc2.48.g4e40fb3
>
> $ time git grep -P "\bseq_.*%p\W" -- "*.[ch]" | wc -l
> 112
>
> real	0m0.437s
> user	0m1.008s
> sys	0m0.381s
>
> So, git grep performance has already been
> quite successfully improved.

...and I have WIP patches to use the PCRE engine for patterns without -P
which I intend to start sending soon after the next release.

Re: grep vs git grep performance?

[Joe Perches]

On Sat, 2017-10-28 at 00:11 +0200, Ævar Arnfjörð Bjarmason wrote:
> On Fri, Oct 27 2017, Joe Perches jotted:
[]
> > git grep performance has already been
> > quite successfully improved.
> 
> ...and I have WIP patches to use the PCRE engine for patterns without -P
> which I intend to start sending soon after the next release.

One addition that would be quite nice would be
an option to have regex matches span input lines.

grep v2.54 was the last grep version that allowed
this and I keep it around just for that.

ie:

$ cat hello.txt 
Hello
World
$ grep -P "Hello\s*World" hello.txt 
$ grep-2.5.4 -P "Hello\s*World" hello.txt 
Hello
World

Re: grep vs git grep performance?

[Ævar Arnfjörð Bjarmason]

On Fri, Oct 27 2017, Joe Perches jotted:

> On Sat, 2017-10-28 at 00:11 +0200, Ævar Arnfjörð Bjarmason wrote:
>> On Fri, Oct 27 2017, Joe Perches jotted:
> []
>> > git grep performance has already been
>> > quite successfully improved.
>>
>> ...and I have WIP patches to use the PCRE engine for patterns without -P
>> which I intend to start sending soon after the next release.
>
> One addition that would be quite nice would be
> an option to have regex matches span input lines.
>
> grep v2.54 was the last grep version that allowed
> this and I keep it around just for that.
>
> ie:
>
> $ cat hello.txt
> Hello
> World
> $ grep -P "Hello\s*World" hello.txt
> $ grep-2.5.4 -P "Hello\s*World" hello.txt
> Hello
> World

I'm unable to build 2.5.4 and can't find anything relevant in the
release notes at a quick glance around that time saying that this would
be removed, if you can still build it I'd be interested to see what this
bisects down to in grep.git.

But aside from that, a feature like this constrains the regex
implementation a lot since it's going to need to either match the entire
file as we'd need to do with PCRE, or we'd need to really deeply embed
the core logic of the regex matcher into our grep implementation.

I.e. in this case a more optimal implementation would start by parsing
this regex down:

    ((EXACT "Hello")
     (STAR (POSIXU "\s"))
     (EXACT "World"))

Then when you open the file you can start searching for the fixed-string
"Hello", if you don't find that you're done, if you do you can forward
look-ahead for the fixed "World", and only if you find that do you need
to match the more complex part in the middle.

Whereas our API for the internal regex matchers now is that we find the
boundaries of newlines and batch-match a bunch of lines with a match()
function that takes a string, and if that matches we drill down to what
specific line matches.

Which is not to say that this can't be done without a potentially
unacceptable memory trade-off (i.e. matching the entire file in all
cases), the PCRE2 engine in particular includes some I/O abstractions
that we're not using but could (but I haven't looked into it).

But right now the entire internal API we have is constrained by catering
to the lowest common denominator (a regexec that takes a char*), so
supporting more fancy multi-line matching features can be a PITA since
we'd need to maintain both codepaths.

Or we could make PCRE a hard dependency, which given the performance
advantages I'm increasingly willing to make the case for.