Re: topological index field for commit objects

From: Jeff King <peff@peff.net>
Date: Jun 29, 2016, 22:30 UTC
Message-ID: <20160629223007.GA4726@sigill.intra.peff.net>
In-Reply-To: <xmqqlh1n1w84.fsf@gitster.mtv.corp.google.com>

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

Show 11 quoted lines

> 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