Re: [PATCH] setlocalversion: Add workaround for "git describe" performance issue

[Jeff King <peff@peff.net>]

On Thu, Oct 31, 2024 at 08:24:56AM -0400, Jeff King wrote:

> We have to feed at least one commit with the "within" flag into the
> traversal so that it can let us end things. But I don't think it really
> matters if that commit is the one we found, or if it's a parent of one
> that we happened to pass "within" bits down to.
> 
> So I think we can just set "gave_up_on" to the final element we found
> (whether from max_candidates or from finding every possible name). I.e.,
> what I showed earlier, or what you were proposing.

Hmph. So I don't think this is quite true, but now I'm puzzled again.

It is accurate to say that we must make sure _some_ commit with the
those flag bits set remains in "list". And I don't think it matters if
it's the candidate we found, or its parent.

But there's other stuff happening in that loop, after we process that
max candidate (where we'd proposed to break) but before we hit the next
possible candidate. Stuff like adding onto the depth of the other
candidates. Josh's example doesn't show that because it only has one
candidate, but I could imagine a case where it does matter (though I
didn't construct one).

So I'd have thought that this:

diff --git a/builtin/describe.c b/builtin/describe.c
index 7330a77b38..b0f645c41d 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -366,6 +366,12 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 		struct commit_name **slot;
 
 		seen_commits++;
+
+		if (match_cnt == max_candidates) {
+			gave_up_on = c;
+			break;
+		}
+
 		slot = commit_names_peek(&commit_names, c);
 		n = slot ? *slot : NULL;
 		if (n) {
@@ -381,10 +387,6 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 				if (n->prio == 2)
 					annotated_cnt++;
 			}
-			else {
-				gave_up_on = c;
-				break;
-			}
 		}
 		for (cur_match = 0; cur_match < match_cnt; cur_match++) {
 			struct possible_tag *t = &all_matches[cur_match];

would do it, by just finishing out the loop iteration and bailing on the
next commit. After all, that commit _could_ be a candidate itself. But
it causes a test in t6120 to fail. We have a disjoint history like this:

                 B
                 o
                  \
    o-----o---o----x
          A

and we expect that "x" is described as "A-3" (because we are including
the disjoint B). But after the patch above and with --candidates=2
(since there are only two tags and part of our goal is to limit
candidates to the number of tags), we find "B-4". Which is worse (at
least by some metrics).

I think this comes from 30b1c7ad9d (describe: don't abort too early when
searching tags, 2020-02-26). And given the problem description there, I
can see how quitting early in a disjoint history will give you worse
answers. But the patch above is triggering a case that already _could_
trigger.

So it feels like 30b1c7ad9d is incomplete. Without any patches, if I
limit it to --candidates=2 but make A^ a tag, then it gets the same
wrong answer (for the exact same reason). And I don't see a way to make
it correct without losing the ability to break out of the traversal
early when we hit max_candidates (which is obviously a very important
optimization in general). But maybe I'm missing something.

I do think my patch above is not introducing a new problem that wasn't
already there. It's just that the toy repo, having so few tags, means
any logic to reduce max_candidates will trigger there.

+cc the author of 30b1c7ad9d for any wisdom

-Peff