Re: [PATCH 6/8] commit: provide a fast multi-tip contains function

Junio C Hamano [off-list ref] writes:

I forgot about the other direction, i.e. "branch --merged $commit".
Since I do "git branch --no-merged pu" fairly often, I care about
its performance ;-)

We paint $commit as Left, and tips of all the branches as Right.  We
try to paint down from $commit but the traversal cannot terminate if
it reaches a commit that is reachable from one Right ref---we may
find that we can reach more Right refs by following its ancestor.
We can stop when we paint Right bits fully, of course, but I wonder
if we can do better than that.

Suppose we just painted a commit with L and Rn bit (i.e. the commit
is a common ancestor of the $commit and one branch).  We know that
traversing down from there will never reach the tip of the branch
whose color is Rn (otherwise we will have a cycle from that commit
back to the tip of the branch), so if the reason we are continuing
the traversal is to prove that the tip of the branch Rn is reachable
(or unreachable) from $commit, there is no reason to continue
digging from there.  Can we exploit that to terminate the traversal
earlier?

I forgot to mention this case because with "branch --no-merged pu"
it never happens, but another clue we can terminate traversal earier
with is when $commit is found to be an ancestor of some Right
commits.  Then we can start ignoring Rn bits for these Right commits
that can reach the Left one, as we know they can never be reached
from the Left.  That is, the last sentence in the paragraph ...

When we encounter a new commit that is painted with L bit and some
but not necessarily all R bits, we propagate the bits and check the
R bits.  Some of the commits in Right set that correspond to R bits
may have been painted in L (i.e. we found branches that are merged
to $commit), and digging further from this commit will not give us
any new information.  Other commits are not painted in L (i.e. we do
not yet know if $commit merges these branches), so we may need to
keep digging.  So perhaps we can stop if a commit is painted in L
and also has all the R bits that correspond to Right commits that
are not yet proven reachable from $commit (i.e. not painted in L)?

... will be more like "ignore Rn bits for Right commits that are
painted in L (i.e. they are reachable from L) or the Left commit is
painted with (i.e. they reach L)".