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

>
> 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