On Mon, Jul 1, 2013 at 10:01 PM, Jeff King <peff@xxxxxxxx> 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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html