As the author of much of `git describe` in C... this isn't the most optimal algorithm. A better approach is to allocate a RevFlag from the RevWalk. Loop through each tag. Parse the tag reference to a commit... if it is a commit, add the RevFlag to it.

Now start from the starting point and walk backwards through history. When RevWalk.next() returns a commit that has your RevFlag, you have found a candidate. Mark the history behind that tag UNINTERESTING and keep going until the RevWalk stops.

If multiple candidates are found, I think you use the one with the largest distance (see below).

I may be forgetting some other isoteric rules related to not picking up the release tag on a maint branch when this is the master branch and there is an -rc tag a further number of commits back, but that is "version number wise" more recent. I think this is why you use the largest distance between a commit and the tag.

IIRC I managed to do the entire thing in just 1 reversion traversal in the C code, with a few commits extra being walked to finish up the counting.

Also as you mention on the commit message, there is a tendency to favor annotated tags over lightweight ones.