Joe PerchesComparing 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
Han-Wen NienhuysRe: grep vs git grep performance?
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
Joe PerchesRe: grep vs git grep performance?
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
SZEDER GáborRe: grep vs git grep performance?
> 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?
Joe PerchesRe: grep vs git grep performance?
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
Stefan BellerRe: grep vs git grep performance?
+ 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.
Joe PerchesRe: grep vs git grep performance?
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
Stefan BellerRe: grep vs git grep performance?
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
Joe PerchesRe: grep vs git grep performance?
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.
Ævar Arnfjörð BjarmasonRe: grep vs git grep performance?
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.
Joe PerchesRe: grep vs git grep performance?
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
Ævar Arnfjörð BjarmasonRe: grep vs git grep performance?
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.