Re: Why is "git tag --contains" so slow?

From: Nicolas Pitre <nico@fluxnic.net>
Date: Jul 8, 2010, 19:29 UTC
Message-ID: <alpine.LFD.2.00.1007081515030.6020@xanadu.home>
In-Reply-To: <m37hl6mdnb.fsf@localhost.localdomain>

On Thu, 8 Jul 2010, Jakub Narebski wrote:

Show 18 quoted lines

> Theodore Tso <tytso@MIT.EDU> writes:
> > On Jul 7, 2010, at 1:45 PM, Jeff King wrote:
> > 
> > >     And of course it's just complex, and I tend to shy away from
> > >     complexity when I can. The question to me comes back to (1) above.
> > >     Is massive clock skew a breakage that should produce a few
> > >     incorrect results, or is it something we should always handle?
> > 
> > Going back to the question that kicked off this thread, I wonder if there
> > is some way that cacheing could be used to speed up the all cases,
> > or at lest the edge cases, without imposing as much latency as tracking
> > the max skew?   i.e., some thing like gitk's gitk.cache file.  For bonus
> > points, it could be a cache file that is used by both gitk and git tag
> > --contains, git branch --contains, and git name-rev.
> > 
> > Does that sound like reasonable idea?
> 
> By the way, what had happened to the rev-cache project from GSoC 2009?

I think the person who worked on it did so in good faith, and that the result is well done.

But I personally cannot convince myself this is fundamentally the right solution to the issue. Maintaining another data structure to work around defficiencies in the primary data structure doesn't sound right to me.

I might be looking at this from my own perspective as one of the few people who hacked extensively on the Git pack format from the very beginning. But I do see a way for the pack format to encode commit and tree objects so that walking them would be a simple lookup in the pack index file where both the SHA1 and offset in the pack for each parent can be immediately retrieved. Same for tree references. No deflating required, no binary search, just simple dereferences. And the pack size would even shrink as a side effect.

Nicolas