# [PATCH v2 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0 9 messages from 2017-05-10 to 2017-05-11. Participants: Ævar Arnfjörð Bjarmason, Jonathan Nieder, Junio C Hamano. Thread: https://gitlist.dev/t/45926 ## Ævar Arnfjörð Bjarmason, 2017-05-10 22:53 Subject: [PATCH v2 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0 Message-ID: <20170510225316.31680-1-avarab@gmail.com> URL: https://gitlist.dev/e/20170510225316.31680-1-avarab%40gmail.com ``` This is a re-send of <20170424211249.28553-1-avarab@gmail.com> (https://public-inbox.org/git/20170424211249.28553-1-avarab@gmail.com/) which fell through the cracks at the time. The only change is a typo fix in the description of the test in 2/2. Ævar Arnfjörð Bjarmason (2): perf: add function to setup a fresh test repo perf: add test showing exponential growth in path globbing t/perf/README | 1 + t/perf/p0100-globbing.sh | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ t/perf/perf-lib.sh | 17 +++++++++++++---- 3 files changed, 62 insertions(+), 4 deletions(-) create mode 100755 t/perf/p0100-globbing.sh -- 2.11.0 ``` ## Ævar Arnfjörð Bjarmason, 2017-05-10 22:53 Subject: [PATCH v2 1/2] perf: add function to setup a fresh test repo Message-ID: <20170510225316.31680-2-avarab@gmail.com> URL: https://gitlist.dev/e/20170510225316.31680-2-avarab%40gmail.com In-Reply-To: <20170510225316.31680-1-avarab@gmail.com> ``` Add a function to setup a fresh test repo via 'git init' to compliment the existing functions to copy over a normal & large repo. Some performance tests don't need any existing repository data at all to be significant, e.g. tests which stress glob matches against revisions or files, which I'm about to add in a subsequent commit. Signed-off-by: Ævar Arnfjörð Bjarmason --- t/perf/README | 1 + t/perf/perf-lib.sh | 17 +++++++++++++---- 2 files changed, 14 insertions(+), 4 deletions(-) diff --git a/t/perf/README b/t/perf/README index 49ea4349be..de2fe15696 100644 --- a/t/perf/README +++ b/t/perf/README @@ -106,6 +106,7 @@ sources perf-lib.sh: After that you will want to use some of the following: + test_perf_fresh_repo # sets up an empty repository test_perf_default_repo # sets up a "normal" repository test_perf_large_repo # sets up a "large" repository diff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh index ab4b8b06ae..f51fc773e8 100644 --- a/t/perf/perf-lib.sh +++ b/t/perf/perf-lib.sh @@ -78,6 +78,10 @@ if test -z "$GIT_PERF_LARGE_REPO"; then GIT_PERF_LARGE_REPO=$TEST_DIRECTORY/.. fi +test_perf_do_repo_symlink_config_ () { + test_have_prereq SYMLINKS || git config core.symlinks false +} + test_perf_create_repo_from () { test "$#" = 2 || error "bug in the test script: not 2 parameters to test-create-repo" @@ -102,15 +106,20 @@ test_perf_create_repo_from () { ) && ( cd "$repo" && - "$MODERN_GIT" init -q && { - test_have_prereq SYMLINKS || - git config core.symlinks false - } && + "$MODERN_GIT" init -q && + test_perf_do_repo_symlink_config_ && mv .git/hooks .git/hooks-disabled 2>/dev/null ) || error "failed to copy repository '$source' to '$repo'" } # call at least one of these to establish an appropriately-sized repository +test_perf_fresh_repo () { + repo="${1:-$TRASH_DIRECTORY}" + "$MODERN_GIT" init -q "$repo" && + cd "$repo" && + test_perf_do_repo_symlink_config_ +} + test_perf_default_repo () { test_perf_create_repo_from "${1:-$TRASH_DIRECTORY}" "$GIT_PERF_REPO" } -- 2.11.0 ``` ## Ævar Arnfjörð Bjarmason, 2017-05-10 22:53 Subject: [PATCH v2 2/2] perf: add test showing exponential growth in path globbing Message-ID: <20170510225316.31680-3-avarab@gmail.com> URL: https://gitlist.dev/e/20170510225316.31680-3-avarab%40gmail.com In-Reply-To: <20170510225316.31680-1-avarab@gmail.com> ``` Add a test showing that ls-files times grow exponentially in the face of some pathological globs, whereas refglobs via for-each-ref don't in practice suffer from the same issue. As noted in the test description this is a test to see whether Git suffers from the issue noted in an article Russ Cox posted today about common bugs in various glob implementations: https://research.swtch.com/glob The pathological git-ls-files globbing is done by wildmatch() in wildmatch.c. The for-each-ref codepath also uses wildmatch(), but will always match against e.g. "refs/tags/aaa...", not "aaa.." as git-ls-files will. I'm unsure why the pathological case isn't triggered by for-each-ref, but in any case, now we have a performance test for it. Signed-off-by: Ævar Arnfjörð Bjarmason --- t/perf/p0100-globbing.sh | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 48 insertions(+) create mode 100755 t/perf/p0100-globbing.sh diff --git a/t/perf/p0100-globbing.sh b/t/perf/p0100-globbing.sh new file mode 100755 index 0000000000..e98fd7ce4b --- /dev/null +++ b/t/perf/p0100-globbing.sh @@ -0,0 +1,48 @@ +#!/bin/sh + +test_description="Tests pathalogical globbing performance + +Shows how Git's globbing performance performs when given the sort of +pathalogical patterns described in at https://research.swtch.com/glob +" + +. ./perf-lib.sh + +test_globs_big='10 25 50 75 100' +test_globs_small='1 2 3 4 5 6' + +test_perf_fresh_repo + +test_expect_success 'setup' ' + for i in $(test_seq 1 100) + do + printf "a" >>refname && + for j in $(test_seq 1 $i) + do + printf "a*" >>refglob.$i + done && + echo b >>refglob.$i + done && + test_commit $(cat refname) && + for i in $(test_seq 1 100) + do + echo git tag $(cat refname)-$i + done && + test_commit hello +' + +for i in $test_globs_big +do + test_perf "refglob((a*)^nb) against tag a^100; n = $i" ' + git for-each-ref "refs/tags/$(cat refglob.'$i')b" + ' +done + +for i in $test_globs_small +do + test_perf "fileglob((a*)^nb) against file (a^100).t; n = $i" ' + git ls-files "$(cat refglob.'$i')b" + ' +done + +test_done -- 2.11.0 ``` ## Jonathan Nieder, 2017-05-10 23:30 Subject: Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo Message-ID: <20170510233032.GD28740@aiede.svl.corp.google.com> URL: https://gitlist.dev/e/20170510233032.GD28740%40aiede.svl.corp.google.com In-Reply-To: <20170510225316.31680-2-avarab@gmail.com> ``` Hi, Ævar Arnfjörð Bjarmason wrote: [...] > # call at least one of these to establish an appropriately-sized repository > +test_perf_fresh_repo () { > + repo="${1:-$TRASH_DIRECTORY}" > + "$MODERN_GIT" init -q "$repo" && > + cd "$repo" && > + test_perf_do_repo_symlink_config_ > +} Unlike the other two variants, wouldn't this leave the cwd inside the new repo? In other words, I wonder if the commands starting with the 'cd' should be in a subshell. Thanks and hope that helps, Jonathan ``` ## Jonathan Nieder, 2017-05-10 23:33 Subject: Re: [PATCH v2 2/2] perf: add test showing exponential growth in path globbing Message-ID: <20170510233311.GE28740@aiede.svl.corp.google.com> URL: https://gitlist.dev/e/20170510233311.GE28740%40aiede.svl.corp.google.com In-Reply-To: <20170510225316.31680-3-avarab@gmail.com> ``` Hi, Ævar Arnfjörð Bjarmason wrote: > Add a test showing that ls-files times grow exponentially in the face > of some pathological globs, whereas refglobs via for-each-ref don't in > practice suffer from the same issue. Cool. [...] > --- /dev/null > +++ b/t/perf/p0100-globbing.sh > @@ -0,0 +1,48 @@ > +#!/bin/sh > + > +test_description="Tests pathalogical globbing performance > + > +Shows how Git's globbing performance performs when given the sort of > +pathalogical patterns described in at https://research.swtch.com/glob s/pathalogical/pathological/ > +" > + > +. ./perf-lib.sh > + > +test_globs_big='10 25 50 75 100' > +test_globs_small='1 2 3 4 5 6' > + > +test_perf_fresh_repo > + > +test_expect_success 'setup' ' > + for i in $(test_seq 1 100) > + do > + printf "a" >>refname && > + for j in $(test_seq 1 $i) > + do > + printf "a*" >>refglob.$i > + done && > + echo b >>refglob.$i > + done && > + test_commit $(cat refname) && > + for i in $(test_seq 1 100) > + do > + echo git tag $(cat refname)-$i Leftover echo from debugging? > + done && > + test_commit hello > +' > + > +for i in $test_globs_big > +do > + test_perf "refglob((a*)^nb) against tag a^100; n = $i" ' > + git for-each-ref "refs/tags/$(cat refglob.'$i')b" > + ' > +done > + > +for i in $test_globs_small > +do > + test_perf "fileglob((a*)^nb) against file (a^100).t; n = $i" ' > + git ls-files "$(cat refglob.'$i')b" > + ' > +done The rest looks sensible. Thanks, Jonathan ``` ## Ævar Arnfjörð Bjarmason, 2017-05-11 00:00 Subject: Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo Message-ID: URL: https://gitlist.dev/e/CACBZZX50-0uzMyYJo5Z92nRH0m-Q70%3DP4Wr-LwBqH71nXdsmcA%40mail.gmail.com In-Reply-To: <20170510233032.GD28740@aiede.svl.corp.google.com> ``` On Thu, May 11, 2017 at 1:30 AM, Jonathan Nieder wrote: > Hi, > > Ęvar Arnfjörš Bjarmason wrote: > > [...] >> # call at least one of these to establish an appropriately-sized repository >> +test_perf_fresh_repo () { >> + repo="${1:-$TRASH_DIRECTORY}" >> + "$MODERN_GIT" init -q "$repo" && >> + cd "$repo" && >> + test_perf_do_repo_symlink_config_ >> +} > > Unlike the other two variants, wouldn't this leave the cwd inside the > new repo? > > In other words, I wonder if the commands starting with the 'cd' should > be in a subshell. > > Thanks and hope that helps, Yup, I'll fix that. Thanks for the review & also on the other patch. Will send a v3 with these issues fixed. ``` ## Junio C Hamano, 2017-05-11 00:33 Subject: Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo Message-ID: URL: https://gitlist.dev/e/xmqqshkcw7u2.fsf%40gitster.mtv.corp.google.com In-Reply-To: ``` Ævar Arnfjörð Bjarmason writes: > On Thu, May 11, 2017 at 1:30 AM, Jonathan Nieder wrote: >> Hi, >> >> Ęvar Arnfjörš Bjarmason wrote: >> >> [...] >>> # call at least one of these to establish an appropriately-sized repository >>> +test_perf_fresh_repo () { >>> + repo="${1:-$TRASH_DIRECTORY}" >>> + "$MODERN_GIT" init -q "$repo" && >>> + cd "$repo" && >>> + test_perf_do_repo_symlink_config_ >>> +} >> >> Unlike the other two variants, wouldn't this leave the cwd inside the >> new repo? >> >> In other words, I wonder if the commands starting with the 'cd' should >> be in a subshell. >> >> Thanks and hope that helps, > > Yup, I'll fix that. Thanks for the review & also on the other patch. > Will send a v3 with these issues fixed. Thanks. FWIW, I didn't see anything questionable other than Jonathan spotted. ``` ## Junio C Hamano, 2017-05-11 09:55 Subject: Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo Message-ID: URL: https://gitlist.dev/e/xmqq8tm3afaa.fsf%40gitster.mtv.corp.google.com In-Reply-To: ``` Ævar Arnfjörð Bjarmason writes: > On Thu, May 11, 2017 at 1:30 AM, Jonathan Nieder wrote: >> Hi, >> >> Ęvar Arnfjörš Bjarmason wrote: >> >> [...] >>> # call at least one of these to establish an appropriately-sized repository >>> +test_perf_fresh_repo () { >>> + repo="${1:-$TRASH_DIRECTORY}" >>> + "$MODERN_GIT" init -q "$repo" && >>> + cd "$repo" && >>> + test_perf_do_repo_symlink_config_ >>> +} >> >> Unlike the other two variants, wouldn't this leave the cwd inside the >> new repo? >> >> In other words, I wonder if the commands starting with the 'cd' should >> be in a subshell. >> >> Thanks and hope that helps, > > Yup, I'll fix that. Thanks for the review & also on the other patch. > Will send a v3 with these issues fixed. Hmph, does v3 actually have this change? ``` ## Ævar Arnfjörð Bjarmason, 2017-05-11 09:59 Subject: Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo Message-ID: URL: https://gitlist.dev/e/CACBZZX5gXWLb4oePjC%2BaCRQ5HsVD8-M9Ao6akgvEKf1%2Bgx-79A%40mail.gmail.com In-Reply-To: ``` On Thu, May 11, 2017 at 11:55 AM, Junio C Hamano wrote: > Ævar Arnfjörð Bjarmason writes: > >> On Thu, May 11, 2017 at 1:30 AM, Jonathan Nieder wrote: >>> Hi, >>> >>> Ęvar Arnfjörš Bjarmason wrote: >>> >>> [...] >>>> # call at least one of these to establish an appropriately-sized repository >>>> +test_perf_fresh_repo () { >>>> + repo="${1:-$TRASH_DIRECTORY}" >>>> + "$MODERN_GIT" init -q "$repo" && >>>> + cd "$repo" && >>>> + test_perf_do_repo_symlink_config_ >>>> +} >>> >>> Unlike the other two variants, wouldn't this leave the cwd inside the >>> new repo? >>> >>> In other words, I wonder if the commands starting with the 'cd' should >>> be in a subshell. >>> >>> Thanks and hope that helps, >> >> Yup, I'll fix that. Thanks for the review & also on the other patch. >> Will send a v3 with these issues fixed. > > Hmph, does v3 actually have this change? Nope, sent v4 to fix it, sorry: https://public-inbox.org/git/20170511094108.8756-1-avarab@gmail.com/ ```