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

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 24, 2012, 16:15 UTC
Message-ID: <7vobm01d1f.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20120824151511.GB15162@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 7 quoted lines

> 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().

Show 6 quoted lines

> 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.