From: Junio C Hamano Date: Thu, 05 Aug 2010 18:22:37 GMT Subject: Re: jk/tag-contains (Re: What's cooking in git.git (Jul 2010, #05; Wed, 28)) Message-ID: <7vd3twex76.fsf@alter.siamese.dyndns.org> In-Reply-To: <20100805175640.GB15760@sigill> Jeff King writes: > 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.