Re: How to still kill git fetch with too many refs

On Mon, Jul 1, 2013 at 10:01 PM, Jeff King [off-list ref] wrote:

On Tue, Jul 02, 2013 at 12:41:51AM -0400, Jeff King wrote:

quoted

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