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

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

[Josh Poimboeuf]

If HEAD isn't associated with an annotated tag, a bug (or feature?) in
"git describe --match" causes it to search every commit in the entire
repository looking for additional match candidates.  Instead of it
taking a fraction of a second, it adds 10-15 seconds to the beginning of
every kernel build.

Fix it by adding an additional dummy match which is slightly further
away from the most recent one, along with setting the max candidate
count to 1 (not 2, apparently another bug).

Before:

  $ git checkout c1e939a21eb1
  $ time make kernel/fork.o -s

  real	0m12.403s
  user	0m11.591s
  sys	0m0.967s

After:

  $ time make kernel/fork.o -s

  real	0m1.119s
  user	0m0.658s
  sys	0m0.659s

Link: https://lore.kernel.org/git/20241030044322.b5n3ji2n6gaeo5u6@treble.attlocal.net/
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>
---
 scripts/setlocalversion | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/scripts/setlocalversion b/scripts/setlocalversion
index 38b96c6797f4..bb8c0bcb7368 100755
--- a/scripts/setlocalversion
+++ b/scripts/setlocalversion
@@ -57,6 +57,8 @@ scm_version()
 		return
 	fi
 
+	githack=" --match=v6.11 --candidates=1"
+
 	# mainline kernel:  6.2.0-rc5  ->  v6.2-rc5
 	# stable kernel:    6.1.7      ->  v6.1.7
 	version_tag=v$(echo "${KERNELVERSION}" | sed -E 's/^([0-9]+\.[0-9]+)\.0(.*)$/\1\2/')
@@ -67,7 +69,7 @@ scm_version()
 	tag=${file_localversion#-}
 	desc=
 	if [ -n "${tag}" ]; then
-		desc=$(git describe --match=$tag 2>/dev/null)
+		desc=$(git describe --match=$tag $githack 2>/dev/null)
 	fi
 
 	# Otherwise, if a localversion* file exists, and the tag
@@ -76,13 +78,13 @@ scm_version()
 	# it. This is e.g. the case in linux-rt.
 	if [ -z "${desc}" ] && [ -n "${file_localversion}" ]; then
 		tag="${version_tag}${file_localversion}"
-		desc=$(git describe --match=$tag 2>/dev/null)
+		desc=$(git describe --match=$tag $githack 2>/dev/null)
 	fi
 
 	# Otherwise, default to the annotated tag derived from KERNELVERSION.
 	if [ -z "${desc}" ]; then
 		tag="${version_tag}"
-		desc=$(git describe --match=$tag 2>/dev/null)
+		desc=$(git describe --match=$tag $githack 2>/dev/null)
 	fi
 
 	# If we are at the tagged commit, we ignore it because the version is
-- 
2.47.0

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

[Rasmus Villemoes]

On Wed, Oct 30 2024, Josh Poimboeuf <jpoimboe@kernel.org> wrote:

> If HEAD isn't associated with an annotated tag, a bug (or feature?) in
> "git describe --match" causes it to search every commit in the entire
> repository looking for additional match candidates.  Instead of it
> taking a fraction of a second, it adds 10-15 seconds to the beginning of
> every kernel build.
>
> Fix it by adding an additional dummy match which is slightly further
> away from the most recent one, along with setting the max candidate
> count to 1 (not 2, apparently another bug).
>

cc += git list

Hm, I tried looking at the git describe source code, and while I can't
claim I understand it very well, I think the main problem is around
this part:

			if (!tags && !all && n->prio < 2) {
				unannotated_cnt++;
			} else if (match_cnt < max_candidates) {
				struct possible_tag *t = &all_matches[match_cnt++];
				t->name = n;
				t->depth = seen_commits - 1;
				t->flag_within = 1u << match_cnt;
				t->found_order = match_cnt;
				c->object.flags |= t->flag_within;
				if (n->prio == 2)
					annotated_cnt++;
			}
			else {
				gave_up_on = c;
				break;
			}

So in the case where one doesn't pass any --match, we get something like

git describe --debug 5f78aec0d7e9
describe 5f78aec0d7e9
No exact match on refs or tags, searching to describe
 annotated        243 v4.19-rc5
 annotated        485 v4.19-rc4
 annotated        814 v4.19-rc3
 annotated       1124 v4.19-rc2
 annotated       1391 v4.19-rc1
 annotated      10546 v4.18
 annotated      10611 v4.18-rc8
 annotated      10819 v4.18-rc7
 annotated      11029 v4.18-rc6
 annotated      11299 v4.18-rc5
traversed 11400 commits
more than 10 tags found; listed 10 most recent
gave up search at 1e4b044d22517cae7047c99038abb444423243ca
v4.19-rc5-243-g5f78aec0d7e9

and that "gave up" commit is v4.18-rc4, the eleventh commit
encountered. That also explains why you have to add a "dummy" second
--match to make --candidates=1 have the expected behaviour.

Perhaps the logic should instead be that as soon as match_cnt hits
max_candidates (i.e. all the tags we're going to consider have actually
been visited), we break out. That is, the last "else" above should
instead be replaced by

  if (match_cnt == max_candidates) {
    ... /* ? , gave_up_on is now a misnomer */
    break;
  }

Then as a further DWIM aid, wherever the initialization logic is could
be updated so that, after expanding all the --match= wildcards, if the
number of tags is less than max_candidates, automatically lower
max_candidates to that number (which in the setlocalversion case will
always be 1 because we're not actually passing a wildcard).

Or, we could explicitly on the kernel side pass that --candidates=1, but
yes, I agree it looks like a bug that the loop requires encountering +1
tag to hit that break;.

Rasmus

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

[Jeff King]

On Thu, Oct 31, 2024 at 11:37:27AM +0100, Rasmus Villemoes wrote:

> and that "gave up" commit is v4.18-rc4, the eleventh commit
> encountered. That also explains why you have to add a "dummy" second
> --match to make --candidates=1 have the expected behaviour.
> 
> Perhaps the logic should instead be that as soon as match_cnt hits
> max_candidates (i.e. all the tags we're going to consider have actually
> been visited), we break out. That is, the last "else" above should
> instead be replaced by
> 
>   if (match_cnt == max_candidates) {
>     ... /* ? , gave_up_on is now a misnomer */
>     break;
>   }

Yes, I agree that is the right direction. Replacing the "else" entirely
feels a little weird, because it is part of the:

  if (!tags && !all && n->prio < 2)
	...
  else if (match_cnt < max_candidates)
	...
  else
	...

So we'd now run that check even if we triggered the first block. But I
don't think it should matter in practice. We only increment match_cnt in
the else-if here. So the "else" block could go away, and the check for
giving up could go inside the else-if.

It does seem like gave_up_on is now pointless, but I'm not sure I
understand all of the code here. I assumed that it was only used to
report "this is where we gave up", and to give you the extra bit of
information that there _were_ other candidates that we omitted (and not
just exactly max_candidates). Of course we don't show that without
--debug. So it seems silly to spend a bunch of extra CPU for that.

But the plot thickens.

What I was going to suggest is that if we wanted to retain that one bit
of information, what we could do instead is: independent of
max_candidates, see if we've found all of the possible names we expanded
from --match. Then max_candidates would work as it does now, but we'd
avoid fruitlessly searching when there are no more names to find.

Counting the number of expanded names is a little weird. We use them to
annotate the commits, but of course multiple names can point to a single
commit, and there's a priority override system. I think the final number
we can find is the number of entries in the "names" hash.

So I expected this to work:

diff --git a/builtin/describe.c b/builtin/describe.c
index 7330a77b38..70a11072de 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -380,6 +380,9 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 				c->object.flags |= t->flag_within;
 				if (n->prio == 2)
 					annotated_cnt++;
+
+				if (match_cnt == hashmap_get_size(&names))
+					break;
 			}
 			else {
 				gave_up_on = c;

but it's still slow! If we set "gave_up_on = c", then it gets fast. I'm
not sure why that is. Later we do:

        if (gave_up_on) {
                commit_list_insert_by_date(gave_up_on, &list);
                seen_commits--;
        }
        seen_commits += finish_depth_computation(&list, &all_matches[0]);

but I don't at all understand why adding gave_up_on lets that finish
sooner. So I'm worried we're missing something about how it is used.

One hack is to just, like the max_candidates case, let us look at one
_more_ commit before bailing. Like this:

diff --git a/builtin/describe.c b/builtin/describe.c
index 7330a77b38..177c8232f6 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -365,6 +365,11 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 		struct commit_list *parents = c->parents;
 		struct commit_name **slot;
 
+		if (match_cnt == hashmap_get_size(&names)) {
+			gave_up_on = c;
+			break;
+		}
+
 		seen_commits++;
 		slot = commit_names_peek(&commit_names, c);
 		n = slot ? *slot : NULL;


That works, but I have a feeling that figured out what the heck is going
on with gave_up_on might produce a more elegant solution.

> Then as a further DWIM aid, wherever the initialization logic is could
> be updated so that, after expanding all the --match= wildcards, if the
> number of tags is less than max_candidates, automatically lower
> max_candidates to that number (which in the setlocalversion case will
> always be 1 because we're not actually passing a wildcard).

Yeah, I had the same thought (though if we do a separate hashmap check
as above, it wouldn't be needed).

-Peff

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

[Jeff King]

On Thu, Oct 31, 2024 at 07:42:10AM -0400, Jeff King wrote:

> That works, but I have a feeling that figured out what the heck is going
> on with gave_up_on might produce a more elegant solution.

OK, I think I might have made some sense of this.

In finish_depth_computation(), we traverse down "list" forever, passing
flags up to our parents, until we find a commit that is marked with the
same "within" flag as our candidate. And then if everything left has
that same "within" flag set, we can bail.

So I _think_ the point is to basically count up what we'd get from this
traversal:

  $tag..$commit

where "$tag" is the candidate tag we found, and "$commit" is what we're
trying to describe (so imagine "git describe --match=$tag $commit").

We can't just use the depth we found while traversing down to $tag,
because there might be side branches we need to count up, too. And we
don't start a new traversal, because we'd be repeating the bits we
already went over when finding $tag in the first place.

And we feed that "list" from the original traversal state. So if we
break out of the traversal early but don't set gave_up_on, then we have
nothing in that state that holds the "within" flag. So we just walk all
of the commits down to the root, because nobody is propagating the flag
to them.

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.


I was also a bit puzzled how this works when there are multiple tags.
We feed only one "best" candidate to finish_depth_computation(), but
gave_up_on does not necessarily have its flag set. But I think that case
the point is that _some_ commit in the list does, and we literally add
every commit to that list.

I'm actually a bit skeptical that any of this is faster than simply
starting over a new traversal of $tag..$commit to find the depth, since
we are considering each commit anew. And there's a bunch of accidentally
quadratic bits of finish_depth_computation(). But frankly I'm somewhat
afraid to touch any of this more than necessary.

-Peff

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

[Jeff King]

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

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

[Benno Evers]

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@bourbaki:~/src/git/tmp-test$ git describe HEAD
    A-3-ga53f69dfb5
    benno@bourbaki:~/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@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

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

[Rasmus Villemoes]

On Thu, Oct 31 2024, Jeff King <peff@peff.net> wrote:

> On Thu, Oct 31, 2024 at 07:42:10AM -0400, Jeff King wrote:
>
>> That works, but I have a feeling that figured out what the heck is going
>> on with gave_up_on might produce a more elegant solution.
>
> OK, I think I might have made some sense of this.
>
> In finish_depth_computation(), we traverse down "list" forever, passing
> flags up to our parents, until we find a commit that is marked with the
> same "within" flag as our candidate. And then if everything left has
> that same "within" flag set, we can bail.
>
> So I _think_ the point is to basically count up what we'd get from this
> traversal:
>
>   $tag..$commit
>
> where "$tag" is the candidate tag we found, and "$commit" is what we're
> trying to describe (so imagine "git describe --match=$tag $commit").

Yeah, so this is really just what the setlocalversion script wants to
know. For a few diffent possible values of $tag (in most cases just 1),
we ask: Is $tag an annotated tag? Is it an ancestor of HEAD? And if so,
how many commits are in $tag..HEAD.

Perhaps we could on the kernel side replace the "git describe --match"
calls with a helper, something like this (needs a lot of polishing):

===
# Produce output similar to what "git describe --match=$tag 2>
# /dev/null" would.  It doesn't have to match exactly as the caller is
# only interested in whether $tag == HEAD, and if not, the number
# between the tag and the short sha1.
describe()
{
    # Is $tag an annotated tag? Could/should probably be written using
    # some plumbing instead of git describe, but with --exact-match,
    # we avoid the walk-to-the-start-of-history behaviour, so fine for
    # this demo.
    git describe --exact-match --match=$tag $tag >/dev/null 2>/dev/null || return 1

    # Can it be used to describe HEAD, i.e. is it an ancestor of HEAD?
    git merge-base --is-ancestor $tag HEAD || return 1

    # Find the number that "git describe" would append.
    count=$(git rev-list --count $tag..HEAD)
    if [ $count -eq 0 ] ; then
        echo "$tag"
    else
        echo "$tag-$count-$head"
    fi
}
===

But if we go this route, we should probably rework the logic
somewhat. There's no point getting the count ourselves, stuffing that
into a string, and then splitting that string with awk to %05d format
the count.

I also don't know if either the --is-ancestor or the rev-list count
could end up doing the same walk-all-commits we're trying to avoid.

Rasmus

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

[Jeff King]

On Fri, Nov 01, 2024 at 11:23:05AM +0100, Rasmus Villemoes wrote:

> Perhaps we could on the kernel side replace the "git describe --match"
> calls with a helper, something like this (needs a lot of polishing):

Yeah, if you are describing off of a single tag, it may just be easier
to query things about the tag directly. Though I do still think
git-describe should be faster here. I'm still pondering what to do about
the disjoint history tests, but otherwise have a polished series to
send.

> ===
> # Produce output similar to what "git describe --match=$tag 2>
> # /dev/null" would.  It doesn't have to match exactly as the caller is
> # only interested in whether $tag == HEAD, and if not, the number
> # between the tag and the short sha1.
> describe()
> {
>     # Is $tag an annotated tag? Could/should probably be written using
>     # some plumbing instead of git describe, but with --exact-match,
>     # we avoid the walk-to-the-start-of-history behaviour, so fine for
>     # this demo.
>     git describe --exact-match --match=$tag $tag >/dev/null 2>/dev/null || return 1

Probably "git cat-file -t $tag" is the simplest way to see if it points
to a tag.

>     # Can it be used to describe HEAD, i.e. is it an ancestor of HEAD?
>     git merge-base --is-ancestor $tag HEAD || return 1
> 
>     # Find the number that "git describe" would append.
>     count=$(git rev-list --count $tag..HEAD)
>     if [ $count -eq 0 ] ; then
>         echo "$tag"
>     else
>         echo "$tag-$count-$head"
>     fi

You can query both of these at once with:

  git rev-list --count --left-right $tag...HEAD

That will traverse down to the merge base and give you two counts. If
the first one is 0, then $tag is a direct ancestor. And the second one
is the count of what's in HEAD.

At first glance, it seems like you'd waste time counting the HEAD side
when the --is-ancestor check could have rejected the tag earlier. But in
practice I think the time will always be dominated by walking down to
the merge base in all commands.

> I also don't know if either the --is-ancestor or the rev-list count
> could end up doing the same walk-all-commits we're trying to avoid.

It shouldn't. In all of those cases we'll generally walk breadth-first
down to the merge base. They're also operations that can take advantage
of other optimizations that git-describe never learned about. E.g.,
generation numbers in the commit graph.

We can even do fast --count with reachability bitmaps, though I wouldn't
expect most dev repos to have bitmaps built. Also, it looks like
"--left-right --count" does not support bitmaps. IMHO that is a bug. ;)

-Peff

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

[Masahiro Yamada]

On Thu, Oct 31, 2024 at 11:37 AM Rasmus Villemoes <ravi@prevas.dk> wrote:
>
> On Wed, Oct 30 2024, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
>
> > If HEAD isn't associated with an annotated tag, a bug (or feature?) in
> > "git describe --match" causes it to search every commit in the entire
> > repository looking for additional match candidates.  Instead of it
> > taking a fraction of a second, it adds 10-15 seconds to the beginning of
> > every kernel build.
> >
> > Fix it by adding an additional dummy match which is slightly further
> > away from the most recent one, along with setting the max candidate
> > count to 1 (not 2, apparently another bug).
> >
>
> cc += git list
>
> Hm, I tried looking at the git describe source code, and while I can't
> claim I understand it very well, I think the main problem is around
> this part:
>
>                         if (!tags && !all && n->prio < 2) {
>                                 unannotated_cnt++;
>                         } else if (match_cnt < max_candidates) {
>                                 struct possible_tag *t = &all_matches[match_cnt++];
>                                 t->name = n;
>                                 t->depth = seen_commits - 1;
>                                 t->flag_within = 1u << match_cnt;
>                                 t->found_order = match_cnt;
>                                 c->object.flags |= t->flag_within;
>                                 if (n->prio == 2)
>                                         annotated_cnt++;
>                         }
>                         else {
>                                 gave_up_on = c;
>                                 break;
>                         }
>
> So in the case where one doesn't pass any --match, we get something like
>
> git describe --debug 5f78aec0d7e9
> describe 5f78aec0d7e9
> No exact match on refs or tags, searching to describe
>  annotated        243 v4.19-rc5
>  annotated        485 v4.19-rc4
>  annotated        814 v4.19-rc3
>  annotated       1124 v4.19-rc2
>  annotated       1391 v4.19-rc1
>  annotated      10546 v4.18
>  annotated      10611 v4.18-rc8
>  annotated      10819 v4.18-rc7
>  annotated      11029 v4.18-rc6
>  annotated      11299 v4.18-rc5
> traversed 11400 commits
> more than 10 tags found; listed 10 most recent
> gave up search at 1e4b044d22517cae7047c99038abb444423243ca
> v4.19-rc5-243-g5f78aec0d7e9
>
> and that "gave up" commit is v4.18-rc4, the eleventh commit
> encountered. That also explains why you have to add a "dummy" second
> --match to make --candidates=1 have the expected behaviour.
>
> Perhaps the logic should instead be that as soon as match_cnt hits
> max_candidates (i.e. all the tags we're going to consider have actually
> been visited), we break out. That is, the last "else" above should
> instead be replaced by
>
>   if (match_cnt == max_candidates) {
>     ... /* ? , gave_up_on is now a misnomer */
>     break;
>   }
>
> Then as a further DWIM aid, wherever the initialization logic is could
> be updated so that, after expanding all the --match= wildcards, if the
> number of tags is less than max_candidates, automatically lower
> max_candidates to that number (which in the setlocalversion case will
> always be 1 because we're not actually passing a wildcard).
>
> Or, we could explicitly on the kernel side pass that --candidates=1, but
> yes, I agree it looks like a bug that the loop requires encountering +1
> tag to hit that break;.
>
> Rasmus
>

I still do not understand the logic either.

git traverses all the way back to
d8470b7c13e11c18cf14a7e3180f0b00e715e4f0.



$ git describe --match=v6.12-rc5 --debug c1e939a21eb1
describe c1e939a21eb1
No exact match on refs or tags, searching to describe
finished search at d8470b7c13e11c18cf14a7e3180f0b00e715e4f0
 annotated         44 v6.12-rc5
traversed 1310005 commits
v6.12-rc5-44-gc1e939a21eb1



Or, more simply,


$ git describe --match=v6.12-rc5 --debug e42b1a9a2557
describe e42b1a9a2557
No exact match on refs or tags, searching to describe
finished search at d8470b7c13e11c18cf14a7e3180f0b00e715e4f0
 annotated          5 v6.12-rc5
traversed 1309966 commits
v6.12-rc5-5-ge42b1a9a2557




e42b1a9a2557 merges v6.12-rc5 and 25f00a13dccf.

The latter is obviously, v6.12-rc2 + 4 commits.
v6.12-rc2 is an ancestor of v6.12-rc5.

I do not understand why git traverses 1.3 million commits.



--
Best Regards

Masahiro Yamada