From: Jeff King <peff@peff.net>
Date: Tue, 02 Jul 2013 04:41:51 GMT
Subject: Re: How to still kill git fetch with too many refs
Message-ID: <20130702044151.GB7068@sigill.intra.peff.net>
In-Reply-To: <20130702040758.GA7068@sigill.intra.peff.net>

On Tue, Jul 02, 2013 at 12:07:58AM -0400, Jeff King wrote:

> And yet another alternative would be to keep the list unsorted during
> the mark_complete calls, and then sort it at the end. Like this:

Amusingly, I seem to have posted the exact same patch last year:

  http://article.gmane.org/gmane.comp.version-control.git/194939

but never polished it up. It does cut a little time off of the initial
ref-loading that fetch-pack does (especially when we do not end up
transferring any objects at all). But it does not solve your problem.

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

-Peff