{"thread":{"id":"51388","subject":"[PATCH 0/1] ref-filter.c: faster multi-pattern ref filtering","startedAt":"2019-06-26T22:41:50Z","lastAt":"2019-07-01T14:49:26Z","messageCount":6,"participants":["Taylor Blau","Jacob Keller"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"378086","messageId":"cover.1561588479.git.me@ttaylorr.com","threadId":"51388","inReplyTo":null,"subject":"[PATCH 0/1] ref-filter.c: faster multi-pattern ref filtering","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2019-06-26T22:41:46Z","receivedAt":"2019-06-26T22:41:50Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi,\n\nPeff and I have been experimenting with using the references from a\nrepository's alternate to speed up the connectivity check following a\n'git clone --reference'.\n\nWe have noticed that the connectivity check becomes much faster when\nadvertising both the heads and tags of an alternate, as opposed to just\nthe heads. But, in our initial experiments, we noticed that it took\n*far* longer to compute the answer to:\n\n $ git for-each-ref refs/heads refs/tags\n\nthen simply\n\n $ git for-each-ref refs/heads\n\nWe found that this dates back to cfe004a5a9 (ref-filter: limit\ntraversal to prefix, 2017-05-22), which drops the user-provided patterns\nentirely when more than one pattern is passed to the ref filter.\n\nTo remedy this, we implemented an algorithm which computes the longest\npattern prefixes over the disjoint subsets of patterns provided to the\nref filter. This produces the most-specific queries (i.e., the ones that\nwe hope to return the fewest extra results) without covering the same\nref more than once.\n\nThe details of the algorithm are written up in detail in the patch. This\ndoesn't have quite the impressive results on repositories the size of\nthe kernel, but yields a drastic improvement on our fork network\nrepositories. Some synthetic results are included in the patch as well.\n\nThanks in advance for your review.\n\nTaylor Blau (1):\n ref-filter.c: find disjoint pattern prefixes\n\n ref-filter.c | 89 +++++++++++++++++++++++++++++------------\n t/t6300-for-each-ref.sh | 26 ++++++++++++\n 2 files changed, 89 insertions(+), 26 deletions(-)\n\n--\n2.21.0.203.g358da99528\n"},{"id":"378087","messageId":"e41db267f7b7086126e9fd3fd5b1a02e38c8c077.1561588479.git.me@ttaylorr.com","threadId":"51388","inReplyTo":"cover.1561588479.git.me@ttaylorr.com","subject":"[PATCH 1/1] ref-filter.c: find disjoint pattern prefixes","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2019-06-26T22:41:48Z","receivedAt":"2019-06-26T22:41:52Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Since cfe004a5a9 (ref-filter: limit traversal to prefix, 2017-05-22),\nthe ref-filter code has sought to limit the traversals to a prefix of\nthe given patterns.\n\nThat code stopped short of handling more than one pattern, because it\nmeans invoking 'for_each_ref_in' multiple times. If we're not careful\nabout which patterns overlap, we will output the same refs multiple\ntimes.\n\nFor instance, consider the set of patterns 'refs/heads/a/*',\n'refs/heads/a/b/c', and 'refs/tags/v1.0.0'. If we naïvely ran:\n\n for_each_ref_in(\"refs/heads/a/*\", ...);\n for_each_ref_in(\"refs/heads/a/b/c\", ...);\n for_each_ref_in(\"refs/tags/v1.0.0\", ...);\n\nwe would see 'refs/heads/a/b/c' (and everything underneath it) twice.\n\nInstead, we want to partition the patterns into disjoint sets, where we\nknow that no ref will be matched by any two patterns in different sets.\nIn the above, these are:\n\n - {'refs/heads/a/*', 'refs/heads/a/b/c'}, and\n - {'refs/tags/v1.0.0'}\n\nGiven one of these disjoint sets, what is a suitable pattern to pass to\n'for_each_ref_in'? One approach is to compute the longest common prefix\nover all elements in that disjoint set, and let the caller cull out the\nrefs they didn't want. Computing the longest prefix means that in most\ncases, we won't match too many things the caller would like to ignore.\n\nThe longest common prefixes of the above are:\n\n - {'refs/heads/a/*', 'refs/heads/a/b/c'} -> refs/heads/a/*\n - {'refs/tags/v1.0.0'} -> refs/tags/v1.0.0\n\nWe instead invoke:\n\n for_each_ref_in(\"refs/heads/a/*\", ...);\n for_each_ref_in(\"refs/tags/v1.0.0\", ...);\n\nWhich provides us with the refs we were looking for with a minimal\namount of extra cruft, but never a duplicate of the ref we asked for.\n\nImplemented here is an algorithm which accomplishes the above, which\nworks as follows:\n\n 1. Lexicographically sort the given list of patterns.\n\n 2. Initialize 'prefix' to the empty string, where our goal is to\n build each element in the above set of longest common prefixes.\n\n 3. Consider each pattern in the given set, and emit 'prefix' if it\n reaches the end of a pattern, or touches a wildcard character. The\n end of a string is treated as if it precedes a wildcard. (Note that\n there is some room for future work to detect that, e.g., 'a?b' and\n 'abc' are disjoint).\n\n 4. Otherwise, recurse on step (3) with the slice of the list\n corresponding to our current prefix (i.e., the subset of patterns\n that have our prefix as a literal string prefix.)\n\nThis algorithm is 'O(kn + n log(n))', where 'k' is max(len(pattern)) for\neach pattern in the list, and 'n' is len(patterns).\n\nBy discovering this set of interesting patterns, we reduce the runtime\nof multi-pattern 'git for-each-ref' (and other ref traversals) from\nO(N) to O(n log(N)), where 'N' is the total number of packed references.\n\nRunning 'git for-each-ref refs/tags/a refs/tags/b' on a repository with\n10,000,000 refs in 'refs/tags/huge-N', my best-of-five times drop from:\n\n real 0m5.805s\n user 0m5.188s\n sys 0m0.468s\n\nto:\n\n real 0m0.001s\n user 0m0.000s\n sys 0m0.000s\n\nOn linux.git, the times to dig out two of the latest -rc tags drops from\n0.002s to 0.001s, so the change on repositories with fewer tags is much\nless noticeable.\n\nCo-authored-by: Jeff King \nSigned-off-by: Jeff King \nSigned-off-by: Taylor Blau \n---\n ref-filter.c | 89 +++++++++++++++++++++++++++++------------\n t/t6300-for-each-ref.sh | 26 ++++++++++++\n 2 files changed, 89 insertions(+), 26 deletions(-)\n\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 8500671bc6..3e10fd647b 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -20,6 +20,7 @@\n #include \"commit-slab.h\"\n #include \"commit-graph.h\"\n #include \"commit-reach.h\"\n+#include \"argv-array.h\"\n \n static struct ref_msg {\n \tconst char *gone;\n@@ -1790,21 +1791,62 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname)\n \treturn match_pattern(filter, refname);\n }\n \n-/*\n- * Find the longest prefix of pattern we can pass to\n- * `for_each_fullref_in()`, namely the part of pattern preceding the\n- * first glob character. (Note that `for_each_fullref_in()` is\n- * perfectly happy working with a prefix that doesn't end at a\n- * pathname component boundary.)\n- */\n-static void find_longest_prefix(struct strbuf *out, const char *pattern)\n+static int qsort_strcmp(const void *va, const void *vb)\n {\n-\tconst char *p;\n+\tconst char *a = *(const char **)va;\n+\tconst char *b = *(const char **)vb;\n \n-\tfor (p = pattern; *p && !is_glob_special(*p); p++)\n-\t\t;\n+\treturn strcmp(a, b);\n+}\n \n-\tstrbuf_add(out, pattern, p - pattern);\n+static void find_longest_prefixes_1(struct string_list *out,\n+\t\t\t\t struct strbuf *prefix,\n+\t\t\t\t const char **patterns, size_t nr)\n+{\n+\tsize_t i;\n+\n+\tfor (i = 0; i < nr; i++) {\n+\t\tchar c = patterns[i][prefix->len];\n+\t\tif (!c || is_glob_special(c)) {\n+\t\t\tstring_list_append(out, prefix->buf);\n+\t\t\treturn;\n+\t\t}\n+\t}\n+\n+\ti = 0;\n+\twhile (i < nr) {\n+\t\tsize_t end;\n+\n+\t\t/*\n+\t\t* Set \"end\" to the index of the element _after_ the last one\n+\t\t* in our group.\n+\t\t*/\n+\t\tfor (end = i + 1; end < nr; end++) {\n+\t\t\tif (patterns[i][prefix->len] != patterns[end][prefix->len])\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tstrbuf_addch(prefix, patterns[i][prefix->len]);\n+\t\tfind_longest_prefixes_1(out, prefix, patterns + i, end - i);\n+\t\tstrbuf_setlen(prefix, prefix->len - 1);\n+\n+\t\ti = end;\n+\t}\n+}\n+\n+static void find_longest_prefixes(struct string_list *out,\n+\t\t\t\t const char **patterns)\n+{\n+\tstruct argv_array sorted = ARGV_ARRAY_INIT;\n+\tstruct strbuf prefix = STRBUF_INIT;\n+\n+\targv_array_pushv(&sorted, patterns);\n+\tQSORT(sorted.argv, sorted.argc, qsort_strcmp);\n+\n+\tfind_longest_prefixes_1(out, &prefix, sorted.argv, sorted.argc);\n+\n+\targv_array_clear(&sorted);\n+\tstrbuf_release(&prefix);\n }\n \n /*\n@@ -1817,7 +1859,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n \t\t\t\t void *cb_data,\n \t\t\t\t int broken)\n {\n-\tstruct strbuf prefix = STRBUF_INIT;\n+\tstruct string_list prefixes = STRING_LIST_INIT_DUP;\n+\tstruct string_list_item *prefix;\n \tint ret;\n \n \tif (!filter->match_as_path) {\n@@ -1843,21 +1886,15 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n \t\treturn for_each_fullref_in(\"\", cb, cb_data, broken);\n \t}\n \n-\tif (filter->name_patterns[1]) {\n-\t\t/*\n-\t\t * multiple patterns; in theory this could still work as long\n-\t\t * as the patterns are disjoint. We'd just make multiple calls\n-\t\t * to for_each_ref(). But if they're not disjoint, we'd end up\n-\t\t * reporting the same ref multiple times. So let's punt on that\n-\t\t * for now.\n-\t\t */\n-\t\treturn for_each_fullref_in(\"\", cb, cb_data, broken);\n+\tfind_longest_prefixes(&prefixes, filter->name_patterns);\n+\n+\tfor_each_string_list_item(prefix, &prefixes) {\n+\t\tret = for_each_fullref_in(prefix->string, cb, cb_data, broken);\n+\t\tif (ret)\n+\t\t\tbreak;\n \t}\n \n-\tfind_longest_prefix(&prefix, filter->name_patterns[0]);\n-\n-\tret = for_each_fullref_in(prefix.buf, cb, cb_data, broken);\n-\tstrbuf_release(&prefix);\n+\tstring_list_clear(&prefixes, 0);\n \treturn ret;\n }\n \ndiff --git a/t/t6300-for-each-ref.sh b/t/t6300-for-each-ref.sh\nindex d9235217fc..ab69aa176d 100755\n--- a/t/t6300-for-each-ref.sh\n+++ b/t/t6300-for-each-ref.sh\n@@ -345,6 +345,32 @@ test_expect_success 'Verify descending sort' '\n \ttest_cmp expected actual\n '\n \n+cat >expected <<\\EOF\n+refs/tags/testtag\n+refs/tags/testtag-2\n+EOF\n+\n+test_expect_success 'exercise patterns with prefixes' '\n+\tgit tag testtag-2 &&\n+\ttest_when_finished \"git tag -d testtag-2\" &&\n+\tgit for-each-ref --format=\"%(refname)\" \\\n+\t\trefs/tags/testtag refs/tags/testtag-2 >actual &&\n+\ttest_cmp expected actual\n+'\n+\n+cat >expected <<\\EOF\n+refs/tags/testtag\n+refs/tags/testtag-2\n+EOF\n+\n+test_expect_success 'exercise glob patterns with prefixes' '\n+\tgit tag testtag-2 &&\n+\ttest_when_finished \"git tag -d testtag-2\" &&\n+\tgit for-each-ref --format=\"%(refname)\" \\\n+\t\trefs/tags/testtag \"refs/tags/testtag-*\" >actual &&\n+\ttest_cmp expected actual\n+'\n+\n cat >expected <<\\EOF\n 'refs/heads/master'\n 'refs/remotes/origin/master'\n-- \n2.21.0.203.g358da99528\n"},{"id":"378106","messageId":"CA+P7+xqQv4UZMy7fEHnGHejU6nvhVKgkSruXdmW-akqUG1TLKA@mail.gmail.com","threadId":"51388","inReplyTo":"e41db267f7b7086126e9fd3fd5b1a02e38c8c077.1561588479.git.me@ttaylorr.com","subject":"Re: [PATCH 1/1] ref-filter.c: find disjoint pattern prefixes","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2019-06-27T00:37:42Z","receivedAt":"2019-06-27T00:37:59Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Wed, Jun 26, 2019 at 3:44 PM Taylor Blau wrote:\n>\n> Since cfe004a5a9 (ref-filter: limit traversal to prefix, 2017-05-22),\n> the ref-filter code has sought to limit the traversals to a prefix of\n> the given patterns.\n>\n> That code stopped short of handling more than one pattern, because it\n> means invoking 'for_each_ref_in' multiple times. If we're not careful\n> about which patterns overlap, we will output the same refs multiple\n> times.\n\nRight.\n\n>\n> For instance, consider the set of patterns 'refs/heads/a/*',\n> 'refs/heads/a/b/c', and 'refs/tags/v1.0.0'. If we naďvely ran:\n>\n> for_each_ref_in(\"refs/heads/a/*\", ...);\n> for_each_ref_in(\"refs/heads/a/b/c\", ...);\n> for_each_ref_in(\"refs/tags/v1.0.0\", ...);\n>\n> we would see 'refs/heads/a/b/c' (and everything underneath it) twice.\n>\n\nExplaining why we ignored solving this before..\n\n> Instead, we want to partition the patterns into disjoint sets, where we\n> know that no ref will be matched by any two patterns in different sets.\n> In the above, these are:\n>\n> - {'refs/heads/a/*', 'refs/heads/a/b/c'}, and\n> - {'refs/tags/v1.0.0'}\n\nIs this disjoint set calculation already existing, or did you have to\nadd it in this patch?\n\n>\n> Given one of these disjoint sets, what is a suitable pattern to pass to\n> 'for_each_ref_in'? One approach is to compute the longest common prefix\n> over all elements in that disjoint set, and let the caller cull out the\n> refs they didn't want. Computing the longest prefix means that in most\n> cases, we won't match too many things the caller would like to ignore.\n>\n> The longest common prefixes of the above are:\n>\n> - {'refs/heads/a/*', 'refs/heads/a/b/c'} -> refs/heads/a/*\n> - {'refs/tags/v1.0.0'} -> refs/tags/v1.0.0\n>\n> We instead invoke:\n>\n> for_each_ref_in(\"refs/heads/a/*\", ...);\n> for_each_ref_in(\"refs/tags/v1.0.0\", ...);\n>\n> Which provides us with the refs we were looking for with a minimal\n> amount of extra cruft, but never a duplicate of the ref we asked for.\n>\n> Implemented here is an algorithm which accomplishes the above, which\n> works as follows:\n>\n> 1. Lexicographically sort the given list of patterns.\n>\n> 2. Initialize 'prefix' to the empty string, where our goal is to\n> build each element in the above set of longest common prefixes.\n>\n> 3. Consider each pattern in the given set, and emit 'prefix' if it\n> reaches the end of a pattern, or touches a wildcard character. The\n> end of a string is treated as if it precedes a wildcard. (Note that\n> there is some room for future work to detect that, e.g., 'a?b' and\n> 'abc' are disjoint).\n\nNeat, so you're calculating disjoint patterns inline while also\nfiguring out which one is the \"best\" for any given pattern set...\nNeat!\n\n>\n> 4. Otherwise, recurse on step (3) with the slice of the list\n> corresponding to our current prefix (i.e., the subset of patterns\n> that have our prefix as a literal string prefix.)\n>\n> This algorithm is 'O(kn + n log(n))', where 'k' is max(len(pattern)) for\n> each pattern in the list, and 'n' is len(patterns).\n>\n\nok, so if we can assume that k is some relatively small constant\nnumber (since the maximum pattern length isn't likely to grow without\nbounds), this is O(n*log(n)) on the number of patterns, so we don't\neven approach n^2 even when we are given a large number of patterns.\nNice!\n\n> By discovering this set of interesting patterns, we reduce the runtime\n> of multi-pattern 'git for-each-ref' (and other ref traversals) from\n> O(N) to O(n log(N)), where 'N' is the total number of packed references.\n\nSo here, n is the number of patterns still? This seems like a pretty\nsignificant gane when we have a large number of packed references.\n\n>\n> Running 'git for-each-ref refs/tags/a refs/tags/b' on a repository with\n> 10,000,000 refs in 'refs/tags/huge-N', my best-of-five times drop from:\n>\n> real 0m5.805s\n> user 0m5.188s\n> sys 0m0.468s\n>\n> to:\n>\n> real 0m0.001s\n> user 0m0.000s\n> sys 0m0.000s\n>\n\nThat's a pretty significant decrease!\n\n> On linux.git, the times to dig out two of the latest -rc tags drops from\n> 0.002s to 0.001s, so the change on repositories with fewer tags is much\n> less noticeable.\n>\n\nThis explains why it might not have been done before.. many\nrepositories wouldn't benefit much.\n\nThat said, the patch description doesn't make it seem very\ncomplicated. I did run out of time reading the message, so I'll have\nto follow up reviewing the actual change below later. I think the\ndescription of the goal and solution is sound though.\n\nThanks,\nJake\n\n> Co-authored-by: Jeff King \n> Signed-off-by: Jeff King \n> Signed-off-by: Taylor Blau \n> ---\n> ref-filter.c | 89 +++++++++++++++++++++++++++++------------\n> t/t6300-for-each-ref.sh | 26 ++++++++++++\n> 2 files changed, 89 insertions(+), 26 deletions(-)\n>\n> diff --git a/ref-filter.c b/ref-filter.c\n> index 8500671bc6..3e10fd647b 100644\n> --- a/ref-filter.c\n> +++ b/ref-filter.c\n> @@ -20,6 +20,7 @@\n> #include \"commit-slab.h\"\n> #include \"commit-graph.h\"\n> #include \"commit-reach.h\"\n> +#include \"argv-array.h\"\n>\n> static struct ref_msg {\n> const char *gone;\n> @@ -1790,21 +1791,62 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname)\n> return match_pattern(filter, refname);\n> }\n>\n> -/*\n> - * Find the longest prefix of pattern we can pass to\n> - * `for_each_fullref_in()`, namely the part of pattern preceding the\n> - * first glob character. (Note that `for_each_fullref_in()` is\n> - * perfectly happy working with a prefix that doesn't end at a\n> - * pathname component boundary.)\n> - */\n> -static void find_longest_prefix(struct strbuf *out, const char *pattern)\n> +static int qsort_strcmp(const void *va, const void *vb)\n> {\n> - const char *p;\n> + const char *a = *(const char **)va;\n> + const char *b = *(const char **)vb;\n>\n> - for (p = pattern; *p && !is_glob_special(*p); p++)\n> - ;\n> + return strcmp(a, b);\n> +}\n>\n> - strbuf_add(out, pattern, p - pattern);\n> +static void find_longest_prefixes_1(struct string_list *out,\n> + struct strbuf *prefix,\n> + const char **patterns, size_t nr)\n> +{\n> + size_t i;\n> +\n> + for (i = 0; i < nr; i++) {\n> + char c = patterns[i][prefix->len];\n> + if (!c || is_glob_special(c)) {\n> + string_list_append(out, prefix->buf);\n> + return;\n> + }\n> + }\n> +\n> + i = 0;\n> + while (i < nr) {\n> + size_t end;\n> +\n> + /*\n> + * Set \"end\" to the index of the element _after_ the last one\n> + * in our group.\n> + */\n> + for (end = i + 1; end < nr; end++) {\n> + if (patterns[i][prefix->len] != patterns[end][prefix->len])\n> + break;\n> + }\n> +\n> + strbuf_addch(prefix, patterns[i][prefix->len]);\n> + find_longest_prefixes_1(out, prefix, patterns + i, end - i);\n> + strbuf_setlen(prefix, prefix->len - 1);\n> +\n> + i = end;\n> + }\n> +}\n> +\n> +static void find_longest_prefixes(struct string_list *out,\n> + const char **patterns)\n> +{\n> + struct argv_array sorted = ARGV_ARRAY_INIT;\n> + struct strbuf prefix = STRBUF_INIT;\n> +\n> + argv_array_pushv(&sorted, patterns);\n> + QSORT(sorted.argv, sorted.argc, qsort_strcmp);\n> +\n> + find_longest_prefixes_1(out, &prefix, sorted.argv, sorted.argc);\n> +\n> + argv_array_clear(&sorted);\n> + strbuf_release(&prefix);\n> }\n>\n> /*\n> @@ -1817,7 +1859,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n> void *cb_data,\n> int broken)\n> {\n> - struct strbuf prefix = STRBUF_INIT;\n> + struct string_list prefixes = STRING_LIST_INIT_DUP;\n> + struct string_list_item *prefix;\n> int ret;\n>\n> if (!filter->match_as_path) {\n> @@ -1843,21 +1886,15 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n> return for_each_fullref_in(\"\", cb, cb_data, broken);\n> }\n>\n> - if (filter->name_patterns[1]) {\n> - /*\n> - * multiple patterns; in theory this could still work as long\n> - * as the patterns are disjoint. We'd just make multiple calls\n> - * to for_each_ref(). But if they're not disjoint, we'd end up\n> - * reporting the same ref multiple times. So let's punt on that\n> - * for now.\n> - */\n> - return for_each_fullref_in(\"\", cb, cb_data, broken);\n> + find_longest_prefixes(&prefixes, filter->name_patterns);\n> +\n> + for_each_string_list_item(prefix, &prefixes) {\n> + ret = for_each_fullref_in(prefix->string, cb, cb_data, broken);\n> + if (ret)\n> + break;\n> }\n>\n> - find_longest_prefix(&prefix, filter->name_patterns[0]);\n> -\n> - ret = for_each_fullref_in(prefix.buf, cb, cb_data, broken);\n> - strbuf_release(&prefix);\n> + string_list_clear(&prefixes, 0);\n> return ret;\n> }\n>\n> diff --git a/t/t6300-for-each-ref.sh b/t/t6300-for-each-ref.sh\n> index d9235217fc..ab69aa176d 100755\n> --- a/t/t6300-for-each-ref.sh\n> +++ b/t/t6300-for-each-ref.sh\n> @@ -345,6 +345,32 @@ test_expect_success 'Verify descending sort' '\n> test_cmp expected actual\n> '\n>\n> +cat >expected <<\\EOF\n> +refs/tags/testtag\n> +refs/tags/testtag-2\n> +EOF\n> +\n> +test_expect_success 'exercise patterns with prefixes' '\n> + git tag testtag-2 &&\n> + test_when_finished \"git tag -d testtag-2\" &&\n> + git for-each-ref --format=\"%(refname)\" \\\n> + refs/tags/testtag refs/tags/testtag-2 >actual &&\n> + test_cmp expected actual\n> +'\n> +\n> +cat >expected <<\\EOF\n> +refs/tags/testtag\n> +refs/tags/testtag-2\n> +EOF\n> +\n> +test_expect_success 'exercise glob patterns with prefixes' '\n> + git tag testtag-2 &&\n> + test_when_finished \"git tag -d testtag-2\" &&\n> + git for-each-ref --format=\"%(refname)\" \\\n> + refs/tags/testtag \"refs/tags/testtag-*\" >actual &&\n> + test_cmp expected actual\n> +'\n> +\n> cat >expected <<\\EOF\n> 'refs/heads/master'\n> 'refs/remotes/origin/master'\n> --\n> 2.21.0.203.g358da99528\n"},{"id":"378223","messageId":"CA+P7+xqhFY2gcV=3f8TgemOPPiPnyZU1CgXoNSzoh60bdw1OYQ@mail.gmail.com","threadId":"51388","inReplyTo":"e41db267f7b7086126e9fd3fd5b1a02e38c8c077.1561588479.git.me@ttaylorr.com","subject":"Re: [PATCH 1/1] ref-filter.c: find disjoint pattern prefixes","fromName":"Jacob Keller","fromEmail":"jacob.keller@gmail.com","sentAt":"2019-06-27T23:21:57Z","receivedAt":"2019-06-27T23:22:12Z","isPatch":true,"sender":{"key":"jacob.keller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"On Wed, Jun 26, 2019 at 3:44 PM Taylor Blau wrote:\n>\n\nOk, now I've got some time to look at the code itself.\n\n> ref-filter.c | 89 +++++++++++++++++++++++++++++------------\n> t/t6300-for-each-ref.sh | 26 ++++++++++++\n> 2 files changed, 89 insertions(+), 26 deletions(-)\n>\n> diff --git a/ref-filter.c b/ref-filter.c\n> index 8500671bc6..3e10fd647b 100644\n> --- a/ref-filter.c\n> +++ b/ref-filter.c\n> @@ -20,6 +20,7 @@\n> #include \"commit-slab.h\"\n> #include \"commit-graph.h\"\n> #include \"commit-reach.h\"\n> +#include \"argv-array.h\"\n>\n> static struct ref_msg {\n> const char *gone;\n> @@ -1790,21 +1791,62 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname)\n> return match_pattern(filter, refname);\n> }\n>\n> -/*\n> - * Find the longest prefix of pattern we can pass to\n> - * `for_each_fullref_in()`, namely the part of pattern preceding the\n> - * first glob character. (Note that `for_each_fullref_in()` is\n> - * perfectly happy working with a prefix that doesn't end at a\n> - * pathname component boundary.)\n> - */\n> -static void find_longest_prefix(struct strbuf *out, const char *pattern)\n> +static int qsort_strcmp(const void *va, const void *vb)\n> {\n> - const char *p;\n> + const char *a = *(const char **)va;\n> + const char *b = *(const char **)vb;\n>\n> - for (p = pattern; *p && !is_glob_special(*p); p++)\n> - ;\n> + return strcmp(a, b);\n> +}\n>\n> - strbuf_add(out, pattern, p - pattern);\n> +static void find_longest_prefixes_1(struct string_list *out,\n> + struct strbuf *prefix,\n> + const char **patterns, size_t nr)\n> +{\n> + size_t i;\n> +\n> + for (i = 0; i < nr; i++) {\n> + char c = patterns[i][prefix->len];\n> + if (!c || is_glob_special(c)) {\n> + string_list_append(out, prefix->buf);\n> + return;\n> + }\n> + }\n\nOk, so we loop over the patterns, find the last character up to our\ncurrent prefix length, and check if it's either the end of the string,\nor a special glob character. I assume that the patterns are sorted so\nthat prefix->len never goes past the array?\n\nIf we find one, we just add this to the list and return, since we\nfound an unambigous one.\n\nOtherwise, we keep searching recursively.\n\nSo, prefix is a strbuf, and its length will initially be zero. So, we\ncheck all patterns, up to the prefix length and check the character\njust past the end of our prefix. If it matches a NUL or glob\ncharacter, then we have found an exact match up to a glob, so this\ngets returned.\n\nOtherwise we continue:\n\n> +\n> + i = 0;\n> + while (i < nr) {\n> + size_t end;\n> +\n\nHere, we're going to loop from beginning to end of all of the strings.\n\n> + /*\n> + * Set \"end\" to the index of the element _after_ the last one\n> + * in our group.\n> + */\n> + for (end = i + 1; end < nr; end++) {\n> + if (patterns[i][prefix->len] != patterns[end][prefix->len])\n> + break;\n> + }\n> +\n\nWe break on the first string which doesn't have the same length as our\ncurrent prefix, but start with the ones after the current loop\niteration.\n\n> + strbuf_addch(prefix, patterns[i][prefix->len]);\n> + find_longest_prefixes_1(out, prefix, patterns + i, end - i);\n> + strbuf_setlen(prefix, prefix->len - 1);\n> +\n\nWe'll add the next character to the prefix, and then find longest\nprefixes again.\n\nThis basically has us recurse and keep adding additional characters,\nessentially splitting the strings apart by their disjoint sets.\n\nI think this works, but it's definitely not clear from reading exactly\nwhat is going on. I think this algorithm would benefit from a comment,\nsince it doesn't quite seem to match your description in the commit\nmessage.\n\n> + i = end;\n> + }\n> +}\n> +\n> +static void find_longest_prefixes(struct string_list *out,\n> + const char **patterns)\n> +{\n> + struct argv_array sorted = ARGV_ARRAY_INIT;\n> + struct strbuf prefix = STRBUF_INIT;\n> +\n> + argv_array_pushv(&sorted, patterns);\n> + QSORT(sorted.argv, sorted.argc, qsort_strcmp);\n> +\n\nWe've sorted the patterns, and then we call find_longest_prefixes_1. Ok.\n\n> + find_longest_prefixes_1(out, &prefix, sorted.argv, sorted.argc);\n> +\n> + argv_array_clear(&sorted);\n> + strbuf_release(&prefix);\n> }\n>\n> /*\n> @@ -1817,7 +1859,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n> void *cb_data,\n> int broken)\n> {\n> - struct strbuf prefix = STRBUF_INIT;\n> + struct string_list prefixes = STRING_LIST_INIT_DUP;\n> + struct string_list_item *prefix;\n> int ret;\n>\n> if (!filter->match_as_path) {\n> @@ -1843,21 +1886,15 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n> return for_each_fullref_in(\"\", cb, cb_data, broken);\n> }\n>\n> - if (filter->name_patterns[1]) {\n> - /*\n> - * multiple patterns; in theory this could still work as long\n> - * as the patterns are disjoint. We'd just make multiple calls\n> - * to for_each_ref(). But if they're not disjoint, we'd end up\n> - * reporting the same ref multiple times. So let's punt on that\n> - * for now.\n> - */\n> - return for_each_fullref_in(\"\", cb, cb_data, broken);\n> + find_longest_prefixes(&prefixes, filter->name_patterns);\n> +\n> + for_each_string_list_item(prefix, &prefixes) {\n> + ret = for_each_fullref_in(prefix->string, cb, cb_data, broken);\n> + if (ret)\n> + break;\n> }\n>\n> - find_longest_prefix(&prefix, filter->name_patterns[0]);\n> -\n> - ret = for_each_fullref_in(prefix.buf, cb, cb_data, broken);\n> - strbuf_release(&prefix);\n> + string_list_clear(&prefixes, 0);\n> return ret;\n> }\n>\n> diff --git a/t/t6300-for-each-ref.sh b/t/t6300-for-each-ref.sh\n> index d9235217fc..ab69aa176d 100755\n> --- a/t/t6300-for-each-ref.sh\n> +++ b/t/t6300-for-each-ref.sh\n> @@ -345,6 +345,32 @@ test_expect_success 'Verify descending sort' '\n> test_cmp expected actual\n> '\n>\n> +cat >expected <<\\EOF\n> +refs/tags/testtag\n> +refs/tags/testtag-2\n> +EOF\n> +\n> +test_expect_success 'exercise patterns with prefixes' '\n> + git tag testtag-2 &&\n> + test_when_finished \"git tag -d testtag-2\" &&\n> + git for-each-ref --format=\"%(refname)\" \\\n> + refs/tags/testtag refs/tags/testtag-2 >actual &&\n> + test_cmp expected actual\n> +'\n> +\n> +cat >expected <<\\EOF\n> +refs/tags/testtag\n> +refs/tags/testtag-2\n> +EOF\n> +\n> +test_expect_success 'exercise glob patterns with prefixes' '\n> + git tag testtag-2 &&\n> + test_when_finished \"git tag -d testtag-2\" &&\n> + git for-each-ref --format=\"%(refname)\" \\\n> + refs/tags/testtag \"refs/tags/testtag-*\" >actual &&\n> + test_cmp expected actual\n> +'\n> +\n> cat >expected <<\\EOF\n> 'refs/heads/master'\n> 'refs/remotes/origin/master'\n> --\n> 2.21.0.203.g358da99528\n"},{"id":"378394","messageId":"20190701143759.GA38109@TaylorsMBP5715.attlocal.net","threadId":"51388","inReplyTo":"CA+P7+xqQv4UZMy7fEHnGHejU6nvhVKgkSruXdmW-akqUG1TLKA@mail.gmail.com","subject":"Re: [PATCH 1/1] ref-filter.c: find disjoint pattern prefixes","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2019-07-01T14:39:02Z","receivedAt":"2019-07-01T14:39:10Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Jacob,\n\nOn Wed, Jun 26, 2019 at 05:37:42PM -0700, Jacob Keller wrote:\n> [ ... ]\n>\n> > Instead, we want to partition the patterns into disjoint sets, where we\n> > know that no ref will be matched by any two patterns in different sets.\n> > In the above, these are:\n> >\n> > - {'refs/heads/a/*', 'refs/heads/a/b/c'}, and\n> > - {'refs/tags/v1.0.0'}\n>\n> Is this disjoint set calculation already existing, or did you have to\n> add it in this patch?\n\nBoth the disjoint set calculation and the prefixing procedure are new in\nthis patch. But, we're never actually computing this disjoint set\nexplicitly, rather, we build it up implicitly while computing what will\nbecome the longest prefixes of each subset.\n\n> > 4. Otherwise, recurse on step (3) with the slice of the list\n> > corresponding to our current prefix (i.e., the subset of patterns\n> > that have our prefix as a literal string prefix.)\n> >\n> > This algorithm is 'O(kn + n log(n))', where 'k' is max(len(pattern)) for\n> > each pattern in the list, and 'n' is len(patterns).\n> >\n>\n> ok, so if we can assume that k is some relatively small constant\n> number (since the maximum pattern length isn't likely to grow without\n> bounds), this is O(n*log(n)) on the number of patterns, so we don't\n> even approach n^2 even when we are given a large number of patterns.\n> Nice!\n>\n> > By discovering this set of interesting patterns, we reduce the runtime\n> > of multi-pattern 'git for-each-ref' (and other ref traversals) from\n> > O(N) to O(n log(N)), where 'N' is the total number of packed references.\n>\n> So here, n is the number of patterns still? This seems like a pretty\n> significant gane when we have a large number of packed references.\n\nYes, 'n' is the number of patterns given. For e.g., the invocation\n\n $ git for-each-ref 'refs/heads/*' 'refs/tags/*'\n\nhas 'n = 2', and 'N' is unknown. The asymptotics here are really\ncomparing the case where we previously didn't make any effort to compute\ngood queries, and resorted to a linear scan of all packed references,\ncompared to now where we have at most one query per pattern, resulting\nin a logarithmic-time scan of .git/packed-refs.\n\n> >\n> > Running 'git for-each-ref refs/tags/a refs/tags/b' on a repository with\n> > 10,000,000 refs in 'refs/tags/huge-N', my best-of-five times drop from:\n> >\n> > real 0m5.805s\n> > user 0m5.188s\n> > sys 0m0.468s\n> >\n> > to:\n> >\n> > real 0m0.001s\n> > user 0m0.000s\n> > sys 0m0.000s\n> >\n>\n> That's a pretty significant decrease!\n\nYes, it's quite good here, but it's designed to be that way ;-). Like I\nnote below, the real world speed-ups aren't quite as remarkable, but\nit's not uncommon for us at GitHub to have a repository of the above\nshape in terms of the number of references.\n\nSo, it's an increase almost no matter where you are, but it works\nespecially well for us.\n\n> > On linux.git, the times to dig out two of the latest -rc tags drops from\n> > 0.002s to 0.001s, so the change on repositories with fewer tags is much\n> > less noticeable.\n> >\n>\n> This explains why it might not have been done before.. many\n> repositories wouldn't benefit much.\n>\n> That said, the patch description doesn't make it seem very\n> complicated. I did run out of time reading the message, so I'll have\n> to follow up reviewing the actual change below later. I think the\n> description of the goal and solution is sound though.\n\nThanks for the initial review :-).\n\nThanks,\nTaylor\n"},{"id":"378406","messageId":"20190701144918.GB38109@TaylorsMBP5715.attlocal.net","threadId":"51388","inReplyTo":"CA+P7+xqhFY2gcV=3f8TgemOPPiPnyZU1CgXoNSzoh60bdw1OYQ@mail.gmail.com","subject":"Re: [PATCH 1/1] ref-filter.c: find disjoint pattern prefixes","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2019-07-01T14:49:18Z","receivedAt":"2019-07-01T14:49:26Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Jacob,\n\nOn Thu, Jun 27, 2019 at 04:21:57PM -0700, Jacob Keller wrote:\n> On Wed, Jun 26, 2019 at 3:44 PM Taylor Blau wrote:\n> >\n>\n> Ok, now I've got some time to look at the code itself.\n>\n> > ref-filter.c | 89 +++++++++++++++++++++++++++++------------\n> > t/t6300-for-each-ref.sh | 26 ++++++++++++\n> > 2 files changed, 89 insertions(+), 26 deletions(-)\n> >\n> > diff --git a/ref-filter.c b/ref-filter.c\n> > index 8500671bc6..3e10fd647b 100644\n> > --- a/ref-filter.c\n> > +++ b/ref-filter.c\n> > @@ -20,6 +20,7 @@\n> > #include \"commit-slab.h\"\n> > #include \"commit-graph.h\"\n> > #include \"commit-reach.h\"\n> > +#include \"argv-array.h\"\n> >\n> > static struct ref_msg {\n> > const char *gone;\n> > @@ -1790,21 +1791,62 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname)\n> > return match_pattern(filter, refname);\n> > }\n> >\n> > -/*\n> > - * Find the longest prefix of pattern we can pass to\n> > - * `for_each_fullref_in()`, namely the part of pattern preceding the\n> > - * first glob character. (Note that `for_each_fullref_in()` is\n> > - * perfectly happy working with a prefix that doesn't end at a\n> > - * pathname component boundary.)\n> > - */\n> > -static void find_longest_prefix(struct strbuf *out, const char *pattern)\n> > +static int qsort_strcmp(const void *va, const void *vb)\n> > {\n> > - const char *p;\n> > + const char *a = *(const char **)va;\n> > + const char *b = *(const char **)vb;\n> >\n> > - for (p = pattern; *p && !is_glob_special(*p); p++)\n> > - ;\n> > + return strcmp(a, b);\n> > +}\n> >\n> > - strbuf_add(out, pattern, p - pattern);\n> > +static void find_longest_prefixes_1(struct string_list *out,\n> > + struct strbuf *prefix,\n> > + const char **patterns, size_t nr)\n> > +{\n> > + size_t i;\n> > +\n> > + for (i = 0; i < nr; i++) {\n> > + char c = patterns[i][prefix->len];\n> > + if (!c || is_glob_special(c)) {\n> > + string_list_append(out, prefix->buf);\n> > + return;\n> > + }\n> > + }\n>\n> Ok, so we loop over the patterns, find the last character up to our\n> current prefix length, and check if it's either the end of the string,\n> or a special glob character. I assume that the patterns are sorted so\n> that prefix->len never goes past the array?\n\nThat's right. The idea here is that if we compare two patterns character\nby character, we can detect where the references \"split\", and thus\nconstitute membership of unique disjoint sets.\n\nConsider the following example:\n\n refs/heads/a\n refs/heads/b\n ^\n\nHere, we were given, say 'git for-each-ref refs/heads/a refs/heads/b',\nand appropriate queries are:\n\n - '*'\n - 'refs/*'\n - 'refs/heads/*'\n - 'refs/heads/a' with 'refs/heads/b'\n\nWhen we have advanced our cursor up until the position where the\npatterns read 'a', and 'b', respectively, we have built up so far as our\npattern: 'refs/heads/'. We would like to realize that those two can\ncreate two queries, so when we discover that 'a' != 'b', we \"split\" the\nstrbuf into two patterns in the next level of recursion.\n\nOne alternative view is that we are trying to construct the shortest\npaths from the root of the tree to the leaf 'NUL' nodes as below:\n\n a --- NUL\n /\n refs --- heads\n \\\n b --- NUL\n\n> If we find one, we just add this to the list and return, since we\n> found an unambigous one.\n>\n> Otherwise, we keep searching recursively.\n>\n> So, prefix is a strbuf, and its length will initially be zero. So, we\n> check all patterns, up to the prefix length and check the character\n> just past the end of our prefix. If it matches a NUL or glob\n> character, then we have found an exact match up to a glob, so this\n> gets returned.\n\nRight: two additional wrinkles here.\n\nOne is that we don't have very careful handling of wildcard characters,\ni.e., between 'a*c' and '*bc' we give up and split those at 'a*', and\n'*b' (an equally good query would be '**c'), so treat the presence of a\nwildcard character the same way we would a disagreement in character as\nabove.\n\nThe second wrinkle is that we originally wrote this patch looking for\ndisagreements in _ref component_, i.e., that given 'refs/heads/a' with\n'refs/tags/a', we would split because 'heads != tags', not 'h != t'. The\nreferences backend (to my surprise) does per-character matching, so\nthat's why we do it, too.\n\n> Here, we're going to loop from beginning to end of all of the strings.\n>\n> > + /*\n> > + * Set \"end\" to the index of the element _after_ the last one\n> > + * in our group.\n> > + */\n> > + for (end = i + 1; end < nr; end++) {\n> > + if (patterns[i][prefix->len] != patterns[end][prefix->len])\n> > + break;\n> > + }\n> > +\n>\n> We break on the first string which doesn't have the same length as our\n> current prefix, but start with the ones after the current loop\n> iteration.\n>\n> > + strbuf_addch(prefix, patterns[i][prefix->len]);\n> > + find_longest_prefixes_1(out, prefix, patterns + i, end - i);\n> > + strbuf_setlen(prefix, prefix->len - 1);\n> > +\n\nRight, we have a potentially long list of patterns underneath that we\nhave just covered, so we can skip those.\n\n> We'll add the next character to the prefix, and then find longest\n> prefixes again.\n>\n> This basically has us recurse and keep adding additional characters,\n> essentially splitting the strings apart by their disjoint sets.\n>\n> I think this works, but it's definitely not clear from reading exactly\n> what is going on. I think this algorithm would benefit from a comment,\n> since it doesn't quite seem to match your description in the commit\n> message.\n> > + find_longest_prefixes_1(out, &prefix, sorted.argv, sorted.argc);\n> > +\n> > + argv_array_clear(&sorted);\n> > + strbuf_release(&prefix);\n\nFair enough, I'm happy to add a comment if others like, too.\n\nThanks,\nTaylor\n"}]}