Re: git describe --contains doesn't work properly for a commit

From: Jeff King <peff@peff.net>
Date: Mar 4, 2015, 18:05 UTC
Message-ID: <20150304180529.GA28074@peff.net>
In-Reply-To: <54F71F69.3080500@drmicha.warpmail.net>

On Wed, Mar 04, 2015 at 04:06:17PM +0100, Michael J Gruber wrote:

Show 12 quoted lines

> >   3. Introduce a more trust-worthy mechanism for ordering commits. The
> >      timestamp here is really just a proxy for the oft-discussed
> >      "generation number" of the commit within the graph. We've avoided
> >      adding generation numbers because of the storage/complexity issues.
> 
> Hmmh.
> 
> Storage: one int (or maybe less) per commit doesn't sound too bad. We
> can probably do without on bare repos by default.
> 
> Complexity: Was that due to replace refs? Other than that, it seemed to
> be simple: max(parent generation numbers)+1.

Calculating them is simple. Caching and storage is the bigger question. When we do we generate them? Where do we store them? What do we do with replace-refs and grafts?

I think the answers are "at repack time", "in an auxiliary file alongside the pack idx", and "we turn it off completely when these features are in use".

See:

  http://thread.gmane.org/gmane.comp.version-control.git/214916

for a sample implementation.

> ... or can reachability bitmaps help???

Sometimes. If you are asking about --contains traversals, then bitmaps can let you stop the traversal early. We have some patches that do this that are running in production at GitHub, but they are kind of gnarly. One of my goals is to clean them up and get them upstream.

It's also part of why I didn't pursue the series above further. Making "--contains" faster is one goal, but making "rev-list --objects --all" faster was more important (since we do it for every fetch). And making commits faster is only half the equation there.

-Peff