# grep vs git grep performance? 12 messages from 2017-10-26 to 2017-10-28. Participants: Joe Perches, Han-Wen Nienhuys, SZEDER Gábor, Stefan Beller, Ævar Arnfjörð Bjarmason. Thread: https://gitlist.dev/t/47034 ## Joe Perches, 2017-10-26 15:02 Subject: grep vs git grep performance? Message-ID: <1509030170.10651.59.camel@perches.com> URL: https://gitlist.dev/e/1509030170.10651.59.camel%40perches.com ``` 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 ``` ## Han-Wen Nienhuys, 2017-10-26 15:11 Subject: Re: grep vs git grep performance? Message-ID: URL: https://gitlist.dev/e/CAFQ2z_P9bpw%2BPc2DhJTCB8dxj-5JAKLE%3DnyvToGuiRA8wV66Wg%40mail.gmail.com In-Reply-To: <1509030170.10651.59.camel@perches.com> ``` On Thu, Oct 26, 2017 at 5:02 PM, Joe Perches 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 Perches, 2017-10-26 15:55 Subject: Re: grep vs git grep performance? Message-ID: <1509033321.11245.3.camel@perches.com> URL: https://gitlist.dev/e/1509033321.11245.3.camel%40perches.com In-Reply-To: ``` On Thu, 2017-10-26 at 17:11 +0200, Han-Wen Nienhuys wrote: > On Thu, Oct 26, 2017 at 5:02 PM, Joe Perches 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ábor, 2017-10-26 16:13 Subject: Re: grep vs git grep performance? Message-ID: <20171026161354.23037-1-szeder.dev@gmail.com> URL: https://gitlist.dev/e/20171026161354.23037-1-szeder.dev%40gmail.com In-Reply-To: <1509030170.10651.59.camel@perches.com> ``` > 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 Perches, 2017-10-26 16:20 Subject: Re: grep vs git grep performance? Message-ID: <1509034857.11245.4.camel@perches.com> URL: https://gitlist.dev/e/1509034857.11245.4.camel%40perches.com In-Reply-To: <20171026161354.23037-1-szeder.dev@gmail.com> ``` 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 Beller, 2017-10-26 16:58 Subject: Re: grep vs git grep performance? Message-ID: URL: https://gitlist.dev/e/CAGZ79ka41NdzNxGAvtVW802088KydKkp3yHx%3DZ5q3Mc9GGa_%2Bg%40mail.gmail.com In-Reply-To: <1509030170.10651.59.camel@perches.com> ``` + 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 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 Perches, 2017-10-26 17:41 Subject: Re: grep vs git grep performance? Message-ID: <1509039696.11245.9.camel@perches.com> URL: https://gitlist.dev/e/1509039696.11245.9.camel%40perches.com In-Reply-To: ``` 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 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 Beller, 2017-10-26 17:45 Subject: Re: grep vs git grep performance? Message-ID: URL: https://gitlist.dev/e/CAGZ79kYWPunzZ2u%3DMtCoCadxXu_4etEK5DYnhYXo%2BCgeHrXQwQ%40mail.gmail.com In-Reply-To: <1509039696.11245.9.camel@perches.com> ``` On Thu, Oct 26, 2017 at 10:41 AM, Joe Perches 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 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 Perches, 2017-10-27 17:22 Subject: Re: grep vs git grep performance? Message-ID: <1509124942.1914.9.camel@perches.com> URL: https://gitlist.dev/e/1509124942.1914.9.camel%40perches.com In-Reply-To: ``` On Thu, 2017-10-26 at 10:45 -0700, Stefan Beller wrote: > On Thu, Oct 26, 2017 at 10:41 AM, Joe Perches 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 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ð Bjarmason, 2017-10-27 22:11 Subject: Re: grep vs git grep performance? Message-ID: <877evgxmu7.fsf@evledraar.booking.com> URL: https://gitlist.dev/e/877evgxmu7.fsf%40evledraar.booking.com In-Reply-To: <1509124942.1914.9.camel@perches.com> ``` 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 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 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 Perches, 2017-10-27 23:22 Subject: Re: grep vs git grep performance? Message-ID: <1509146542.1914.19.camel@perches.com> URL: https://gitlist.dev/e/1509146542.1914.19.camel%40perches.com In-Reply-To: <877evgxmu7.fsf@evledraar.booking.com> ``` 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ð Bjarmason, 2017-10-28 07:45 Subject: Re: grep vs git grep performance? Message-ID: <8760azyato.fsf@evledraar.booking.com> URL: https://gitlist.dev/e/8760azyato.fsf%40evledraar.booking.com In-Reply-To: <1509146542.1914.19.camel@perches.com> ``` 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. ```