Jeff King <> writes:

> I thought you were just interested in speeding up is_descendent_of. You
> should be able to do that without a generation number. Just start from A
> and B as above, do the two-color painting, and do not add the parents of
> any two-color commits (because you know they are ancestors of both, and
> therefore you cannot find either by looking backwards). If you paint "B"
> amber, then it is a descendent of "A" (and vice versa if you paint "A"
> blue).

Yes, that is what merge_bases_many() (the one without the post
processing to cull candidates) is primarily doing.  The function
also does the "STALE" bit processing that aims to reduce the number
of candidates in "no clock skew" cases with minimum effort, to
mimimize the cost of get_merge_bases_many() in the post-processing
phase, but removing the "STALE" bit processing shouldn't affect the
correctness of get_merge_bases_many() and would help performance of
merge_bases_many() proper, which is useful for is_descendant_of().

> The reason I did not do that for "tag --contains" is that I wanted to
> do a simultaneous walk for all tags. That would require N color bits for
> N tags, and we have a limited space in each commit object. I didn't time
> using a separate hash table to store those bits outside of the commit
> objects. That would have a higher constant, but should still yield good
> big-O complexity.

It may not be a bad idea to at least try and see the performance
implications of moving many users of object->flags to a new
implementation of per-purpose flag bits based on the decoration
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