From: Junio C Hamano <gitster@pobox.com>
Date: Thu, 23 Aug 2012 18:08:46 GMT
Subject: Re: in_merge_bases() is too expensive for recent "pu" update
Message-ID: <7vd32h4h1t.fsf@alter.siamese.dyndns.org>
In-Reply-To: <878vd5k7uu.fsf@thomas.inf.ethz.ch>

Thomas Rast <trast@student.ethz.ch> writes:

> At the very least it should be possible to change in_merge_bases() to
> not do any of the post-filtering; perhaps like the patch below.

I do not recall the details but the post-filtering was added after
the initial naive version without it that was posted to the list did
not work correctly in corner cases.  I wouldn't doubt that N*(N-1)
loop can be optimized to something with log(N), but I offhand find
it hard to believe "to not do any" could be correct without seeing
more detailed analysis.