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

Jeff King [off-list ref] 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
infrastracture.