{"thread":{"id":"34321","subject":"How to still kill git fetch with too many refs","startedAt":"2013-07-02T03:02:31Z","lastAt":"2013-07-02T17:52:47Z","messageCount":15,"participants":["Martin Fick","Jeff King","Junio C Hamano","Eric Sunshine","Michael Haggerty","Brandon Casey"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"222330","messageId":"201307012102.31384.mfick@codeaurora.org","threadId":"34321","inReplyTo":null,"subject":"How to still kill git fetch with too many refs","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-07-02T03:02:31Z","receivedAt":"2013-07-02T03:02:31Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"I have often reported problems with git fetch when there are \nmany refs in a repo, and I have been pleasantly surprised \nhow many problems I reported were so quickly fixed. :) With \ntime, others have created various synthetic test cases to \nensure that git can handle many many refs.  A simple \nsynthetic test case with 1M refs all pointing to the same \nsha1 seems to be easily handled by git these days.  However, \nin our experience with our internal git repo, we still have \nperformance issues related to having too many refs, in our \nkernel/msm instance we have around 400K.\n\nWhen I tried the simple synthetic test case and could not \nreproduce bad results, so I tried something just a little \nmore complex and was able to get atrocious results!!! \nBasically, I generate a packed-refs files with many refs \nwhich each point to a different sha1.  To get a list of \nvalid but unique sha1s for the repo, I simply used rev-list.  \nThe result, a copy of linus' repo with a million unique \nvalid refs and a git fetch of a single updated ref taking a \nvery long time (55mins and it did not complete yet).  Note, \nwith 100K refs it completes in about 2m40s.  It is likely \nnot linear since 2m40s * 10 would be ~26m (but the \ndifference could also just be how the data in the sha1s are \nordered).\n\n\nHere is my small reproducible test case for this issue:\n\ngit clone \ngit://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git\ncp -rp linux linux.1Mrefs-revlist\n\ncd linux\necho \"Hello\" > hello ; git add hello ; git ci -a -m 'hello'\ncd ..\n\ncd linux.1Mrefs-revlist\ngit rev-list HEAD | for nn in $(seq 0 100) ; do for c in \n$(seq 0 10000) ; do  read sha ; echo $sha refs/c/$nn/$c$nn ; \ndone ; done > .git/packed-refs\n\ntime git fetch file:///$(dirname $PWD)/linux \nrefs/heads/master\n\nAny insights as to why it is so slow, and how we could \npossibly speed it up?\n\nThanks,\n\n-Martin\n\nPS: My tests were performed with git version 1.8.2.1 on \nlinux 2.6.32-37-generic #81-Ubuntu SMP \n\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n \n"},{"id":"222331","messageId":"20130702040758.GA7068@sigill.intra.peff.net","threadId":"34321","inReplyTo":"201307012102.31384.mfick@codeaurora.org","subject":"Re: How to still kill git fetch with too many refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-02T04:07:58Z","receivedAt":"2013-07-02T04:07:58Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 01, 2013 at 09:02:31PM -0600, Martin Fick wrote:\n\n> A simple synthetic test case with 1M refs all pointing to the same\n> sha1 seems to be easily handled by git these days.  However, in our\n> experience with our internal git repo, we still have performance\n> issues related to having too many refs, in our kernel/msm instance we\n> have around 400K.\n\nI'm not too surprised. There's O(n^2) behavior in fetch-pack's\nmark_complete function, as it adds each of the N ref tips to a\ncommit_list, sorting by date (so each insertion is O(n)).\n\nI posted two alternative patches in May of 2011.  The first simply\navoids adding duplicate objects, which is simple and covers many\nreal-world cases (e.g., an \"alternates\" repository which has a bunch of\ncopies of the same tags, one per fork). The second one switches the\ncommit_list out for a heap-based priority queue.\n\nWe ended up taking the first (as ea5f220), since it was trivial and\nobviously correct, but didn't bother with the second since:\n\n  1. There had been no real-world reports of it.\n\n  2. While in theory a priority queue implementation would be used in\n     other spots, too, it ended up being a pain to use it, as most of\n     the callers wanted list-like splicing.\n\nYou can see the original here:\n\n  http://thread.gmane.org/gmane.comp.version-control.git/174003/focus=174005\n\nThough it probably doesn't apply cleanly anymore.  However, I've kept it\nrebased over the years at:\n\n  git://github.com/peff/git.git jk/fast-commit-list\n\nJunio recently added a priority queue implementation in b4b594a\n(prio-queue: priority queue of pointers to structs, 2013-06-06), which\nis currently in next. So a modern version of that series would build on\ntop of that, rather than my priority queue.\n\nAnd yet another alternative would be to keep the list unsorted during\nthe mark_complete calls, and then sort it at the end. Like this:\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex abe5ffb..4df8abd 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -505,7 +505,7 @@ static int mark_complete(const char *refname, const unsigned char *sha1, int fla\n \t\tstruct commit *commit = (struct commit *)o;\n \t\tif (!(commit->object.flags & COMPLETE)) {\n \t\t\tcommit->object.flags |= COMPLETE;\n-\t\t\tcommit_list_insert_by_date(commit, &complete);\n+\t\t\tcommit_list_insert(commit, &complete);\n \t\t}\n \t}\n \treturn 0;\n@@ -622,6 +622,7 @@ static int everything_local(struct fetch_pack_args *args,\n \tif (!args->depth) {\n \t\tfor_each_ref(mark_complete, NULL);\n \t\tfor_each_alternate_ref(mark_alternate_complete, NULL);\n+\t\tcommit_list_sort_by_date(&complete);\n \t\tif (cutoff)\n \t\t\tmark_recent_complete_commits(args, cutoff);\n \t}\n\n(If you're wondering why we didn't do this trivial bit at the time, it\nwas because back then we did not yet have the René's nice linked-list\nmergesort that backs commit_list_sort_by_date).\n\n> The result, a copy of linus' repo with a million unique \n> valid refs and a git fetch of a single updated ref taking a \n> very long time (55mins and it did not complete yet).  Note, \n> with 100K refs it completes in about 2m40s.  It is likely \n> not linear since 2m40s * 10 would be ~26m (but the \n> difference could also just be how the data in the sha1s are \n> ordered).\n\nThat sounds like the O(n^2) problem. My timings back then with 100K refs\nwere 1-2 minutes. Does the patch above fix it for you?\n\n-Peff\n"},{"id":"222332","messageId":"20130702044151.GB7068@sigill.intra.peff.net","threadId":"34321","inReplyTo":"20130702040758.GA7068@sigill.intra.peff.net","subject":"Re: How to still kill git fetch with too many refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-02T04:41:51Z","receivedAt":"2013-07-02T04:41:51Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 02, 2013 at 12:07:58AM -0400, Jeff King wrote:\n\n> And yet another alternative would be to keep the list unsorted during\n> the mark_complete calls, and then sort it at the end. Like this:\n\nAmusingly, I seem to have posted the exact same patch last year:\n\n  http://article.gmane.org/gmane.comp.version-control.git/194939\n\nbut never polished it up. It does cut a little time off of the initial\nref-loading that fetch-pack does (especially when we do not end up\ntransferring any objects at all). But it does not solve your problem.\n\nI replicated your test setup, and the problem is that we have many\ncommon objects on both sides during the ref negotiation. So we end up in\nrev_list_push for each one, which has the same O(n^2) behavior.\nSwitching it to just sort at the end is not trivial; we first insert all\nof the objects, but then we actually walk the parents, pushing onto the\nlist as we go. So I think we'd want a better data structure (like a\npriority queue).\n\n-Peff\n"},{"id":"222333","messageId":"20130702050142.GA1206@sigill.intra.peff.net","threadId":"34321","inReplyTo":"20130702044151.GB7068@sigill.intra.peff.net","subject":"Re: How to still kill git fetch with too many refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-02T05:01:42Z","receivedAt":"2013-07-02T05:01:42Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 02, 2013 at 12:41:51AM -0400, Jeff King wrote:\n\n> I replicated your test setup, and the problem is that we have many\n> common objects on both sides during the ref negotiation. So we end up in\n> rev_list_push for each one, which has the same O(n^2) behavior.\n> Switching it to just sort at the end is not trivial; we first insert all\n> of the objects, but then we actually walk the parents, pushing onto the\n> list as we go. So I think we'd want a better data structure (like a\n> priority queue).\n\nLike the patch below, which is built on top of next (which has Junio's\nprio_queue implementation), and has both the priority queue fix for\nrev_list_push and the mark_complete sort-at-the-end fix. With this, your\ntest case completes in a few seconds (no clue if it would ever have\nfinished otherwise; I never let it run for more than a minute or two,\nbut I did confirm that it was spending all of its time in\ncommit_list_insert_by_date).\n\nI didn't look too hard at the actual semantics, so there might be away\nto not mark so many commits in the first place. This is just a mindless\nreplacement of an O(n^2) list insertion with the queue.\n\nI did note two oddities, though:\n\n  1. In the original, we never free the commit_list pointers when we pop\n     them (or when we clear the list in find_common. So I think the\n     existing code was leaking memory, and my version does not.\n\n  2. In the original version of get_rev, we \"peek\" at the head commit of\n     rev_list:\n\n               commit = rev_list->item;\n\n     Then we look at the parents of that commit, and possibly push them\n     onto rev_list:\n\n               while (parents) {\n                      if (!(parents->item->object.flags & SEEN))\n                              rev_list_push(parents->item, mark);\n                      ...\n               }\n\n     and then finally, \"pop\" the commit off the list:\n\n               rev_list = rev_list->next;\n\n     But what guarantee do we have that the commit we just processed is\n     still at the front of the list? If the timestamps are monotonic,\n     then the parent must come after the descendent and therefore will\n     not have gotten pushed onto the front of the list. But in the face\n     of clock skew, this is not the case, and we will have just skipped\n     over the parent with our \"pop\".\n\n     So unless I am missing something very clever, I think this was a\n     bug (albeit a difficult one to have matter). And it's also fixed by\n     using prio_queue (which does the peek/pop together at the top of\n     the function).\n\ndiff --git a/commit.c b/commit.c\nindex 521e49c..ebc0eea 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -581,7 +581,7 @@ static int compare_commits_by_author_date(const void *a_, const void *b_,\n \treturn 0;\n }\n \n-static int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n+int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n {\n \tconst struct commit *a = a_, *b = b_;\n \t/* newer commits with larger date first */\ndiff --git a/commit.h b/commit.h\nindex 4d452dc..18a5234 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -254,4 +254,6 @@ extern void check_commit_signature(const struct commit* commit, struct signature\n  */\n extern void check_commit_signature(const struct commit* commit, struct signature_check *sigc);\n \n+int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused);\n+\n #endif /* COMMIT_H */\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex abe5ffb..6684348 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -11,6 +11,7 @@\n #include \"run-command.h\"\n #include \"transport.h\"\n #include \"version.h\"\n+#include \"prio-queue.h\"\n \n static int transfer_unpack_limit = -1;\n static int fetch_unpack_limit = -1;\n@@ -37,7 +38,7 @@ static int marked;\n  */\n #define MAX_IN_VAIN 256\n \n-static struct commit_list *rev_list;\n+static struct prio_queue rev_list = { compare_commits_by_commit_date };\n static int non_common_revs, multi_ack, use_sideband, allow_tip_sha1_in_want;\n \n static void rev_list_push(struct commit *commit, int mark)\n@@ -49,7 +50,7 @@ static void rev_list_push(struct commit *commit, int mark)\n \t\t\tif (parse_commit(commit))\n \t\t\t\treturn;\n \n-\t\tcommit_list_insert_by_date(commit, &rev_list);\n+\t\tprio_queue_put(&rev_list, commit);\n \n \t\tif (!(commit->object.flags & COMMON))\n \t\t\tnon_common_revs++;\n@@ -122,10 +123,10 @@ static const unsigned char *get_rev(void)\n \t\tunsigned int mark;\n \t\tstruct commit_list *parents;\n \n-\t\tif (rev_list == NULL || non_common_revs == 0)\n+\t\tif (rev_list.nr == 0 || non_common_revs == 0)\n \t\t\treturn NULL;\n \n-\t\tcommit = rev_list->item;\n+\t\tcommit = prio_queue_get(&rev_list);\n \t\tif (!commit->object.parsed)\n \t\t\tparse_commit(commit);\n \t\tparents = commit->parents;\n@@ -152,8 +153,6 @@ static const unsigned char *get_rev(void)\n \t\t\t\tmark_common(parents->item, 1, 0);\n \t\t\tparents = parents->next;\n \t\t}\n-\n-\t\trev_list = rev_list->next;\n \t}\n \n \treturn commit->object.sha1;\n@@ -442,7 +441,7 @@ static int find_common(struct fetch_pack_args *args,\n \t\t\t\t\tin_vain = 0;\n \t\t\t\t\tgot_continue = 1;\n \t\t\t\t\tif (ack == ACK_ready) {\n-\t\t\t\t\t\trev_list = NULL;\n+\t\t\t\t\t\tclear_prio_queue(&rev_list);\n \t\t\t\t\t\tgot_ready = 1;\n \t\t\t\t\t}\n \t\t\t\t\tbreak;\n@@ -505,7 +504,7 @@ static int mark_complete(const char *refname, const unsigned char *sha1, int fla\n \t\tstruct commit *commit = (struct commit *)o;\n \t\tif (!(commit->object.flags & COMPLETE)) {\n \t\t\tcommit->object.flags |= COMPLETE;\n-\t\t\tcommit_list_insert_by_date(commit, &complete);\n+\t\t\tcommit_list_insert(commit, &complete);\n \t\t}\n \t}\n \treturn 0;\n@@ -622,6 +621,7 @@ static int everything_local(struct fetch_pack_args *args,\n \tif (!args->depth) {\n \t\tfor_each_ref(mark_complete, NULL);\n \t\tfor_each_alternate_ref(mark_alternate_complete, NULL);\n+\t\tcommit_list_sort_by_date(&complete);\n \t\tif (cutoff)\n \t\t\tmark_recent_complete_commits(args, cutoff);\n \t}\n"},{"id":"222337","messageId":"7vtxkd8rns.fsf@alter.siamese.dyndns.org","threadId":"34321","inReplyTo":"20130702050142.GA1206@sigill.intra.peff.net","subject":"Re: How to still kill git fetch with too many refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-02T05:19:51Z","receivedAt":"2013-07-02T05:19:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Tue, Jul 02, 2013 at 12:41:51AM -0400, Jeff King wrote:\n>\n>> I replicated your test setup, and the problem is that we have many\n>> common objects on both sides during the ref negotiation. So we end up in\n>> rev_list_push for each one, which has the same O(n^2) behavior.\n>> Switching it to just sort at the end is not trivial; we first insert all\n>> of the objects, but then we actually walk the parents, pushing onto the\n>> list as we go. So I think we'd want a better data structure (like a\n>> priority queue).\n>\n> Like the patch below, which is built on top of next (which has Junio's\n> prio_queue implementation), and has both the priority queue fix for\n> rev_list_push and the mark_complete sort-at-the-end fix.\n\nWow, I saw \"160 lines\" in my MUA which scared me a bit until I\nopened it to realize 40% is discussion and most of the remaining\nlines are context around single liners.\n\nIt just looks too easy/simple, but the result looks correct, at\nleast from a cursory read.\n\nGood job ;-)\n"},{"id":"222338","messageId":"20130702052827.GA10626@sigill.intra.peff.net","threadId":"34321","inReplyTo":"7vtxkd8rns.fsf@alter.siamese.dyndns.org","subject":"Re: How to still kill git fetch with too many refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-02T05:28:27Z","receivedAt":"2013-07-02T05:28:27Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 01, 2013 at 10:19:51PM -0700, Junio C Hamano wrote:\n\n> > Like the patch below, which is built on top of next (which has Junio's\n> > prio_queue implementation), and has both the priority queue fix for\n> > rev_list_push and the mark_complete sort-at-the-end fix.\n> \n> Wow, I saw \"160 lines\" in my MUA which scared me a bit until I\n> opened it to realize 40% is discussion and most of the remaining\n> lines are context around single liners.\n> \n> It just looks too easy/simple, but the result looks correct, at\n> least from a cursory read.\n> \n> Good job ;-)\n\nThanks. :)\n\nI'm splitting it out into readable patches now. At first I was made a\nbit nervous by the \"popping\" behavior I described as \"oddity #2\"\nearlier.  But the more I look at it, the more I am convinced it is\nsimply a bug that we can happen to fix along the way.\n\nPatches in a few minutes.\n\n-Peff\n"},{"id":"222339","messageId":"20130702061149.GB1206@sigill.intra.peff.net","threadId":"34321","inReplyTo":"20130702052827.GA10626@sigill.intra.peff.net","subject":"[PATCH 0/3] avoid quadratic behavior in fetch-pack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-02T06:11:49Z","receivedAt":"2013-07-02T06:11:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Here are my patches to deal with Martin's pathological case, split out\nfor easy reading. I took a few timings to show that the results of the\n3rd patch are noticeable even with 50,000 unique refs (which is still a\nlot, but something that I could conceive of a busy repo accumulating\nover time).\n\n  [1/3]: fetch-pack: avoid quadratic list insertion in mark_complete\n  [2/3]: commit.c: make compare_commits_by_commit_date global\n  [3/3]: fetch-pack: avoid quadratic behavior in rev_list_push\n\nAnd here's the diffstat to prove it is really not scary. :)\n\n commit.c     |  2 +-\n commit.h     |  2 ++\n fetch-pack.c | 16 ++++++++--------\n 3 files changed, 11 insertions(+), 9 deletions(-)\n\n-Peff\n"},{"id":"222340","messageId":"20130702061623.GA27856@sigill.intra.peff.net","threadId":"34321","inReplyTo":"20130702061149.GB1206@sigill.intra.peff.net","subject":"[PATCH 1/3] fetch-pack: avoid quadratic list insertion in mark_complete","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-02T06:16:23Z","receivedAt":"2013-07-02T06:16:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We insert the commit pointed to by each ref one-by-one into\nthe \"complete\" commit_list using insert_by_date. Because\neach insertion is O(n), we end up with O(n^2) behavior.\n\nThis typically doesn't matter, because the number of refs is\nreasonably small. And even if there are a lot of refs, they\noften point to a smaller set of objects (in which case the\noptimization in commit ea5f220 keeps our \"n\" small).\n\nHowever, in pathological repositories (hundreds of thousands\nof refs, each pointing to a unique commit), this quadratic\nbehavior can make a difference. Since we do not care about\nthe list order until we have finished building it, we can\nsimply keep it unsorted during the insertion phase, then\nsort it afterwards.\n\nOn a repository like the one described above, this dropped\nthe time to do a no-op fetch from 2.0s to 1.7s. On normal\nrepositories, it probably does not matter at all, but it\ndoes not hurt to protect ourselves from pathological cases.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nA note on the timings. I measured the times above last year when I wrote\nthe same patch here:\n\n  http://article.gmane.org/gmane.comp.version-control.git/194939\n\nAnd earlier tonight, I did a fetch that showed the same result. But when\nI tried to replicate it while writing the commit message, I had trouble,\nbecause either:\n\n  1. I was fetching actual commits, in which case the more serious\n     problem behavior in find_common kicked in, ruining the measurement.\n\n  2. It was a no-op fetch, in which case quickfetch() kicked in and we\n     did not call mark_complete at all.\n\nSo I'm rather confused how I managed to get timings earlier (both last\nyear, and earlier today). But I still think it's an obviously correct\nthing to do, and does protect us in case (1) above (actually fetching a\ncommit) once we fix the problem in find_common.\n\n fetch-pack.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex abe5ffb..4df8abd 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -505,7 +505,7 @@ static int mark_complete(const char *refname, const unsigned char *sha1, int fla\n \t\tstruct commit *commit = (struct commit *)o;\n \t\tif (!(commit->object.flags & COMPLETE)) {\n \t\t\tcommit->object.flags |= COMPLETE;\n-\t\t\tcommit_list_insert_by_date(commit, &complete);\n+\t\t\tcommit_list_insert(commit, &complete);\n \t\t}\n \t}\n \treturn 0;\n@@ -622,6 +622,7 @@ static int everything_local(struct fetch_pack_args *args,\n \tif (!args->depth) {\n \t\tfor_each_ref(mark_complete, NULL);\n \t\tfor_each_alternate_ref(mark_alternate_complete, NULL);\n+\t\tcommit_list_sort_by_date(&complete);\n \t\tif (cutoff)\n \t\t\tmark_recent_complete_commits(args, cutoff);\n \t}\n-- \n1.8.3.rc2.14.g7eee6b3\n"},{"id":"222341","messageId":"20130702062148.GB27856@sigill.intra.peff.net","threadId":"34321","inReplyTo":"20130702061149.GB1206@sigill.intra.peff.net","subject":"[PATCH 2/3] commit.c: make compare_commits_by_commit_date global","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-02T06:21:48Z","receivedAt":"2013-07-02T06:21:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This helper function was introduced as a prio_queue\ncomparator to help topological sorting. However, other users\nof prio_queue who want to replace commit_list_insert_by_date\nwill want to use it, too. So let's make it public.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThere is also compare_commits_by_author_date, but I expect it to be less\ngenerally useful (especially because it relies on a slab), so I didn't\nbother publicizing it.  I think this is sufficient for now, and any\nlater users can make the author version public if they need to.\n\nNote also that we have a similar comparison function,\ncommit_list_compare_by_date, which gets fed to the linked-list mergesort\nfor commit_list_sort_by_date. I was tempted to unify them, but we can't,\nbecause it takes an actual \"struct commit_list *\", not a \"struct commit\n*\" (and the logic is not so complex that it is worth factoring out to a\nshared helper).\n\n commit.c | 2 +-\n commit.h | 2 ++\n 2 files changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/commit.c b/commit.c\nindex 521e49c..ebc0eea 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -581,7 +581,7 @@ static int compare_commits_by_author_date(const void *a_, const void *b_,\n \treturn 0;\n }\n \n-static int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n+int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)\n {\n \tconst struct commit *a = a_, *b = b_;\n \t/* newer commits with larger date first */\ndiff --git a/commit.h b/commit.h\nindex 4d452dc..18a5234 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -254,4 +254,6 @@ extern void check_commit_signature(const struct commit* commit, struct signature\n  */\n extern void check_commit_signature(const struct commit* commit, struct signature_check *sigc);\n \n+int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused);\n+\n #endif /* COMMIT_H */\n-- \n1.8.3.rc2.14.g7eee6b3\n"},{"id":"222342","messageId":"20130702062420.GC27856@sigill.intra.peff.net","threadId":"34321","inReplyTo":"20130702061149.GB1206@sigill.intra.peff.net","subject":"[PATCH 3/3] fetch-pack: avoid quadratic behavior in rev_list_push","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-02T06:24:21Z","receivedAt":"2013-07-02T06:24:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we call find_common to start finding common ancestors\nwith the remote side of a fetch, the first thing we do is\ninsert the tip of each ref into our rev_list linked list. We\nkeep the list sorted the whole time with\ncommit_list_insert_by_date, which means our insertion ends\nup doing O(n^2) timestamp comparisons.\n\nWe could teach rev_list_push to use an unsorted list, and\nthen sort it once after we have added each ref. However, in\nget_rev, we process the list by popping commits off the\nfront and adding parents back in timestamp-sorted order. So\nthat procedure would still operate on the large list.\n\nInstead, we can replace the linked list with a heap-based\npriority queue, which can do O(log n) insertion, making the\nwhole insertion procedure O(n log n).\n\nAs a result of switching to the prio_queue struct, we fix\ntwo minor bugs:\n\n  1. When we \"pop\" a commit in get_rev, and when we clear\n     the rev_list in find_common, we do not take care to\n     free the \"struct commit_list\", and just leak its\n     memory. With the prio_queue implementation, the memory\n     management is handled for us.\n\n  2. In get_rev, we look at the head commit of the list,\n     possibly push its parents onto the list, and then \"pop\"\n     the front of the list off, assuming it is the same\n     element that we just peeked at. This is typically going\n     to be the case, but would not be in the face of clock\n     skew: the parents are inserted by date, and could\n     potentailly be inserted at the head of the list if they\n     have a timestamp newer than their descendent. In this\n     case, we would accidentally pop the parent, and never\n     process it at all.\n\n     The new implementation pulls the commit off of the\n     queue as we examine it, and so does not suffer from\n     this problem.\n\nWith this patch, a fetch of a single commit into a\nrepository with 50,000 refs went from:\n\n  real    0m7.984s\n  user    0m7.852s\n  sys     0m0.120s\n\nto:\n\n  real    0m2.017s\n  user    0m1.884s\n  sys     0m0.124s\n\nBefore this patch, a larger case with 370K refs still had\nnot completed after tens of minutes; with this patch, it\ncompletes in about 12 seconds.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nNot that it really matters, but Martin, note that your \"one million\nrefs\" case is actually more like 370K, because that is how many commits\nthere are in the linux.git repo. The rest of the lines written to your\npacked-refs file are just bogus.\n\n fetch-pack.c | 13 ++++++-------\n 1 file changed, 6 insertions(+), 7 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 4df8abd..6684348 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -11,6 +11,7 @@\n #include \"run-command.h\"\n #include \"transport.h\"\n #include \"version.h\"\n+#include \"prio-queue.h\"\n \n static int transfer_unpack_limit = -1;\n static int fetch_unpack_limit = -1;\n@@ -37,7 +38,7 @@ static int marked;\n  */\n #define MAX_IN_VAIN 256\n \n-static struct commit_list *rev_list;\n+static struct prio_queue rev_list = { compare_commits_by_commit_date };\n static int non_common_revs, multi_ack, use_sideband, allow_tip_sha1_in_want;\n \n static void rev_list_push(struct commit *commit, int mark)\n@@ -49,7 +50,7 @@ static void rev_list_push(struct commit *commit, int mark)\n \t\t\tif (parse_commit(commit))\n \t\t\t\treturn;\n \n-\t\tcommit_list_insert_by_date(commit, &rev_list);\n+\t\tprio_queue_put(&rev_list, commit);\n \n \t\tif (!(commit->object.flags & COMMON))\n \t\t\tnon_common_revs++;\n@@ -122,10 +123,10 @@ static const unsigned char *get_rev(void)\n \t\tunsigned int mark;\n \t\tstruct commit_list *parents;\n \n-\t\tif (rev_list == NULL || non_common_revs == 0)\n+\t\tif (rev_list.nr == 0 || non_common_revs == 0)\n \t\t\treturn NULL;\n \n-\t\tcommit = rev_list->item;\n+\t\tcommit = prio_queue_get(&rev_list);\n \t\tif (!commit->object.parsed)\n \t\t\tparse_commit(commit);\n \t\tparents = commit->parents;\n@@ -152,8 +153,6 @@ static const unsigned char *get_rev(void)\n \t\t\t\tmark_common(parents->item, 1, 0);\n \t\t\tparents = parents->next;\n \t\t}\n-\n-\t\trev_list = rev_list->next;\n \t}\n \n \treturn commit->object.sha1;\n@@ -442,7 +441,7 @@ static int find_common(struct fetch_pack_args *args,\n \t\t\t\t\tin_vain = 0;\n \t\t\t\t\tgot_continue = 1;\n \t\t\t\t\tif (ack == ACK_ready) {\n-\t\t\t\t\t\trev_list = NULL;\n+\t\t\t\t\t\tclear_prio_queue(&rev_list);\n \t\t\t\t\t\tgot_ready = 1;\n \t\t\t\t\t}\n \t\t\t\t\tbreak;\n-- \n1.8.3.rc2.14.g7eee6b3\n"},{"id":"222346","messageId":"CAPig+cRYdinZVA0+nU6tU_TcusFu6Pe0qaQ5Bv4Xbmg1izDbLQ@mail.gmail.com","threadId":"34321","inReplyTo":"20130702062420.GC27856@sigill.intra.peff.net","subject":"Re: [PATCH 3/3] fetch-pack: avoid quadratic behavior in rev_list_push","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-07-02T07:52:04Z","receivedAt":"2013-07-02T07:52:04Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Jul 2, 2013 at 2:24 AM, Jeff King <peff@peff.net> wrote:\n> When we call find_common to start finding common ancestors\n> with the remote side of a fetch, the first thing we do is\n> insert the tip of each ref into our rev_list linked list. We\n> keep the list sorted the whole time with\n> commit_list_insert_by_date, which means our insertion ends\n> up doing O(n^2) timestamp comparisons.\n>\n> We could teach rev_list_push to use an unsorted list, and\n> then sort it once after we have added each ref. However, in\n> get_rev, we process the list by popping commits off the\n> front and adding parents back in timestamp-sorted order. So\n> that procedure would still operate on the large list.\n>\n> Instead, we can replace the linked list with a heap-based\n> priority queue, which can do O(log n) insertion, making the\n> whole insertion procedure O(n log n).\n>\n> As a result of switching to the prio_queue struct, we fix\n> two minor bugs:\n>\n>   1. When we \"pop\" a commit in get_rev, and when we clear\n>      the rev_list in find_common, we do not take care to\n>      free the \"struct commit_list\", and just leak its\n>      memory. With the prio_queue implementation, the memory\n>      management is handled for us.\n>\n>   2. In get_rev, we look at the head commit of the list,\n>      possibly push its parents onto the list, and then \"pop\"\n>      the front of the list off, assuming it is the same\n>      element that we just peeked at. This is typically going\n>      to be the case, but would not be in the face of clock\n>      skew: the parents are inserted by date, and could\n>      potentailly be inserted at the head of the list if they\n\ns/potentailly/potentially/\n\n>      have a timestamp newer than their descendent. In this\n>      case, we would accidentally pop the parent, and never\n>      process it at all.\n>\n>      The new implementation pulls the commit off of the\n>      queue as we examine it, and so does not suffer from\n>      this problem.\n>\n> With this patch, a fetch of a single commit into a\n> repository with 50,000 refs went from:\n>\n>   real    0m7.984s\n>   user    0m7.852s\n>   sys     0m0.120s\n>\n> to:\n>\n>   real    0m2.017s\n>   user    0m1.884s\n>   sys     0m0.124s\n>\n> Before this patch, a larger case with 370K refs still had\n> not completed after tens of minutes; with this patch, it\n> completes in about 12 seconds.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n"},{"id":"222360","messageId":"51D29C3E.5070600@alum.mit.edu","threadId":"34321","inReplyTo":"201307012102.31384.mfick@codeaurora.org","subject":"Re: How to still kill git fetch with too many refs","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-07-02T09:24:14Z","receivedAt":"2013-07-02T09:24:14Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 07/02/2013 05:02 AM, Martin Fick wrote:\n> I have often reported problems with git fetch when there are \n> many refs in a repo, and I have been pleasantly surprised \n> how many problems I reported were so quickly fixed. :) With \n> time, others have created various synthetic test cases to \n> ensure that git can handle many many refs.  A simple \n> synthetic test case with 1M refs all pointing to the same \n> sha1 seems to be easily handled by git these days.  However, \n> in our experience with our internal git repo, we still have \n> performance issues related to having too many refs, in our \n> kernel/msm instance we have around 400K.\n> \n> When I tried the simple synthetic test case and could not \n> reproduce bad results, so I tried something just a little \n> more complex and was able to get atrocious results!!! \n> Basically, I generate a packed-refs files with many refs \n> which each point to a different sha1.  To get a list of \n> valid but unique sha1s for the repo, I simply used rev-list.  \n> The result, a copy of linus' repo with a million unique \n> valid refs and a git fetch of a single updated ref taking a \n> very long time (55mins and it did not complete yet).  Note, \n> with 100K refs it completes in about 2m40s.  It is likely \n> not linear since 2m40s * 10 would be ~26m (but the \n> difference could also just be how the data in the sha1s are \n> ordered).\n> \n> \n> Here is my small reproducible test case for this issue:\n> \n> git clone \n> git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git\n> cp -rp linux linux.1Mrefs-revlist\n> \n> cd linux\n> echo \"Hello\" > hello ; git add hello ; git ci -a -m 'hello'\n> cd ..\n> \n> cd linux.1Mrefs-revlist\n> git rev-list HEAD | for nn in $(seq 0 100) ; do for c in \n> $(seq 0 10000) ; do  read sha ; echo $sha refs/c/$nn/$c$nn ; \n> done ; done > .git/packed-refs\n\nI believe this generates a packed-refs file that is not sorted\nlexicographically by refname, whereas all Git-generated packed-refs\nfiles are sorted.  There are some optimizations in refs.c for adding\nreferences in order that might therefore be circumvented by your\nunsorted file.  Please try sorting the file by refname and see if that\nhelps.  (You can do so by deleting one of the packed references; then\ngit will sort the remainder while rewriting the file.)\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"222375","messageId":"201307021058.58563.mfick@codeaurora.org","threadId":"34321","inReplyTo":"51D29C3E.5070600@alum.mit.edu","subject":"Re: How to still kill git fetch with too many refs","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-07-02T16:58:58Z","receivedAt":"2013-07-02T16:58:58Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Tuesday, July 02, 2013 03:24:14 am Michael Haggerty \nwrote:\n> > git rev-list HEAD | for nn in $(seq 0 100) ; do for c\n> > in $(seq 0 10000) ; do  read sha ; echo $sha\n> > refs/c/$nn/$c$nn ; done ; done > .git/packed-refs\n> \n> I believe this generates a packed-refs file that is not\n> sorted lexicographically by refname, whereas all\n> Git-generated packed-refs files are sorted.  \n\n\nYes, you are indeed correct.  I was attempting to be too \nclever with my sharding I guess.  Thanks.\n\n> There are\n> some optimizations in refs.c for adding references in\n> order that might therefore be circumvented by your\n> unsorted file.  Please try sorting the file by refname\n> and see if that helps.  (You can do so by deleting one\n> of the packed references; then git will sort the\n> remainder while rewriting the file.)\n\nA simple git pack-refs seems to clean it up.\n\nThe original test did complete in ~77mins last night.  A \nrerun with a sorted file takes ~61mins,\n\n-Martin\n\n\nPS: This test was performed with git version 1.8.2.1 on \nlinux 2.6.32-37-generic #81-Ubuntu SMP \n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n \n"},{"id":"222382","messageId":"201307021145.07726.mfick@codeaurora.org","threadId":"34321","inReplyTo":"20130702061149.GB1206@sigill.intra.peff.net","subject":"Re: [PATCH 0/3] avoid quadratic behavior in fetch-pack","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-07-02T17:45:07Z","receivedAt":"2013-07-02T17:45:07Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Tuesday, July 02, 2013 12:11:49 am Jeff King wrote:\n> Here are my patches to deal with Martin's pathological\n> case, split out for easy reading. I took a few timings\n> to show that the results of the 3rd patch are noticeable\n> even with 50,000 unique refs (which is still a lot, but\n> something that I could conceive of a busy repo\n> accumulating over time).\n> \n>   [1/3]: fetch-pack: avoid quadratic list insertion in\n> mark_complete [2/3]: commit.c: make\n> compare_commits_by_commit_date global [3/3]: fetch-pack:\n> avoid quadratic behavior in rev_list_push\n> \n> And here's the diffstat to prove it is really not scary.\n> :)\n> \n>  commit.c     |  2 +-\n>  commit.h     |  2 ++\n>  fetch-pack.c | 16 ++++++++--------\n>  3 files changed, 11 insertions(+), 9 deletions(-)\n> \n> -Peff\n\nI applied these 3 patches and it indeed improves things \ndramatically.  Thanks Peff, you are awesome!!!\n\n\nThe synthetic test case (but sorted), now comes in at around \n15s.  The more important real world case (for us), fetching \nfrom my production server, which took around 12mins \npreviously, now takes around 30s (I think the extra time is \nnow spent on the Gerrit server, but I will investigate that \na bit more)!  That is very significant and should make many \nworkflows much more efficient.  +1 for merging this. :)\n\nAgain, thanks,\n\n-Martin\n\n\nNote, I tested git-next 1.8.3.2.883.g27cfd27 to be sure that \nit is still problematic without this patch, it is (running \nfor 10mins now without completing).\n\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n \n"},{"id":"222384","messageId":"CA+sFfMf4Y2zPYhewADxJyR8DR5aAsa89+PW2UDNp3zSsXqjUHA@mail.gmail.com","threadId":"34321","inReplyTo":"20130702050142.GA1206@sigill.intra.peff.net","subject":"Re: How to still kill git fetch with too many refs","fromName":"Brandon Casey","fromEmail":"drafnel@gmail.com","sentAt":"2013-07-02T17:52:47Z","receivedAt":"2013-07-02T17:52:47Z","isPatch":false,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"On Mon, Jul 1, 2013 at 10:01 PM, Jeff King <peff@peff.net> wrote:\n> On Tue, Jul 02, 2013 at 12:41:51AM -0400, Jeff King wrote:\n>\n>> I replicated your test setup, and the problem is that we have many\n>> common objects on both sides during the ref negotiation. So we end up in\n>> rev_list_push for each one, which has the same O(n^2) behavior.\n>> Switching it to just sort at the end is not trivial; we first insert all\n>> of the objects, but then we actually walk the parents, pushing onto the\n>> list as we go. So I think we'd want a better data structure (like a\n>> priority queue).\n>\n> Like the patch below,\n\n<snip>\n\nLooks obviously correct to me since I've got essentially the same\npatch sitting in my local repo. :b\n\nI've got the patch coming that fixes the same problem on the push side\nof things and provides the same order of magnitude improvement.\n\n-Brandon\n"}]}