[PATCH 4/4] describe: stop traversing when we run out of names

When trying to describe a commit, we'll traverse from the commit, collecting candidate tags that point to its ancestors. But once we've seen all of the tags in the repo, there's no point in traversing further. There's nothing left to find!

For a default "git describe", this isn't usually a big problem. In a large repo you'll probably have multiple tags, so we'll eventually find 10 candidates (the default for max_candidates) and stop there. And in a small repo, it's quick to traverse to the root.

But you can imagine a large repo with few tags. Or, as we saw in a real world case, explicitly limiting the set of matches like this (on linux.git):

  git describe --match=v6.12-rc4 HEAD

which goes all the way to the root before realizing that no, there are no other tags under consideration besides the one we fed via --match. If we add in "--candidates=1" there, it's much faster (at least as of the previous commit).

But we should be able to speed this up without the user asking for it. After expanding all matching tags, we know the total number of names. We could just stop the traversal there, but as hinted at above we already have a mechanism for doing that: the max_candidate limit. So we can just reduce that limit to match the number of possible candidates.

Our p6100 test shows this off:

  Test                                           HEAD^             HEAD
  ---------------------------------------------------------------------------------------
  6100.2: describe HEAD                          0.71(0.65+0.06)   0.72(0.68+0.04) +1.4%
  6100.3: describe HEAD with one max candidate   0.01(0.00+0.00)   0.01(0.00+0.00) +0.0%
  6100.4: describe HEAD with one tag             0.72(0.66+0.05)   0.01(0.00+0.00) -98.6%

Now we are fast automatically, just as if --candidates=1 were supplied by the user.

Reported-by: Josh Poimboeuf <jpoimboe@kernel.org>
Helped-by: Rasmus Villemoes <ravi@prevas.dk>
Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/describe.c | 2 ++
 1 file changed, 2 insertions(+)