Re: [RFH] revision limiting sometimes ignored

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 3, 2008, 08:18 UTC
Message-ID: <7vir16xxkx.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <20080203071833.GA16273@coredump.intra.peff.net>

Jeff King <peff@peff.net> writes:

> There is probably a performance impact since we will end up traversing
> the whole commit chain just to mark them all uninteresting.

Yes. "tip..initial" obviously need to traverse almost all history to find out that the initial is reachable from tip, but there is no avoiding that.

However, a typical usage is "old..new" and old and new are both far from the initial commit, and forcing traversal down to the initial commit in such a usual case is unacceptable.

I think we only need to traverse down to their merge bases to prove that new cannot be reachable from old, and we can find out all of their merge bases without traversing down to root.