From: Brandon Casey <drafnel@gmail.com>
Date: Tue, 02 Jul 2013 17:52:47 GMT
Subject: Re: How to still kill git fetch with too many refs
Message-ID: <CA+sFfMf4Y2zPYhewADxJyR8DR5aAsa89+PW2UDNp3zSsXqjUHA@mail.gmail.com>
In-Reply-To: <20130702050142.GA1206@sigill.intra.peff.net>

On Mon, Jul 1, 2013 at 10:01 PM, Jeff King <peff@peff.net> wrote:
> On Tue, Jul 02, 2013 at 12:41:51AM -0400, Jeff King wrote:
>
>> I replicated your test setup, and the problem is that we have many
>> common objects on both sides during the ref negotiation. So we end up in
>> rev_list_push for each one, which has the same O(n^2) behavior.
>> Switching it to just sort at the end is not trivial; we first insert all
>> of the objects, but then we actually walk the parents, pushing onto the
>> list as we go. So I think we'd want a better data structure (like a
>> priority queue).
>
> Like the patch below,

<snip>

Looks obviously correct to me since I've got essentially the same
patch sitting in my local repo. :b

I've got the patch coming that fixes the same problem on the push side
of things and provides the same order of magnitude improvement.

-Brandon