[PATCH] describe: count the distance correctly when commit dates are skewed

[PATCH] describe: count the distance correctly when commit dates are skewed

[Linus Torvalds]

From: Linus Torvalds <torvalds@linux-foundation.org>

The current merge window for Linux v7.4 showed annoying behavior with
'git describe', where it doesn't actually follow the documented intent
of the result: the commit distance is miscomputed when the commit dates
aren't entirely reliable.

This makes the 'git describe' output not match what the kernel
calculates in its localversion:

	linux$ git describe && uname -r
	v7.3-19342-g2a500a04d6f9
	7.3.0-19059-g2a500a04d6f9

and the kernel calculation is correct, and 'git describe' is wrong. The
number that 'git describe' gives (19342) is nonsense.

The reason is that 'git describe' has walked the commit list past the
actual tagged release due to walking the commits purely in date order,
and is thus counting a few hundred commits that were already included in
Linux 7.3.

The fix is to take the commit generation number into account when
ordering the commits. That will still fail if the repository has no
commit graph, but it at least improves on the situation in the common
case. With that one-liner fix, 'git describe' gets the correct commit
distance on my kernel tree:

	linux$ git describe && uname -r
	v7.3-19059-g2a500a04d6f9
	7.3.0-19059-g2a500a04d6f9

See also commit 1b600e659a ("Compute accurate distances in git-describe
before output.", 2007-01-27) which fixed a different issue in this same
area. Clearly the *intent* is that the distance number is actually the
real distance.

Also add a test-case for this. Thanks to Claude.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

[ Using my kernel.org email to send this, because setting that up is
  easier than fighting gmail ..   - Linus ]

 builtin/describe.c  |  2 +-
 t/t6120-describe.sh | 27 +++++++++++++++++++++++++++
 2 files changed, 28 insertions(+), 1 deletion(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index c0abc931a5..2cd597d919 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -328,7 +328,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
 static void describe_commit(struct commit *cmit, struct strbuf *dst)
 {
 	struct commit *c, *gave_up_on = NULL;
-	struct prio_queue queue = { compare_commits_by_commit_date };
+	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 	struct commit_name *n;
 	struct possible_tag all_matches[MAX_TAGS];
 	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
index 7a7c46658a..a75f9227d9 100755
--- a/t/t6120-describe.sh
+++ b/t/t6120-describe.sh
@@ -749,6 +749,33 @@ test_expect_success 'setup: describe commits with disjoint bases 2' '
 check_describe -C disjoint2 "B-3-gHASH" HEAD
 check_describe -C disjoint2 --expect-failure "B-3-gHASH" --candidates=2 HEAD
 
+#            T
+#  o----o----o----x
+#        \       /
+#         `--o--'
+#            B
+#
+# T is dated an hour before its parent, so a walk by commit date
+# reaches T's parent through B before it reaches T.
+#
+test_expect_success 'setup: describe a tag dated before its parent' '
+	git init skew &&
+	(
+		cd skew &&
+		git config core.commitGraph true &&
+		test_commit --date "2020-01-01 18:00" base &&
+		test_commit --date "2020-01-01 18:01" o &&
+		test_commit --annotate --date "2020-01-01 17:01" T &&
+		git checkout -b side o &&
+		test_commit --date "2020-01-01 18:02" B &&
+		git checkout main &&
+		GIT_COMMITTER_DATE="2020-01-01 18:03" git merge --no-ff -m x side &&
+		git commit-graph write --reachable
+	)
+'
+
+check_describe -C skew "T-2-gHASH" HEAD
+
 test_expect_success 'setup misleading taggerdates' '
 	GIT_COMMITTER_DATE="2006-12-12 12:31" git tag -a -m "another tag" newer-tag-older-commit unique-file~1
 '
-- 
2.56.0.237.g993442f913

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Tuomas Ahola]

Linus Torvalds <torvalds@kernel.org> wrote:

> From: Linus Torvalds <torvalds@linux-foundation.org>
> 
> The current merge window for Linux v7.4 showed annoying behavior with
> 'git describe', where it doesn't actually follow the documented intent
> of the result: the commit distance is miscomputed when the commit dates
> aren't entirely reliable.
> 
> This makes the 'git describe' output not match what the kernel
> calculates in its localversion:
> 
> 	linux$ git describe && uname -r
> 	v7.3-19342-g2a500a04d6f9
> 	7.3.0-19059-g2a500a04d6f9
> 
> and the kernel calculation is correct, and 'git describe' is wrong. The
> number that 'git describe' gives (19342) is nonsense.
> 
> The reason is that 'git describe' has walked the commit list past the
> actual tagged release due to walking the commits purely in date order,
> and is thus counting a few hundred commits that were already included in
> Linux 7.3.
> 
> The fix is to take the commit generation number into account when
> ordering the commits. That will still fail if the repository has no
> commit graph, but it at least improves on the situation in the common
> case. With that one-liner fix, 'git describe' gets the correct commit
> distance on my kernel tree:
> 
> 	linux$ git describe && uname -r
> 	v7.3-19059-g2a500a04d6f9
> 	7.3.0-19059-g2a500a04d6f9
> 
> See also commit 1b600e659a ("Compute accurate distances in git-describe
> before output.", 2007-01-27) which fixed a different issue in this same
> area. Clearly the *intent* is that the distance number is actually the
> real distance.
> 
> Also add a test-case for this. Thanks to Claude.
> 
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> ---
> 
> [ Using my kernel.org email to send this, because setting that up is
>   easier than fighting gmail ..   - Linus ]
> 
>  builtin/describe.c  |  2 +-
>  t/t6120-describe.sh | 27 +++++++++++++++++++++++++++
>  2 files changed, 28 insertions(+), 1 deletion(-)
> 
> diff --git a/builtin/describe.c b/builtin/describe.c
> index c0abc931a5..2cd597d919 100644
> --- a/builtin/describe.c
> +++ b/builtin/describe.c
> @@ -328,7 +328,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
>  static void describe_commit(struct commit *cmit, struct strbuf *dst)
>  {
>  	struct commit *c, *gave_up_on = NULL;
> -	struct prio_queue queue = { compare_commits_by_commit_date };
> +	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
>  	struct commit_name *n;
>  	struct possible_tag all_matches[MAX_TAGS];
>  	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
> diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
> index 7a7c46658a..a75f9227d9 100755
> --- a/t/t6120-describe.sh
> +++ b/t/t6120-describe.sh
> @@ -749,6 +749,33 @@ test_expect_success 'setup: describe commits with disjoint bases 2' '
>  check_describe -C disjoint2 "B-3-gHASH" HEAD
>  check_describe -C disjoint2 --expect-failure "B-3-gHASH" --candidates=2 HEAD
>  
> +#            T
> +#  o----o----o----x
> +#        \       /
> +#         `--o--'
> +#            B
> +#
> +# T is dated an hour before its parent, so a walk by commit date
> +# reaches T's parent through B before it reaches T.
> +#
> +test_expect_success 'setup: describe a tag dated before its parent' '
> +	git init skew &&
> +	(
> +		cd skew &&
> +		git config core.commitGraph true &&
> +		test_commit --date "2020-01-01 18:00" base &&
> +		test_commit --date "2020-01-01 18:01" o &&
> +		test_commit --annotate --date "2020-01-01 17:01" T &&
> +		git checkout -b side o &&
> +		test_commit --date "2020-01-01 18:02" B &&
> +		git checkout main &&
> +		GIT_COMMITTER_DATE="2020-01-01 18:03" git merge --no-ff -m x side &&
> +		git commit-graph write --reachable
> +	)
> +'

Just a clueless rewrite of the above.  I had quite fun writing it, so why not
to share... it works and might even offer some not-completely-bogus food for
thought.

	git init skew &&
	(
		cd skew &&
		test_config core.commitGraph true &&
		test_commit base &&
		test_commit o &&
		test_tick=$(($test_tick - 3600)) &&
		test_commit --annotate T &&
		test_tick=$(($test_tick + 3600)) &&
		git checkout o &&
		test_commit B &&
		git checkout main &&
		test_merge x B &&
		git commit-graph write --reachable
	)

> +
> +check_describe -C skew "T-2-gHASH" HEAD
> +
>  test_expect_success 'setup misleading taggerdates' '
>  	GIT_COMMITTER_DATE="2006-12-12 12:31" git tag -a -m "another tag" newer-tag-older-commit unique-file~1
>  '
> -- 
> 2.56.0.237.g993442f913
> 

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Junio C Hamano]

Tuomas Ahola <taahol@utu.fi> writes:

> Linus Torvalds <torvalds@kernel.org> wrote:
>
>> From: Linus Torvalds <torvalds@linux-foundation.org>
>> 
>> The current merge window for Linux v7.4 showed annoying behavior with
>> 'git describe', where it doesn't actually follow the documented intent
>> of the result: the commit distance is miscomputed when the commit dates
>> aren't entirely reliable.
>> 
>> This makes the 'git describe' output not match what the kernel
>> calculates in its localversion:
>> 
>> 	linux$ git describe && uname -r
>> 	v7.3-19342-g2a500a04d6f9
>> 	7.3.0-19059-g2a500a04d6f9
>> 
>> and the kernel calculation is correct, and 'git describe' is wrong. The
>> number that 'git describe' gives (19342) is nonsense.
>> 
>> The reason is that 'git describe' has walked the commit list past the
>> actual tagged release due to walking the commits purely in date order,
>> and is thus counting a few hundred commits that were already included in
>> Linux 7.3.
>> 
>> The fix is to take the commit generation number into account when
>> ordering the commits. That will still fail if the repository has no
>> commit graph, but it at least improves on the situation in the common
>> case. With that one-liner fix, 'git describe' gets the correct commit
>> distance on my kernel tree:
>> 
>> 	linux$ git describe && uname -r
>> 	v7.3-19059-g2a500a04d6f9
>> 	7.3.0-19059-g2a500a04d6f9
>> 
>> See also commit 1b600e659a ("Compute accurate distances in git-describe
>> before output.", 2007-01-27) which fixed a different issue in this same
>> area. Clearly the *intent* is that the distance number is actually the
>> real distance.
>> 
>> Also add a test-case for this. Thanks to Claude.
>> 
>> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
>> ---
>> +test_expect_success 'setup: describe a tag dated before its parent' '
>> +	git init skew &&
>> +	(
>> +		cd skew &&
>> +		git config core.commitGraph true &&
>> +		test_commit --date "2020-01-01 18:00" base &&
>> +		test_commit --date "2020-01-01 18:01" o &&
>> +		test_commit --annotate --date "2020-01-01 17:01" T &&
>> +		git checkout -b side o &&
>> +		test_commit --date "2020-01-01 18:02" B &&
>> +		git checkout main &&
>> +		GIT_COMMITTER_DATE="2020-01-01 18:03" git merge --no-ff -m x side &&
>> +		git commit-graph write --reachable
>> +	)
>> +'
>
> Just a clueless rewrite of the above.  I had quite fun writing it, so why not
> to share... it works and might even offer some not-completely-bogus food for
> thought.
>
> 	git init skew &&
> 	(
> 		cd skew &&
> 		test_config core.commitGraph true &&

Doesn't this barf when it tries to register a clean-up action from
inside a subshell?

> 		test_commit base &&
> 		test_commit o &&
> 		test_tick=$(($test_tick - 3600)) &&
> 		test_commit --annotate T &&
> 		test_tick=$(($test_tick + 3600)) &&
> 		git checkout o &&
> 		test_commit B &&

Quite honestly, I do not see much value in this rewrite.  Explicit
dates and times from six years ago will eventually become distant
history, but at least they made it clear, even in the source code,
which event was recorded with what exact timestamp.  In the
original, it was much easier to tell which commit had a newer or
older timestamp than in the rewritten version.  Can you tell if the
annotated commit 'T' has a timestamp older by 3600, 3599, or 3601
seconds than the next commit 'B', just by looking at the sequence
above and without inspecting how 'test_commit --annotate' is
implemented?

Unless the focus of the test in question is "I do not really care
what time they record as long as they are reasonable and
reproducible from one run to the next", relying on $test_tick is
probably counterproductive.  The test for this fix, where the issue
is entirely about the relative ordering of timestamps on the
involved commits, is a prime example of where using explicit --date
options would make things much easier to understand.

> 		git checkout main &&
> 		test_merge x B &&
> 		git commit-graph write --reachable
> 	)
>
>> +
>> +check_describe -C skew "T-2-gHASH" HEAD
>> +
>>  test_expect_success 'setup misleading taggerdates' '
>>  	GIT_COMMITTER_DATE="2006-12-12 12:31" git tag -a -m "another tag" newer-tag-older-commit unique-file~1
>>  '
>> -- 
>> 2.56.0.237.g993442f913
>> 

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Tuomas Ahola]

Junio C Hamano <gitster@pobox.com> wrote:

> Tuomas Ahola <taahol@utu.fi> writes:
> 
> > Linus Torvalds <torvalds@kernel.org> wrote:
> >
> >> ---
> >> +test_expect_success 'setup: describe a tag dated before its parent' '
> >> +	git init skew &&
> >> +	(
> >> +		cd skew &&
> >> +		git config core.commitGraph true &&
> >> +		test_commit --date "2020-01-01 18:00" base &&
> >> +		test_commit --date "2020-01-01 18:01" o &&
> >> +		test_commit --annotate --date "2020-01-01 17:01" T &&
> >> +		git checkout -b side o &&
> >> +		test_commit --date "2020-01-01 18:02" B &&
> >> +		git checkout main &&
> >> +		GIT_COMMITTER_DATE="2020-01-01 18:03" git merge --no-ff -m x side &&
> >> +		git commit-graph write --reachable
> >> +	)
> >> +'
> >
> > Just a clueless rewrite of the above.  I had quite fun writing it, so why not
> > to share... it works and might even offer some not-completely-bogus food for
> > thought.
> >
> > 	git init skew &&
> > 	(
> > 		cd skew &&
> > 		test_config core.commitGraph true &&
> 
> Doesn't this barf when it tries to register a clean-up action from
> inside a subshell?
> 

Hmm, only in Bash---something I forgot to test.  This of course fails properly:

	$ make -C t/ SHELL=bash t6120-describe.sh 

> > 		test_commit base &&
> > 		test_commit o &&
> > 		test_tick=$(($test_tick - 3600)) &&
> > 		test_commit --annotate T &&
> > 		test_tick=$(($test_tick + 3600)) &&
> > 		git checkout o &&
> > 		test_commit B &&
> 
> Quite honestly, I do not see much value in this rewrite.

Well, I did prepend the code with a "caveat lector", quite aware that the
rewrite was somewhat pointless---if it had contained any good parts, that
would've been by sheer luck and happenstance.

That said, I actually tried my best, and I am quite happy that you gave that
clueless waste of time a serious review.  Thanks!

>                                                    [...]  Explicit
> dates and times from six years ago will eventually become distant
> history, but at least they made it clear, even in the source code,
> which event was recorded with what exact timestamp.  In the
> original, it was much easier to tell which commit had a newer or
> older timestamp than in the rewritten version.  Can you tell if the
> annotated commit 'T' has a timestamp older by 3600, 3599, or 3601
> seconds than the next commit 'B', just by looking at the sequence
> above and without inspecting how 'test_commit --annotate' is
> implemented?
> 
> Unless the focus of the test in question is "I do not really care
> what time they record as long as they are reasonable and
> reproducible from one run to the next", relying on $test_tick is
> probably counterproductive.  The test for this fix, where the issue
> is entirely about the relative ordering of timestamps on the
> involved commits, is a prime example of where using explicit --date
> options would make things much easier to understand.
> 

Okay, I'll be wiser next time.

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Junio C Hamano]

Tuomas Ahola <taahol@utu.fi> writes:

> Hmm, only in Bash---something I forgot to test.  This of course fails properly:
>
> 	$ make -C t/ SHELL=bash t6120-describe.sh 

It is more like "we must not use anything that relies on
test_when_finished in a subshell in any shell, and we wanted to
detect such mistaken use of test_config and its friends, but that
unfortunately was something we couldn't do portably".  It would be
great if you can make the check available to other shells ;-) but
that would be a completely separate topic.

In any case, let's pick up this patch and move it forward.

Thanks, all.

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[SZEDER Gábor]

On Sat, Oct 31, 2026 at 06:07:10PM -0700, Junio C Hamano wrote:
> Tuomas Ahola <taahol@utu.fi> writes:
> 
> > Linus Torvalds <torvalds@kernel.org> wrote:
> >
> >> +test_expect_success 'setup: describe a tag dated before its parent' '
> >> +	git init skew &&
> >> +	(
> >> +		cd skew &&
> >> +		git config core.commitGraph true &&
> >> +		test_commit --date "2020-01-01 18:00" base &&
> >> +		test_commit --date "2020-01-01 18:01" o &&
> >> +		test_commit --annotate --date "2020-01-01 17:01" T &&
> >> +		git checkout -b side o &&
> >> +		test_commit --date "2020-01-01 18:02" B &&
> >> +		git checkout main &&
> >> +		GIT_COMMITTER_DATE="2020-01-01 18:03" git merge --no-ff -m x side &&
> >> +		git commit-graph write --reachable
> >> +	)
> >> +'
> >
> > Just a clueless rewrite of the above.  I had quite fun writing it, so why not
> > to share... it works and might even offer some not-completely-bogus food for
> > thought.
> >
> > 	git init skew &&
> > 	(
> > 		cd skew &&
> > 		test_config core.commitGraph true &&
> 
> Doesn't this barf when it tries to register a clean-up action from
> inside a subshell?

In both cases this is a freshly initialized repository, and the commit
graph has been enabled by default for a long time, so why do we need
to set this config in the first place?

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Patrick Steinhardt]

On Fri, Oct 30, 2026 at 11:55:03PM -0700, Linus Torvalds wrote:
> From: Linus Torvalds <torvalds@linux-foundation.org>
> 
> The current merge window for Linux v7.4 showed annoying behavior with
> 'git describe', where it doesn't actually follow the documented intent
> of the result: the commit distance is miscomputed when the commit dates
> aren't entirely reliable.
> 
> This makes the 'git describe' output not match what the kernel
> calculates in its localversion:
> 
> 	linux$ git describe && uname -r
> 	v7.3-19342-g2a500a04d6f9
> 	7.3.0-19059-g2a500a04d6f9
> 
> and the kernel calculation is correct, and 'git describe' is wrong. The
> number that 'git describe' gives (19342) is nonsense.

Out of curiosity, how do you calculate the localversion...? *goes
checking* Ah, you seem to use `git rev-list --count --left-right $tag`,
so you basically reimplement parts of git-describe(1).

Is there a reason why you use your own script, e.g. because of a missing
feature? Besides the fact of course that git-describe(1) is buggy in
this particular case.

> The fix is to take the commit generation number into account when
> ordering the commits. That will still fail if the repository has no
> commit graph, but it at least improves on the situation in the common
> case. With that one-liner fix, 'git describe' gets the correct commit
> distance on my kernel tree:
> 
> 	linux$ git describe && uname -r
> 	v7.3-19059-g2a500a04d6f9
> 	7.3.0-19059-g2a500a04d6f9
> 
> See also commit 1b600e659a ("Compute accurate distances in git-describe
> before output.", 2007-01-27) which fixed a different issue in this same
> area. Clearly the *intent* is that the distance number is actually the
> real distance.

Hmm. The big downside of this particular change is that you may now get
different results depending on whether or not you have a recent commit
graph. So you may get different results based on when git-maintenance(1)
last decided to update it, and that would in turn result in highly
puzzling behaviour for the end user.

So...

> diff --git a/builtin/describe.c b/builtin/describe.c
> index c0abc931a5..2cd597d919 100644
> --- a/builtin/describe.c
> +++ b/builtin/describe.c
> @@ -328,7 +328,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
>  static void describe_commit(struct commit *cmit, struct strbuf *dst)
>  {
>  	struct commit *c, *gave_up_on = NULL;
> -	struct prio_queue queue = { compare_commits_by_commit_date };
> +	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
>  	struct commit_name *n;
>  	struct possible_tag all_matches[MAX_TAGS];
>  	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;

... I wonder whether we should also call `ensure_generations_valid()`
here. That function is very expensive in cases where we don't have a
commit graph as it backfills generation numbers, and it may have to walk
the complete commit graph to do so. But isn't that better compared to
silently yielding a potentially-wrong result?

Thanks!

Patrick

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Derrick Stolee]

On 11/2/2026 7:46 AM, Patrick Steinhardt wrote:
> On Fri, Oct 30, 2026 at 11:55:03PM -0700, Linus Torvalds wrote:
>> From: Linus Torvalds <torvalds@linux-foundation.org>

>> diff --git a/builtin/describe.c b/builtin/describe.c
>> index c0abc931a5..2cd597d919 100644
>> --- a/builtin/describe.c
>> +++ b/builtin/describe.c
>> @@ -328,7 +328,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
>>  static void describe_commit(struct commit *cmit, struct strbuf *dst)
>>  {
>>  	struct commit *c, *gave_up_on = NULL;
>> -	struct prio_queue queue = { compare_commits_by_commit_date };
>> +	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
>>  	struct commit_name *n;
>>  	struct possible_tag all_matches[MAX_TAGS];
>>  	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
> 
> ... I wonder whether we should also call `ensure_generations_valid()`
> here. That function is very expensive in cases where we don't have a
> commit graph as it backfills generation numbers, and it may have to walk
> the complete commit graph to do so. But isn't that better compared to
> silently yielding a potentially-wrong result?
I came here to say exactly that. Even when a commit-graph exists, it can
be slightly behind the object database and so we need to fix up the
newest commits with generation number details.

The biggest downside is that it becomes very slow when a commit-graph
doesn't exist (it walks all reachable commits from the starting points)
but that's typically better than giving an incorrect answer.

Thanks,
-Stolee

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

>>> +	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
>>>  	struct commit_name *n;
>>>  	struct possible_tag all_matches[MAX_TAGS];
>>>  	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
>> 
>> ... I wonder whether we should also call `ensure_generations_valid()`
>> here. That function is very expensive in cases where we don't have a
>> commit graph as it backfills generation numbers, and it may have to walk
>> the complete commit graph to do so. But isn't that better compared to
>> silently yielding a potentially-wrong result?
> I came here to say exactly that. Even when a commit-graph exists, it can
> be slightly behind the object database and so we need to fix up the
> newest commits with generation number details.
>
> The biggest downside is that it becomes very slow when a commit-graph
> doesn't exist (it walks all reachable commits from the starting points)
> but that's typically better than giving an incorrect answer.

When we ended up spending the huge cost by doing this in a
repository without existing commit-graph or with an out of date
commit-graph, I wonder if it is possible to recoup the cost by
amortizing it over time by writing a commit-graph out?

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Derrick Stolee]

On 11/2/2026 12:03 PM, Junio C Hamano wrote:
> Derrick Stolee <stolee@gmail.com> writes:
> 
>>>> +	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
>>>>  	struct commit_name *n;
>>>>  	struct possible_tag all_matches[MAX_TAGS];
>>>>  	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
>>>
>>> ... I wonder whether we should also call `ensure_generations_valid()`
>>> here. That function is very expensive in cases where we don't have a
>>> commit graph as it backfills generation numbers, and it may have to walk
>>> the complete commit graph to do so. But isn't that better compared to
>>> silently yielding a potentially-wrong result?
>> I came here to say exactly that. Even when a commit-graph exists, it can
>> be slightly behind the object database and so we need to fix up the
>> newest commits with generation number details.
>>
>> The biggest downside is that it becomes very slow when a commit-graph
>> doesn't exist (it walks all reachable commits from the starting points)
>> but that's typically better than giving an incorrect answer.
> 
> When we ended up spending the huge cost by doing this in a
> repository without existing commit-graph or with an out of date
> commit-graph, I wonder if it is possible to recoup the cost by
> amortizing it over time by writing a commit-graph out?

I do like this idea, as we could take the structure that was
computed and write it out with relatively small overhead at
that point. We are expecting the commit-graph to exist in
more places, and it has been baking for several years now.
Maybe it's time to make that expectation more explicit and
have it become an opt-out instead of opt-in feature.

It does lead to some concerns that commands that are "read
only" become mutators of disk state. This is something that
could be rectified with appropriate guardrails.

Thanks,
-Stolee

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Linus Torvalds]

On Mon, 2 Nov 2026 at 04:47, Patrick Steinhardt <ps@pks.im> wrote:
>
> Out of curiosity, how do you calculate the localversion...? *goes
> checking* Ah, you seem to use `git rev-list --count --left-right $tag`,
> so you basically reimplement parts of git-describe(1).
>
> Is there a reason why you use your own script, e.g. because of a missing
> feature? Besides the fact of course that git-describe(1) is buggy in
> this particular case.

I think it's partly historical, and partly because the kernel version
has actually always had the full "three number" version without the
'v' (ie the kernel localversion uses "7.3.0" instead of "v7.3")

The kernel localversion is also configurable and wasn't tied to git
specifically, so it was never just "git describe". *I* want the git
version (and that's what "CONFIG_LOCALVERSION_AUTO" does for the
kernel automatically if you are using a git tree), but I think all
distros do their own versioning manually).

So there's a whole 'setlocalversion' script in the kernel that does
many different cases, and it's all hacky and historical and I actually
suspect some of it predates "git describe" even existing.

> Hmm. The big downside of this particular change is that you may now get
> different results depending on whether or not you have a recent commit
> graph. So you may get different results based on when git-maintenance(1)
> last decided to update it, and that would in turn result in highly
> puzzling behaviour for the end user.

Well, honestly, no more puzzling than the odd existing behavior. But:

> ... I wonder whether we should also call `ensure_generations_valid()`
> here.

I suspect that is just *way* too expensive in the bad case, but I
would hope/assume that any big repo already has generation numbers in
it, so maybe it doesn't matter.

Maybe add a "--exact" flag ot something to force it, and just document
that without it, you can get slightly odd numbers.

Becasue rigth now, the numbers may be consistent, but when they can be
consistently *wrong*, I don't think that's a good thing either. It
took me a week of annoyance to even start looking at *why* they were
wrong.

            Linus

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Patrick Steinhardt]

On Mon, Nov 02, 2026 at 10:37:57AM -0800, Linus Torvalds wrote:
> On Mon, 2 Nov 2026 at 04:47, Patrick Steinhardt <ps@pks.im> wrote:
> > Hmm. The big downside of this particular change is that you may now get
> > different results depending on whether or not you have a recent commit
> > graph. So you may get different results based on when git-maintenance(1)
> > last decided to update it, and that would in turn result in highly
> > puzzling behaviour for the end user.
> 
> Well, honestly, no more puzzling than the odd existing behavior. But:
> 
> > ... I wonder whether we should also call `ensure_generations_valid()`
> > here.
> 
> I suspect that is just *way* too expensive in the bad case, but I
> would hope/assume that any big repo already has generation numbers in
> it, so maybe it doesn't matter.

We nowadays generate commit graphs by default, yes. So usually
repositories should have one, but there will of course be outliers where
they don't exist because of whatever reason.

> Maybe add a "--exact" flag ot something to force it, and just document
> that without it, you can get slightly odd numbers.
> 
> Becasue rigth now, the numbers may be consistent, but when they can be
> consistently *wrong*, I don't think that's a good thing either. It
> took me a week of annoyance to even start looking at *why* they were
> wrong.

I fully agree that being consistently wrong isn't great. I just wonder
whether being intermittently wrong is even worse because now the actual
result depends on timing. And consequently I'm a bit hesitant to
introduce an "--exact" flag and have people opt-in to a consistently
correct result, because they won't even know that git-describe(1) may by
default produce incorrect results.

An alternative that might be worth considering here is to instead make
users opt-out with "--no-exact", and then make that discoverable by
emitting a warning in the case where we don't have a commit graph in the
repository.

Patrick

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Linus Torvalds]

On Mon, 2 Nov 2026 at 23:16, Patrick Steinhardt <ps@pks.im> wrote:
>
> An alternative that might be worth considering here is to instead make
> users opt-out with "--no-exact", and then make that discoverable by
> emitting a warning in the case where we don't have a commit graph in the
> repository.

That sounds sane - that way people who see performance issues but for
some reason or another don't want to do generation numbers in the repo
itself (read-only legacy repositories?) have a way out.

            Linus

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

>> I suspect that is just *way* too expensive in the bad case, but I
>> would hope/assume that any big repo already has generation numbers in
>> it, so maybe it doesn't matter.
>
> We nowadays generate commit graphs by default, yes. So usually
> repositories should have one, but there will of course be outliers where
> they don't exist because of whatever reason.

FWIW, one (out of two) tests that are expected to fail in
t6120-describe.sh started failing in the feature-testbed CI job
started failing.  I think GIT_TEST_COMMIT_GRAPH is the culprit.

> An alternative that might be worth considering here is to instead make
> users opt-out with "--no-exact", and then make that discoverable by
> emitting a warning in the case where we don't have a commit graph in the
> repository.

That would work as an escape hatch.  Sounds like a good plan.

Re: [PATCH] describe: count the distance correctly when commit dates are skewed

[Kristofer Karlsson]

On Wed, 4 Nov 2026 at 01:34, Junio C Hamano <gitster@pobox.com> wrote:
>
> Patrick Steinhardt <ps@pks.im> writes:
>
> > An alternative that might be worth considering here is to instead make
> > users opt-out with "--no-exact", and then make that discoverable by
> > emitting a warning in the case where we don't have a commit graph in the
> > repository.
>
> That would work as an escape hatch.  Sounds like a good plan.
>

Sorry for being a bit late to this thread; I have been playing
around with a local prototype for this problem, and I wonder if it
would be possible to make the escape hatch largely unnecessary, by
making the depth exact (or very close to it) without generation
numbers, at roughly today's cost.

The problem today is that the walk eagerly increments a tag's depth
for every commit it visits that does not carry the tag's bit yet,
but if the bit reaches that commit later via another path, the
depth is never decremented.  My prototype instead keeps one counter
of all visited commits, and per tag a counter of visited commits
that carry its bit.  The depth is then the difference of the two,
whatever the order in which commits were visited.  When an already
visited commit gains a bit late, that tag's counter is bumped and
the commit is enqueued again, so that the bit keeps propagating.
As bits are only ever added, that happens at most once per commit
and tag.

What remains is knowing when to stop.  With the queue ordered by
generation number, as in Linus's patch, that is exact for commits in
the commit-graph.  For commits outside of it, it is exact as long as
no commit is dated more than some epsilon before one of its own
ancestors.  That is a sufficient condition, not a necessary one: on
linux.git the worst such case since v6.0 is about 60 days, but a
miscount also needs the skew to be right where the walk stops, and
an epsilon of a week gave exact depths for every commit I tried,
including the ones right around the skewed spots, at no measurable
cost.

A nice property is that this also works well with a partial
commit-graph.  The commits outside of it are visited first, and only
those rely on the epsilon; once the walk reaches the commits in it,
it can stop as soon as the depths are final.  So the commit-graph
does not need to be fully up to date to help, much like with other
walks that use generation numbers.

For 2a500a04d6f9 it gives v7.3-19059 with and without a
commit-graph, in about the same time as master, and it matches
"rev-list --count" on the ~450 commits of the last merge window.
Both expected failures in t6120 pass with it, with and without
GIT_TEST_COMMIT_GRAPH.  The change is about 120 lines added and 60
removed in builtin/describe.c.

Would this be worth pursuing, either instead of or on top of
Linus's patch?  If so, I would be happy to clean it up and send it.

Thanks,
Kristofer