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
Brandon Casey <drafnel@gmail.com>
Date
Jul 2, 2013, 17:52 UTC
Message-ID
<CA+sFfMf4Y2zPYhewADxJyR8DR5aAsa89+PW2UDNp3zSsXqjUHA@mail.gmail.com>
In-Reply-To
<20130702050142.GA1206@sigill.intra.peff.net>
On Mon, Jul 1, 2013 at 10:01 PM, Jeff King <peff@peff.net> wrote:
Show 11 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,
<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
Previous: Martin FickNext: Michael Haggerty
Message 13 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.