Subject: Re: What's cooking in git.git (topics)

From: "Shawn O. Pearce" <[email-masked]>
Date: Thu, 11 Jan 2007 05:08:00 -0500

Junio C Hamano <[email-masked]> wrote:
> I looked at the algorithm, and after scratching my head for a
> while, I finally found it sane (modulo leaks, which I think I
> fixed with the attached patch).

Thanks.  I don't think it says much for the quality of my code
if you had to scratch your head before you understood it.  But
at least you finally got it.  :)
 
> One minor problem that you inherited from the original algorithm
> is the name priority.  If you have an annotated tag A and a
> lightweight tag b, and ask "git describe --tags" in this graph:
> 
>     ---o---o---o---o---x
>            A   b
> 
> you would still want to describe 'x' with A, not b.
> Unfortunately you don't (and the original doesn't either).

Actually I think you want to describe it with b.  If you ask
'--tags' then you want the lightweight ones too.  In the case above
the lightweight tag b better describes x as it has more in common
with x than A has.

> I think this is probably easy to solve in the loop that finds
> "all_matches"; once you hit an annotated tag, your traversal
> should stop in any case.  But if you were asked for --tags, and
> if your "initialized" piece did find both lightweight and
> annotated tags, you do not stop when you saw a lightweight one,
> but keep looking for an annotated one, ignoring any further
> lightweight ones.

I just implemented this in that loop, and then realized what
I wrote above.  The lower loop that performs the revision list
traversal would have both A and b in all_matches and b would win,
as its closer to x.  So having the first loop abort when it does
is the right thing to do, and so is describing x with b.

> Another thought.  I often do "git describe maint master next
> pu", and I see an opportunity for optimizing for such a
> multi-ref query.  Once you traversed the commits in
> "all_matches" loop, you know which strands of pearls are
> reachable to what tags, so you could hang that information
> somewhere (perhaps ->utils) in each commit.  But I think
> optimizing for a multi-ref query is probably not worth it.

Without my patch its ~170ms; with my patch its ~1000ms.  That is
a huge difference for such a simple program.  I'm not sure your
optimization will make a big difference.  The bulk of the cost
appears to be in the later loop, not in the earlier one that
produces all_matches.

-- 
Shawn.