From: Junio C Hamano Date: Tue, 02 Jul 2013 05:19:51 GMT Subject: Re: How to still kill git fetch with too many refs Message-ID: <7vtxkd8rns.fsf@alter.siamese.dyndns.org> In-Reply-To: <20130702050142.GA1206@sigill.intra.peff.net> Jeff King writes: > 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, which is built on top of next (which has Junio's > prio_queue implementation), and has both the priority queue fix for > rev_list_push and the mark_complete sort-at-the-end fix. Wow, I saw "160 lines" in my MUA which scared me a bit until I opened it to realize 40% is discussion and most of the remaining lines are context around single liners. It just looks too easy/simple, but the result looks correct, at least from a cursory read. Good job ;-)