{"thread":{"id":"62431","subject":"Re: [PATCH] setlocalversion: Add workaround for \"git describe\" performance issue","startedAt":"2024-10-31T10:37:26Z","lastAt":"2024-12-06T05:42:20Z","messageCount":27,"participants":["Rasmus Villemoes","Jeff King","Masahiro Yamada","Benno Evers","Junio C Hamano","Josh Steadmon"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"506381","messageId":"87bjz0k17c.fsf@prevas.dk","threadId":"62431","inReplyTo":"309549cafdcfe50c4fceac3263220cc3d8b109b2.1730337435.git.jpoimboe@kernel.org","subject":"Re: [PATCH] setlocalversion: Add workaround for \"git describe\" performance issue","fromName":"Rasmus Villemoes","fromEmail":"ravi@prevas.dk","sentAt":"2024-10-31T10:37:27Z","receivedAt":"2024-10-31T10:37:26Z","isPatch":true,"sender":{"key":"ravi@prevas.dk","avatar":null},"body":"On Wed, Oct 30 2024, Josh Poimboeuf wrote:\n\n> If HEAD isn't associated with an annotated tag, a bug (or feature?) in\n> \"git describe --match\" causes it to search every commit in the entire\n> repository looking for additional match candidates. Instead of it\n> taking a fraction of a second, it adds 10-15 seconds to the beginning of\n> every kernel build.\n>\n> Fix it by adding an additional dummy match which is slightly further\n> away from the most recent one, along with setting the max candidate\n> count to 1 (not 2, apparently another bug).\n>\n\ncc += git list\n\nHm, I tried looking at the git describe source code, and while I can't\nclaim I understand it very well, I think the main problem is around\nthis part:\n\n\t\t\tif (!tags && !all && n->prio < 2) {\n\t\t\t\tunannotated_cnt++;\n\t\t\t} else if (match_cnt < max_candidates) {\n\t\t\t\tstruct possible_tag *t = &all_matches[match_cnt++];\n\t\t\t\tt->name = n;\n\t\t\t\tt->depth = seen_commits - 1;\n\t\t\t\tt->flag_within = 1u << match_cnt;\n\t\t\t\tt->found_order = match_cnt;\n\t\t\t\tc->object.flags |= t->flag_within;\n\t\t\t\tif (n->prio == 2)\n\t\t\t\t\tannotated_cnt++;\n\t\t\t}\n\t\t\telse {\n\t\t\t\tgave_up_on = c;\n\t\t\t\tbreak;\n\t\t\t}\n\nSo in the case where one doesn't pass any --match, we get something like\n\ngit describe --debug 5f78aec0d7e9\ndescribe 5f78aec0d7e9\nNo exact match on refs or tags, searching to describe\n annotated 243 v4.19-rc5\n annotated 485 v4.19-rc4\n annotated 814 v4.19-rc3\n annotated 1124 v4.19-rc2\n annotated 1391 v4.19-rc1\n annotated 10546 v4.18\n annotated 10611 v4.18-rc8\n annotated 10819 v4.18-rc7\n annotated 11029 v4.18-rc6\n annotated 11299 v4.18-rc5\ntraversed 11400 commits\nmore than 10 tags found; listed 10 most recent\ngave up search at 1e4b044d22517cae7047c99038abb444423243ca\nv4.19-rc5-243-g5f78aec0d7e9\n\nand that \"gave up\" commit is v4.18-rc4, the eleventh commit\nencountered. That also explains why you have to add a \"dummy\" second\n--match to make --candidates=1 have the expected behaviour.\n\nPerhaps the logic should instead be that as soon as match_cnt hits\nmax_candidates (i.e. all the tags we're going to consider have actually\nbeen visited), we break out. That is, the last \"else\" above should\ninstead be replaced by\n\n if (match_cnt == max_candidates) {\n ... /* ? , gave_up_on is now a misnomer */\n break;\n }\n\nThen as a further DWIM aid, wherever the initialization logic is could\nbe updated so that, after expanding all the --match= wildcards, if the\nnumber of tags is less than max_candidates, automatically lower\nmax_candidates to that number (which in the setlocalversion case will\nalways be 1 because we're not actually passing a wildcard).\n\nOr, we could explicitly on the kernel side pass that --candidates=1, but\nyes, I agree it looks like a bug that the loop requires encountering +1\ntag to hit that break;.\n\nRasmus\n"},{"id":"506382","messageId":"20241031114210.GA593548@coredump.intra.peff.net","threadId":"62431","inReplyTo":"87bjz0k17c.fsf@prevas.dk","subject":"Re: [PATCH] setlocalversion: Add workaround for \"git describe\" performance issue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-31T11:42:10Z","receivedAt":"2024-10-31T11:42:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 31, 2024 at 11:37:27AM +0100, Rasmus Villemoes wrote:\n\n> and that \"gave up\" commit is v4.18-rc4, the eleventh commit\n> encountered. That also explains why you have to add a \"dummy\" second\n> --match to make --candidates=1 have the expected behaviour.\n> \n> Perhaps the logic should instead be that as soon as match_cnt hits\n> max_candidates (i.e. all the tags we're going to consider have actually\n> been visited), we break out. That is, the last \"else\" above should\n> instead be replaced by\n> \n> if (match_cnt == max_candidates) {\n> ... /* ? , gave_up_on is now a misnomer */\n> break;\n> }\n\nYes, I agree that is the right direction. Replacing the \"else\" entirely\nfeels a little weird, because it is part of the:\n\n if (!tags && !all && n->prio < 2)\n\t...\n else if (match_cnt < max_candidates)\n\t...\n else\n\t...\n\nSo we'd now run that check even if we triggered the first block. But I\ndon't think it should matter in practice. We only increment match_cnt in\nthe else-if here. So the \"else\" block could go away, and the check for\ngiving up could go inside the else-if.\n\nIt does seem like gave_up_on is now pointless, but I'm not sure I\nunderstand all of the code here. I assumed that it was only used to\nreport \"this is where we gave up\", and to give you the extra bit of\ninformation that there _were_ other candidates that we omitted (and not\njust exactly max_candidates). Of course we don't show that without\n--debug. So it seems silly to spend a bunch of extra CPU for that.\n\nBut the plot thickens.\n\nWhat I was going to suggest is that if we wanted to retain that one bit\nof information, what we could do instead is: independent of\nmax_candidates, see if we've found all of the possible names we expanded\nfrom --match. Then max_candidates would work as it does now, but we'd\navoid fruitlessly searching when there are no more names to find.\n\nCounting the number of expanded names is a little weird. We use them to\nannotate the commits, but of course multiple names can point to a single\ncommit, and there's a priority override system. I think the final number\nwe can find is the number of entries in the \"names\" hash.\n\nSo I expected this to work:\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 7330a77b38..70a11072de 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -380,6 +380,9 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\t\tc->object.flags |= t->flag_within;\n \t\t\t\tif (n->prio == 2)\n \t\t\t\t\tannotated_cnt++;\n+\n+\t\t\t\tif (match_cnt == hashmap_get_size(&names))\n+\t\t\t\t\tbreak;\n \t\t\t}\n \t\t\telse {\n \t\t\t\tgave_up_on = c;\n\nbut it's still slow! If we set \"gave_up_on = c\", then it gets fast. I'm\nnot sure why that is. Later we do:\n\n if (gave_up_on) {\n commit_list_insert_by_date(gave_up_on, &list);\n seen_commits--;\n }\n seen_commits += finish_depth_computation(&list, &all_matches[0]);\n\nbut I don't at all understand why adding gave_up_on lets that finish\nsooner. So I'm worried we're missing something about how it is used.\n\nOne hack is to just, like the max_candidates case, let us look at one\n_more_ commit before bailing. Like this:\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 7330a77b38..177c8232f6 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -365,6 +365,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\tstruct commit_list *parents = c->parents;\n \t\tstruct commit_name **slot;\n \n+\t\tif (match_cnt == hashmap_get_size(&names)) {\n+\t\t\tgave_up_on = c;\n+\t\t\tbreak;\n+\t\t}\n+\n \t\tseen_commits++;\n \t\tslot = commit_names_peek(&commit_names, c);\n \t\tn = slot ? *slot : NULL;\n\n\nThat works, but I have a feeling that figured out what the heck is going\non with gave_up_on might produce a more elegant solution.\n\n> Then as a further DWIM aid, wherever the initialization logic is could\n> be updated so that, after expanding all the --match= wildcards, if the\n> number of tags is less than max_candidates, automatically lower\n> max_candidates to that number (which in the setlocalversion case will\n> always be 1 because we're not actually passing a wildcard).\n\nYeah, I had the same thought (though if we do a separate hashmap check\nas above, it wouldn't be needed).\n\n-Peff\n"},{"id":"506383","messageId":"CAK7LNAT6VbaT=_v5_qMp3-jw5CWui=ZXyiAb2dP20p1tU0JpyA@mail.gmail.com","threadId":"62431","inReplyTo":"87bjz0k17c.fsf@prevas.dk","subject":"Re: [PATCH] setlocalversion: Add workaround for \"git describe\" performance issue","fromName":"Masahiro Yamada","fromEmail":"masahiroy@kernel.org","sentAt":"2024-10-31T11:43:56Z","receivedAt":"2024-10-31T11:44:34Z","isPatch":true,"sender":{"key":"masahiroy@kernel.org","avatar":"https://gravatar.com/avatar/de07e07e05be0542e420cb9b79a723c58893c54989cddfee4a69e05e5dac4a9f?d=mp&s=160"},"body":"On Thu, Oct 31, 2024 at 11:37 AM Rasmus Villemoes wrote:\n>\n> On Wed, Oct 30 2024, Josh Poimboeuf wrote:\n>\n> > If HEAD isn't associated with an annotated tag, a bug (or feature?) in\n> > \"git describe --match\" causes it to search every commit in the entire\n> > repository looking for additional match candidates. Instead of it\n> > taking a fraction of a second, it adds 10-15 seconds to the beginning of\n> > every kernel build.\n> >\n> > Fix it by adding an additional dummy match which is slightly further\n> > away from the most recent one, along with setting the max candidate\n> > count to 1 (not 2, apparently another bug).\n> >\n>\n> cc += git list\n>\n> Hm, I tried looking at the git describe source code, and while I can't\n> claim I understand it very well, I think the main problem is around\n> this part:\n>\n> if (!tags && !all && n->prio < 2) {\n> unannotated_cnt++;\n> } else if (match_cnt < max_candidates) {\n> struct possible_tag *t = &all_matches[match_cnt++];\n> t->name = n;\n> t->depth = seen_commits - 1;\n> t->flag_within = 1u << match_cnt;\n> t->found_order = match_cnt;\n> c->object.flags |= t->flag_within;\n> if (n->prio == 2)\n> annotated_cnt++;\n> }\n> else {\n> gave_up_on = c;\n> break;\n> }\n>\n> So in the case where one doesn't pass any --match, we get something like\n>\n> git describe --debug 5f78aec0d7e9\n> describe 5f78aec0d7e9\n> No exact match on refs or tags, searching to describe\n> annotated 243 v4.19-rc5\n> annotated 485 v4.19-rc4\n> annotated 814 v4.19-rc3\n> annotated 1124 v4.19-rc2\n> annotated 1391 v4.19-rc1\n> annotated 10546 v4.18\n> annotated 10611 v4.18-rc8\n> annotated 10819 v4.18-rc7\n> annotated 11029 v4.18-rc6\n> annotated 11299 v4.18-rc5\n> traversed 11400 commits\n> more than 10 tags found; listed 10 most recent\n> gave up search at 1e4b044d22517cae7047c99038abb444423243ca\n> v4.19-rc5-243-g5f78aec0d7e9\n>\n> and that \"gave up\" commit is v4.18-rc4, the eleventh commit\n> encountered. That also explains why you have to add a \"dummy\" second\n> --match to make --candidates=1 have the expected behaviour.\n>\n> Perhaps the logic should instead be that as soon as match_cnt hits\n> max_candidates (i.e. all the tags we're going to consider have actually\n> been visited), we break out. That is, the last \"else\" above should\n> instead be replaced by\n>\n> if (match_cnt == max_candidates) {\n> ... /* ? , gave_up_on is now a misnomer */\n> break;\n> }\n>\n> Then as a further DWIM aid, wherever the initialization logic is could\n> be updated so that, after expanding all the --match= wildcards, if the\n> number of tags is less than max_candidates, automatically lower\n> max_candidates to that number (which in the setlocalversion case will\n> always be 1 because we're not actually passing a wildcard).\n>\n> Or, we could explicitly on the kernel side pass that --candidates=1, but\n> yes, I agree it looks like a bug that the loop requires encountering +1\n> tag to hit that break;.\n>\n> Rasmus\n>\n\nI still do not understand the logic either.\n\ngit traverses all the way back to\nd8470b7c13e11c18cf14a7e3180f0b00e715e4f0.\n\n\n\n$ git describe --match=v6.12-rc5 --debug c1e939a21eb1\ndescribe c1e939a21eb1\nNo exact match on refs or tags, searching to describe\nfinished search at d8470b7c13e11c18cf14a7e3180f0b00e715e4f0\n annotated 44 v6.12-rc5\ntraversed 1310005 commits\nv6.12-rc5-44-gc1e939a21eb1\n\n\n\nOr, more simply,\n\n\n$ git describe --match=v6.12-rc5 --debug e42b1a9a2557\ndescribe e42b1a9a2557\nNo exact match on refs or tags, searching to describe\nfinished search at d8470b7c13e11c18cf14a7e3180f0b00e715e4f0\n annotated 5 v6.12-rc5\ntraversed 1309966 commits\nv6.12-rc5-5-ge42b1a9a2557\n\n\n\n\ne42b1a9a2557 merges v6.12-rc5 and 25f00a13dccf.\n\nThe latter is obviously, v6.12-rc2 + 4 commits.\nv6.12-rc2 is an ancestor of v6.12-rc5.\n\nI do not understand why git traverses 1.3 million commits.\n\n\n\n--\nBest Regards\n\nMasahiro Yamada\n"},{"id":"506387","messageId":"20241031122456.GB593548@coredump.intra.peff.net","threadId":"62431","inReplyTo":"20241031114210.GA593548@coredump.intra.peff.net","subject":"Re: [PATCH] setlocalversion: Add workaround for \"git describe\" performance issue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-31T12:24:56Z","receivedAt":"2024-10-31T12:24:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 31, 2024 at 07:42:10AM -0400, Jeff King wrote:\n\n> That works, but I have a feeling that figured out what the heck is going\n> on with gave_up_on might produce a more elegant solution.\n\nOK, I think I might have made some sense of this.\n\nIn finish_depth_computation(), we traverse down \"list\" forever, passing\nflags up to our parents, until we find a commit that is marked with the\nsame \"within\" flag as our candidate. And then if everything left has\nthat same \"within\" flag set, we can bail.\n\nSo I _think_ the point is to basically count up what we'd get from this\ntraversal:\n\n $tag..$commit\n\nwhere \"$tag\" is the candidate tag we found, and \"$commit\" is what we're\ntrying to describe (so imagine \"git describe --match=$tag $commit\").\n\nWe can't just use the depth we found while traversing down to $tag,\nbecause there might be side branches we need to count up, too. And we\ndon't start a new traversal, because we'd be repeating the bits we\nalready went over when finding $tag in the first place.\n\nAnd we feed that \"list\" from the original traversal state. So if we\nbreak out of the traversal early but don't set gave_up_on, then we have\nnothing in that state that holds the \"within\" flag. So we just walk all\nof the commits down to the root, because nobody is propagating the flag\nto them.\n\nWe have to feed at least one commit with the \"within\" flag into the\ntraversal so that it can let us end things. But I don't think it really\nmatters if that commit is the one we found, or if it's a parent of one\nthat we happened to pass \"within\" bits down to.\n\nSo I think we can just set \"gave_up_on\" to the final element we found\n(whether from max_candidates or from finding every possible name). I.e.,\nwhat I showed earlier, or what you were proposing.\n\n\nI was also a bit puzzled how this works when there are multiple tags.\nWe feed only one \"best\" candidate to finish_depth_computation(), but\ngave_up_on does not necessarily have its flag set. But I think that case\nthe point is that _some_ commit in the list does, and we literally add\nevery commit to that list.\n\nI'm actually a bit skeptical that any of this is faster than simply\nstarting over a new traversal of $tag..$commit to find the depth, since\nwe are considering each commit anew. And there's a bunch of accidentally\nquadratic bits of finish_depth_computation(). But frankly I'm somewhat\nafraid to touch any of this more than necessary.\n\n-Peff\n"},{"id":"506389","messageId":"20241031144351.GA1720940@coredump.intra.peff.net","threadId":"62431","inReplyTo":"20241031122456.GB593548@coredump.intra.peff.net","subject":"Re: [PATCH] setlocalversion: Add workaround for \"git describe\" performance issue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-31T14:43:51Z","receivedAt":"2024-10-31T14:43:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 31, 2024 at 08:24:56AM -0400, Jeff King wrote:\n\n> We have to feed at least one commit with the \"within\" flag into the\n> traversal so that it can let us end things. But I don't think it really\n> matters if that commit is the one we found, or if it's a parent of one\n> that we happened to pass \"within\" bits down to.\n> \n> So I think we can just set \"gave_up_on\" to the final element we found\n> (whether from max_candidates or from finding every possible name). I.e.,\n> what I showed earlier, or what you were proposing.\n\nHmph. So I don't think this is quite true, but now I'm puzzled again.\n\nIt is accurate to say that we must make sure _some_ commit with the\nthose flag bits set remains in \"list\". And I don't think it matters if\nit's the candidate we found, or its parent.\n\nBut there's other stuff happening in that loop, after we process that\nmax candidate (where we'd proposed to break) but before we hit the next\npossible candidate. Stuff like adding onto the depth of the other\ncandidates. Josh's example doesn't show that because it only has one\ncandidate, but I could imagine a case where it does matter (though I\ndidn't construct one).\n\nSo I'd have thought that this:\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 7330a77b38..b0f645c41d 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -366,6 +366,12 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\tstruct commit_name **slot;\n \n \t\tseen_commits++;\n+\n+\t\tif (match_cnt == max_candidates) {\n+\t\t\tgave_up_on = c;\n+\t\t\tbreak;\n+\t\t}\n+\n \t\tslot = commit_names_peek(&commit_names, c);\n \t\tn = slot ? *slot : NULL;\n \t\tif (n) {\n@@ -381,10 +387,6 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\t\tif (n->prio == 2)\n \t\t\t\t\tannotated_cnt++;\n \t\t\t}\n-\t\t\telse {\n-\t\t\t\tgave_up_on = c;\n-\t\t\t\tbreak;\n-\t\t\t}\n \t\t}\n \t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n \t\t\tstruct possible_tag *t = &all_matches[cur_match];\n\nwould do it, by just finishing out the loop iteration and bailing on the\nnext commit. After all, that commit _could_ be a candidate itself. But\nit causes a test in t6120 to fail. We have a disjoint history like this:\n\n B\n o\n \\\n o-----o---o----x\n A\n\nand we expect that \"x\" is described as \"A-3\" (because we are including\nthe disjoint B). But after the patch above and with --candidates=2\n(since there are only two tags and part of our goal is to limit\ncandidates to the number of tags), we find \"B-4\". Which is worse (at\nleast by some metrics).\n\nI think this comes from 30b1c7ad9d (describe: don't abort too early when\nsearching tags, 2020-02-26). And given the problem description there, I\ncan see how quitting early in a disjoint history will give you worse\nanswers. But the patch above is triggering a case that already _could_\ntrigger.\n\nSo it feels like 30b1c7ad9d is incomplete. Without any patches, if I\nlimit it to --candidates=2 but make A^ a tag, then it gets the same\nwrong answer (for the exact same reason). And I don't see a way to make\nit correct without losing the ability to break out of the traversal\nearly when we hit max_candidates (which is obviously a very important\noptimization in general). But maybe I'm missing something.\n\nI do think my patch above is not introducing a new problem that wasn't\nalready there. It's just that the toy repo, having so few tags, means\nany logic to reduce max_candidates will trigger there.\n\n+cc the author of 30b1c7ad9d for any wisdom\n\n-Peff\n"},{"id":"506439","messageId":"8734kbjlrq.fsf@prevas.dk","threadId":"62431","inReplyTo":"20241031122456.GB593548@coredump.intra.peff.net","subject":"Re: [PATCH] setlocalversion: Add workaround for \"git describe\" performance issue","fromName":"Rasmus Villemoes","fromEmail":"ravi@prevas.dk","sentAt":"2024-11-01T10:23:05Z","receivedAt":"2024-11-01T10:23:03Z","isPatch":true,"sender":{"key":"ravi@prevas.dk","avatar":null},"body":"On Thu, Oct 31 2024, Jeff King wrote:\n\n> On Thu, Oct 31, 2024 at 07:42:10AM -0400, Jeff King wrote:\n>\n>> That works, but I have a feeling that figured out what the heck is going\n>> on with gave_up_on might produce a more elegant solution.\n>\n> OK, I think I might have made some sense of this.\n>\n> In finish_depth_computation(), we traverse down \"list\" forever, passing\n> flags up to our parents, until we find a commit that is marked with the\n> same \"within\" flag as our candidate. And then if everything left has\n> that same \"within\" flag set, we can bail.\n>\n> So I _think_ the point is to basically count up what we'd get from this\n> traversal:\n>\n> $tag..$commit\n>\n> where \"$tag\" is the candidate tag we found, and \"$commit\" is what we're\n> trying to describe (so imagine \"git describe --match=$tag $commit\").\n\nYeah, so this is really just what the setlocalversion script wants to\nknow. For a few diffent possible values of $tag (in most cases just 1),\nwe ask: Is $tag an annotated tag? Is it an ancestor of HEAD? And if so,\nhow many commits are in $tag..HEAD.\n\nPerhaps we could on the kernel side replace the \"git describe --match\"\ncalls with a helper, something like this (needs a lot of polishing):\n\n===\n# Produce output similar to what \"git describe --match=$tag 2>\n# /dev/null\" would. It doesn't have to match exactly as the caller is\n# only interested in whether $tag == HEAD, and if not, the number\n# between the tag and the short sha1.\ndescribe()\n{\n # Is $tag an annotated tag? Could/should probably be written using\n # some plumbing instead of git describe, but with --exact-match,\n # we avoid the walk-to-the-start-of-history behaviour, so fine for\n # this demo.\n git describe --exact-match --match=$tag $tag >/dev/null 2>/dev/null || return 1\n\n # Can it be used to describe HEAD, i.e. is it an ancestor of HEAD?\n git merge-base --is-ancestor $tag HEAD || return 1\n\n # Find the number that \"git describe\" would append.\n count=$(git rev-list --count $tag..HEAD)\n if [ $count -eq 0 ] ; then\n echo \"$tag\"\n else\n echo \"$tag-$count-$head\"\n fi\n}\n===\n\nBut if we go this route, we should probably rework the logic\nsomewhat. There's no point getting the count ourselves, stuffing that\ninto a string, and then splitting that string with awk to %05d format\nthe count.\n\nI also don't know if either the --is-ancestor or the rev-list count\ncould end up doing the same walk-all-commits we're trying to avoid.\n\nRasmus\n"},{"id":"506440","messageId":"20241101113910.GA2301440@coredump.intra.peff.net","threadId":"62431","inReplyTo":"8734kbjlrq.fsf@prevas.dk","subject":"Re: [PATCH] setlocalversion: Add workaround for \"git describe\" performance issue","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-11-01T11:39:10Z","receivedAt":"2024-11-01T11:39:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 01, 2024 at 11:23:05AM +0100, Rasmus Villemoes wrote:\n\n> Perhaps we could on the kernel side replace the \"git describe --match\"\n> calls with a helper, something like this (needs a lot of polishing):\n\nYeah, if you are describing off of a single tag, it may just be easier\nto query things about the tag directly. Though I do still think\ngit-describe should be faster here. I'm still pondering what to do about\nthe disjoint history tests, but otherwise have a polished series to\nsend.\n\n> ===\n> # Produce output similar to what \"git describe --match=$tag 2>\n> # /dev/null\" would. It doesn't have to match exactly as the caller is\n> # only interested in whether $tag == HEAD, and if not, the number\n> # between the tag and the short sha1.\n> describe()\n> {\n> # Is $tag an annotated tag? Could/should probably be written using\n> # some plumbing instead of git describe, but with --exact-match,\n> # we avoid the walk-to-the-start-of-history behaviour, so fine for\n> # this demo.\n> git describe --exact-match --match=$tag $tag >/dev/null 2>/dev/null || return 1\n\nProbably \"git cat-file -t $tag\" is the simplest way to see if it points\nto a tag.\n\n> # Can it be used to describe HEAD, i.e. is it an ancestor of HEAD?\n> git merge-base --is-ancestor $tag HEAD || return 1\n> \n> # Find the number that \"git describe\" would append.\n> count=$(git rev-list --count $tag..HEAD)\n> if [ $count -eq 0 ] ; then\n> echo \"$tag\"\n> else\n> echo \"$tag-$count-$head\"\n> fi\n\nYou can query both of these at once with:\n\n git rev-list --count --left-right $tag...HEAD\n\nThat will traverse down to the merge base and give you two counts. If\nthe first one is 0, then $tag is a direct ancestor. And the second one\nis the count of what's in HEAD.\n\nAt first glance, it seems like you'd waste time counting the HEAD side\nwhen the --is-ancestor check could have rejected the tag earlier. But in\npractice I think the time will always be dominated by walking down to\nthe merge base in all commands.\n\n> I also don't know if either the --is-ancestor or the rev-list count\n> could end up doing the same walk-all-commits we're trying to avoid.\n\nIt shouldn't. In all of those cases we'll generally walk breadth-first\ndown to the merge base. They're also operations that can take advantage\nof other optimizations that git-describe never learned about. E.g.,\ngeneration numbers in the commit graph.\n\nWe can even do fast --count with reachability bitmaps, though I wouldn't\nexpect most dev repos to have bitmaps built. Also, it looks like\n\"--left-right --count\" does not support bitmaps. IMHO that is a bug. ;)\n\n-Peff\n"},{"id":"506525","messageId":"CAEQVFRFWT02QTL7PTf84p6AAferijHx8L_Tu6ON1H7U=iEdb3A@mail.gmail.com","threadId":"62431","inReplyTo":"20241031144351.GA1720940@coredump.intra.peff.net","subject":"Re: [PATCH] setlocalversion: Add workaround for \"git describe\" performance issue","fromName":"Benno Evers","fromEmail":"benno.martin.evers@gmail.com","sentAt":"2024-11-04T12:37:27Z","receivedAt":"2024-11-04T12:37:41Z","isPatch":true,"sender":{"key":"benno.martin.evers@gmail.com","avatar":null},"body":"Hi,\n\nI'm afraid I can't offer much wisdom, but a few thoughts:\n\nIn the testcase, the difference between A-3 and B-4 looks very\nacademic, but on a real repo the results are more obviously wrong. For\nexample, if I put the test setup on top of the current git repo:\n\n benno@bourbaki:~/src/git/tmp-test$ git describe HEAD\n A-3-ga53f69dfb5\n benno@bourbaki:~/src/git/tmp-test$ git describe --candidates=2 HEAD\n B-75205-ga53f69dfb5\n\nWhen writing the patch I thought that it might be a good idea to\nchange the definition of `describe` to favor the tag with the shortest\nfirst-parent distance to the described tag and print A-2 in the test\nscenario, to me that seems the most intuitive description. But that's\na change in behavior, and it's not even clear that most people would\nagree A-2 is better, so I discarded the idea.\n\nOther than that, the only way I can see to implement the behavior\nexactly as described would be add the same condition when breaking for\nreaching the max number of candidates, ie. to stop adding new\ncandidates but to delay the break from the loop until all disjoint\npaths are unified. No idea how much of a performance hit that would be\nin practice, I guess it depends on average branch lengths.\n\nBest regards,\nBenno\n\nAm Do., 31. Okt. 2024 um 15:43 Uhr schrieb Jeff King :\n>\n> On Thu, Oct 31, 2024 at 08:24:56AM -0400, Jeff King wrote:\n>\n> > We have to feed at least one commit with the \"within\" flag into the\n> > traversal so that it can let us end things. But I don't think it really\n> > matters if that commit is the one we found, or if it's a parent of one\n> > that we happened to pass \"within\" bits down to.\n> >\n> > So I think we can just set \"gave_up_on\" to the final element we found\n> > (whether from max_candidates or from finding every possible name). I.e.,\n> > what I showed earlier, or what you were proposing.\n>\n> Hmph. So I don't think this is quite true, but now I'm puzzled again.\n>\n> It is accurate to say that we must make sure _some_ commit with the\n> those flag bits set remains in \"list\". And I don't think it matters if\n> it's the candidate we found, or its parent.\n>\n> But there's other stuff happening in that loop, after we process that\n> max candidate (where we'd proposed to break) but before we hit the next\n> possible candidate. Stuff like adding onto the depth of the other\n> candidates. Josh's example doesn't show that because it only has one\n> candidate, but I could imagine a case where it does matter (though I\n> didn't construct one).\n>\n> So I'd have thought that this:\n>\n> diff --git a/builtin/describe.c b/builtin/describe.c\n> index 7330a77b38..b0f645c41d 100644\n> --- a/builtin/describe.c\n> +++ b/builtin/describe.c\n> @@ -366,6 +366,12 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n> struct commit_name **slot;\n>\n> seen_commits++;\n> +\n> + if (match_cnt == max_candidates) {\n> + gave_up_on = c;\n> + break;\n> + }\n> +\n> slot = commit_names_peek(&commit_names, c);\n> n = slot ? *slot : NULL;\n> if (n) {\n> @@ -381,10 +387,6 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n> if (n->prio == 2)\n> annotated_cnt++;\n> }\n> - else {\n> - gave_up_on = c;\n> - break;\n> - }\n> }\n> for (cur_match = 0; cur_match < match_cnt; cur_match++) {\n> struct possible_tag *t = &all_matches[cur_match];\n>\n> would do it, by just finishing out the loop iteration and bailing on the\n> next commit. After all, that commit _could_ be a candidate itself. But\n> it causes a test in t6120 to fail. We have a disjoint history like this:\n>\n> B\n> o\n> \\\n> o-----o---o----x\n> A\n>\n> and we expect that \"x\" is described as \"A-3\" (because we are including\n> the disjoint B). But after the patch above and with --candidates=2\n> (since there are only two tags and part of our goal is to limit\n> candidates to the number of tags), we find \"B-4\". Which is worse (at\n> least by some metrics).\n>\n> I think this comes from 30b1c7ad9d (describe: don't abort too early when\n> searching tags, 2020-02-26). And given the problem description there, I\n> can see how quitting early in a disjoint history will give you worse\n> answers. But the patch above is triggering a case that already _could_\n> trigger.\n>\n> So it feels like 30b1c7ad9d is incomplete. Without any patches, if I\n> limit it to --candidates=2 but make A^ a tag, then it gets the same\n> wrong answer (for the exact same reason). And I don't see a way to make\n> it correct without losing the ability to break out of the traversal\n> early when we hit max_candidates (which is obviously a very important\n> optimization in general). But maybe I'm missing something.\n>\n> I do think my patch above is not introducing a new problem that wasn't\n> already there. It's just that the toy repo, having so few tags, means\n> any logic to reduce max_candidates will trigger there.\n>\n> +cc the author of 30b1c7ad9d for any wisdom\n>\n> -Peff\n"},{"id":"506751","messageId":"20241106192236.GC880133@coredump.intra.peff.net","threadId":"62431","inReplyTo":"CAEQVFRFWT02QTL7PTf84p6AAferijHx8L_Tu6ON1H7U=iEdb3A@mail.gmail.com","subject":"[PATCH 0/4] perf improvements for git-describe with few tags","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-11-06T19:22:36Z","receivedAt":"2024-11-06T19:22:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 04, 2024 at 01:37:27PM +0100, Benno Evers wrote:\n\n> I'm afraid I can't offer much wisdom, but a few thoughts:\n\nThank you. Between this response and a bit of pondering over the last\nfew days, I think I have a firm understanding of the issue and possible\npaths forward.\n\nSo here's the series I came up with, which starts by adjusting the tests\nto be resilient to the later changes, but also to show the existing\nfailure mode.\n\nAnd then the rest of the patches add the performance improvements we've\nbeen discussing in the thread.\n\nI'll drop the kernel lists from the cc since I think this has gotten\nwell off topic there.\n\n [1/4]: t6120: demonstrate weakness in disjoint-root handling\n [2/4]: t/perf: add tests for git-describe\n [3/4]: describe: stop digging for max_candidates+1\n [4/4]: describe: stop traversing when we run out of names\n\n builtin/describe.c | 17 ++++++++++-------\n t/perf/p6100-describe.sh | 30 ++++++++++++++++++++++++++++++\n t/t6120-describe.sh | 15 ++++++++++++---\n 3 files changed, 52 insertions(+), 10 deletions(-)\n create mode 100755 t/perf/p6100-describe.sh\n\n-Peff\n"},{"id":"506752","messageId":"20241106192650.GA912471@coredump.intra.peff.net","threadId":"62431","inReplyTo":"20241106192236.GC880133@coredump.intra.peff.net","subject":"Re: [PATCH 0/4] perf improvements for git-describe with few tags","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-11-06T19:26:50Z","receivedAt":"2024-11-06T19:26:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 06, 2024 at 02:22:37PM -0500, Jeff King wrote:\n\n> So here's the series I came up with, which starts by adjusting the tests\n> to be resilient to the later changes, but also to show the existing\n> failure mode.\n> \n> And then the rest of the patches add the performance improvements we've\n> been discussing in the thread.\n\nOops, I just realized there's a silly error in my patch, but I need to\ngo offline before I can fix it. I'll send patches later today, but I\ndidn't want to leave anybody confused about the delay. :)\n\n-Peff\n"},{"id":"506760","messageId":"20241106211658.GA956383@coredump.intra.peff.net","threadId":"62431","inReplyTo":"20241106192236.GC880133@coredump.intra.peff.net","subject":"[PATCH 1/4] t6120: demonstrate weakness in disjoint-root handling","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-11-06T21:16:58Z","receivedAt":"2024-11-06T21:17:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Commit 30b1c7ad9d (describe: don't abort too early when searching tags,\n2020-02-26) tried to fix a problem that happens when there are disjoint\nhistories: to accurately compare the counts for different tags, we need\nto keep walking the history longer in order to find a common base.\n\nBut its fix misses a case: we may still bail early if we hit the\nmax_candidates limit, producing suboptimal output. You can see this in\naction by adding \"--candidates=2\" to the tests; we'll stop traversing as\nsoon as we see the second tag and will produce the wrong answer. I hit\nthis in practice while trying to teach git-describe not to keep looking\nfor candidates after we've seen all tags in the repo (effectively adding\n--candidates=2, since these toy repos have only two tags each).\n\nThis is probably fixable by continuing to walk after hitting the\nmax-candidates limit, all the way down to a common ancestor of all\ncandidates. But it's not clear in practice what the preformance\nimplications would be (it would depend on how long the branches that\nhold the candidates are).\n\nSo I'm punting on that for now, but I'd like to adjust the tests to be\nmore resilient, and to document the findings. So this patch:\n\n 1. Adds an extra tag at the bottom of history. This shouldn't change\n the output, but does mean we are more resilient to low values of\n --candidates (e.g., if we start reducing it to the total number of\n tags). This is arguably closer to the real world anyway, where\n you're not going to have just 2 tags, but an arbitrarily long\n history going back in time, possibly with multiple irrelevant tags\n in it (I called the new tag \"H\" here for \"history\").\n\n 2. Run the same tests with --candidates=2, which shows that even with\n the current code they can fail if we end the traversal early. That\n leaves a trail for anybody interested in trying to improve the\n behavior.\n\nSigned-off-by: Jeff King \n---\n t/t6120-describe.sh | 14 +++++++++++---\n 1 file changed, 11 insertions(+), 3 deletions(-)\n\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 05ed2510d9..69689d2f36 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -19,13 +19,17 @@ TEST_PASSES_SANITIZE_LEAK=true\n \n check_describe () {\n \tindir= &&\n+\toutcome=success &&\n \twhile test $# != 0\n \tdo\n \t\tcase \"$1\" in\n \t\t-C)\n \t\t\tindir=\"$2\"\n \t\t\tshift\n \t\t\t;;\n+\t\t--expect-failure)\n+\t\t\toutcome=failure\n+\t\t\t;;\n \t\t*)\n \t\t\tbreak\n \t\t\t;;\n@@ -36,7 +40,7 @@ check_describe () {\n \texpect=\"$1\"\n \tshift\n \tdescribe_opts=\"$@\"\n-\ttest_expect_success \"describe $describe_opts\" '\n+\ttest_expect_${outcome} \"describe $describe_opts\" '\n \t\tgit ${indir:+ -C \"$indir\"} describe $describe_opts >raw &&\n \t\tsed -e \"s/-g[0-9a-f]*\\$/-gHASH/\" actual &&\n \t\techo \"$expect\" >expect &&\n@@ -617,7 +621,7 @@ test_expect_success 'name-rev --annotate-stdin works with commitGraph' '\n \n # B\n # o\n-# \\\n+# H \\\n # o-----o---o----x\n # A\n #\n@@ -627,6 +631,7 @@ test_expect_success 'setup: describe commits with disjoint bases' '\n \t\tcd disjoint1 &&\n \n \t\techo o >> file && git add file && git commit -m o &&\n+\t\tgit tag H -a -m H &&\n \t\techo A >> file && git add file && git commit -m A &&\n \t\tgit tag A -a -m A &&\n \t\techo o >> file && git add file && git commit -m o &&\n@@ -639,8 +644,9 @@ test_expect_success 'setup: describe commits with disjoint bases' '\n '\n \n check_describe -C disjoint1 \"A-3-gHASH\" HEAD\n+check_describe -C disjoint1 --expect-failure \"A-3-gHASH\" --candidates=2 HEAD\n \n-# B\n+# H B\n # o---o---o------------.\n # \\\n # o---o---x\n@@ -658,13 +664,15 @@ test_expect_success 'setup: describe commits with disjoint bases 2' '\n \t\tgit checkout --orphan branch &&\n \t\techo o >> file2 && git add file2 && GIT_COMMITTER_DATE=\"2020-01-01 15:00\" git commit -m o &&\n \t\techo o >> file2 && git add file2 && GIT_COMMITTER_DATE=\"2020-01-01 15:01\" git commit -m o &&\n+\t\tgit tag H -a -m H &&\n \t\techo B >> file2 && git add file2 && GIT_COMMITTER_DATE=\"2020-01-01 15:02\" git commit -m B &&\n \t\tgit tag B -a -m B &&\n \t\tgit merge --no-ff --allow-unrelated-histories main -m x\n \t)\n '\n \n check_describe -C disjoint2 \"B-3-gHASH\" HEAD\n+check_describe -C disjoint2 --expect-failure \"B-3-gHASH\" --candidates=2 HEAD\n \n test_expect_success 'setup misleading taggerdates' '\n \tGIT_COMMITTER_DATE=\"2006-12-12 12:31\" git tag -a -m \"another tag\" newer-tag-older-commit unique-file~1\n-- \n2.47.0.441.g1a09955689\n\n"},{"id":"506761","messageId":"20241106211708.GB956383@coredump.intra.peff.net","threadId":"62431","inReplyTo":"20241106192236.GC880133@coredump.intra.peff.net","subject":"[PATCH 2/4] t/perf: add tests for git-describe","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-11-06T21:17:08Z","receivedAt":"2024-11-06T21:17:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We don't have a perf script for git-describe, despite it often being\naccused of slowness. Let's add a few simple tests to start with.\n\nRather than use the existing tags from our test repo, we'll make our own\nso that we have a known quantity and position. We'll add a \"new\" tag\nnear the tip of HEAD, and an \"old\" one that is at the very bottom. And\nthen our tests are:\n\n 1. Describing HEAD naively requires walking all the way down to the\n old tag as we collect candidates. This gives us a baseline for what\n \"slow\" looks like.\n\n 2. Doing the same with --candidates=1 can potentially be fast, because\n we can quie after finding \"new\". But we don't, and it's also slow.\n\n 3. Likewise we should be able to quit when there are no more tags to\n find. This can happen naturally if a repo has few tags, but also if\n you restrict the set of tags with --match.\n\nHere are the results running against linux.git. Note that I have a\ncommit-graph built for the repo, so \"slow\" here is ~700ms. Without a\ncommit graph it's more like 9s!\n\n Test HEAD\n --------------------------------------------------------------\n 6100.2: describe HEAD 0.70(0.66+0.04)\n 6100.3: describe HEAD with one max candidate 0.70(0.66+0.04)\n 6100.4: describe HEAD with one tag 0.70(0.64+0.06)\n\nSigned-off-by: Jeff King \n---\n t/perf/p6100-describe.sh | 30 ++++++++++++++++++++++++++++++\n 1 file changed, 30 insertions(+)\n create mode 100755 t/perf/p6100-describe.sh\n\ndiff --git a/t/perf/p6100-describe.sh b/t/perf/p6100-describe.sh\nnew file mode 100755\nindex 0000000000..069f91ce49\n--- /dev/null\n+++ b/t/perf/p6100-describe.sh\n@@ -0,0 +1,30 @@\n+#!/bin/sh\n+\n+test_description='performance of git-describe'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+# clear out old tags and give us a known state\n+test_expect_success 'set up tags' '\n+\tgit for-each-ref --format=\"delete %(refname)\" refs/tags >to-delete &&\n+\tgit update-ref --stdin \nHelped-by: Rasmus Villemoes \nSigned-off-by: Jeff King \n---\n builtin/describe.c | 15 ++++++++-------\n 1 file changed, 8 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 7330a77b38..69f2d942be 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -366,6 +366,12 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\tstruct commit_name **slot;\n \n \t\tseen_commits++;\n+\n+\t\tif (match_cnt == max_candidates) {\n+\t\t\tgave_up_on = c;\n+\t\t\tbreak;\n+\t\t}\n+\n \t\tslot = commit_names_peek(&commit_names, c);\n \t\tn = slot ? *slot : NULL;\n \t\tif (n) {\n@@ -381,10 +387,6 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\t\tif (n->prio == 2)\n \t\t\t\t\tannotated_cnt++;\n \t\t\t}\n-\t\t\telse {\n-\t\t\t\tgave_up_on = c;\n-\t\t\t\tbreak;\n-\t\t\t}\n \t\t}\n \t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n \t\t\tstruct possible_tag *t = &all_matches[cur_match];\n@@ -470,9 +472,8 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\tfprintf(stderr, _(\"traversed %lu commits\\n\"), seen_commits);\n \t\tif (gave_up_on) {\n \t\t\tfprintf(stderr,\n-\t\t\t\t_(\"more than %i tags found; listed %i most recent\\n\"\n-\t\t\t\t\"gave up search at %s\\n\"),\n-\t\t\t\tmax_candidates, max_candidates,\n+\t\t\t\t_(\"found %i tags; gave up search at %s\\n\"),\n+\t\t\t\tmax_candidates,\n \t\t\t\toid_to_hex(&gave_up_on->object.oid));\n \t\t}\n \t}\n-- \n2.47.0.441.g1a09955689\n\n"},{"id":"506763","messageId":"20241106211717.GD956383@coredump.intra.peff.net","threadId":"62431","inReplyTo":"20241106192236.GC880133@coredump.intra.peff.net","subject":"[PATCH 4/4] describe: stop traversing when we run out of names","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-11-06T21:17:17Z","receivedAt":"2024-11-06T21:17:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When trying to describe a commit, we'll traverse from the commit,\ncollecting candidate tags that point to its ancestors. But once we've\nseen all of the tags in the repo, there's no point in traversing\nfurther. There's nothing left to find!\n\nFor a default \"git describe\", this isn't usually a big problem. In a\nlarge repo you'll probably have multiple tags, so we'll eventually find\n10 candidates (the default for max_candidates) and stop there. And in a\nsmall repo, it's quick to traverse to the root.\n\nBut you can imagine a large repo with few tags. Or, as we saw in a real\nworld case, explicitly limiting the set of matches like this (on\nlinux.git):\n\n git describe --match=v6.12-rc4 HEAD\n\nwhich goes all the way to the root before realizing that no, there are\nno other tags under consideration besides the one we fed via --match.\nIf we add in \"--candidates=1\" there, it's much faster (at least as of\nthe previous commit).\n\nBut we should be able to speed this up without the user asking for it.\nAfter expanding all matching tags, we know the total number of names. We\ncould just stop the traversal there, but as hinted at above we already\nhave a mechanism for doing that: the max_candidate limit. So we can just\nreduce that limit to match the number of possible candidates.\n\nOur p6100 test shows this off:\n\n Test HEAD^ HEAD\n ---------------------------------------------------------------------------------------\n 6100.2: describe HEAD 0.71(0.65+0.06) 0.72(0.68+0.04) +1.4%\n 6100.3: describe HEAD with one max candidate 0.01(0.00+0.00) 0.01(0.00+0.00) +0.0%\n 6100.4: describe HEAD with one tag 0.72(0.66+0.05) 0.01(0.00+0.00) -98.6%\n\nNow we are fast automatically, just as if --candidates=1 were supplied\nby the user.\n\nReported-by: Josh Poimboeuf \nHelped-by: Rasmus Villemoes \nSigned-off-by: Jeff King \n---\n builtin/describe.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 69f2d942be..8ec3be87df 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -667,6 +667,8 @@ int cmd_describe(int argc,\n \t\t\t NULL);\n \tif (!hashmap_get_size(&names) && !always)\n \t\tdie(_(\"No names found, cannot describe anything.\"));\n+\tif (hashmap_get_size(&names) < max_candidates)\n+\t\tmax_candidates = hashmap_get_size(&names);\n \n \tif (argc == 0) {\n \t\tif (broken) {\n-- \n2.47.0.441.g1a09955689\n"},{"id":"508135","messageId":"xmqqldx61t65.fsf@gitster.g","threadId":"62431","inReplyTo":"20241106192236.GC880133@coredump.intra.peff.net","subject":"Re: [PATCH 0/4] perf improvements for git-describe with few tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-11-26T05:05:22Z","receivedAt":"2024-11-26T05:05:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> So here's the series I came up with, which starts by adjusting the tests\n> to be resilient to the later changes, but also to show the existing\n> failure mode.\n>\n> And then the rest of the patches add the performance improvements we've\n> been discussing in the thread.\n\nSo, this did not get any comments, but I had a time to read it over,\nand did not find anything suspicious in there.\n\nLet me mark it for 'next', this time for real, in the What's cooking\ndraft I have.\n\nThanks.\n"},{"id":"508629","messageId":"fxbv4ihz4sgdfwtq4vkadntank2lzwkt6abgipuojhumjmuxjs@fegutv3kcamo","threadId":"62431","inReplyTo":"xmqqldx61t65.fsf@gitster.g","subject":"Re: [PATCH 0/4] perf improvements for git-describe with few tags","fromName":"Josh Steadmon","fromEmail":"steadmon@google.com","sentAt":"2024-12-04T23:04:59Z","receivedAt":"2024-12-04T23:05:06Z","isPatch":true,"sender":{"key":"steadmon@google.com","avatar":"https://avatars.githubusercontent.com/u/2654920?v=4"},"body":"On 2024.11.26 14:05, Junio C Hamano wrote:\n> Jeff King writes:\n> \n> > So here's the series I came up with, which starts by adjusting the tests\n> > to be resilient to the later changes, but also to show the existing\n> > failure mode.\n> >\n> > And then the rest of the patches add the performance improvements we've\n> > been discussing in the thread.\n> \n> So, this did not get any comments, but I had a time to read it over,\n> and did not find anything suspicious in there.\n> \n> Let me mark it for 'next', this time for real, in the What's cooking\n> draft I have.\n> \n> Thanks.\n> \n\nThis breaks the case of `git describe --always $SOME_HASH` (we hit the\ndie at builtin/describe.c:340) when there are no tags in the repo. I can\nsend a test case and a small fix shortly.\n"},{"id":"508630","messageId":"00270315b83b585f7d62ad1204ca1df93a668791.1733354035.git.steadmon@google.com","threadId":"62431","inReplyTo":"20241106211717.GD956383@coredump.intra.peff.net","subject":"[PATCH] fixup! describe: stop traversing when we run out of names","fromName":"Josh Steadmon","fromEmail":"steadmon@google.com","sentAt":"2024-12-04T23:15:42Z","receivedAt":"2024-12-04T23:15:45Z","isPatch":true,"sender":{"key":"steadmon@google.com","avatar":"https://avatars.githubusercontent.com/u/2654920?v=4"},"body":"Don't exit when we run out of names if we also set --always\n\nSigned-off-by: Josh Steadmon \n---\n builtin/describe.c | 2 +-\n t/t6120-describe.sh | 14 ++++++++++++++\n 2 files changed, 15 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 8ec3be87df..065c1bde6e 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -336,7 +336,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\treturn;\n \t}\n \n-\tif (!max_candidates)\n+\tif (!max_candidates && !always)\n \t\tdie(_(\"no tag exactly matches '%s'\"), oid_to_hex(&cmit->object.oid));\n \tif (debug)\n \t\tfprintf(stderr, _(\"No exact match on refs or tags, searching to describe\\n\"));\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 5633b11d01..9aebf09d3d 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -715,4 +715,18 @@ test_expect_success 'describe --broken --dirty with a file with changed stat' '\n \t)\n '\n \n+test_expect_success '--always with no refs falls back to commit hash' '\n+\tgit init always-no-refs &&\n+\t(\n+\t\tcd always-no-refs &&\n+\t\ttest_commit --no-tag A &&\n+\t\ttest_commit --no-tag B &&\n+\t\ttest_commit --no-tag C &&\n+\t\tgit describe --abbrev=12 --always HEAD^ >actual &&\n+\t\techo 13 >expected_size &&\n+\t\ttest_file_size actual >actual_size &&\n+\t\ttest_cmp expected_size actual_size\n+\t)\n+'\n+\n test_done\n\nbase-commit: a4f8a869558d59677e8d9798666a23391f0b4ca8\n-- \n2.47.0.338.g60cca15819-goog\n\n"},{"id":"508631","messageId":"20241204232016.GA1460459@coredump.intra.peff.net","threadId":"62431","inReplyTo":"fxbv4ihz4sgdfwtq4vkadntank2lzwkt6abgipuojhumjmuxjs@fegutv3kcamo","subject":"Re: [PATCH 0/4] perf improvements for git-describe with few tags","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-04T23:20:16Z","receivedAt":"2024-12-04T23:20:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 04, 2024 at 03:04:59PM -0800, Josh Steadmon wrote:\n\n> This breaks the case of `git describe --always $SOME_HASH` (we hit the\n> die at builtin/describe.c:340) when there are no tags in the repo. I can\n> send a test case and a small fix shortly.\n\nYeah, this is easy to reproduce. I think it was always broken with:\n\n git describe --candidates=0 --always ...\n\nsince there is a line that skips the whole algorithm and bails early if\nthere are no candidates allowed. But that should surely not kick in if\n\"always\" is set. I.e., I'd expect the fix to be something like:\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex d6c77a714f..d4c869e3d5 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -332,7 +332,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\treturn;\n \t}\n \n-\tif (!max_candidates)\n+\tif (!max_candidates && !always)\n \t\tdie(_(\"no tag exactly matches '%s'\"), oid_to_hex(&cmit->object.oid));\n \tif (debug)\n \t\tfprintf(stderr, _(\"No exact match on refs or tags, searching to describe\\n\"));\n\nBut I'll wait and see what your proposed fix looks like.\n\n-Peff\n"},{"id":"508633","messageId":"20241204232750.GA1460551@coredump.intra.peff.net","threadId":"62431","inReplyTo":"00270315b83b585f7d62ad1204ca1df93a668791.1733354035.git.steadmon@google.com","subject":"Re: [PATCH] fixup! describe: stop traversing when we run out of names","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-04T23:27:50Z","receivedAt":"2024-12-04T23:27:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 04, 2024 at 03:15:42PM -0800, Josh Steadmon wrote:\n\n> diff --git a/builtin/describe.c b/builtin/describe.c\n> index 8ec3be87df..065c1bde6e 100644\n> --- a/builtin/describe.c\n> +++ b/builtin/describe.c\n> @@ -336,7 +336,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n> \t\treturn;\n> \t}\n> \n> -\tif (!max_candidates)\n> +\tif (!max_candidates && !always)\n> \t\tdie(_(\"no tag exactly matches '%s'\"), oid_to_hex(&cmit->object.oid));\n> \tif (debug)\n> \t\tfprintf(stderr, _(\"No exact match on refs or tags, searching to describe\\n\"));\n\nYep, this is the same spot I found. I think it's the right place to make\nthe fix.\n\n> Subject: Re: [PATCH] fixup! describe: stop traversing when we run out of names\n\nThis commit is already in 'next', so it's too late to squash in a change\n(though I'd have done this separately anyway, as it's already an issue\nfor a manual --candidates=0 setting, as unlikely as that is).\n\nCan you re-send with a full commit message?\n\n> diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\n> index 5633b11d01..9aebf09d3d 100755\n> --- a/t/t6120-describe.sh\n> +++ b/t/t6120-describe.sh\n> @@ -715,4 +715,18 @@ test_expect_success 'describe --broken --dirty with a file with changed stat' '\n> \t)\n> '\n> \n> +test_expect_success '--always with no refs falls back to commit hash' '\n> +\tgit init always-no-refs &&\n> +\t(\n> +\t\tcd always-no-refs &&\n> +\t\ttest_commit --no-tag A &&\n> +\t\ttest_commit --no-tag B &&\n> +\t\ttest_commit --no-tag C &&\n> +\t\tgit describe --abbrev=12 --always HEAD^ >actual &&\n> +\t\techo 13 >expected_size &&\n> +\t\ttest_file_size actual >actual_size &&\n> +\t\ttest_cmp expected_size actual_size\n> +\t)\n> +'\n\nI'm not sure if I'm missing anything subtle, but this seems more\ncomplicated than necessary to show the bug. I think just the exit code\nof:\n\n git describe --match=does-not-exist --always HEAD\n\nis sufficient, even in a repo with tags. If you really want to check\nstdout, then probably comparing against:\n\n git rev-list -1 --abbrev-commit --abbrev=13 HEAD >expect &&\n test_cmp expect actual\n\nis a little more obvious than the size check.\n\n-Peff\n"},{"id":"508635","messageId":"20241204235440.GA2560861@coredump.intra.peff.net","threadId":"62431","inReplyTo":"20241204232750.GA1460551@coredump.intra.peff.net","subject":"Re: [PATCH] fixup! describe: stop traversing when we run out of names","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-04T23:54:40Z","receivedAt":"2024-12-04T23:54:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 04, 2024 at 06:27:50PM -0500, Jeff King wrote:\n\n> > -\tif (!max_candidates)\n> > +\tif (!max_candidates && !always)\n> > \t\tdie(_(\"no tag exactly matches '%s'\"), oid_to_hex(&cmit->object.oid));\n> > \tif (debug)\n> > \t\tfprintf(stderr, _(\"No exact match on refs or tags, searching to describe\\n\"));\n> \n> Yep, this is the same spot I found. I think it's the right place to make\n> the fix.\n> \n> > Subject: Re: [PATCH] fixup! describe: stop traversing when we run out of names\n> \n> This commit is already in 'next', so it's too late to squash in a change\n> (though I'd have done this separately anyway, as it's already an issue\n> for a manual --candidates=0 setting, as unlikely as that is).\n> \n> Can you re-send with a full commit message?\n\nIn case it helps with writing a commit message:\n\nI wondered why this line was there at all. It comes from 2c33f75754\n(Teach git-describe --exact-match to avoid expensive tag searches,\n2008-02-24). The --exact-match option is implemented by setting\nmax-candidates to 0. So:\n\n git describe --exact-match --always\n\nhas always been broken, but probably nobody ever cared. My series\nreduces the max_candidates setting automatically when there is nothing\nto find, which means you are more likely to hit the bug.\n\n-Peff\n"},{"id":"508685","messageId":"20241205201449.GA2635755@coredump.intra.peff.net","threadId":"62431","inReplyTo":"20241204232750.GA1460551@coredump.intra.peff.net","subject":"[PATCH] describe: drop early return for max_candidates == 0","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-05T20:14:49Z","receivedAt":"2024-12-05T20:14:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 04, 2024 at 06:27:50PM -0500, Jeff King wrote:\n\n> > Subject: Re: [PATCH] fixup! describe: stop traversing when we run out of names\n> \n> This commit is already in 'next', so it's too late to squash in a change\n> (though I'd have done this separately anyway, as it's already an issue\n> for a manual --candidates=0 setting, as unlikely as that is).\n> \n> Can you re-send with a full commit message?\n\nActually, after thinking on this a bit more, I think the solution below\nis a bit more elegant. This can go on top of jk/describe-perf.\n\n-- >8 --\nFrom: Josh Steadmon \nSubject: [PATCH] describe: drop early return for max_candidates == 0\n\nBefore we even start the describe algorithm, we check to see if\nmax_candidates is 0 and bail immediately if we did not find an exact\nmatch. This comes from 2c33f75754 (Teach git-describe --exact-match to\navoid expensive tag searches, 2008-02-24), since the the --exact-match\noption just sets max_candidates to 0.\n\nBut this interacts badly with the --always option (ironically added only\na week later in da2478dbb0 (describe --always: fall back to showing an\nabbreviated object name, 2008-03-02)). With --always, we'd still want to\nshow the hash rather than calling die().\n\nSo this:\n\n git describe --exact-match --always\n\nand likewise:\n\n git describe --exact-match --candidates=0\n\nhas always been broken. But nobody ever noticed, because using those\noptions together is rather unlikely. However, this bug became a lot\neasier to trigger with a30154187a (describe: stop traversing when we run\nout of names, 2024-10-31). There we reduce max_candidates automatically\nbased on the number of tags available. So in a repo with no tags (or one\nwhere --match finds no tags), max_candidates becomes 0, and --always\nwill never show anything.\n\nSo that early check for --exact-match's zero candidates needs to be\nadjusted. One way to do so is to have it check the \"always\" flag and\nhandle it specially, producing the expected hash. But that would require\nduplicating the output code for \"always\".\n\nInstead, we'd prefer to just fall through to the normal algorithm, which\nshould notice that we are not allowed to find any more candidates, stop\nlooking, and then hit the regular \"always\" output code. Back when\n2c33f75754 was first done, this was a bad idea, since the normal\nalgorithm kept looking for the max+1 candidate. But since 082a4d90af\n(describe: stop digging for max_candidates+1, 2024-10-31), we don't do\nthat anymore, and the algorithm is essentially a noop.\n\nSo we can drop the early return entirely, and the fact that\nmax_candidates is 0 will let us quit early without any special casing.\n\nReported-by: Josh Steadmon \nSigned-off-by: Jeff King \n---\nThere is some small bit of setup work in the algorithm, like creating\nthe reverse index of commits->names in a slab. I don't think that's\nworth worrying about. But if we did care, we could lazily initialize\nthat index, which would also benefit any other cases that bail before\nneeding it.\n\n builtin/describe.c | 2 --\n t/t6120-describe.sh | 6 ++++++\n 2 files changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 8ec3be87df..21e1c87c65 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -336,8 +336,6 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\treturn;\n \t}\n \n-\tif (!max_candidates)\n-\t\tdie(_(\"no tag exactly matches '%s'\"), oid_to_hex(&cmit->object.oid));\n \tif (debug)\n \t\tfprintf(stderr, _(\"No exact match on refs or tags, searching to describe\\n\"));\n \ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 5633b11d01..009d84ff17 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -715,4 +715,10 @@ test_expect_success 'describe --broken --dirty with a file with changed stat' '\n \t)\n '\n \n+test_expect_success '--always with no refs falls back to commit hash' '\n+\tgit rev-parse HEAD >expect &&\n+\tgit describe --no-abbrev --always --match=no-such-tag >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.47.1.734.g721956425b\n\n"},{"id":"508694","messageId":"plncccgcchrmspkelepacifqpfua7nzsb4y5xzjv4vzc3p36yr@r63i2xo6avba","threadId":"62431","inReplyTo":"20241205201449.GA2635755@coredump.intra.peff.net","subject":"Re: [PATCH] describe: drop early return for max_candidates == 0","fromName":"Josh Steadmon","fromEmail":"steadmon@google.com","sentAt":"2024-12-05T22:28:45Z","receivedAt":"2024-12-05T22:28:51Z","isPatch":true,"sender":{"key":"steadmon@google.com","avatar":"https://avatars.githubusercontent.com/u/2654920?v=4"},"body":"On 2024.12.05 15:14, Jeff King wrote:\n> On Wed, Dec 04, 2024 at 06:27:50PM -0500, Jeff King wrote:\n> \n> > > Subject: Re: [PATCH] fixup! describe: stop traversing when we run out of names\n> > \n> > This commit is already in 'next', so it's too late to squash in a change\n> > (though I'd have done this separately anyway, as it's already an issue\n> > for a manual --candidates=0 setting, as unlikely as that is).\n> > \n> > Can you re-send with a full commit message?\n> \n> Actually, after thinking on this a bit more, I think the solution below\n> is a bit more elegant. This can go on top of jk/describe-perf.\n> \n\nThanks, and sorry for not replying earlier, I got distracted by a\ndifferent $DAYJOB breakage:\nhttps://lore.kernel.org/git/b41ae080654a3603af09801018df539f656cf9d8.1733430345.git.steadmon@google.com/\n"},{"id":"508696","messageId":"20241205232132.GA3171999@coredump.intra.peff.net","threadId":"62431","inReplyTo":"plncccgcchrmspkelepacifqpfua7nzsb4y5xzjv4vzc3p36yr@r63i2xo6avba","subject":"Re: [PATCH] describe: drop early return for max_candidates == 0","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-05T23:21:32Z","receivedAt":"2024-12-05T23:21:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 05, 2024 at 02:28:45PM -0800, Josh Steadmon wrote:\n\n> > Actually, after thinking on this a bit more, I think the solution below\n> > is a bit more elegant. This can go on top of jk/describe-perf.\n> > \n> \n> Thanks, and sorry for not replying earlier, I got distracted by a\n> different $DAYJOB breakage:\n\nNo problem. Thanks for finding it!\n\n-Peff\n"},{"id":"508698","messageId":"xmqqser1zf8q.fsf@gitster.g","threadId":"62431","inReplyTo":"20241205201449.GA2635755@coredump.intra.peff.net","subject":"Re: [PATCH] describe: drop early return for max_candidates == 0","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-12-06T03:01:41Z","receivedAt":"2024-12-06T03:01:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Actually, after thinking on this a bit more, I think the solution below\n> is a bit more elegant. This can go on top of jk/describe-perf.\n>\n> -- >8 --\n> From: Josh Steadmon \n> Subject: [PATCH] describe: drop early return for max_candidates == 0\n\nOK, so the patch authorship still blames Josh. But there is no\nsign-off because ... the approach to the fix is so different that\nblaming Josh for this implementation is no longer appropriate?\n\n> Reported-by: Josh Steadmon \n> Signed-off-by: Jeff King \n\nIf so, please take the authorship yourself.\n\n> Before we even start the describe algorithm, we check to see if\n> max_candidates is 0 and bail immediately if we did not find an exact\n> match. This comes from 2c33f75754 (Teach git-describe --exact-match to\n> avoid expensive tag searches, 2008-02-24), since the the --exact-match\n> option just sets max_candidates to 0.\n> ...\n> So this:\n>\n> git describe --exact-match --always\n>\n> and likewise:\n>\n> git describe --exact-match --candidates=0\n\nDid the latter mean to say \"git decribe --candidates=0 --always\", as\nthe earlier paragraph explains that \"--exact\" affects the number of\ncandidates?\n\nWithout this patch, all three give the same result:\n\n $ git describe --exact-match --always HEAD\n fatal: no tag exactly matches '59d18088fe8ace4bf18ade27eeef3664fb6b0878'\n $ git describe --exact-match --candidates=0 HEAD\n fatal: no tag exactly matches '59d18088fe8ace4bf18ade27eeef3664fb6b0878'\n $ git describe --candidates=0 --always HEAD\n fatal: no tag exactly matches '59d18088fe8ace4bf18ade27eeef3664fb6b0878'\n\nWith this patch, we instead get this:\n\n $ ./git describe --exact-match --always HEAD\n 59d18088fe\n $ ./git describe --exact-match --candidates=0 HEAD\n fatal: No tags can describe '59d18088fe8ace4bf18ade27eeef3664fb6b0878'.\n Try --always, or create some tags.\n $ ./git describe --candidates=0 --always HEAD\n 59d18088fe\n\n> But this interacts badly with the --always option (ironically added only\n> a week later in da2478dbb0 (describe --always: fall back to showing an\n> abbreviated object name, 2008-03-02)). With --always, we'd still want to\n> show the hash rather than calling die().\n> ...\n\n> has always been broken.\n\nHmph, I am not sure if the behaviour is _broken_ in the first place.\n\nThe user asks with \"--exact-match\" that a result based on some ref\nthat does not directly point at the object being described is *not*\nacceptable, so with or without \"--always\", it looks to me that it is\ndoing the right thing, if there is no exact match (or there is no\ntag and the user only allowed tag to describe the objects) and the\nresult is \"no tag exactly matches object X\" failure.\n\nOr is our position that these mutually incompatible options, namely\n\"--exact-match\" and \"--always\", follow the \"last one wins\" rule?\nThe implementation does not seem to say so.\n\nIf the earlier request is to describe only as exact tag (and fail if\nthere is no appropriate tag), but then we changed our mind and ask\nto fall back to an abbreviation, this one is understandable:\n\n $ ./git describe --exact-match --always HEAD\n 59d18088fe\n\nBut then this is not. The last thing we explicitly told the command\nis that we accept only the exact match, but this one does not fail,\nwhich seems like a bug:\n\n $ ./git describe --always --exact-match HEAD\n 59d18088fe\n\nSo I am not sure if the \"buggy\" behaviour is buggy to begin with.\nThe way these two are documented can be read both ways,\n\n --exact-match::\n Only output exact matches (a tag directly references the\n supplied commit). This is a synonym for --candidates=0.\n\n --always::\n Show uniquely abbreviated commit object as fallback.\n\nbut my reading is when you give both and when the object given is\nnot directly pointed at by any existing tag, \"ONLY output exact\nmatches\" cannot be satisified. And \"show as fallback\" cannot be\nsatisfied within the constraint that the command is allowed \"only\noutput exact matches\".\n\nI think the complexity from the point of view of a calling script to\ndeal with either behaviour is probably similar. If you ask for\n\"--exact-match\" and there is no exact match, you can ask rev-parse\nto give a shortened one, and you know which one you are giving the\nuser. We can change what \"--exact-match + --candidate=0\" combination\nmeans to let it fallback, but then you'd need to check the output to\nsee if you got an exact tag or a fallback, and for that you'd\nprobably need to ask \"show-ref refs/tags/$output\" or something.\n\nSo I am not sure if it is worth changing the behaviour this late in\nthe game?\n"},{"id":"508701","messageId":"20241206032807.GA3176362@coredump.intra.peff.net","threadId":"62431","inReplyTo":"xmqqser1zf8q.fsf@gitster.g","subject":"Re: [PATCH] describe: drop early return for max_candidates == 0","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-06T03:28:07Z","receivedAt":"2024-12-06T03:28:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 06, 2024 at 12:01:41PM +0900, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Actually, after thinking on this a bit more, I think the solution below\n> > is a bit more elegant. This can go on top of jk/describe-perf.\n> >\n> > -- >8 --\n> > From: Josh Steadmon \n> > Subject: [PATCH] describe: drop early return for max_candidates == 0\n> \n> OK, so the patch authorship still blames Josh. But there is no\n> sign-off because ... the approach to the fix is so different that\n> blaming Josh for this implementation is no longer appropriate?\n\nOh, whoops. I had originally intended to just write the commit message\nand leave him with credit, but then I ended up changing approach.\nLeaving him as the author was an oversight.\n\n> > Before we even start the describe algorithm, we check to see if\n> > max_candidates is 0 and bail immediately if we did not find an exact\n> > match. This comes from 2c33f75754 (Teach git-describe --exact-match to\n> > avoid expensive tag searches, 2008-02-24), since the the --exact-match\n> > option just sets max_candidates to 0.\n> > ...\n> > So this:\n> >\n> > git describe --exact-match --always\n> >\n> > and likewise:\n> >\n> > git describe --exact-match --candidates=0\n> \n> Did the latter mean to say \"git decribe --candidates=0 --always\", as\n> the earlier paragraph explains that \"--exact\" affects the number of\n> candidates?\n\nUrgh, yes, you are correct. I can resend, but I think we should resolve\nthe questions below.\n\n> Without this patch, all three give the same result:\n> \n> $ git describe --exact-match --always HEAD\n> fatal: no tag exactly matches '59d18088fe8ace4bf18ade27eeef3664fb6b0878'\n> $ git describe --exact-match --candidates=0 HEAD\n> fatal: no tag exactly matches '59d18088fe8ace4bf18ade27eeef3664fb6b0878'\n> $ git describe --candidates=0 --always HEAD\n> fatal: no tag exactly matches '59d18088fe8ace4bf18ade27eeef3664fb6b0878'\n> \n> With this patch, we instead get this:\n> \n> $ ./git describe --exact-match --always HEAD\n> 59d18088fe\n> $ ./git describe --exact-match --candidates=0 HEAD\n> fatal: No tags can describe '59d18088fe8ace4bf18ade27eeef3664fb6b0878'.\n> Try --always, or create some tags.\n> $ ./git describe --candidates=0 --always HEAD\n> 59d18088fe\n\nRight, exactly.\n\n> > But this interacts badly with the --always option (ironically added only\n> > a week later in da2478dbb0 (describe --always: fall back to showing an\n> > abbreviated object name, 2008-03-02)). With --always, we'd still want to\n> > show the hash rather than calling die().\n> > ...\n> > has always been broken.\n> \n> Hmph, I am not sure if the behaviour is _broken_ in the first place.\n> \n> The user asks with \"--exact-match\" that a result based on some ref\n> that does not directly point at the object being described is *not*\n> acceptable, so with or without \"--always\", it looks to me that it is\n> doing the right thing, if there is no exact match (or there is no\n> tag and the user only allowed tag to describe the objects) and the\n> result is \"no tag exactly matches object X\" failure.\n> \n> Or is our position that these mutually incompatible options, namely\n> \"--exact-match\" and \"--always\", follow the \"last one wins\" rule?\n> The implementation does not seem to say so.\n\nI think you could argue that they are mutually incompatible. But we have\nnever marked them as such, nor do we do any sort of last-one-wins.\nThey are two distinct options, but in --exact-match mode, --always is\nsimply ignored. Which I think is a bug.\n\n> So I am not sure if the \"buggy\" behaviour is buggy to begin with.\n> The way these two are documented can be read both ways,\n> \n> --exact-match::\n> Only output exact matches (a tag directly references the\n> supplied commit). This is a synonym for --candidates=0.\n> \n> --always::\n> Show uniquely abbreviated commit object as fallback.\n> \n> but my reading is when you give both and when the object given is\n> not directly pointed at by any existing tag, \"ONLY output exact\n> matches\" cannot be satisified. And \"show as fallback\" cannot be\n> satisfied within the constraint that the command is allowed \"only\n> output exact matches\".\n\nI think there can be a more expansive reading of --exact-match (or of\n--candidates=0), which is: only output a tag that matches exactly. And\nthen --always is orthogonal to that. There is no other output to\nproduce, so we show the commit object itself.\n\nNow that more expansive reading is not what --exact-match says above.\nBut it is the only thing that makes sense to me for --candidates=0, and\nthe two are synonyms.\n\n> I think the complexity from the point of view of a calling script to\n> deal with either behaviour is probably similar. If you ask for\n> \"--exact-match\" and there is no exact match, you can ask rev-parse\n> to give a shortened one, and you know which one you are giving the\n> user. We can change what \"--exact-match + --candidate=0\" combination\n> means to let it fallback, but then you'd need to check the output to\n> see if you got an exact tag or a fallback, and for that you'd\n> probably need to ask \"show-ref refs/tags/$output\" or something.\n> \n> So I am not sure if it is worth changing the behaviour this late in\n> the game?\n\nI think there are really two questions here:\n\n 1. Is the current behavior of \"describe --exact-match --always\" a bug?\n I'll grant that probably nobody cares deeply, which is why the\n interaction has not been noticed for all of these years. I think\n the semantics this patch gives are the only ones that make sense,\n but I also don't care that deeply. But...\n\n 2. What should we do about the new regression caused by limiting the\n candidate list? I.e., my earlier patches in this topic make us\n behave as if --candidates= was given when there are fewer tags\n in the repo. That runs afoul of the special-casing of\n --candidates=0 when there are no tags in the repo (or you limit the\n candidates to zero via --match).\n\n If we are not going to address (1) as this patch does, then we need\n another solution. We can internally hold an extra variable to\n distinguish the number of user-requested candidates from the number\n of actual candidates available. But I think my solution to (1) here\n harmonizes the --candidates=0 case with --always, and then the\n auto-adjusted max-candidates case just falls out naturally.\n\n-Peff\n"},{"id":"508705","messageId":"xmqq1pylzbmv.fsf@gitster.g","threadId":"62431","inReplyTo":"20241206032807.GA3176362@coredump.intra.peff.net","subject":"Re: [PATCH] describe: drop early return for max_candidates == 0","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-12-06T04:19:36Z","receivedAt":"2024-12-06T04:19:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> Without this patch, all three give the same result:\n>> \n>> $ git describe --exact-match --always HEAD\n>> fatal: no tag exactly matches '59d18088fe8ace4bf18ade27eeef3664fb6b0878'\n>> $ git describe --exact-match --candidates=0 HEAD\n>> fatal: no tag exactly matches '59d18088fe8ace4bf18ade27eeef3664fb6b0878'\n>> $ git describe --candidates=0 --always HEAD\n>> fatal: no tag exactly matches '59d18088fe8ace4bf18ade27eeef3664fb6b0878'\n>> \n>> With this patch, we instead get this:\n>> \n>> $ ./git describe --exact-match --always HEAD\n>> 59d18088fe\n>> $ ./git describe --exact-match --candidates=0 HEAD\n>> fatal: No tags can describe '59d18088fe8ace4bf18ade27eeef3664fb6b0878'.\n>> Try --always, or create some tags.\n>> $ ./git describe --candidates=0 --always HEAD\n>> 59d18088fe\n> ...\n> I think there are really two questions here:\n>\n> 1. Is the current behavior of \"describe --exact-match --always\" a bug?\n> I'll grant that probably nobody cares deeply, which is why the\n> interaction has not been noticed for all of these years. I think\n> the semantics this patch gives are the only ones that make sense,\n> but I also don't care that deeply. But...\n>\n> 2. What should we do about the new regression caused by limiting the\n> candidate list?\n\nAhh, OK, these --candidate=0 / --exact-match were for illustration\npurposes only. The real issue is that the user does not, with\n\n $ git describe --always HEAD\n\nask for exact matches only at all, but we internally pretend as if\nthey did, which is not nice.\n\nMy gut reaction is that it is wrong not to give the abbreviated\nobject name in this case, but the price to do so shouldn't be to\nchange the behaviour when --exact-match was requested the the user.\n\nLoosening the interaction between the two options, when both were\ngiven explicitly, may be an improvement, but I think that should be\ntreated as a separate topic, with its merit justified independently,\nsince the command has been behaving this way from fairly early\nversion, possibly the one that had both of the options for the first\ntime.\n\n $ rungit v2.20.0 describe --exact-match HEAD\n fatal: No names found, cannot describe anything.\n $ rungit v2.20.0 describe --exact-match --always HEAD\n fatal: no tag exactly matches '13a3dd7fe014658da465e9621ec3651f5473041e'\n $ rungit v2.20.0 describe --exact-match --candidate=0 HEAD\n fatal: No names found, cannot describe anything.\n\nThanks.\n"},{"id":"508708","messageId":"20241206054218.GA3203047@coredump.intra.peff.net","threadId":"62431","inReplyTo":"xmqq1pylzbmv.fsf@gitster.g","subject":"[PATCH] describe: split \"found all tags\" and max_candidates logic","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-06T05:42:18Z","receivedAt":"2024-12-06T05:42:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 06, 2024 at 01:19:36PM +0900, Junio C Hamano wrote:\n\n> My gut reaction is that it is wrong not to give the abbreviated\n> object name in this case, but the price to do so shouldn't be to\n> change the behaviour when --exact-match was requested the the user.\n\nI think this is where we differ. You call it a price, but to me it is a\nbonus. ;)\n\n> Loosening the interaction between the two options, when both were\n> given explicitly, may be an improvement, but I think that should be\n> treated as a separate topic, with its merit justified independently,\n> since the command has been behaving this way from fairly early\n> version, possibly the one that had both of the options for the first\n> time.\n> \n> $ rungit v2.20.0 describe --exact-match HEAD\n> fatal: No names found, cannot describe anything.\n> $ rungit v2.20.0 describe --exact-match --always HEAD\n> fatal: no tag exactly matches '13a3dd7fe014658da465e9621ec3651f5473041e'\n> $ rungit v2.20.0 describe --exact-match --candidate=0 HEAD\n> fatal: No names found, cannot describe anything.\n\nOK. That's certainly the more conservative approach, since it reduces\nthe change of behavior from previous versions.\n\nHere's a replacement patch (again, on top of jk/describe-perf).\n\n-- >8 --\nSubject: [PATCH] describe: split \"found all tags\" and max_candidates logic\n\nCommit a30154187a (describe: stop traversing when we run out of names,\n2024-10-31) taught git-describe to automatically reduce the\nmax_candidates setting to match the total number of possible names. This\nlets us break out of the traversal rather than fruitlessly searching for\nmore candidates when there are no more to be found.\n\nHowever, setting max_candidates to 0 (e.g., if the repo has no tags)\noverlaps with the --exact-match option, which explicitly uses the same\nvalue. And this causes a regression with --always, which is ignored in\nexact-match mode. We used to get this in a repo with no tags:\n\n $ git describe --always HEAD\n b2f0a7f\n\nand now we get:\n\n $ git describe --always HEAD\n fatal: no tag exactly matches 'b2f0a7f47f5f2aebe1e7fceff19a57de20a78c06'\n\nThe reason is that we bail early in describe_commit() when\nmax_candidates is set to 0. This logic goes all the way back to\n2c33f75754 (Teach git-describe --exact-match to avoid expensive tag\nsearches, 2008-02-24).\n\nWe should obviously fix this regression, but there are two paths,\ndepending on what you think:\n\n $ git describe --always --exact-match\n\nand\n\n $ git describe --always --candidates=0\n\nshould do. Since the \"--always\" option was added, it has always been\nignored in --exact-match (or --candidates=0) mode. I.e., we treat\n--exact-match as a true exact match of a tag, and never fall back to\nusing --always, even if it was requested.\n\nIf we think that's a bug (or at least a misfeature), then the right\nsolution is to fix it by removing the early bail-out from 2c33f75754,\nletting the noop algorithm run and then hitting the --always fallback\noutput. And then our regression naturally goes away, because it follows\nthe same path.\n\nIf we think that the current \"--exact-match --always\" behavior is the\nright thing, then we have to differentiate the case where we\nautomatically reduced max_candidates to 0 from the case where the user\nasked for it specifically. That's possible to do with a flag, but we can\nalso just reimplement the logic from a30154187a to explicitly break out\nof the traversal when we run out of candidates (rather than relying on\nthe existing max_candidates check).\n\nMy gut feeling is along the lines of option 1 (it's a bug, and people\nwould be happy for \"--exact-match --always\" to give the fallback rather\nthan ignoring \"--always\"). But the documentation can be interpreted in\nthe other direction, and we've certainly lived with the existing\nbehavior for many years. So it's possible that changing it now is the\nwrong thing.\n\nSo this patch fixes the regression by taking the second option,\nretaining the \"--exact-match\" behavior as-is. There are two new tests.\nThe first shows that the regression is fixed (we don't even need a new\nrepo without tags; a restrictive --match is enough to create the\nsituation that there are no candidate names).\n\nThe second test confirms that the \"--exact-match --always\" behavior\nremains unchanged and continues to die when there is no tag pointing at\nthe specified commit. It's possible we may reconsider this in the\nfuture, but this shows that the approach described above is implemented\nfaithfully.\n\nWe can also run the perf tests in p6100 to see that we've retained the\nspeedup that a30154187a was going for:\n\n Test HEAD^ HEAD\n --------------------------------------------------------------------------------------\n 6100.2: describe HEAD 0.72(0.64+0.07) 0.72(0.66+0.06) +0.0%\n 6100.3: describe HEAD with one max candidate 0.01(0.00+0.00) 0.01(0.00+0.00) +0.0%\n 6100.4: describe HEAD with one tag 0.01(0.01+0.00) 0.01(0.01+0.00) +0.0%\n\nReported-by: Josh Steadmon \nSigned-off-by: Jeff King \n---\n builtin/describe.c | 5 ++---\n t/t6120-describe.sh | 10 ++++++++++\n 2 files changed, 12 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 8ec3be87df..a6ef8af32a 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -367,7 +367,8 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \n \t\tseen_commits++;\n \n-\t\tif (match_cnt == max_candidates) {\n+\t\tif (match_cnt == max_candidates ||\n+\t\t match_cnt == hashmap_get_size(&names)) {\n \t\t\tgave_up_on = c;\n \t\t\tbreak;\n \t\t}\n@@ -667,8 +668,6 @@ int cmd_describe(int argc,\n \t\t\t NULL);\n \tif (!hashmap_get_size(&names) && !always)\n \t\tdie(_(\"No names found, cannot describe anything.\"));\n-\tif (hashmap_get_size(&names) < max_candidates)\n-\t\tmax_candidates = hashmap_get_size(&names);\n \n \tif (argc == 0) {\n \t\tif (broken) {\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 5633b11d01..3f6160d702 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -715,4 +715,14 @@ test_expect_success 'describe --broken --dirty with a file with changed stat' '\n \t)\n '\n \n+test_expect_success '--always with no refs falls back to commit hash' '\n+\tgit rev-parse HEAD >expect &&\n+\tgit describe --no-abbrev --always --match=no-such-tag >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success '--exact-match does not show --always fallback' '\n+\ttest_must_fail git describe --exact-match --always\n+'\n+\n test_done\n-- \n2.47.1.734.g721956425b\n\n"}]}