{"thread":{"id":"45926","subject":"[PATCH v2 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0","startedAt":"2017-05-10T22:53:34Z","lastAt":"2017-05-11T09:59:37Z","messageCount":9,"participants":["Ævar Arnfjörð Bjarmason","Jonathan Nieder","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"319299","messageId":"20170510225316.31680-1-avarab@gmail.com","threadId":"45926","inReplyTo":null,"subject":"[PATCH v2 0/2] perf: show that wildmatch() regressed for pathological cases in v2.0","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-05-10T22:53:14Z","receivedAt":"2017-05-10T22:53:34Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"This is a re-send of <20170424211249.28553-1-avarab@gmail.com>\n(https://public-inbox.org/git/20170424211249.28553-1-avarab@gmail.com/)\nwhich fell through the cracks at the time.\n\nThe only change is a typo fix in the description of the test in 2/2.\n\nÆvar Arnfjörð Bjarmason (2):\n  perf: add function to setup a fresh test repo\n  perf: add test showing exponential growth in path globbing\n\n t/perf/README            |  1 +\n t/perf/p0100-globbing.sh | 48 ++++++++++++++++++++++++++++++++++++++++++++++++\n t/perf/perf-lib.sh       | 17 +++++++++++++----\n 3 files changed, 62 insertions(+), 4 deletions(-)\n create mode 100755 t/perf/p0100-globbing.sh\n\n-- \n2.11.0\n\n"},{"id":"319300","messageId":"20170510225316.31680-2-avarab@gmail.com","threadId":"45926","inReplyTo":"20170510225316.31680-1-avarab@gmail.com","subject":"[PATCH v2 1/2] perf: add function to setup a fresh test repo","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-05-10T22:53:15Z","receivedAt":"2017-05-10T22:53:36Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Add a function to setup a fresh test repo via 'git init' to compliment\nthe existing functions to copy over a normal & large repo.\n\nSome performance tests don't need any existing repository data at all\nto be significant, e.g. tests which stress glob matches against\nrevisions or files, which I'm about to add in a subsequent commit.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n---\n t/perf/README      |  1 +\n t/perf/perf-lib.sh | 17 +++++++++++++----\n 2 files changed, 14 insertions(+), 4 deletions(-)\n\ndiff --git a/t/perf/README b/t/perf/README\nindex 49ea4349be..de2fe15696 100644\n--- a/t/perf/README\n+++ b/t/perf/README\n@@ -106,6 +106,7 @@ sources perf-lib.sh:\n \n After that you will want to use some of the following:\n \n+\ttest_perf_fresh_repo    # sets up an empty repository\n \ttest_perf_default_repo  # sets up a \"normal\" repository\n \ttest_perf_large_repo    # sets up a \"large\" repository\n \ndiff --git a/t/perf/perf-lib.sh b/t/perf/perf-lib.sh\nindex ab4b8b06ae..f51fc773e8 100644\n--- a/t/perf/perf-lib.sh\n+++ b/t/perf/perf-lib.sh\n@@ -78,6 +78,10 @@ if test -z \"$GIT_PERF_LARGE_REPO\"; then\n \tGIT_PERF_LARGE_REPO=$TEST_DIRECTORY/..\n fi\n \n+test_perf_do_repo_symlink_config_ () {\n+\ttest_have_prereq SYMLINKS || git config core.symlinks false\n+}\n+\n test_perf_create_repo_from () {\n \ttest \"$#\" = 2 ||\n \terror \"bug in the test script: not 2 parameters to test-create-repo\"\n@@ -102,15 +106,20 @@ test_perf_create_repo_from () {\n \t) &&\n \t(\n \t\tcd \"$repo\" &&\n-\t\t\"$MODERN_GIT\" init -q && {\n-\t\t\ttest_have_prereq SYMLINKS ||\n-\t\t\tgit config core.symlinks false\n-\t\t} &&\n+\t\t\"$MODERN_GIT\" init -q &&\n+\t\ttest_perf_do_repo_symlink_config_ &&\n \t\tmv .git/hooks .git/hooks-disabled 2>/dev/null\n \t) || error \"failed to copy repository '$source' to '$repo'\"\n }\n \n # call at least one of these to establish an appropriately-sized repository\n+test_perf_fresh_repo () {\n+\trepo=\"${1:-$TRASH_DIRECTORY}\"\n+\t\"$MODERN_GIT\" init -q \"$repo\" &&\n+\tcd \"$repo\" &&\n+\ttest_perf_do_repo_symlink_config_\n+}\n+\n test_perf_default_repo () {\n \ttest_perf_create_repo_from \"${1:-$TRASH_DIRECTORY}\" \"$GIT_PERF_REPO\"\n }\n-- \n2.11.0\n\n"},{"id":"319301","messageId":"20170510225316.31680-3-avarab@gmail.com","threadId":"45926","inReplyTo":"20170510225316.31680-1-avarab@gmail.com","subject":"[PATCH v2 2/2] perf: add test showing exponential growth in path globbing","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-05-10T22:53:16Z","receivedAt":"2017-05-10T22:53:39Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Add a test showing that ls-files times grow exponentially in the face\nof some pathological globs, whereas refglobs via for-each-ref don't in\npractice suffer from the same issue.\n\nAs noted in the test description this is a test to see whether Git\nsuffers from the issue noted in an article Russ Cox posted today about\ncommon bugs in various glob implementations:\nhttps://research.swtch.com/glob\n\nThe pathological git-ls-files globbing is done by wildmatch() in\nwildmatch.c. The for-each-ref codepath also uses wildmatch(), but will\nalways match against e.g. \"refs/tags/aaa...\", not \"aaa..\" as\ngit-ls-files will.\n\nI'm unsure why the pathological case isn't triggered by for-each-ref,\nbut in any case, now we have a performance test for it.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n---\n t/perf/p0100-globbing.sh | 48 ++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 48 insertions(+)\n create mode 100755 t/perf/p0100-globbing.sh\n\ndiff --git a/t/perf/p0100-globbing.sh b/t/perf/p0100-globbing.sh\nnew file mode 100755\nindex 0000000000..e98fd7ce4b\n--- /dev/null\n+++ b/t/perf/p0100-globbing.sh\n@@ -0,0 +1,48 @@\n+#!/bin/sh\n+\n+test_description=\"Tests pathalogical globbing performance\n+\n+Shows how Git's globbing performance performs when given the sort of\n+pathalogical patterns described in at https://research.swtch.com/glob\n+\"\n+\n+. ./perf-lib.sh\n+\n+test_globs_big='10 25 50 75 100'\n+test_globs_small='1 2 3 4 5 6'\n+\n+test_perf_fresh_repo\n+\n+test_expect_success 'setup' '\n+\tfor i in $(test_seq 1 100)\n+\tdo\n+\t\tprintf \"a\" >>refname &&\n+\t\tfor j in $(test_seq 1 $i)\n+\t\tdo\n+\t\t\tprintf \"a*\" >>refglob.$i\n+\t\tdone &&\n+\t\techo b >>refglob.$i\n+\tdone &&\n+\ttest_commit $(cat refname) &&\n+\tfor i in $(test_seq 1 100)\n+\tdo\n+\techo\tgit tag $(cat refname)-$i\n+\tdone &&\n+\ttest_commit hello\n+'\n+\n+for i in $test_globs_big\n+do\n+\ttest_perf \"refglob((a*)^nb) against tag a^100; n = $i\" '\n+\t\tgit for-each-ref \"refs/tags/$(cat refglob.'$i')b\"\n+\t'\n+done\n+\n+for i in $test_globs_small\n+do\n+\ttest_perf \"fileglob((a*)^nb) against file (a^100).t; n = $i\" '\n+\t\tgit ls-files \"$(cat refglob.'$i')b\"\n+\t'\n+done\n+\n+test_done\n-- \n2.11.0\n\n"},{"id":"319303","messageId":"20170510233032.GD28740@aiede.svl.corp.google.com","threadId":"45926","inReplyTo":"20170510225316.31680-2-avarab@gmail.com","subject":"Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-05-10T23:30:32Z","receivedAt":"2017-05-10T23:30:39Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nÆvar Arnfjörð Bjarmason wrote:\n\n[...]\n>  # call at least one of these to establish an appropriately-sized repository\n> +test_perf_fresh_repo () {\n> +\trepo=\"${1:-$TRASH_DIRECTORY}\"\n> +\t\"$MODERN_GIT\" init -q \"$repo\" &&\n> +\tcd \"$repo\" &&\n> +\ttest_perf_do_repo_symlink_config_\n> +}\n\nUnlike the other two variants, wouldn't this leave the cwd inside the\nnew repo?\n\nIn other words, I wonder if the commands starting with the 'cd' should\nbe in a subshell.\n\nThanks and hope that helps,\nJonathan\n"},{"id":"319304","messageId":"20170510233311.GE28740@aiede.svl.corp.google.com","threadId":"45926","inReplyTo":"20170510225316.31680-3-avarab@gmail.com","subject":"Re: [PATCH v2 2/2] perf: add test showing exponential growth in path globbing","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-05-10T23:33:11Z","receivedAt":"2017-05-10T23:33:19Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nÆvar Arnfjörð Bjarmason wrote:\n\n> Add a test showing that ls-files times grow exponentially in the face\n> of some pathological globs, whereas refglobs via for-each-ref don't in\n> practice suffer from the same issue.\n\nCool.\n\n[...]\n> --- /dev/null\n> +++ b/t/perf/p0100-globbing.sh\n> @@ -0,0 +1,48 @@\n> +#!/bin/sh\n> +\n> +test_description=\"Tests pathalogical globbing performance\n> +\n> +Shows how Git's globbing performance performs when given the sort of\n> +pathalogical patterns described in at https://research.swtch.com/glob\n\ns/pathalogical/pathological/\n\n> +\"\n> +\n> +. ./perf-lib.sh\n> +\n> +test_globs_big='10 25 50 75 100'\n> +test_globs_small='1 2 3 4 5 6'\n> +\n> +test_perf_fresh_repo\n> +\n> +test_expect_success 'setup' '\n> +\tfor i in $(test_seq 1 100)\n> +\tdo\n> +\t\tprintf \"a\" >>refname &&\n> +\t\tfor j in $(test_seq 1 $i)\n> +\t\tdo\n> +\t\t\tprintf \"a*\" >>refglob.$i\n> +\t\tdone &&\n> +\t\techo b >>refglob.$i\n> +\tdone &&\n> +\ttest_commit $(cat refname) &&\n> +\tfor i in $(test_seq 1 100)\n> +\tdo\n> +\techo\tgit tag $(cat refname)-$i\n\nLeftover echo from debugging?\n\n> +\tdone &&\n> +\ttest_commit hello\n> +'\n> +\n> +for i in $test_globs_big\n> +do\n> +\ttest_perf \"refglob((a*)^nb) against tag a^100; n = $i\" '\n> +\t\tgit for-each-ref \"refs/tags/$(cat refglob.'$i')b\"\n> +\t'\n> +done\n> +\n> +for i in $test_globs_small\n> +do\n> +\ttest_perf \"fileglob((a*)^nb) against file (a^100).t; n = $i\" '\n> +\t\tgit ls-files \"$(cat refglob.'$i')b\"\n> +\t'\n> +done\n\nThe rest looks sensible.\n\nThanks,\nJonathan\n"},{"id":"319305","messageId":"CACBZZX50-0uzMyYJo5Z92nRH0m-Q70=P4Wr-LwBqH71nXdsmcA@mail.gmail.com","threadId":"45926","inReplyTo":"20170510233032.GD28740@aiede.svl.corp.google.com","subject":"Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-05-11T00:00:12Z","receivedAt":"2017-05-11T00:00:41Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Thu, May 11, 2017 at 1:30 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n> Hi,\n>\n> Ęvar Arnfjörš Bjarmason wrote:\n>\n> [...]\n>>  # call at least one of these to establish an appropriately-sized repository\n>> +test_perf_fresh_repo () {\n>> +     repo=\"${1:-$TRASH_DIRECTORY}\"\n>> +     \"$MODERN_GIT\" init -q \"$repo\" &&\n>> +     cd \"$repo\" &&\n>> +     test_perf_do_repo_symlink_config_\n>> +}\n>\n> Unlike the other two variants, wouldn't this leave the cwd inside the\n> new repo?\n>\n> In other words, I wonder if the commands starting with the 'cd' should\n> be in a subshell.\n>\n> Thanks and hope that helps,\n\nYup, I'll fix that. Thanks for the review & also on the other patch.\nWill send a v3 with these issues fixed.\n"},{"id":"319307","messageId":"xmqqshkcw7u2.fsf@gitster.mtv.corp.google.com","threadId":"45926","inReplyTo":"CACBZZX50-0uzMyYJo5Z92nRH0m-Q70=P4Wr-LwBqH71nXdsmcA@mail.gmail.com","subject":"Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-05-11T00:33:25Z","receivedAt":"2017-05-11T00:33:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n\n> On Thu, May 11, 2017 at 1:30 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n>> Hi,\n>>\n>> Ęvar Arnfjörš Bjarmason wrote:\n>>\n>> [...]\n>>>  # call at least one of these to establish an appropriately-sized repository\n>>> +test_perf_fresh_repo () {\n>>> +     repo=\"${1:-$TRASH_DIRECTORY}\"\n>>> +     \"$MODERN_GIT\" init -q \"$repo\" &&\n>>> +     cd \"$repo\" &&\n>>> +     test_perf_do_repo_symlink_config_\n>>> +}\n>>\n>> Unlike the other two variants, wouldn't this leave the cwd inside the\n>> new repo?\n>>\n>> In other words, I wonder if the commands starting with the 'cd' should\n>> be in a subshell.\n>>\n>> Thanks and hope that helps,\n>\n> Yup, I'll fix that. Thanks for the review & also on the other patch.\n> Will send a v3 with these issues fixed.\n\nThanks.  FWIW, I didn't see anything questionable other than\nJonathan spotted.\n"},{"id":"319381","messageId":"xmqq8tm3afaa.fsf@gitster.mtv.corp.google.com","threadId":"45926","inReplyTo":"CACBZZX50-0uzMyYJo5Z92nRH0m-Q70=P4Wr-LwBqH71nXdsmcA@mail.gmail.com","subject":"Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-05-11T09:55:41Z","receivedAt":"2017-05-11T09:55:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n\n> On Thu, May 11, 2017 at 1:30 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n>> Hi,\n>>\n>> Ęvar Arnfjörš Bjarmason wrote:\n>>\n>> [...]\n>>>  # call at least one of these to establish an appropriately-sized repository\n>>> +test_perf_fresh_repo () {\n>>> +     repo=\"${1:-$TRASH_DIRECTORY}\"\n>>> +     \"$MODERN_GIT\" init -q \"$repo\" &&\n>>> +     cd \"$repo\" &&\n>>> +     test_perf_do_repo_symlink_config_\n>>> +}\n>>\n>> Unlike the other two variants, wouldn't this leave the cwd inside the\n>> new repo?\n>>\n>> In other words, I wonder if the commands starting with the 'cd' should\n>> be in a subshell.\n>>\n>> Thanks and hope that helps,\n>\n> Yup, I'll fix that. Thanks for the review & also on the other patch.\n> Will send a v3 with these issues fixed.\n\nHmph, does v3 actually have this change?\n"},{"id":"319382","messageId":"CACBZZX5gXWLb4oePjC+aCRQ5HsVD8-M9Ao6akgvEKf1+gx-79A@mail.gmail.com","threadId":"45926","inReplyTo":"xmqq8tm3afaa.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2 1/2] perf: add function to setup a fresh test repo","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2017-05-11T09:59:01Z","receivedAt":"2017-05-11T09:59:37Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Thu, May 11, 2017 at 11:55 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n>\n>> On Thu, May 11, 2017 at 1:30 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:\n>>> Hi,\n>>>\n>>> Ęvar Arnfjörš Bjarmason wrote:\n>>>\n>>> [...]\n>>>>  # call at least one of these to establish an appropriately-sized repository\n>>>> +test_perf_fresh_repo () {\n>>>> +     repo=\"${1:-$TRASH_DIRECTORY}\"\n>>>> +     \"$MODERN_GIT\" init -q \"$repo\" &&\n>>>> +     cd \"$repo\" &&\n>>>> +     test_perf_do_repo_symlink_config_\n>>>> +}\n>>>\n>>> Unlike the other two variants, wouldn't this leave the cwd inside the\n>>> new repo?\n>>>\n>>> In other words, I wonder if the commands starting with the 'cd' should\n>>> be in a subshell.\n>>>\n>>> Thanks and hope that helps,\n>>\n>> Yup, I'll fix that. Thanks for the review & also on the other patch.\n>> Will send a v3 with these issues fixed.\n>\n> Hmph, does v3 actually have this change?\n\nNope, sent v4 to fix it, sorry:\nhttps://public-inbox.org/git/20170511094108.8756-1-avarab@gmail.com/\n"}]}