Re: topological index field for commit objects

[Jeff King <peff@peff.net>]

On Wed, Jun 29, 2016 at 03:11:39PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > Yes, though generation numbers can help with more questions (e.g., "what
> > is the merge base").
> 
> Hmm, how?  I have two commits, with generation number 38 and 47,
> respectively.  What generation number does the commit that is the
> merge base of these two commits?
> 
> I know we can say that 38 cannot possibly be a descendant of 47, but
> can we say anything else that is useful?

I don't think it can give you the answer immediately from those values,
but in general generation numbers help you bound actual traversals and
avoid walking down unproductive paths. So comparing 38 and 47 is not
nearly as useful as walking from 47 down to 37 and saying "I know that I
cannot possibly reach 38 by walking further".

I haven't thought hard specifically about merge bases computation, so
perhaps that is a case that isn't helped at all. It has been a while
since I've looked into this, but I recall there were some computations
that are hard to improve with bitmaps. I may also simply be
mis-remembering; in my patches generations were tightly tied to having a
packv4-style cache of commit properties that can be used rather than
inflating the commit object itself. That cache helps any time you walk
by speeding up the parse_commit() process. But it's a per-commit
speedup. It doesn't change the algorithmic complexity of what you're
doing.

-Peff