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
Jeff King <peff@peff.net>
Date
Jul 2, 2013, 04:41 UTC
Message-ID
<20130702044151.GB7068@sigill.intra.peff.net>
In-Reply-To
<20130702040758.GA7068@sigill.intra.peff.net>
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
Previous: Jeff KingNext: Jeff King
Message 3 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.