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

Thomas Rast <trast@inf.ethz.ch> writes:

I actually am not all that surprised. It just shows that the original code was layered in more or less the right way. At the the bottom layer we would want a way to paint graph down to common ancestors cheaply, and then on top we want to have a way to filter out the redundant ones. It is a different story that the implementation of individual layers may still have rooms for improvements (just like the last patch in my series showed for the upper layer where we used to do N * (N-1) when we only needed N).

I have a suspicion that the merge_bases_many() at the bottom layer could be built on an even cheaper API. This caller you added does not need "bases" list returned; it only wants to see that ancestors of "commit" and "reference" down to their common ancestors are painted in two colors PARENT1 and PARENT2. Instead of iterating over the returned candidate list, we might be able to do

	common = PARENT1 | PARENT2;
	paint_ancestors(commit, 1, reference);
        commit_is_common = ((commit->object.flags & common) == common);
        clear_commit_marks(commit, all_flags);
        clear_commit_marks(*reference, all_flags);

where paint_ancestors() just paints but does not accumlate to return a commit_list. Note that paint_ancestors() need to always paint its arguments (merge_bases_many() has an early special case to return a list that only has "commit" when it appears in "reference" without painting anything, and the callers like get_merge_bases_many() know this to avoid calling clear_commit_marks()) if we are to go in this direction, so it is unclear if it will be overall gain.