Re: topological index field for commit objects

["Jakub Narębski" <jnareb@gmail.com>]

W dniu 2016-07-05 o 13:43, Johannes Schindelin pisze:
> 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