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

From: Shawn O. Pearce <spearce@spearce.org>
Date: Jan 11, 2007, 10:08 UTC
Message-ID: <20070111100800.GB28309@spearce.org>
In-Reply-To: <7v1wm16gyd.fsf@assigned-by-dhcp.cox.net>

Junio C Hamano <junkio@cox.net> 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.  :)

Show 9 quoted lines

> 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.

Show 7 quoted lines

> 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.

Show 7 quoted lines

> 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.