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

Junio C Hamano [off-list ref] writes:

The objective of this second traversal is very different from the
first one, though.  We do not need _all_ the merge bases between '1'
and '2'; we do not even need merge bases.

The only thing we need to prove that '1' is a merge base (i.e. not
an ancestor of any other merge base candidates the first round of
traversal between A and B found) is to do the first round of the
traversal for '1' as "one" and all the other ('2' in this case) as
"two"s; if the first round of such traversal finishes without
painting '1' in both colors, that would mean '1' is not reachable
from any other candidates of merge base between A and B, so we have
proven that '1' is a merge base.

So I suspect that the postprocess phase could be made from N*(N-1)
to N (run merge_bases_many() once for each of the common ancestor
the first round found).  You might also be able to stop the
traversal used in the first phase (i.e. get_merge_bases()) a bit
earlier, if we are digging through '1' to paint 'z' (and eventually
'2') in STALE (amber+blue) color, as digging further only to paint
things in STALE color is not necessary with the postprocess.

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.