From: Junio C Hamano <gitster@pobox.com>
Date: Sun, 03 Feb 2008 08:18:06 GMT
Subject: Re: [RFH] revision limiting sometimes ignored
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.