Re: in_merge_bases() is too expensive for recent "pu" update

[Thomas Rast <trast@student.ethz.ch>]

Junio C Hamano <gitster@pobox.com> writes:

> As a corollary, the "is pu@{0} a fast-forward of pu@{1}?" check does
> not need merge base computation at all.  The only thing it needs to
> do is to prove pu@{1} is reachable from pu@{0}, and that can be done
> the same way in which '1' can be proved unreachable from '2' in the
> post processing phase as described above, i.e. it needs only the
> first phase of running merge_bases_many() without postprocessing.

Well, yeah, you snipped this part from my original post :-)

} Even if this turns out to be flawed, we should also identify uses of
} in_merge_bases() where the real question was is_descendant_of() [I
} somewhat suspect that's all of them], and then replace is_descendant_of
} with a much cheaper lookup.  This can be as simple as propagating a mark
} from the candidate until it either goes beyond all possible ancestors,
} or hits one of them.

As far as the "real question" goes, I'm purely guessing here -- it is
entirely possible that a bunch of the in_merge_bases() checks really do
need the pruned set of merge bases.  But this particular check, and I
suspect a bunch of others, does not.

Then there's the next bit:

} By the way, the internal slowness of git-merge-base also affects the
} A...B syntax.  For example,
} 
}   git rev-list --left-right --count @{upstream}...
} 
} is used by the __git_ps1 code to determine the prompt display, which
} just got very slow for me today.  Again, it should be easy to figure out
} the boundary of the symmetric difference simply by propagating two
} marks.  I do not think that the result of A...B actually depends on
} figuring out exactly what the merge bases are, simply excluding *any*
} candidate without pruning is enough.

Apart from __git_ps1, this is also used by git-status, git-checkout and
'git branch -v' to show "your branch is N behind and M ahead".  Again
it's a bit of a hunch, but I think figuring out the symmetric difference
is a simple matter of propagating two marks and including only commits
that ended up having exactly one of them.  At least the counting case
should be easy, rev-list is slightly harder to fix.

-- 
Thomas Rast
trast@{inf,student}.ethz.ch