{"thread":{"id":"48671","subject":"git grep with leading inverted bracket expression","startedAt":"2018-06-07T15:27:16Z","lastAt":"2018-06-07T19:29:54Z","messageCount":4,"participants":["Matthew Wilcox","Ævar Arnfjörð Bjarmason"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"349645","messageId":"20180607152711.GA27079@bombadil.infradead.org","threadId":"48671","inReplyTo":null,"subject":"git grep with leading inverted bracket expression","fromName":"Matthew Wilcox","fromEmail":"willy@infradead.org","sentAt":"2018-06-07T15:27:11Z","receivedAt":"2018-06-07T15:27:16Z","isPatch":false,"sender":{"key":"willy@infradead.org","avatar":null},"body":"\nIf the first atom of a regex is a bracket expression with an inverted range,\ngit grep is very slow.\n\n$ time git grep 'struct_size' >/dev/null\n\nreal\t0m0.368s\nuser\t0m0.563s\nsys\t0m0.453s\n\n$ time git grep '[^t]truct_size' >/dev/null\n\nreal\t0m31.529s\nuser\t1m54.909s\nsys\t0m0.805s\n\nIf the bracket expression is moved to even the second position in the string,\nit runs much faster:\n\n$ time git grep 's[^p]ruct_size' >/dev/null\n\nreal\t0m3.989s\nuser\t0m13.939s\nsys\t0m0.403s\n\nIt's pretty bad with even a '.' as the first character:\n\n$ time git grep '.truct_size' >/dev/null\n\nreal\t0m14.514s\nuser\t0m52.624s\nsys\t0m0.598s\n\n$ git --version\ngit version 2.17.1\n\nSetting LANG=C improves matters by a factor of 3-4 (depending if you\ncount real or user time):\n\n$ time git grep '[^t]truct_size' >/dev/null\nreal\t0m10.035s\nuser\t0m28.795s\nsys\t0m0.537s\n\n(this is using something pretty close to Linus' current HEAD of the\nlinux repository, an i7-7500, 16GB memory).\n"},{"id":"349664","messageId":"87602uza56.fsf@evledraar.gmail.com","threadId":"48671","inReplyTo":"20180607152711.GA27079@bombadil.infradead.org","subject":"Re: git grep with leading inverted bracket expression","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-06-07T19:09:25Z","receivedAt":"2018-06-07T19:09:33Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jun 07 2018, Matthew Wilcox wrote:\n\n> If the first atom of a regex is a bracket expression with an inverted range,\n> git grep is very slow.\n>\n> $ time git grep 'struct_size' >/dev/null\n>\n> real\t0m0.368s\n> user\t0m0.563s\n> sys\t0m0.453s\n>\n> $ time git grep '[^t]truct_size' >/dev/null\n>\n> real\t0m31.529s\n> user\t1m54.909s\n> sys\t0m0.805s\n>\n> If the bracket expression is moved to even the second position in the string,\n> it runs much faster:\n>\n> $ time git grep 's[^p]ruct_size' >/dev/null\n>\n> real\t0m3.989s\n> user\t0m13.939s\n> sys\t0m0.403s\n>\n> It's pretty bad with even a '.' as the first character:\n>\n> $ time git grep '.truct_size' >/dev/null\n>\n> real\t0m14.514s\n> user\t0m52.624s\n> sys\t0m0.598s\n>\n> $ git --version\n> git version 2.17.1\n>\n> Setting LANG=C improves matters by a factor of 3-4 (depending if you\n> count real or user time):\n>\n> $ time git grep '[^t]truct_size' >/dev/null\n> real\t0m10.035s\n> user\t0m28.795s\n> sys\t0m0.537s\n>\n> (this is using something pretty close to Linus' current HEAD of the\n> linux repository, an i7-7500, 16GB memory).\n\nI have some WIP patches to fix all of this, which I'll hopefully submit\nbefore 2.19 is out the door.\n\nWhat you've discovered here is how shitty your libc regex engine is,\nbecause unless you provide -P and compile with a reasonably up-to-date\nlibpcre (preferably v2) with JIT that's what you'll get.\n\nThe reason stuff like 'struct_size' is so much faster is because there\nwe don't use any regex engine at all, but rather an optimized\nfixed-string searcher.\n\nWith our own benchmarks modified per your E-Mail:\n    \n    diff --git a/t/perf/p7820-grep-engines.sh b/t/perf/p7820-grep-engines.sh\n    index 8b09c5bf32..fe4c5681da 100755\n    --- a/t/perf/p7820-grep-engines.sh\n    +++ b/t/perf/p7820-grep-engines.sh\n    @@ -28,11 +28,10 @@ then\n     fi\n    \n     for pattern in \\\n    -       'how.to' \\\n    -       '^how to' \\\n    -       '[how] to' \\\n    -       '\\(e.t[^ ]*\\|v.ry\\) rare' \\\n    -       'm\\(ú\\|u\\)lt.b\\(æ\\|y\\)te'\n    +       'struct size' \\\n    +       '[^t]truct_size' \\\n    +       's[^p]ruct_size' \\\n    +       '.truct_size'\n     do\n            for engine in basic extended perl\n            do\n\nI get these results against linux.git:\n\n    $ GIT_PERF_LARGE_REPO=~/g/linux ./run p7820-grep-engines.sh\n    [...]\n    Test                                      this tree\n    ----------------------------------------------------------\n    7820.1: basic grep 'struct size'          0.23(0.52+0.76)\n    7820.2: extended grep 'struct size'       0.22(0.60+0.61)\n    7820.3: perl grep 'struct size'           0.22(0.56+0.65)\n    7820.5: basic grep '[^t]truct_size'       4.29(29.43+0.51)\n    7820.6: extended grep '[^t]truct_size'    4.27(29.59+0.36)\n    7820.7: perl grep '[^t]truct_size'        0.21(0.40+0.69)\n    7820.9: basic grep 's[^p]ruct_size'       0.49(2.22+0.49)\n    7820.10: extended grep 's[^p]ruct_size'   0.43(2.24+0.48)\n    7820.11: perl grep 's[^p]ruct_size'       0.21(0.38+0.71)\n    7820.13: basic grep '.truct_size'         4.42(31.29+0.44)\n    7820.14: extended grep '.truct_size'      4.50(31.18+0.46)\n    7820.15: perl grep '.truct_size'          0.21(0.35+0.75)\n\nSo you need to just use an up-to-date libpcre2 & -P and performance\nwon't suck.\n\nMy WIP patches will make us use PCRE for all grep modes, using an API it\nhas to convert basic & extended regexp syntax to its own syntax, so\nwe'll be able to do that transparently.\n"},{"id":"349665","messageId":"20180607192213.GB24370@bombadil.infradead.org","threadId":"48671","inReplyTo":"87602uza56.fsf@evledraar.gmail.com","subject":"Re: git grep with leading inverted bracket expression","fromName":"Matthew Wilcox","fromEmail":"willy@infradead.org","sentAt":"2018-06-07T19:22:13Z","receivedAt":"2018-06-07T19:22:16Z","isPatch":false,"sender":{"key":"willy@infradead.org","avatar":null},"body":"On Thu, Jun 07, 2018 at 09:09:25PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> On Thu, Jun 07 2018, Matthew Wilcox wrote:\n> > If the first atom of a regex is a bracket expression with an inverted range,\n> > git grep is very slow.\n> \n> I have some WIP patches to fix all of this, which I'll hopefully submit\n> before 2.19 is out the door.\n> \n> What you've discovered here is how shitty your libc regex engine is,\n> because unless you provide -P and compile with a reasonably up-to-date\n> libpcre (preferably v2) with JIT that's what you'll get.\n\nI'm using Debian's build, and it is linked against a recent libpcre2:\n$ ldd /usr/lib/git-core/git\n\tlibpcre2-8.so.0 => /usr/lib/x86_64-linux-gnu/libpcre2-8.so.0 (0x00007f59ad5f2000)\n$ dpkg --status libpcre2-8-0\nVersion: 10.31-3\n\nBut I wasn't using -P.  If I do, then I see the performance numbers you do:\n\n$ time git grep -P '[^t]truct_size' >/dev/null\nreal\t0m0.354s\nuser\t0m0.340s\nsys\t0m0.639s\n$ time git grep -P 'struct_size' >/dev/null\nreal\t0m0.336s\nuser\t0m0.552s\nsys\t0m0.457s\n$ time git grep 'struct_size' >/dev/null\nreal\t0m0.335s\nuser\t0m0.535s\nsys\t0m0.474s\n\n> So you need to just use an up-to-date libpcre2 & -P and performance\n> won't suck.\n\nI don't tend to use terribly advanced regexps, so I'll just set\ngrep.patternType to 'perl' and then it'll automatically be fast for me\nwithout your patches ;-)\n\n> My WIP patches will make us use PCRE for all grep modes, using an API it\n> has to convert basic & extended regexp syntax to its own syntax, so\n> we'll be able to do that transparently.\n\nThat's clearly the right answer.  Thanks!\n"},{"id":"349666","messageId":"874liez977.fsf@evledraar.gmail.com","threadId":"48671","inReplyTo":"20180607192213.GB24370@bombadil.infradead.org","subject":"Re: git grep with leading inverted bracket expression","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-06-07T19:29:48Z","receivedAt":"2018-06-07T19:29:54Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jun 07 2018, Matthew Wilcox wrote:\n\n> On Thu, Jun 07, 2018 at 09:09:25PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>> On Thu, Jun 07 2018, Matthew Wilcox wrote:\n>> > If the first atom of a regex is a bracket expression with an inverted range,\n>> > git grep is very slow.\n>>\n>> I have some WIP patches to fix all of this, which I'll hopefully submit\n>> before 2.19 is out the door.\n>>\n>> What you've discovered here is how shitty your libc regex engine is,\n>> because unless you provide -P and compile with a reasonably up-to-date\n>> libpcre (preferably v2) with JIT that's what you'll get.\n>\n> I'm using Debian's build, and it is linked against a recent libpcre2:\n> $ ldd /usr/lib/git-core/git\n> \tlibpcre2-8.so.0 => /usr/lib/x86_64-linux-gnu/libpcre2-8.so.0 (0x00007f59ad5f2000)\n> $ dpkg --status libpcre2-8-0\n> Version: 10.31-3\n>\n> But I wasn't using -P.  If I do, then I see the performance numbers you do:\n>\n> $ time git grep -P '[^t]truct_size' >/dev/null\n> real\t0m0.354s\n> user\t0m0.340s\n> sys\t0m0.639s\n> $ time git grep -P 'struct_size' >/dev/null\n> real\t0m0.336s\n> user\t0m0.552s\n> sys\t0m0.457s\n> $ time git grep 'struct_size' >/dev/null\n> real\t0m0.335s\n> user\t0m0.535s\n> sys\t0m0.474s\n>\n>> So you need to just use an up-to-date libpcre2 & -P and performance\n>> won't suck.\n\nYeah that's recent enough & will get you all the benefits.\n\n> I don't tend to use terribly advanced regexps, so I'll just set\n> grep.patternType to 'perl' and then it'll automatically be fast for me\n> without your patches ;-)\n\nIndeed, if you're happy with that that'll do it.\n\n>> My WIP patches will make us use PCRE for all grep modes, using an API it\n>> has to convert basic & extended regexp syntax to its own syntax, so\n>> we'll be able to do that transparently.\n>\n> That's clearly the right answer.  Thanks!\n\nYeah, unfortunately git-grep's default is \"basic\" regexp which has a\nreally atrocious syntax that's different enough from extended & Perl's\nthat we probably couldn't just switch it over.\n\nThat won't be needed with my patches, but maybe I'll follow-up with\nsomething to s/basic/extended/g by default, because on side effect of\nhaving the pattern converter is that we could have a warning whenever\nthe user has a pattern that would be different under extended/perl, so\nwe can see how common that is.\n"}]}