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