git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Junio C Hamano <gitster@pobox.com>
Date
Jul 2, 2013, 05:19 UTC
Message-ID
<7vtxkd8rns.fsf@alter.siamese.dyndns.org>
In-Reply-To
<20130702050142.GA1206@sigill.intra.peff.net>
Jeff King <peff@peff.net> writes:
Show 13 quoted lines
> 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 ;-)
Previous: Jeff KingNext: Jeff King
Message 5 of 15 in “How to still kill git fetch with too many refs”
  1. Martin FickJul 2, 2013
  2. Jeff KingJul 2, 2013
  3. Jeff KingJul 2, 2013
  4. Jeff KingJul 2, 2013
  5. Junio C HamanoJul 2, 2013
  6. Jeff KingJul 2, 2013
  7. 0/3 avoid quadratic behavior in fetch-packJeff King, Jul 2, 2013
  8. 1/3 fetch-pack: avoid quadratic list insertion in mark_completeJeff King, Jul 2, 2013
  9. 2/3 commit.c: make compare_commits_by_commit_date globalJeff King, Jul 2, 2013
  10. 3/3 fetch-pack: avoid quadratic behavior in rev_list_pushJeff King, Jul 2, 2013
  11. Eric SunshineJul 2, 2013
  12. Martin FickJul 2, 2013
  13. Brandon CaseyJul 2, 2013
  14. Michael HaggertyJul 2, 2013
  15. Martin FickJul 2, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.