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

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

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.