Re: topological index field for commit objects

From: Jeff King <peff@peff.net>
Date: Jun 29, 2016, 22:00 UTC
Message-ID: <20160629220049.GA4416@sigill.intra.peff.net>
In-Reply-To: <5774426F.3090000@gmail.com>

On Wed, Jun 29, 2016 at 11:49:35PM +0200, Jakub Narębski wrote:

Show 7 quoted lines

> > So this is the ideal case for generation numbers (the worst cases are
> > when the things you are looking for are in branchy, close history where
> > the generation numbers don't tell you much; but in such cases the
> > walking is usually not too bad).
> 
> There are other approaches (special indices) that help reachability
> queries beside "generation number".

Yes, though generation numbers can help with more questions (e.g., "what is the merge base").

> By the way, what should happen if you add a replacement (in the git-replace
> meaning) that creates a shortcut, therefore invalidating generation numbers,
> at least in strict sense - committerdate as generation number would be still
> good, I think?

This is one of the open questions. My older patches turned them off when replacements and grafts are in effect.

Show 9 quoted lines

> > I have patches that generate and store the numbers at pack time, similar
> > to the way we do the reachability bitmaps. They're not production ready,
> > but they could probably be made so without too much effort. You wouldn't
> > have ready-made generation numbers for commits since the last full
> > repack, but you can compute them incrementally based on what you do have
> > at a cost linear to the unpacked commits (this is the same for bitmaps).
> 
> Do Git use EWAH / EWOK bitmaps for reachability analysis, or is it still
> limited to object counting?

At GitHub we are using them for --contains analysis, along with mass ahead/behind (e.g., as in https://github.com/gitster/git/branches). My plan is to send patches upstream, but they need some cleanup first.

-Peff