Johannes Schindelin <Johannes.Schindelin@xxxxxx> writes: > Having said that, the change I suggested (to use `get_reachable_subset()` > instead of repeated `in_merge_bases_many()`) is _still_ the right thing to > do: we are not actually interested in the merge bases at all, but in > reachability, and in the future there might be more efficient ways to > determine that than painting down all the way to merge bases. I agree with you that the age-old implementation has an obvious room for optimization. I think I already pointed out a #leftoverbit that we can invent a version of paint_down_to_common() that can short-circuit and return immediately after one side (the "commit" side) gets painted, so that in_merge_bases_many() can stop immediately after finding out that the answer is "true". The function is *not* about computing the merge base across the commits on the "reference" side but finding out if "commit" is reachable from any in the "reference" side, so (1) it has a wrong name and more importantly (2) it wants to do something quite similar to get_reachable_subset(), but it is much less ambitious. get_reachable_subset() is capable of doing a lot more. Unlike the older in_merge_bases_many() that allowed only one commit on the candidate for an ancestor side, it can throw a set and ask "which ones among these are reachable from the other set". So from the "semantics" point of view, get_reachable_subset() is overkill and less suitable than in_merge_bases_many() for this particular application. We know we have only one candidate, and we want to ask "is this reachable, or not?" a single bit question. In any case, they should yield the right answer from correctness point of view ;-) Having said that. I do not think in the longer term we should keep both. Clearly the get_reachable_subset() function can handle more general cases, so it would make a lot of sense to make in_merge_bases_many() into a thin wrapper that feeds just a single commit array on one side to be filtered while feeding the "reference" commits to the other side, as long as we can demonstrate that the result is just as correct as, and it is not slower than, the current implementation. That may be a bit larger than a typical #leftoverbit but would be a good clean-up project.
