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

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

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