Thomas Rast <> writes:

> I'm also mildly surprised that it ended up being correct, albeit with
> some extra work from you :-)

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.
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to
More majordomo info at

Reply via email to