Re: topological index field for commit objects

From: Jakub Narębski <jnareb@gmail.com>
Date: Jul 5, 2016, 12:59 UTC
Message-ID: <577BAF3C.90601@gmail.com>
In-Reply-To: <alpine.DEB.2.20.1607051339040.8378@virtualbox>

W dniu 2016-07-05 o 13:43, Johannes Schindelin pisze:

Show 11 quoted lines

> On Wed, 29 Jun 2016, Jeff King wrote:
> 
>> I haven't thought hard specifically about merge bases computation, so
>> perhaps that is a case that isn't helped at all.
> 
> I guess it is not helped by generation numbers.
> 
> But then, we often ask: "is commit A an ancestor of commit B" e.g. to
> check whether we can fast-forward. The way we do it now is to compute the
> merge base (singular: if there are more than one, we stop at the first one
> we found) and then look whether commit A is identical to the merge base.

I wonder if this query can be answered faster than finding the merge base (the common ancestor) with Git core, and if it would be worth it to expose this functionality to shell...

> If we had generation numbers available, then we would have to change those
> computations in order to benefit from them when determining ancestry.

Generation numbers (node level / topological rank) can help with such query. First, if level of A is greater than level of B, then A cannot be an ancestor of B. Second, when following from B we can prune path if we get to node with level lower than A. This is so called "level filter" in literature.

FELINE indices cut search space even more... though I don't know if they would help with finding common ancestors. Perhaps some other technique would be better (taking into account Git use of EWAH bitmaps for reachability of objects).

> 
> But then, reachability would accelerate that even more than generation
> numbers.

I wonder if Git uses bitmap indices here, if possible -- they are generated sparsely. They can help both in reachability queries (is A in reachability of B, or in reachability of one of ancestors of B?) and in finding merge bases (intersection of reachabilities of A and B, or their ancestors... or something like that, I think, probably more complicated).

-- 
Jakub Narębski