From: Kristofer Karlsson <krka@spotify.com>
Date: Wed, 04 Nov 2026 11:01:58 GMT
Subject: Re: [PATCH] describe: count the distance correctly when commit dates are skewed
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:
>
> 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