{"thread":{"id":"57953","subject":"[PATCH] builtin/show-ref.c: avoid over-iterating with --heads, --tags","startedAt":"2022-06-03T21:55:43Z","lastAt":"2022-06-06T17:16:48Z","messageCount":3,"participants":["Taylor Blau","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"456639","messageId":"3fa6932641f18d78156bbf60b1571383f2cb5046.1654293264.git.me@ttaylorr.com","threadId":"57953","inReplyTo":null,"subject":"[PATCH] builtin/show-ref.c: avoid over-iterating with --heads, --tags","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2022-06-03T21:55:36Z","receivedAt":"2022-06-03T21:55:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When `show-ref` is combined with the `--heads` or `--tags` options, it\ncan avoid iterating parts of a repository's references that it doesn't\ncare about.\n\nBut it doesn't take advantage of this potential optimization. When this\ncommand was introduced back in 358ddb62cf (Add \"git show-ref\" builtin\ncommand, 2006-09-15), `for_each_ref_in()` did exist. But since most\nrepositories don't have many (any?) references that aren't branches or\ntags already, this makes little difference in practice.\n\nThough for repositories with a large imbalance of branches and tags (or,\nmore likely in the case of server operators, many hidden references),\nthis can make quite a difference. Take, for example, a repository with\n500,000 \"hidden\" references (all of the form \"refs/__hidden__/N\"), and\na single branch:\n\n    git commit --allow-empty -m \"base\" &&\n    seq 1 500000 | sed 's,\\(.*\\),create refs/__hidden__/\\1 HEAD,' |\n      git update-ref --stdin &&\n    git pack-refs --all\n\nOutputting the existence of that single branch currently takes on the\norder of ~50ms on my machine. The vast majority of this time is wasted\niterating through references that we know we're going to discard.\n\nInstead, teach `show-ref` that it can iterate just \"refs/heads\" and/or\n\"refs/tags\" when given `--heads` and/or `--tags`, respectively. A few\nsmall interesting things to note:\n\n  - When given either option, we can avoid the general-purpose\n    for_each_ref() call altogether, since we know that it won't give us\n    any references that we wouldn't filter out already.\n\n  - We can make two separate calls to `for_each_fullref_in()` (and\n    avoid, say, the more specialized `for_each_fullref_in_prefixes()`,\n    since we know that the set of references enumerated by each is\n    disjoint, so we'll never see the same reference appear in both\n    calls.\n\n  - We have to use the \"fullref\" variant (instead of just\n    `for_each_branch_ref()` and `for_each_tag_ref()`), since we expect\n    fully-qualified reference names to appear in `show-ref`'s output.\n\nWhen either of `heads_only` or `tags_only` is set, we can eliminate the\nstrcmp() calls in `builtin/show-ref.c::show_ref()` altogether, since we\nknow that `show_ref()` will never see a non-branch or tag reference.\n\nUnfortunately, we can't use `for_each_fullref_in_prefixes()` to enhance\n`show-ref`'s pattern matching, since `show-ref` patterns match on the\n_suffix_ (e.g., the pattern \"foo\" shows \"refs/heads/foo\",\n\"refs/tags/foo\", and etc, not \"foo/*\").\n\nNonetheless, in our synthetic example above, this provides a significant\nspeed-up (\"git\" is roughly v2.36, \"git.compile\" is this patch):\n\n    $ hyperfine -N 'git show-ref --heads' 'git.compile show-ref --heads'\n    Benchmark 1: git show-ref --heads\n      Time (mean ± σ):      49.9 ms ±   6.2 ms    [User: 45.6 ms, System: 4.1 ms]\n      Range (min … max):    46.1 ms …  73.6 ms    43 runs\n\n    Benchmark 2: git.compile show-ref --heads\n      Time (mean ± σ):       2.8 ms ±   0.4 ms    [User: 1.4 ms, System: 1.2 ms]\n      Range (min … max):     1.3 ms …   5.6 ms    957 runs\n\n    Summary\n      'git.compile show-ref --heads' ran\n       18.03 ± 3.38 times faster than 'git show-ref --heads'\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\nThis is obviously a little extreme of an example for most use-cases,\nbut it does come up more often than not within GitHub, where we have\nmany repositories with lots of hidden references that we're wasting time\nenumerating with `show-ref`.\n\n builtin/show-ref.c | 17 ++++++++---------\n 1 file changed, 8 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/show-ref.c b/builtin/show-ref.c\nindex 7f8a5332f8..5fa207a044 100644\n--- a/builtin/show-ref.c\n+++ b/builtin/show-ref.c\n@@ -52,14 +52,6 @@ static int show_ref(const char *refname, const struct object_id *oid,\n \tif (show_head && !strcmp(refname, \"HEAD\"))\n \t\tgoto match;\n\n-\tif (tags_only || heads_only) {\n-\t\tint match;\n-\n-\t\tmatch = heads_only && starts_with(refname, \"refs/heads/\");\n-\t\tmatch |= tags_only && starts_with(refname, \"refs/tags/\");\n-\t\tif (!match)\n-\t\t\treturn 0;\n-\t}\n \tif (pattern) {\n \t\tint reflen = strlen(refname);\n \t\tconst char **p = pattern, *m;\n@@ -216,7 +208,14 @@ int cmd_show_ref(int argc, const char **argv, const char *prefix)\n\n \tif (show_head)\n \t\thead_ref(show_ref, NULL);\n-\tfor_each_ref(show_ref, NULL);\n+\tif (heads_only || tags_only) {\n+\t\tif (heads_only)\n+\t\t\tfor_each_fullref_in(\"refs/heads/\", show_ref, NULL);\n+\t\tif (tags_only)\n+\t\t\tfor_each_fullref_in(\"refs/tags/\", show_ref, NULL);\n+\t} else {\n+\t\tfor_each_ref(show_ref, NULL);\n+\t}\n \tif (!found_match) {\n \t\tif (verify && !quiet)\n \t\t\tdie(\"No match\");\n--\n2.36.1.94.gb0d54bedca\n"},{"id":"456653","messageId":"af32aefc-8184-94ff-fd80-76221dc313b4@github.com","threadId":"57953","inReplyTo":"3fa6932641f18d78156bbf60b1571383f2cb5046.1654293264.git.me@ttaylorr.com","subject":"Re: [PATCH] builtin/show-ref.c: avoid over-iterating with --heads, --tags","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2022-06-04T02:33:47Z","receivedAt":"2022-06-04T02:33:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/3/2022 5:55 PM, Taylor Blau wrote:\n> When `show-ref` is combined with the `--heads` or `--tags` options, it\n> can avoid iterating parts of a repository's references that it doesn't\n> care about.\n> \n> But it doesn't take advantage of this potential optimization. When this\n> command was introduced back in 358ddb62cf (Add \"git show-ref\" builtin\n> command, 2006-09-15), `for_each_ref_in()` did exist. But since most\n> repositories don't have many (any?) references that aren't branches or\n> tags already, this makes little difference in practice.\n...\n> Nonetheless, in our synthetic example above, this provides a significant\n> speed-up (\"git\" is roughly v2.36, \"git.compile\" is this patch):\n> \n>     $ hyperfine -N 'git show-ref --heads' 'git.compile show-ref --heads'\n>     Benchmark 1: git show-ref --heads\n>       Time (mean ± σ):      49.9 ms ±   6.2 ms    [User: 45.6 ms, System: 4.1 ms]\n>       Range (min … max):    46.1 ms …  73.6 ms    43 runs\n> \n>     Benchmark 2: git.compile show-ref --heads\n>       Time (mean ± σ):       2.8 ms ±   0.4 ms    [User: 1.4 ms, System: 1.2 ms]\n>       Range (min … max):     1.3 ms …   5.6 ms    957 runs\n> \n>     Summary\n>       'git.compile show-ref --heads' ran\n>        18.03 ± 3.38 times faster than 'git show-ref --heads'\n\nExcellent speedup.\n\n> -\tfor_each_ref(show_ref, NULL);\n> +\tif (heads_only || tags_only) {\n> +\t\tif (heads_only)\n> +\t\t\tfor_each_fullref_in(\"refs/heads/\", show_ref, NULL);\n> +\t\tif (tags_only)\n> +\t\t\tfor_each_fullref_in(\"refs/tags/\", show_ref, NULL);\n\nThis looks a little silly if these were truly \"only\" (they\ncould not both be true), but indeed they could both be true\nand the names are just slightly misleading.\n\nIndeed, t1403-show-ref.sh tests all combinations of these\noptions.\n\n> +\t} else {\n> +\t\tfor_each_ref(show_ref, NULL);\n> +\t}\n\nThanks for finding this!\n-Stolee\n"},{"id":"456726","messageId":"xmqq35ghaffn.fsf@gitster.g","threadId":"57953","inReplyTo":"af32aefc-8184-94ff-fd80-76221dc313b4@github.com","subject":"Re: [PATCH] builtin/show-ref.c: avoid over-iterating with --heads, --tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-06-06T17:07:40Z","receivedAt":"2022-06-06T17:16:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <derrickstolee@github.com> writes:\n\n>> -\tfor_each_ref(show_ref, NULL);\n>> +\tif (heads_only || tags_only) {\n>> +\t\tif (heads_only)\n>> +\t\t\tfor_each_fullref_in(\"refs/heads/\", show_ref, NULL);\n>> +\t\tif (tags_only)\n>> +\t\t\tfor_each_fullref_in(\"refs/tags/\", show_ref, NULL);\n>\n> This looks a little silly if these were truly \"only\" (they\n> could not both be true), but indeed they could both be true\n> and the names are just slightly misleading.\n>\n> Indeed, t1403-show-ref.sh tests all combinations of these\n> options.\n\nHmph, that is right. show-heads and show-tags, perhaps.\n\nThanks, both.  Queued.\n"}]}