Message-ID: <CAEQVFRFWT02QTL7PTf84p6AAferijHx8L_Tu6ON1H7U=iEdb3A@mail.gmail.com>
Date: Mon, 4 Nov 2024 13:37:27 +0100
From: Benno Evers <benno.martin.evers@...il.com>
To: Jeff King <peff@...f.net>
Cc: Rasmus Villemoes <ravi@...vas.dk>, Benno Evers <benno@...vers.de>, 
	Josh Poimboeuf <jpoimboe@...nel.org>, Masahiro Yamada <masahiroy@...nel.org>, linux-kernel@...r.kernel.org, 
	linux-kbuild@...r.kernel.org, git@...r.kernel.org
Subject: Re: [PATCH] setlocalversion: Add workaround for "git describe"
 performance issue

Hi,

I'm afraid I can't offer much wisdom, but a few thoughts:

In the testcase, the difference between A-3 and B-4 looks very
academic, but on a real repo the results are more obviously wrong. For
example, if I put the test setup on top of the current git repo:

    benno@...rbaki:~/src/git/tmp-test$ git describe HEAD
    A-3-ga53f69dfb5
    benno@...rbaki:~/src/git/tmp-test$ git describe --candidates=2 HEAD
    B-75205-ga53f69dfb5

When writing the patch I thought that it might be a good idea to
change the definition of `describe` to favor the tag with the shortest
first-parent distance to the described tag and print A-2 in the test
scenario, to me that seems the most intuitive description. But that's
a change in behavior, and it's not even clear that most people would
agree A-2 is better, so I discarded the idea.

Other than that, the only way I can see to implement the behavior
exactly as described would be add the same condition when breaking for
reaching the max number of candidates, ie. to stop adding new
candidates but to delay the break from the loop until all disjoint
paths are unified. No idea how much of a performance hit that would be
in practice, I guess it depends on average branch lengths.

Best regards,
Benno

Am Do., 31. Okt. 2024 um 15:43 Uhr schrieb Jeff King <peff@...f.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

Powered by blists - more mailing lists