From: 'Ben Boeckel' <ben.boeckel@kitware.com>
Date: Sat, 28 Feb 2026 06:11:43 GMT
Subject: Re: [BUG] `git describe` doesn't traverse the graph in topological order
Message-ID: <aaKHH6Mf_oKJ9H6M@rotor.dev.benboeckel.internal>
In-Reply-To: <20251120080525.GB1283645@coredump.intra.peff.net>

On Thu, Nov 20, 2025 at 03:05:25 -0500, Jeff King wrote:
> On Wed, Nov 19, 2025 at 09:48:52PM -0500, 'Ben Boeckel' wrote:
> 
> > So I finally found some time to go back to this. The actual fix is
> > actually rather easy (patch attached). However, as guessed at previously
> > in the thread, the performance is in the tank without an up-to-date
> > commit graph ("instant" with it versus "minutes" without). On the other
> > hand, it is *accurate*. It does fix one expect-fail test case already in
> > the test suite (also included in the patch).
> 
> Minutes? Yikes. Let's look...
> 
> > +/*
> > + * Topological comparison: always return parents before children.
> > + * This is reverse topological order: children before parents.
> > + */
> > +static int compare_commits_topo(const void *a_, const void *b_, void *_unused_ UNUSED)
> > +{
> > +	struct commit *a = (struct commit *)a_;
> > +	struct commit *b = (struct commit *)b_;
> > +	if (repo_is_descendant_of(the_repository, a, &(struct commit_list){ b, NULL }))
> > +		return -1; // a is descendant, so comes before b
> > +	if (repo_is_descendant_of(the_repository, b, &(struct commit_list){ a, NULL }))
> > +		return 1; // b is descendant, so comes before a
> > +	// fallback: order by hash for determinism
> > +	return oidcmp(&a->object.oid, &b->object.oid);
> > +}
> 
> Ah. So you are doing two full traversals for each comparison. That is
> going to be expensive. You would do much better to walk all of history
> one time, marking the generation number (distance to root) of each
> commit, and then comparing generations here (if A has a lower generation
> than B, then you know that B cannot be an ancestor of A). Or if we have
> commit graphs, just use the generation numbers they already contain. ;)

Ok, so it sounds like I should, in `describe_commit`:

- check if commit graphs are enabled (and verified?): if so, use their
  generation numbers
- if they're not enabled, perform a local walk to store a generation
  number (somewhere?) that is `max(cmit->parents[].generation) + 1`
  (however the `generation` is stored)

and then in the comparator, use this to exclude one of the comparisons
at least. However…

> We do all of this already for the "--topo-order" option of the revision
> traversal machinery. If we have commit graphs, it can output in
> topographical order in a streaming way (see init_topo_walk() in
> revision.c). If not, then we collect all of the commits up front and
> call sort_in_topological_order().

The key here seems to be:

	if (revs->topo_order && !generation_numbers_enabled(the_repository))
		revs->limited = 1;

which then goes down the `sort_in_topological_order` path.

> Sadly, git-describe does not seem to use the traversal machinery, so it
> is not as easy as just setting revs.topo_order. Either we have to adapt
> to using the regular traversal code, or those same concepts need to be
> applied to its custom traversal.

I suppose I can try to convert it over to a proper walk following
`MyFirstObjectWalk.adoc` if that is a more fruitful path than the above
ideas. As long as all children of a commit are walked before the commit
itself, it should slot into the existing bookkeeping fairly well.

Thanks,

--Ben