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

From: Kristofer Karlsson <krka@spotify.com>
Date: Nov 4, 2026, 11:01 UTC
Message-ID: <CAL71e4PqEQkGoont3tL5wJWd1_itsaaxfX+DOkLj64x-S7xR1A@mail.gmail.com>
In-Reply-To: <xmqq5wyd4epv.fsf@gitster.g>

On Wed, 4 Nov 2026 at 01:34, Junio C Hamano <gitster@pobox.com> wrote:

Show 10 quoted lines

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