git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: "Ævar Arnfjörð Bjarmason" <avarab@gmail.com>
To: Johannes Schindelin via GitGitGadget <gitgitgadget@gmail.com>
Cc: git@vger.kernel.org, "Junio C Hamano" <gitster@pobox.com>,
	"Johannes Schindelin" <johannes.schindelin@gmx.de>,
	"SZEDER Gábor" <szeder.dev@gmail.com>,
	"Jeff King" <peff@peff.net>,
	git-packagers@googlegroups.com
Subject: Re: Can we just get rid of kwset & obstack in favor of optimistically using PCRE v2 JIT?
Date: Sat, 15 Jun 2019 01:19:33 +0200	[thread overview]
Message-ID: <87tvcr92m2.fsf@evledraar.gmail.com> (raw)
In-Reply-To: <87v9x793qi.fsf@evledraar.gmail.com>


On Sat, Jun 15 2019, Ævar Arnfjörð Bjarmason wrote:

> On Thu, Jun 13 2019, Johannes Schindelin via GitGitGadget wrote:
>
>> The kwset functionality makes use of the obstack code, which expects to
>> be handed a function that can allocate large chunks of data. It expects
>> that function to accept a `size` parameter of type `long`.
>>
>> This upsets GCC 8 on Windows, because `long` does not have the same
>> bit size as `size_t` there.
>>
>> Now, the proper thing to do would be to switch to `size_t`. But this
>> would make us deviate from the "upstream" code even further, making it
>> hard to synchronize with newer versions, and also it would be quite
>> involved because that `long` type is so invasive in that code.
>>
>> Let's punt, and instead provide a super small wrapper around
>> `xmalloc()`.
>
> I have a WIP patches from 2017 that do $subject that I can dig up, but
> thought I'd gauge interest first.
>
> Right now the grep code & pickaxe machinery will detect fixed strings
> and use kwset() as an optimization.
>
> Back when kwset was added in 9eceddeec6 ("Use kwset in grep",
> 2011-08-21) this helped, but now doing this for grep with a PCRE pattern
> is actually counterproductive for performance. On top of current
> `master`:
>
>     @@ -368 +368 @@ static int is_fixed(const char *s, size_t len)
>     -       return 1;
>     +       return 0;
>
> And running p7821-grep-engines-fixed.sh[1] (which is in git.git, and is
> as far as I got with this) we get:
>
>     Test                             HEAD~             HEAD
>     -------------------------------------------------------------------------
>     7821.1: fixed grep int           0.48(1.59+0.63)   0.48(1.53+0.68) +0.0%
>     7821.2: basic grep int           0.55(1.64+0.51)   0.72(2.97+0.54) +30.9%
>     7821.3: extended grep int        0.65(1.63+0.54)   0.77(2.92+0.60) +18.5%
>     7821.4: perl grep int            1.01(1.62+0.55)   0.36(0.97+0.58) -64.4%
>     7821.6: fixed grep uncommon      0.18(0.51+0.45)   0.18(0.51+0.46) +0.0%
>     7821.7: basic grep uncommon      0.18(0.50+0.46)   0.30(1.36+0.33) +66.7%
>     7821.8: extended grep uncommon   0.18(0.45+0.52)   0.28(1.37+0.37) +55.6%
>     7821.9: perl grep uncommon       0.18(0.52+0.45)   0.16(0.28+0.54) -11.1%
>     7821.11: fixed grep æ            0.31(1.28+0.39)   0.31(1.24+0.43) +0.0%
>     7821.12: basic grep æ            0.30(1.29+0.38)   0.22(0.85+0.36) -26.7%
>     7821.13: extended grep æ         0.30(1.26+0.40)   0.22(0.78+0.45) -26.7%
>     7821.14: perl grep æ             0.30(1.33+0.34)   0.16(0.25+0.56) -46.7%
>
> So what this means on my Debian box is that when we use PCRE with JIT
> and just get out of its way and let it do its own fixed string matching
> it's up to ~65% faster than the kwset() path.
>
> The usual case of just feeding the fixed pattern to glibc's regex
> function is slower, although as seen there when you grep for a
> rarely-occurring non-ASCII string glibc does better now (the perils of
> using ancient last-version-to-use-GPLv2 snapshots...).
>
> So my plan for this (which I partially implemented) was to have a series
> where if we have a fixed string and have PCRE v2 we'd use it instead of
> kwset() for fixed strings.
>
> It seems most packagers build with PCRE v2 now (CC:
> git-packagers@). I.e. we'd keep something like compile_fixed_regexp()
> (and as an aside just use PCRE's \Q...\E instead of our own escaping).
>
> We'd have performance regression for platforms that use kwset() now but
> don't build pcre2, or where pcre2 jit doesn't work. Does anyone care?
>
> This would allow us to just "git rm" kwset.[ch] compat/obstack.[ch],
> which is ~2k lines of tricky code, 1/2 of which we're currently doomed
> to maintain a bitrotting version of due to license incompatibilities
> with upstream[2].
>
> As an aside there's other code in grep.c that we could similarly remove
> in favor of optimistic PCRE v2 use, e.g. the -w case can be replaced by
> \b<word>\b, but I found that less promising[3]. We can also get a huge
> performance win for BRE and ERE patterns by using PCRE v2 with a
> translation layer for those under the hood[4], but various solvable
> backwards compatible headaches[5] related to that are why I got lost in
> the weeds back in 2017 and didn't finish this.
>
> But just the s/kwset/pcre2/ case is easy enough.

...small correction, we currently hard-rely on kwset() for any pattern
containing a \0 for "git-grep" (these can only by supplied via the -f
<pattern-from-file> option), this means that any pattern containing a \0
is implicitly fixed, unless kwset() doesn't like it (-i and non-ASCII),
what a mess.

Since we hard depend on REG_STARTEND since 2f8952250a ("regex: add
regexec_buf() that can work on a non NUL-terminated string", 2016-09-21)
we should just fix that while we're at it. It's a backwards-incompatible
change, but I doubt anyone is relying on our undocumented behavior of
implicitly considering grep patterns with \0 in them always fixed.


> 1. Via:
>
>     GIT_PERF_REPEAT_COUNT=10 GIT_PERF_LARGE_REPO=~/g/linux GIT_PERF_7821_GREP_OPTS='' GIT_PERF_MAKE_OPTS='-j8 CFLAGS=-O3 USE_LIBPCRE2=YesPlease' ./run HEAD~ HEAD -- p7821-grep-engines-fixed.sh
> 2. https://public-inbox.org/git/87wohn95vb.fsf@evledraar.gmail.com/
> 3. https://github.com/avar/git/commit/49ca92e799
> 4. https://github.com/avar/git/commit/a3cc090344
> 5. https://github.com/avar/git/commit/7dd367eb37

  reply	other threads:[~2019-06-14 23:19 UTC|newest]

Thread overview: 90+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-06-13 11:49 [PATCH 0/4] Support building with GCC v8.x/v9.x Johannes Schindelin via GitGitGadget
2019-06-13 11:49 ` [PATCH 1/4] poll (mingw): allow compiling with GCC 8 and DEVELOPER=1 Johannes Schindelin via GitGitGadget
2019-06-13 11:49 ` [PATCH 2/4] kwset: allow building with GCC 8 Johannes Schindelin via GitGitGadget
2019-06-13 16:11   ` Junio C Hamano
2019-06-14  9:53   ` SZEDER Gábor
2019-06-14 10:00     ` [RFC/PATCH v1 0/4] compat/obstack: update from upstream SZEDER Gábor
2019-06-14 10:00       ` [PATCH v1 1/4] " SZEDER Gábor
2019-06-14 10:00       ` [PATCH v1 2/4] SQUASH??? compat/obstack: fix portability issues SZEDER Gábor
2019-06-14 10:00       ` [PATCH v1 3/4] SQUASH??? compat/obstack: fix build errors with Clang SZEDER Gábor
2019-06-14 10:00       ` [PATCH v1 4/4] compat/obstack: fix some sparse warnings SZEDER Gábor
2019-06-14 17:57       ` [RFC/PATCH v1 0/4] compat/obstack: update from upstream Jeff King
2019-06-14 18:19       ` Junio C Hamano
2019-06-14 20:30       ` Ramsay Jones
2019-06-14 21:24         ` Ramsay Jones
2019-06-17 18:36         ` SZEDER Gábor
2019-06-14 16:12     ` [PATCH 2/4] kwset: allow building with GCC 8 Junio C Hamano
2019-06-17 18:26       ` SZEDER Gábor
2019-06-14 22:09   ` Ævar Arnfjörð Bjarmason
2019-06-14 22:55   ` Can we just get rid of kwset & obstack in favor of optimistically using PCRE v2 JIT? Ævar Arnfjörð Bjarmason
2019-06-14 23:19     ` Ævar Arnfjörð Bjarmason [this message]
2019-06-20 10:35       ` Jeff King
2019-06-15  9:01     ` Carlo Arenas
2019-06-15 19:15     ` brian m. carlson
2019-06-15 22:14       ` Ævar Arnfjörð Bjarmason
2019-06-26  0:03         ` [RFC/PATCH 0/7] grep: move from kwset to optional PCRE v2 Ævar Arnfjörð Bjarmason
2019-06-26 14:02           ` Johannes Schindelin
2019-06-27  9:16             ` Johannes Schindelin
2019-06-27 16:27               ` Ævar Arnfjörð Bjarmason
2019-06-27 18:21                 ` Johannes Schindelin
2019-06-27 23:39           ` [PATCH v2 0/9] " Ævar Arnfjörð Bjarmason
2019-06-28  7:23             ` Ævar Arnfjörð Bjarmason
2019-06-28 16:10               ` Junio C Hamano
2019-07-01 21:20             ` [PATCH v3 00/10] " Ævar Arnfjörð Bjarmason
2019-07-01 21:31               ` Junio C Hamano
2019-07-02 11:10                 ` Ævar Arnfjörð Bjarmason
2019-07-02 12:32               ` Johannes Schindelin
2019-07-02 19:57                 ` Junio C Hamano
2019-07-03 10:08                   ` Johannes Schindelin
2019-07-03 10:25                 ` Johannes Schindelin
2019-07-03 11:27                   ` Johannes Schindelin
2019-07-01 21:20             ` [PATCH v3 01/10] log tests: test regex backends in "--encode=<enc>" tests Ævar Arnfjörð Bjarmason
2019-07-01 21:20             ` [PATCH v3 02/10] grep: don't use PCRE2?_UTF8 with "log --encoding=<non-utf8>" Ævar Arnfjörð Bjarmason
2019-07-01 21:20             ` [PATCH v3 03/10] t4210: skip more command-line encoding tests on MinGW Ævar Arnfjörð Bjarmason
2019-07-01 21:20             ` [PATCH v3 04/10] grep: inline the return value of a function call used only once Ævar Arnfjörð Bjarmason
2019-07-01 21:20             ` [PATCH v3 05/10] grep tests: move "grep binary" alongside the rest Ævar Arnfjörð Bjarmason
2019-07-01 21:20             ` [PATCH v3 06/10] grep tests: move binary pattern tests into their own file Ævar Arnfjörð Bjarmason
2019-07-01 21:20             ` [PATCH v3 07/10] grep: make the behavior for NUL-byte in patterns sane Ævar Arnfjörð Bjarmason
2019-07-01 21:20             ` [PATCH v3 08/10] grep: drop support for \0 in --fixed-strings <pattern> Ævar Arnfjörð Bjarmason
2019-07-01 21:20             ` [PATCH v3 09/10] grep: remove the kwset optimization Ævar Arnfjörð Bjarmason
2019-07-01 21:21             ` [PATCH v3 10/10] grep: use PCRE v2 for optimized fixed-string search Ævar Arnfjörð Bjarmason
2019-06-27 23:39           ` [PATCH v2 1/9] log tests: test regex backends in "--encode=<enc>" tests Ævar Arnfjörð Bjarmason
2019-06-27 23:39           ` [PATCH v2 2/9] grep: don't use PCRE2?_UTF8 with "log --encoding=<non-utf8>" Ævar Arnfjörð Bjarmason
2019-06-27 23:39           ` [PATCH v2 3/9] grep: inline the return value of a function call used only once Ævar Arnfjörð Bjarmason
2019-06-27 23:39           ` [PATCH v2 4/9] grep tests: move "grep binary" alongside the rest Ævar Arnfjörð Bjarmason
2019-06-27 23:39           ` [PATCH v2 5/9] grep tests: move binary pattern tests into their own file Ævar Arnfjörð Bjarmason
2019-06-27 23:39           ` [PATCH v2 6/9] grep: make the behavior for NUL-byte in patterns sane Ævar Arnfjörð Bjarmason
2019-06-27 23:39           ` [PATCH v2 7/9] grep: drop support for \0 in --fixed-strings <pattern> Ævar Arnfjörð Bjarmason
2019-06-27 23:39           ` [PATCH v2 8/9] grep: remove the kwset optimization Ævar Arnfjörð Bjarmason
2019-06-27 23:39           ` [PATCH v2 9/9] grep: use PCRE v2 for optimized fixed-string search Ævar Arnfjörð Bjarmason
2019-06-26  0:03         ` [RFC/PATCH 1/7] grep: inline the return value of a function call used only once Ævar Arnfjörð Bjarmason
2019-06-26  0:03         ` [RFC/PATCH 2/7] grep tests: move "grep binary" alongside the rest Ævar Arnfjörð Bjarmason
2019-06-26 14:05           ` Johannes Schindelin
2019-06-26 18:13           ` Junio C Hamano
2019-06-26  0:03         ` [RFC/PATCH 3/7] grep tests: move binary pattern tests into their own file Ævar Arnfjörð Bjarmason
2019-06-26  0:03         ` [RFC/PATCH 4/7] grep: make the behavior for \0 in patterns sane Ævar Arnfjörð Bjarmason
2019-06-27  2:03           ` brian m. carlson
2019-06-26  0:03         ` [RFC/PATCH 5/7] grep: drop support for \0 in --fixed-strings <pattern> Ævar Arnfjörð Bjarmason
2019-06-26 16:14           ` Junio C Hamano
2019-06-26  0:03         ` [RFC/PATCH 6/7] grep: remove the kwset optimization Ævar Arnfjörð Bjarmason
2019-06-26  0:03         ` [RFC/PATCH 7/7] grep: use PCRE v2 for optimized fixed-string search Ævar Arnfjörð Bjarmason
2019-06-26 14:13           ` Johannes Schindelin
2019-06-26 18:45             ` Junio C Hamano
2019-06-27  9:31               ` Johannes Schindelin
2019-06-27 18:45                 ` Johannes Schindelin
2019-06-27 19:06                   ` Junio C Hamano
2019-06-28 10:56                     ` Johannes Schindelin
2019-06-13 11:49 ` [PATCH 3/4] winansi: simplify loading the GetCurrentConsoleFontEx() function Johannes Schindelin via GitGitGadget
2019-06-13 11:49 ` [PATCH 4/4] config: avoid calling `labs()` on too-large data type Johannes Schindelin via GitGitGadget
2019-06-13 16:13   ` Junio C Hamano
2019-06-16  6:48   ` René Scharfe
2019-06-16  8:24     ` René Scharfe
2019-06-16 14:01       ` René Scharfe
2019-06-16 22:26         ` Junio C Hamano
2019-06-20 19:58           ` René Scharfe
2019-06-20 21:07             ` Junio C Hamano
2019-06-21 18:35             ` Johannes Schindelin
2019-06-22 10:03               ` René Scharfe
2019-06-22 10:03           ` [PATCH v2 1/3] config: use unsigned_mult_overflows to check for overflows René Scharfe
2019-06-22 10:03           ` [PATCH v2 2/3] config: don't multiply in parse_unit_factor() René Scharfe
2019-06-22 10:03           ` [PATCH v2 3/3] config: simplify parsing of unit factors René Scharfe

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=87tvcr92m2.fsf@evledraar.gmail.com \
    --to=avarab@gmail.com \
    --cc=git-packagers@googlegroups.com \
    --cc=git@vger.kernel.org \
    --cc=gitgitgadget@gmail.com \
    --cc=gitster@pobox.com \
    --cc=johannes.schindelin@gmx.de \
    --cc=peff@peff.net \
    --cc=szeder.dev@gmail.com \
    --subject='Re: Can we just get rid of kwset & obstack in favor of optimistically using PCRE v2 JIT?' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).