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

[Jeff King <peff@peff.net>]

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

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