Re: jk/tag-contains (Re: What's cooking in git.git (Jul 2010, #05; Wed, 28))

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 5, 2010, 18:22 UTC
Message-ID: <7vd3twex76.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20100805175640.GB15760@sigill>

Jeff King <peff@peff.net> writes:

Show 8 quoted lines

> That's basically a finer-grained version of what I implemented. Mine
> finds the _worst_ skew for the whole graph, and never lets you optimize
> a traversal cutoff more than that skew. So it is nicely bounded
> space-wise, as it is always a single integer, but you waste effort on
> the entire traversal because a couple of commits are skewed. Yours
> optimizes perfectly, but needs O(skewed commits) storage. Which is
> probably a better tradeoff when the number of skewed commits is tiny
> (which is what we expect).

One thing missing from the above equation is that O(skewed commits) approach will need O(number of commits) look-ups in the skew database (be it a notes tree or whatever), only to make sure that most of the look-ups say "no timestamp tweak required". So I think the global single integer approach you took would probably be better in the overall picture.