{"thread":{"id":"30574","subject":"remove_duplicates() in builtin/fetch-pack.c is O(N^2)","startedAt":"2012-05-21T08:13:33Z","lastAt":"2012-05-25T06:50:40Z","messageCount":46,"participants":["Michael Haggerty","Junio C Hamano","demerphq","Jeff King","Martin Fick","Nguyen Thai Ngoc Duy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"191795","messageId":"4FB9F92D.8000305@alum.mit.edu","threadId":"30574","inReplyTo":null,"subject":"remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-21T08:13:33Z","receivedAt":"2012-05-21T08:13:33Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"I just noticed that the remove_duplicates() function in \nbuiltin/fetch-pack.c is O(N^2) in the number of heads.  Empirically, \nthis function takes on the order of 25 seconds to process 100k references.\n\nI know that 100k heads is kindof absurd.  Perhaps handling this many \nheads is unrealistic for other reasons.  But I vaguely recall numbers \nlike this being mentioned on the mailing list.\n\nIt would be pretty trivial to reduce the work to O(N) by using a hash \nset to keep track of the references that have already been seen.\n\nI don't plan to work on this, but I thought I would point it out in case \nit is causing somebody pain.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191796","messageId":"7vaa1199yp.fsf@alter.siamese.dyndns.org","threadId":"30574","inReplyTo":"4FB9F92D.8000305@alum.mit.edu","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-21T09:09:34Z","receivedAt":"2012-05-21T09:09:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> It would be pretty trivial to reduce the work to O(N) by using a hash\n> set to keep track of the references that have already been seen.\n\nSounds like a sensible thing to do.\n"},{"id":"191799","messageId":"CANgJU+WwA0FfwVFWO23o0wLbpXNS+RXwwx=VKZ_J3e57r1pBsQ@mail.gmail.com","threadId":"30574","inReplyTo":"4FB9F92D.8000305@alum.mit.edu","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"demerphq","fromEmail":"demerphq@gmail.com","sentAt":"2012-05-21T09:42:06Z","receivedAt":"2012-05-21T09:42:06Z","isPatch":false,"sender":{"key":"demerphq@gmail.com","avatar":null},"body":"On 21 May 2012 10:13, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> I just noticed that the remove_duplicates() function in builtin/fetch-pack.c\n> is O(N^2) in the number of heads.  Empirically, this function takes on the\n> order of 25 seconds to process 100k references.\n\nDoes \"heads\" in this context include tags? Sorry if this is a stupid question.\n\nYves\n\n\n-- \nperl -Mre=debug -e \"/just|another|perl|hacker/\"\n"},{"id":"191819","messageId":"20120521174525.GA22643@sigill.intra.peff.net","threadId":"30574","inReplyTo":"4FB9F92D.8000305@alum.mit.edu","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T17:45:25Z","receivedAt":"2012-05-21T17:45:25Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 21, 2012 at 10:13:33AM +0200, Michael Haggerty wrote:\n\n> I just noticed that the remove_duplicates() function in\n> builtin/fetch-pack.c is O(N^2) in the number of heads.  Empirically,\n> this function takes on the order of 25 seconds to process 100k\n> references.\n> \n> I know that 100k heads is kindof absurd.  Perhaps handling this many\n> heads is unrealistic for other reasons.  But I vaguely recall numbers\n> like this being mentioned on the mailing list.\n\nThe rails/rails network repository at GitHub (i.e., a master repo with\nall of the objects and refs for all of the forks) has about 400K refs,\nand has been the usual impetus for me finding and fixing these sorts of\nquadratic problems.\n\nI've never triggered this one, though, because it relies not just on\nhaving a repo with a lot of refs, but actually fetching all of them at\none time (which we don't tend to do).\n\nBut it would be nice to fix it. There is a similar case in filter_refs,\nwhich I mentioned here:\n\n  http://article.gmane.org/gmane.comp.version-control.git/186994\n\n> It would be pretty trivial to reduce the work to O(N) by using a hash\n> set to keep track of the references that have already been seen.\n\nI don't think there is any reason we can't sort the list of heads, and\nthen we can get rid of the duplicates with an O(n) traversal, like the\n(largely untested) patch below.\n\n> I don't plan to work on this, but I thought I would point it out in\n> case it is causing somebody pain.\n\nI'll clean up the patch and make one for the filter_refs case, too.\n\n-Peff\n\n---\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex b6cc75e..7efcf2f 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -859,25 +859,23 @@ static struct ref *do_fetch_pack(int fd[2],\n \treturn ref;\n }\n \n+static int compare_heads(const void *a, const void *b)\n+{\n+\treturn strcmp(*(const char **)a, *(const char **)b);\n+}\n+\n static int remove_duplicates(int nr_heads, char **heads)\n {\n \tint src, dst;\n \n-\tfor (src = dst = 0; src < nr_heads; src++) {\n-\t\t/* If heads[src] is different from any of\n-\t\t * heads[0..dst], push it in.\n-\t\t */\n-\t\tint i;\n-\t\tfor (i = 0; i < dst; i++) {\n-\t\t\tif (!strcmp(heads[i], heads[src]))\n-\t\t\t\tbreak;\n-\t\t}\n-\t\tif (i < dst)\n-\t\t\tcontinue;\n-\t\tif (src != dst)\n-\t\t\theads[dst] = heads[src];\n-\t\tdst++;\n-\t}\n+\tif (!nr_heads)\n+\t\treturn 0;\n+\n+\tqsort(heads, nr_heads, sizeof(*heads), compare_heads);\n+\n+\tfor (src = dst = 1; src < nr_heads; src++)\n+\t\tif (strcmp(heads[src], heads[dst-1]))\n+\t\t\theads[dst++] = heads[src];\n \treturn dst;\n }\n \n"},{"id":"191821","messageId":"201205211215.14455.mfick@codeaurora.org","threadId":"30574","inReplyTo":"4FB9F92D.8000305@alum.mit.edu","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-05-21T18:15:13Z","receivedAt":"2012-05-21T18:15:13Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Monday, May 21, 2012 02:13:33 am Michael Haggerty wrote:\n> I just noticed that the remove_duplicates() function in\n> builtin/fetch-pack.c is O(N^2) in the number of heads. \n> Empirically, this function takes on the order of 25\n> seconds to process 100k references.\n> \n> I know that 100k heads is kindof absurd.  Perhaps\n> handling this many heads is unrealistic for other\n> reasons.  But I vaguely recall numbers like this being\n> mentioned on the mailing list.\n\nYes I have mentioned 100K several times, and I greatly \nappreciate the many fixes already made to make git to better \nhandle large ref counts.\n\nHowever, I would like to suggest that 100K not really be \nviewed as absurd anymore. :) There are many users for whom \nit is not absurd, certainly not if you are including tags.  \nBut, I know that some of the tag uses have been brushed off \nas abuses, so I will focus on feature branches, of which we \nactually have more than tags in our larger repos, we have \naround 60K in our kernel repo.\n\nOf course, we use Gerrit, so features tend to be called \nchanges and each change may get many revisions (patchsets), \nso all of these get refs, but I think that it might be wrong \nto consider that out of the ordinary anymore.  After all, \nshould a version control system such as git not support 100K \nrevisions of features developed independently on separate \nbranches (within Gerrit or not)?  100K is not really that \nmany when you consider a large project.  Even without \nGerrit, if someone wanted to track that many features \n(likely over a few years), they will probably use up tons of \nrefs.  \n\nIt may be too easy to think that because git is distributed \nthat features will get developed in a distributed way and \ntherefor no one would ever want to track them all in one \nplace, but I suspect that this may be a bad assumption.  \nThat being said, I believe that we are not even tracking \nexternal features, and we have over 60K feature revisions \n(gerrit patchsets) in one rep), so if someone were to track \nall the changes for the kernel, I can only imagine that this \nnumber would be in the millions.\n\nI am sure that 1M refs is even within the sights of some \nindividuals already, I know users who actually have 250K.  I \nhope that 10M or even perhaps 100M refs will be considered \nfeasible to use long term with git.  \n\nAgain, I really hope that this will no longer be seen as \nabsurd, but rather just normal for large projects.  After \nall the kernel was (still is?) the primary use case of git.  \nOur largest ref project is the kernel so I don't know that \nwe should be considered fringe, and I hope that we along \nwith other larger kernel contributors will be considered \nnormal to git, :)\n\n-Martin\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"191823","messageId":"20120521194114.GA28358@sigill.intra.peff.net","threadId":"30574","inReplyTo":"201205211215.14455.mfick@codeaurora.org","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T19:41:14Z","receivedAt":"2012-05-21T19:41:14Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 21, 2012 at 12:15:13PM -0600, Martin Fick wrote:\n\n> Of course, we use Gerrit, so features tend to be called \n> changes and each change may get many revisions (patchsets), \n> so all of these get refs, but I think that it might be wrong \n> to consider that out of the ordinary anymore.  After all, \n> should a version control system such as git not support 100K \n> revisions of features developed independently on separate \n> branches (within Gerrit or not)?  100K is not really that \n> many when you consider a large project.  Even without \n> Gerrit, if someone wanted to track that many features \n> (likely over a few years), they will probably use up tons of \n> refs.  \n\nI think the more compelling line of argument is not \"is this\nreasonable?\", but rather that git has been designed from the ground-up\nto be efficient, and these are not fundamental design issues with git at\nall. They are just silly little spots where we used a quick-to-write\nquadratic algorithm instead of something more complex with better\nasymptotic behavior. And if we can fix these silly spots easily, then\nthere's no reason not to. It helps the small-N case a tiny bit, and it\nmakes the big-N case feasible.\n\nSo far, the only quadratic case I have seen that is not easy to fix is\nreplacing \"struct commit_list\" with a priority queue or similar.  But we\nmanaged to hack around that long ago with fce87ae (Fix quadratic\nperformance in rewrite_one., 2008-07-12), and I don't think it's\ngenerally a problem in practice.\n\nAnyway, my point is that we don't even have to talk about \"reasonable\"\nor \"absurd\". Git should be fast even on absurd cases, because 99% of the\nwork has already been done, and the last 1% is easy.\n\n-Peff\n"},{"id":"191831","messageId":"7vvcjp6vbl.fsf@alter.siamese.dyndns.org","threadId":"30574","inReplyTo":"20120521194114.GA28358@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-21T22:08:46Z","receivedAt":"2012-05-21T22:08:46Z","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> Anyway, my point is that we don't even have to talk about \"reasonable\"\n> or \"absurd\".  Git should be fast even on absurd cases,...\n\nI agree with you 98%.\n\nIf we can make Git fast even on \"absurd\" cases without penalizing less\nextreme and boring cases and/or maintainability of the code, we should\nstrive to do so.  And I think the codepaths mentioned in this thread falls\ninto that category.\n\nThe remaining 2% is only to allow me to say that we reserve the right to\nlabel cases \"absurd\" when it is extremely painful to support without\npenalizing the code and performance of less extreme and boring cases ;-)\n"},{"id":"191834","messageId":"20120521221417.GA22664@sigill.intra.peff.net","threadId":"30574","inReplyTo":"20120521174525.GA22643@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T22:14:17Z","receivedAt":"2012-05-21T22:14:17Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 21, 2012 at 01:45:25PM -0400, Jeff King wrote:\n\n> > I don't plan to work on this, but I thought I would point it out in\n> > case it is causing somebody pain.\n> \n> I'll clean up the patch and make one for the filter_refs case, too.\n\nHere are the patches. I tested these with three repositories:\n\n  - the rails/rails network repo, with ~400K refs\n\n  - the git/git network repo, with ~220 refs\n\n  - a fake repo made from git.git, with 3 numbered refs pointing at each\n    commit for a total of ~100K refs (I didn't have a real dataset that\n    was ~100K).\n\nBefore these patches, I never managed to complete a \"git clone --mirror\nfile://$repo\" on the first two, as I got impatient after 5-10 minutes\nand killed the process. The third one completed in ~110s.\n\n  [1/5]: fetch-pack: sort incoming heads\n  [2/5]: fetch-pack: avoid quadratic behavior in remove_duplicates\n\nAfter this one, the \"fake\" case was down to ~63s.\n\n  [3/5]: add sorting infrastructure for list refs\n  [4/5]: fetch-pack: sort the list of incoming refs\n  [5/5]: fetch-pack: avoid quadratic loop in filter_refs\n\nAnd after this one, the \"fake\" case was down to ~32s. Notably, most of\nthe time was spent on the actual object transfer (i.e., before it would\nhang before even getting to \"Counting objects...\", and now it starts\nthat almost immediately). Perf corroborates this by showing most of the\ntime in zlib inflate and delta resolution.\n\nThe rails and git cases run in ~28s and ~37s, respectively, again mostly\ngoing to the actual object transfer. So I think this series removes all\nof the asymptotically bad behavior from this code path.\n\nOne thing to note about all of these repos is that they tend to have\nseveral refs pointing to a single commit. None of the speedups in this\nseries depends on that fact, but it may be that on a repo with more\nindependent refs, we may uncover other code paths (e.g., I know that my\nfix for mark_complete in ea5f220 improves the case with duplicate refs,\nbut would not help if you really have 400K refs pointing to unique\ncommits[1]).\n\nMartin, let me know if this improves things for your many-ref cases (and\nif you are still seeing slowness in your repos with many refs, let me\nknow which operations cause it).\n\n-Peff\n\n[1] At the time of that commit, I proposed a fix with a priority queue\n    replacing the commit_list, but we deemed it too much code for\n    a case that was unlikely to happen. But now it sounds like that case\n    is less unlikely than we thought, and now that we have René's\n    linked-list merge-sort code, I think we could fix it with a 2-line\n    change. I'll look into it.\n"},{"id":"191836","messageId":"20120521221702.GA22914@sigill.intra.peff.net","threadId":"30574","inReplyTo":"20120521221417.GA22664@sigill.intra.peff.net","subject":"[PATCH 1/5] fetch-pack: sort incoming heads","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T22:17:02Z","receivedAt":"2012-05-21T22:17:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There's no reason to preserve the incoming order of the\nheads we're requested to fetch. By having them sorted, we\ncan replace some of the quadratic algorithms with linear\nones.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI actually wouldn't be surprised if these were typically sorted already,\nas they frequently come from the ref-mapping functions, which in turn\nprocess the lists we get from the remote. But we also might get random\njunk on the command-line of fetch-pack, so we need to be careful.\n\n builtin/fetch-pack.c | 7 +++++++\n 1 file changed, 7 insertions(+)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex 10db15b..380743e 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -1057,6 +1057,11 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)\n \treturn ret;\n }\n \n+static int compare_heads(const void *a, const void *b)\n+{\n+\treturn strcmp(*(const char **)a, *(const char **)b);\n+}\n+\n struct ref *fetch_pack(struct fetch_pack_args *my_args,\n \t\t       int fd[], struct child_process *conn,\n \t\t       const struct ref *ref,\n@@ -1076,6 +1081,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,\n \t\t\tst.st_mtime = 0;\n \t}\n \n+\tqsort(heads, nr_heads, sizeof(*heads), compare_heads);\n+\n \tif (heads && nr_heads)\n \t\tnr_heads = remove_duplicates(nr_heads, heads);\n \tif (!ref) {\n-- \n1.7.10.1.19.g711d603\n"},{"id":"191837","messageId":"20120521221720.GB22914@sigill.intra.peff.net","threadId":"30574","inReplyTo":"20120521221417.GA22664@sigill.intra.peff.net","subject":"[PATCH 2/5] fetch-pack: avoid quadratic behavior in remove_duplicates","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T22:17:20Z","receivedAt":"2012-05-21T22:17:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We remove duplicate entries from the list of refs we are\nfed in fetch-pack. The original algorithm is quadratic over\nthe number of refs, but since the list is now guaranteed to\nbe sorted, we can do it in linear time.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/fetch-pack.c | 21 ++++++---------------\n 1 file changed, 6 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex 380743e..3522d8e 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -834,21 +834,12 @@ static int remove_duplicates(int nr_heads, char **heads)\n {\n \tint src, dst;\n \n-\tfor (src = dst = 0; src < nr_heads; src++) {\n-\t\t/* If heads[src] is different from any of\n-\t\t * heads[0..dst], push it in.\n-\t\t */\n-\t\tint i;\n-\t\tfor (i = 0; i < dst; i++) {\n-\t\t\tif (!strcmp(heads[i], heads[src]))\n-\t\t\t\tbreak;\n-\t\t}\n-\t\tif (i < dst)\n-\t\t\tcontinue;\n-\t\tif (src != dst)\n-\t\t\theads[dst] = heads[src];\n-\t\tdst++;\n-\t}\n+\tif (!nr_heads)\n+\t\treturn 0;\n+\n+\tfor (src = dst = 1; src < nr_heads; src++)\n+\t\tif (strcmp(heads[src], heads[dst-1]))\n+\t\t\theads[dst++] = heads[src];\n \treturn dst;\n }\n \n-- \n1.7.10.1.19.g711d603\n"},{"id":"191838","messageId":"20120521221928.GC22914@sigill.intra.peff.net","threadId":"30574","inReplyTo":"20120521221417.GA22664@sigill.intra.peff.net","subject":"[PATCH 3/5] add sorting infrastructure for list refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T22:19:28Z","receivedAt":"2012-05-21T22:19:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Since we store lists of refs as linked lists, we can use\nllist_mergesort to efficiently sort them.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nMany thanks to René for the llist_mergesort code.\n\n remote.c | 22 ++++++++++++++++++++++\n remote.h |  2 ++\n 2 files changed, 24 insertions(+)\n\ndiff --git a/remote.c b/remote.c\nindex b296d17..6833538 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -7,6 +7,7 @@\n #include \"dir.h\"\n #include \"tag.h\"\n #include \"string-list.h\"\n+#include \"mergesort.h\"\n \n enum map_direction { FROM_SRC, FROM_DST };\n \n@@ -918,6 +919,27 @@ void free_refs(struct ref *ref)\n \t}\n }\n \n+int ref_compare_name(const void *va, const void *vb)\n+{\n+\tconst struct ref *a = va, *b = vb;\n+\treturn strcmp(a->name, b->name);\n+}\n+\n+static void *ref_list_get_next(const void *a)\n+{\n+\treturn ((const struct ref *)a)->next;\n+}\n+\n+static void ref_list_set_next(void *a, void *next)\n+{\n+\t((struct ref *)a)->next = next;\n+}\n+\n+void sort_ref_list(struct ref **l, int (*cmp)(const void *, const void *))\n+{\n+\t*l = llist_mergesort(*l, ref_list_get_next, ref_list_set_next, cmp);\n+}\n+\n static int count_refspec_match(const char *pattern,\n \t\t\t       struct ref *refs,\n \t\t\t       struct ref **matched_ref)\ndiff --git a/remote.h b/remote.h\nindex 9ad8eb6..251d8fd 100644\n--- a/remote.h\n+++ b/remote.h\n@@ -72,6 +72,8 @@ extern const struct refspec *tag_refspec;\n struct ref *alloc_ref(const char *name);\n struct ref *copy_ref(const struct ref *ref);\n struct ref *copy_ref_list(const struct ref *ref);\n+void sort_ref_list(struct ref **, int (*cmp)(const void *, const void *));\n+int ref_compare_name(const void *, const void *);\n \n int check_ref_type(const struct ref *ref, int flags);\n \n-- \n1.7.10.1.19.g711d603\n"},{"id":"191839","messageId":"20120521221951.GD22914@sigill.intra.peff.net","threadId":"30574","inReplyTo":"20120521221417.GA22664@sigill.intra.peff.net","subject":"[PATCH 4/5] fetch-pack: sort the list of incoming refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T22:19:51Z","receivedAt":"2012-05-21T22:19:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Having the list sorted means we can avoid some quadratic\nalgorithms when comparing lists.\n\nThese should typically be sorted already, but they do come\nfrom the remote, so let's be extra careful. Our ref-sorting\nimplementation does a mergesort, so we do not have to care\nabout performance degrading in the common case that the list\nis already sorted.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/fetch-pack.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex 3522d8e..bee329f 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -777,6 +777,8 @@ static struct ref *do_fetch_pack(int fd[2],\n \tstruct ref *ref = copy_ref_list(orig_ref);\n \tunsigned char sha1[20];\n \n+\tsort_ref_list(&ref, ref_compare_name);\n+\n \tif (is_repository_shallow() && !server_supports(\"shallow\"))\n \t\tdie(\"Server does not support shallow clients\");\n \tif (server_supports(\"multi_ack_detailed\")) {\n-- \n1.7.10.1.19.g711d603\n"},{"id":"191842","messageId":"20120521222329.GE22914@sigill.intra.peff.net","threadId":"30574","inReplyTo":"20120521221417.GA22664@sigill.intra.peff.net","subject":"[PATCH 5/5] fetch-pack: avoid quadratic loop in filter_refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T22:23:29Z","receivedAt":"2012-05-21T22:23:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We have a list of refs that we want to compare against the\n\"match\" array. The current code searches the match list\nlinearly, giving quadratic behavior over the number of refs\nwhen you want to fetch all of them.\n\nInstead, we can compare the lists as we go, giving us linear\nbehavior.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThis is the only actual tricky patch in the series. I think I got the\nlist traversing right, but more eyeballs are appreciated.\n\nThis makes the result O(n).  An alternative implementation would be to\nsimply binary-search the sorted \"match\" array for each ref. That's O(n\nlg n), but we've already spent O(n lg n) sorting in the first place, so\nit's not a big deal. The code for that would be a little bit simpler.\nHowever, it's not as simple as you'd like, because we zero-out the match\narray to mark entries as \"found\". So we'd have to add a separate\nbit array.\n\nI think this version is simple enough.\n\n builtin/fetch-pack.c | 19 +++++++++++++------\n 1 file changed, 13 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex bee329f..d091865 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -528,6 +528,7 @@ static void filter_refs(struct ref **refs, int nr_match, char **match)\n \tstruct ref **newtail = &newlist;\n \tstruct ref *ref, *next;\n \tstruct ref *fastarray[32];\n+\tint match_pos;\n \n \tif (nr_match && !args.fetch_all) {\n \t\tif (ARRAY_SIZE(fastarray) < nr_match)\n@@ -540,6 +541,7 @@ static void filter_refs(struct ref **refs, int nr_match, char **match)\n \telse\n \t\treturn_refs = NULL;\n \n+\tmatch_pos = 0;\n \tfor (ref = *refs; ref; ref = next) {\n \t\tnext = ref->next;\n \t\tif (!memcmp(ref->name, \"refs/\", 5) &&\n@@ -553,15 +555,20 @@ static void filter_refs(struct ref **refs, int nr_match, char **match)\n \t\t\tcontinue;\n \t\t}\n \t\telse {\n-\t\t\tint i;\n-\t\t\tfor (i = 0; i < nr_match; i++) {\n-\t\t\t\tif (!strcmp(ref->name, match[i])) {\n-\t\t\t\t\tmatch[i][0] = '\\0';\n-\t\t\t\t\treturn_refs[i] = ref;\n+\t\t\tint cmp = -1;\n+\t\t\twhile (match_pos < nr_match) {\n+\t\t\t\tcmp = strcmp(ref->name, match[match_pos]);\n+\t\t\t\tif (cmp < 0) /* definitely do not have it */\n+\t\t\t\t\tbreak;\n+\t\t\t\telse if (cmp == 0) { /* definitely have it */\n+\t\t\t\t\tmatch[match_pos][0] = '\\0';\n+\t\t\t\t\treturn_refs[match_pos] = ref;\n \t\t\t\t\tbreak;\n \t\t\t\t}\n+\t\t\t\telse /* might have it; keep looking */\n+\t\t\t\t\tmatch_pos++;\n \t\t\t}\n-\t\t\tif (i < nr_match)\n+\t\t\tif (!cmp)\n \t\t\t\tcontinue; /* we will link it later */\n \t\t}\n \t\tfree(ref);\n-- \n1.7.10.1.19.g711d603\n"},{"id":"191844","messageId":"20120521222440.GB22664@sigill.intra.peff.net","threadId":"30574","inReplyTo":"7vvcjp6vbl.fsf@alter.siamese.dyndns.org","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T22:24:40Z","receivedAt":"2012-05-21T22:24:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 21, 2012 at 03:08:46PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > Anyway, my point is that we don't even have to talk about \"reasonable\"\n> > or \"absurd\".  Git should be fast even on absurd cases,...\n> \n> I agree with you 98%.\n> \n> If we can make Git fast even on \"absurd\" cases without penalizing less\n> extreme and boring cases and/or maintainability of the code, we should\n> strive to do so.  And I think the codepaths mentioned in this thread falls\n> into that category.\n> \n> The remaining 2% is only to allow me to say that we reserve the right to\n> label cases \"absurd\" when it is extremely painful to support without\n> penalizing the code and performance of less extreme and boring cases ;-)\n\nYes, I should be more careful with what I promise. :) I agree very much\nthat we should reserve that right.\n\n-Peff\n"},{"id":"191862","messageId":"20120521235219.GA5589@sigill.intra.peff.net","threadId":"30574","inReplyTo":"20120521221417.GA22664@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-21T23:52:19Z","receivedAt":"2012-05-21T23:52:19Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 21, 2012 at 06:14:17PM -0400, Jeff King wrote:\n\n> The rails and git cases run in ~28s and ~37s, respectively, again mostly\n> going to the actual object transfer. So I think this series removes all\n> of the asymptotically bad behavior from this code path.\n> \n> One thing to note about all of these repos is that they tend to have\n> several refs pointing to a single commit. None of the speedups in this\n> series depends on that fact, but it may be that on a repo with more\n> independent refs, we may uncover other code paths (e.g., I know that my\n> fix for mark_complete in ea5f220 improves the case with duplicate refs,\n> but would not help if you really have 400K refs pointing to unique\n> commits[1]).\n\nHmm. So I started to do some experimentation with this and noticed\nsomething odd.\n\nTry doing \"git fetch . refs/*:refs/*\" in a repository with a large\nnumber of refs (e.g., 400K). With git v1.7.10, this takes about 9.5s on\nmy machine. But using the version of git in \"next\" takes about 16.5s.\nBisection points to your 432ad41 (refs: store references hierarchically,\n2012-04-10). Perf shows sort_ref_dir and msort_with_tmp as hot spots.\n\n-Peff\n"},{"id":"191863","messageId":"20120522000747.GA8920@sigill.intra.peff.net","threadId":"30574","inReplyTo":"20120521235219.GA5589@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-22T00:07:47Z","receivedAt":"2012-05-22T00:07:47Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 21, 2012 at 07:52:19PM -0400, Jeff King wrote:\n\n> Try doing \"git fetch . refs/*:refs/*\" in a repository with a large\n> number of refs (e.g., 400K). With git v1.7.10, this takes about 9.5s on\n> my machine. But using the version of git in \"next\" takes about 16.5s.\n> Bisection points to your 432ad41 (refs: store references hierarchically,\n> 2012-04-10). Perf shows sort_ref_dir and msort_with_tmp as hot spots.\n\nA few more facts:\n\n  - I usually compile with -O0 because I am debugging so frequently.\n    With -O3, those numbers become 6.0s and 11.2s, respectively. Much\n    faster, but there is still a performance regression.\n\n  - Almost all of the refs are packed. IIRC, the packed-refs file should\n    already be sorted. I wonder if we did not bother double-checking\n    that before your patch, and now we do. That could explain the\n    difference.\n\n  - I don't compile with INTERNAL_QSORT. So mentioning msort_with_tmp is\n    slightly confusing, as it is actually the version from libc, not\n    ours IOW, it is really just qsort. But the primary culprit remains\n    sort_ref_dir.\n\n-Peff\n"},{"id":"191864","messageId":"4FBB0F21.5080608@alum.mit.edu","threadId":"30574","inReplyTo":"20120521235219.GA5589@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-22T03:59:29Z","receivedAt":"2012-05-22T03:59:29Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/22/2012 01:52 AM, Jeff King wrote:\n> On Mon, May 21, 2012 at 06:14:17PM -0400, Jeff King wrote:\n>\n>> The rails and git cases run in ~28s and ~37s, respectively, again mostly\n>> going to the actual object transfer. So I think this series removes all\n>> of the asymptotically bad behavior from this code path.\n>>\n>> One thing to note about all of these repos is that they tend to have\n>> several refs pointing to a single commit. None of the speedups in this\n>> series depends on that fact, but it may be that on a repo with more\n>> independent refs, we may uncover other code paths (e.g., I know that my\n>> fix for mark_complete in ea5f220 improves the case with duplicate refs,\n>> but would not help if you really have 400K refs pointing to unique\n>> commits[1]).\n>\n> Hmm. So I started to do some experimentation with this and noticed\n> something odd.\n>\n> Try doing \"git fetch . refs/*:refs/*\" in a repository with a large\n> number of refs (e.g., 400K). With git v1.7.10, this takes about 9.5s on\n> my machine. But using the version of git in \"next\" takes about 16.5s.\n> Bisection points to your 432ad41 (refs: store references hierarchically,\n> 2012-04-10). Perf shows sort_ref_dir and msort_with_tmp as hot spots.\n\nI'm looking into this.\n\nFor your test, were the 400k references all in one \"directory\", or were \nthey sharded somehow?\n\nA large number of packed references in a single namespace is the \nworst-case scenario for the hierarchical refs change.  Since the refs in \na namespace are all stored in a single array, there is no benefit from \nthe hierarchical storage whereas there is some extra cost from \ntraversing the namespace tree for each lookup.  But the performance hit \nshouldn't be this large.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191865","messageId":"20120522041123.GA9972@sigill.intra.peff.net","threadId":"30574","inReplyTo":"4FBB0F21.5080608@alum.mit.edu","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-22T04:11:23Z","receivedAt":"2012-05-22T04:11:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 22, 2012 at 05:59:29AM +0200, Michael Haggerty wrote:\n\n> >Try doing \"git fetch . refs/*:refs/*\" in a repository with a large\n> >number of refs (e.g., 400K). With git v1.7.10, this takes about 9.5s on\n> >my machine. But using the version of git in \"next\" takes about 16.5s.\n> >Bisection points to your 432ad41 (refs: store references hierarchically,\n> >2012-04-10). Perf shows sort_ref_dir and msort_with_tmp as hot spots.\n> \n> I'm looking into this.\n> \n> For your test, were the 400k references all in one \"directory\", or\n> were they sharded somehow?\n\nSharded. This was the rails network repo, so it basically looks like\nthis:\n\n  refs/remotes/XXXXXXX/heads/master\n  refs/remotes/XXXXXXX/tags/v1.0\n  refs/remotes/XXXXXXX/tags/v1.1\n  ...\n  refs/remotes/XXXXXXX/tags/v3.5\n  refs/remotes/YYYYYYY/heads/master\n  refs/remotes/YYYYYYY/tags/v1.0\n  refs/remotes/YYYYYYY/tags/v1.1\n  ...\n\nBasically the same 90 or so refs you would have in a normal repository\n(a branch or two, and a bunch of tags), repeated over and over under\nnumbered remote hierarchies (i.e., each remote is basically a copy of\nthe refs from somebody's fork of the repo).\n\nI can provide you with the exact repo if you want, but it is about 100M.\n\nInterestingly, I don't seem to get nearly as much slow-down in my \"fake\"\nmany-refs repo, which has all 100K entries directly in refs/heads.\n\n-Peff\n"},{"id":"191877","messageId":"3b77e2a3-872a-41c1-9a51-0f219a549c04@email.android.com","threadId":"30574","inReplyTo":"20120521194114.GA28358@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-05-22T05:51:16Z","receivedAt":"2012-05-22T05:51:16Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"\n\nJeff King <peff@peff.net> wrote:\n\n>On Mon, May 21, 2012 at 12:15:13PM -0600, Martin Fick wrote:\n>\n>> Of course, we use Gerrit, so features tend to be called \n>> changes and each change may get many revisions (patchsets), \n>> so all of these get refs, but I think that it might be wrong \n>> to consider that out of the ordinary anymore.  After all, \n>> should a version control system such as git not support 100K \n>> revisions of features developed independently on separate \n>> branches (within Gerrit or not)?  100K is not really that \n>> many when you consider a large project.  Even without \n>> Gerrit, if someone wanted to track that many features \n>> (likely over a few years), they will probably use up tons of \n>> refs.  \n...\n>\n>Anyway, my point is that we don't even have to talk about \"reasonable\"\n>or \"absurd\". Git should be fast even on absurd cases, because 99% of\n>the work has already been done, and the last 1% is easy.\n\nI hope you are right, but I don't quite completely share your optimism.  Some of that last 1% is perhaps last exactly because it is hard.  More specificaly, I am talking about the git protocol's ref advertisement on connection.  This has been considered a known issue for many years, yet it has not been fixed because it is hard to fix since it requires breaking the protocol in a non backwards compatible way.  I would be delighted if you had an easy fix for this rather fundamental ref scaling issue? We talked with Junio and Shawn and they agreed that it would be reasonable to put forward a proposal which does break backwards compatibility. So if there is a chance that there still may be another way, I hope it is found before this gets underway (no, I don't really expect that to happen),\n\n-Martin\n\nEmployee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum\n"},{"id":"191883","messageId":"4FBB3D2B.4010300@alum.mit.edu","threadId":"30574","inReplyTo":"20120522041123.GA9972@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-22T07:15:55Z","receivedAt":"2012-05-22T07:15:55Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/22/2012 06:11 AM, Jeff King wrote:\n> On Tue, May 22, 2012 at 05:59:29AM +0200, Michael Haggerty wrote:\n>\n>>> Try doing \"git fetch . refs/*:refs/*\" in a repository with a large\n>>> number of refs (e.g., 400K). With git v1.7.10, this takes about 9.5s on\n>>> my machine. But using the version of git in \"next\" takes about 16.5s.\n>>> Bisection points to your 432ad41 (refs: store references hierarchically,\n>>> 2012-04-10). Perf shows sort_ref_dir and msort_with_tmp as hot spots.\n>>\n>> I'm looking into this.\n>>\n>> For your test, were the 400k references all in one \"directory\", or\n>> were they sharded somehow?\n>\n> Sharded. This was the rails network repo, so it basically looks like\n> this:\n>\n>    refs/remotes/XXXXXXX/heads/master\n>    refs/remotes/XXXXXXX/tags/v1.0\n>    refs/remotes/XXXXXXX/tags/v1.1\n>    ...\n>    refs/remotes/XXXXXXX/tags/v3.5\n>    refs/remotes/YYYYYYY/heads/master\n>    refs/remotes/YYYYYYY/tags/v1.0\n>    refs/remotes/YYYYYYY/tags/v1.1\n>    ...\n>\n> Basically the same 90 or so refs you would have in a normal repository\n> (a branch or two, and a bunch of tags), repeated over and over under\n> numbered remote hierarchies (i.e., each remote is basically a copy of\n> the refs from somebody's fork of the repo).\n>\n> I can provide you with the exact repo if you want, but it is about 100M.\n>\n> Interestingly, I don't seem to get nearly as much slow-down in my \"fake\"\n> many-refs repo, which has all 100K entries directly in refs/heads.\n\nThat could explain why I cannot reproduce your result.  I have done all \nof my testing in fake repos (with sharded and non-sharded variants) with \nvery little file content.\n\nIf it is not too much trouble, please let me know where I can obtain \nyour test repo and what commands you used to get your result.  (Was the \nlocal repo already a full clone of the remote, including all 400k \nreferences?  How was the remote set up--sharing data or not, local or \nremote?  Warm or cold disk cache?)\n\nThanks,\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191884","messageId":"20120522073740.GA10093@sigill.intra.peff.net","threadId":"30574","inReplyTo":"4FBB3D2B.4010300@alum.mit.edu","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-22T07:37:40Z","receivedAt":"2012-05-22T07:37:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 22, 2012 at 09:15:55AM +0200, Michael Haggerty wrote:\n\n> If it is not too much trouble, please let me know where I can obtain\n> your test repo and what commands you used to get your result.  (Was\n> the local repo already a full clone of the remote, including all 400k\n> references?  How was the remote set up--sharing data or not, local or\n> remote?  Warm or cold disk cache?)\n\nI've put the repo up at:\n\n  https://gist.github.com/raw/2767328/603926240fabb4d3e3abc3c93a1913d91852cc7e/rails.tar.gz\n\nYou can reproduce the slow-down with:\n\n  cd rails.git &&\n  git fetch . refs/*:refs/*\n\nwhich should be a no-op, as we already have all of the refs. I don't\nknow if the problem is actually specific to fetch; that was just how I\nnoticed it.\n\nWhen I try it with both 'next' and v1.7.10, I see that the latter is\nmuch faster.  I did my tests with a warm cache, but the interesting\nnumber is the CPU time, which is quite different.\n\n-Peff\n"},{"id":"191892","messageId":"CACsJy8Dw+mbP+ttTP6gAfX9o4q4NyZgPYpbhS=tket=5fvBXwg@mail.gmail.com","threadId":"30574","inReplyTo":"20120521174525.GA22643@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-22T12:18:00Z","receivedAt":"2012-05-22T12:18:00Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, May 22, 2012 at 12:45 AM, Jeff King <peff@peff.net> wrote:\n> The rails/rails network repository at GitHub (i.e., a master repo with\n> all of the objects and refs for all of the forks) has about 400K refs,\n> and has been the usual impetus for me finding and fixing these sorts of\n> quadratic problems.\n\nOff topic and pure speculation. With 400k refs, each one 20 byte in\nlength, the pathname part only can take 7MB. Perhaps packed-refs\nshould learn prefix compressing too, like index v4, to reduce size\n(and hopefully improve startup speed). Compressing refs/heads/ and\nrefs/tags/ only could gain quite a bit already.\n-- \nDuy\n"},{"id":"191895","messageId":"4FBB9480.4010407@alum.mit.edu","threadId":"30574","inReplyTo":"20120522073740.GA10093@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-22T13:28:32Z","receivedAt":"2012-05-22T13:28:32Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/22/2012 09:37 AM, Jeff King wrote:\n> On Tue, May 22, 2012 at 09:15:55AM +0200, Michael Haggerty wrote:\n>\n>> If it is not too much trouble, please let me know where I can obtain\n>> your test repo and what commands you used to get your result.  (Was\n>> the local repo already a full clone of the remote, including all 400k\n>> references?  How was the remote set up--sharing data or not, local or\n>> remote?  Warm or cold disk cache?)\n>\n> I've put the repo up at:\n>\n>    https://gist.github.com/raw/2767328/603926240fabb4d3e3abc3c93a1913d91852cc7e/rails.tar.gz\n>\n> You can reproduce the slow-down with:\n>\n>    cd rails.git&&\n>    git fetch . refs/*:refs/*\n>\n> which should be a no-op, as we already have all of the refs. I don't\n> know if the problem is actually specific to fetch; that was just how I\n> noticed it.\n>\n> When I try it with both 'next' and v1.7.10, I see that the latter is\n> much faster.  I did my tests with a warm cache, but the interesting\n> number is the CPU time, which is quite different.\n\nI cannot reproduce anything as big as the performance regression that \nyou see.  I did find a regression 9.5 s -> 10.1 s caused by\n\n5fa044184 find_containing_dir(): use strbuf in implementation of this \nfunction\n\nIt is fixed by the patch that I just sent to the mailing list [1], which \nsizes the strbuf in that function to strlen(refname) instead of \nPATH_MAX.  Since your experiments suggest that the performance \nregression is related to the size of the repository contents, it could \nbe that the same test produces more memory pressure on your system and \ntherefore a larger effect.  Please try the patch and tell me if it fixes \nthe problem for you.\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/198197\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191896","messageId":"4FBB961A.2030806@alum.mit.edu","threadId":"30574","inReplyTo":"CACsJy8Dw+mbP+ttTP6gAfX9o4q4NyZgPYpbhS=tket=5fvBXwg@mail.gmail.com","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-22T13:35:22Z","receivedAt":"2012-05-22T13:35:22Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/22/2012 02:18 PM, Nguyen Thai Ngoc Duy wrote:\n> On Tue, May 22, 2012 at 12:45 AM, Jeff King<peff@peff.net>  wrote:\n>> The rails/rails network repository at GitHub (i.e., a master repo with\n>> all of the objects and refs for all of the forks) has about 400K refs,\n>> and has been the usual impetus for me finding and fixing these sorts of\n>> quadratic problems.\n>\n> Off topic and pure speculation. With 400k refs, each one 20 byte in\n> length, the pathname part only can take 7MB. Perhaps packed-refs\n> should learn prefix compressing too, like index v4, to reduce size\n> (and hopefully improve startup speed). Compressing refs/heads/ and\n> refs/tags/ only could gain quite a bit already.\n\nI considered this idea but put it off for now for the reasons explained \nin the docstring for struct ref_entry in refs.c:\n\n  * Please note that the name field contains the fully-qualified\n  * reference (or subdirectory) name.  Space could be saved by only\n  * storing the relative names.  But that would require the full names\n  * to be generated on the fly when iterating in do_for_each_ref(), and\n  * would break callback functions, who have always been able to assume\n  * that the name strings that they are passed will not be freed during\n  * the iteration.\n\nThus, all of the callers of the for_each_ref functions would have to be \naudited (and perhaps adjusted) before such a change could be implemented.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191899","messageId":"7vwr445gy8.fsf@alter.siamese.dyndns.org","threadId":"30574","inReplyTo":"20120521174525.GA22643@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-22T16:16:47Z","receivedAt":"2012-05-22T16:16:47Z","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> I don't think there is any reason we can't sort the list of heads, and\n> then we can get rid of the duplicates with an O(n) traversal, like the\n> (largely untested) patch below.\n\nYeah, I think the only case the order matters in fetch is the traditional\n\"when multiple non-glob fetch refspecs are configured, only merge the\nfirst one\" logic, but it kicks in a much higher layer and the order in\nthis list should not have any effect on it.\n\nThanks.\n"},{"id":"191903","messageId":"20120522170101.GA11600@sigill.intra.peff.net","threadId":"30574","inReplyTo":"CACsJy8Dw+mbP+ttTP6gAfX9o4q4NyZgPYpbhS=tket=5fvBXwg@mail.gmail.com","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-22T17:01:01Z","receivedAt":"2012-05-22T17:01:01Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 22, 2012 at 07:18:00PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Tue, May 22, 2012 at 12:45 AM, Jeff King <peff@peff.net> wrote:\n> > The rails/rails network repository at GitHub (i.e., a master repo with\n> > all of the objects and refs for all of the forks) has about 400K refs,\n> > and has been the usual impetus for me finding and fixing these sorts of\n> > quadratic problems.\n> \n> Off topic and pure speculation. With 400k refs, each one 20 byte in\n> length, the pathname part only can take 7MB. Perhaps packed-refs\n> should learn prefix compressing too, like index v4, to reduce size\n> (and hopefully improve startup speed). Compressing refs/heads/ and\n> refs/tags/ only could gain quite a bit already.\n\nIn this case, the packed-refs file is 30MB. Even just gzipping it takes\nit down to 2MB. As far as I know, we don't ever do random access on the\nfile, but instead just stream it into memory.\n\n-Peff\n"},{"id":"191907","messageId":"20120522173355.GC11600@sigill.intra.peff.net","threadId":"30574","inReplyTo":"4FBB9480.4010407@alum.mit.edu","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-22T17:33:55Z","receivedAt":"2012-05-22T17:33:55Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 22, 2012 at 03:28:32PM +0200, Michael Haggerty wrote:\n\n> >When I try it with both 'next' and v1.7.10, I see that the latter is\n> >much faster.  I did my tests with a warm cache, but the interesting\n> >number is the CPU time, which is quite different.\n> \n> I cannot reproduce anything as big as the performance regression that\n> you see.  I did find a regression 9.5 s -> 10.1 s caused by\n> \n> 5fa044184 find_containing_dir(): use strbuf in implementation of this\n> function\n> \n> It is fixed by the patch that I just sent to the mailing list [1],\n> which sizes the strbuf in that function to strlen(refname) instead of\n> PATH_MAX.  Since your experiments suggest that the performance\n> regression is related to the size of the repository contents, it\n> could be that the same test produces more memory pressure on your\n> system and therefore a larger effect.  Please try the patch and tell\n> me if it fixes the problem for you.\n\nThat patch drops about a second off of the slow case, but the main\nproblem still remains. Just to be sure we are both doing the exact same\nthing, here is a complete reproduction recipe:\n\n  GIT=/path/to/your/git/checkout\n  RAILS=/path/to/unpacked/rails.git\n\n  cd $GIT &&\n  git checkout 432ad41e60cedb87ceec446ab034d46a53f5f9d8^ &&\n  make &&\n\n  cd $RAILS &&\n  time $GIT/bin-wrappers/git fetch . refs/*:refs/* &&\n\n  cd $GIT &&\n  git checkout 432ad41e60cedb87ceec446ab034d46a53f5f9d8 &&\n  make &&\n\n  cd $RAILS &&\n  time $GIT/bin-wrappers/git fetch . refs/*:refs/*\n\nproduces:\n\n  [before]\n  real    0m9.128s\n  user    0m9.369s\n  sys     0m0.976s\n\n  [after]\n  real    0m15.926s\n  user    0m16.181s\n  sys     0m0.984s\n\nI don't think memory pressure is involved. The git process maxes out at\n~300M, and this machine has 7.5G available.\n\nI wonder why we are getting different results. Could it be compilation\noptions? As I mentioned, I compile with -O0, but I got similar results\nwith -O3.\n\n-Peff\n"},{"id":"191909","messageId":"7vaa105dah.fsf@alter.siamese.dyndns.org","threadId":"30574","inReplyTo":"20120522170101.GA11600@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-22T17:35:50Z","receivedAt":"2012-05-22T17:35:50Z","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, May 22, 2012 at 07:18:00PM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> On Tue, May 22, 2012 at 12:45 AM, Jeff King <peff@peff.net> wrote:\n>> > The rails/rails network repository at GitHub (i.e., a master repo with\n>> > all of the objects and refs for all of the forks) has about 400K refs,\n>> > and has been the usual impetus for me finding and fixing these sorts of\n>> > quadratic problems.\n>> \n>> Off topic and pure speculation. With 400k refs, each one 20 byte in\n>> length, the pathname part only can take 7MB. Perhaps packed-refs\n>> should learn prefix compressing too, like index v4, to reduce size\n>> (and hopefully improve startup speed). Compressing refs/heads/ and\n>> refs/tags/ only could gain quite a bit already.\n>\n> In this case, the packed-refs file is 30MB. Even just gzipping it takes\n> it down to 2MB. As far as I know, we don't ever do random access on the\n> file, but instead just stream it into memory.\n\nTrue.\n\nThe current code reads the whole thing in upon first use of _any_ element\nin the file, just like the index codepath does for the index file.\n\nBut the calling pattern to the refs machinery is fairly well isolated and\nall happens in refs.c file.  Especially thanks to the recent work by\nMichael Haggerty, for \"I am about to create a new branch 'frotz'; do I\nhave 'refs/heads/frotz' or anything that begins with 'refs/heads/frotz/'?\"\nkind of callers, it is reasonably easy to design a better structured\npacked-refs file format to allow us to read only a subtree portion of\nrefs/ hierarchy, and plug that logic into the lazy ref population code.\nSuch a \"design a better packed-refs format for scalability to 400k refs\"\nis a very well isolated project that has high chance of succeeding without\nbreaking things.  No code outside refs.c assumes that there is a flat\narray of refs that records what was read from the packed-refs file and can\nwalk linearly over it, unlike the in-core index.\n\nIf you do \"for_each_ref()\" for everything (e.g. sending 'have' during the\nobject transfer, or repacking the whole repository), you would end up\nneeding to read the whole thing for obvious reasons.\n"},{"id":"191911","messageId":"20120522174648.GE11600@sigill.intra.peff.net","threadId":"30574","inReplyTo":"7vaa105dah.fsf@alter.siamese.dyndns.org","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-22T17:46:48Z","receivedAt":"2012-05-22T17:46:48Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 22, 2012 at 10:35:50AM -0700, Junio C Hamano wrote:\n\n> > In this case, the packed-refs file is 30MB. Even just gzipping it takes\n> > it down to 2MB. As far as I know, we don't ever do random access on the\n> > file, but instead just stream it into memory.\n> \n> True.\n> \n> The current code reads the whole thing in upon first use of _any_ element\n> in the file, just like the index codepath does for the index file.\n> \n> But the calling pattern to the refs machinery is fairly well isolated and\n> all happens in refs.c file.  Especially thanks to the recent work by\n> Michael Haggerty, for \"I am about to create a new branch 'frotz'; do I\n> have 'refs/heads/frotz' or anything that begins with 'refs/heads/frotz/'?\"\n> kind of callers, it is reasonably easy to design a better structured\n> packed-refs file format to allow us to read only a subtree portion of\n> refs/ hierarchy, and plug that logic into the lazy ref population code.\n> Such a \"design a better packed-refs format for scalability to 400k refs\"\n> is a very well isolated project that has high chance of succeeding without\n> breaking things.  No code outside refs.c assumes that there is a flat\n> array of refs that records what was read from the packed-refs file and can\n> walk linearly over it, unlike the in-core index.\n\nYeah. As gross as I find a 30MB packed-refs file, I don't actually think\nthat is the bottle-neck at all. Sure, it wastes some disk cache, but\nin the grand scheme of things, anybody with 400K refs probably has a\nmuch, much bigger object database.\n\nSo there probably isn't much point in clever tricks to make it smaller\non disk, especially if they will make further partial-read optimizations\nharder to do. But...\n\n> If you do \"for_each_ref()\" for everything (e.g. sending 'have' during the\n> object transfer, or repacking the whole repository), you would end up\n> needing to read the whole thing for obvious reasons.\n\nI think Michael's work is really great for the loose refs, where hitting\neach directory is very expensive. But for a repo with packed refs that\nis just going to call for_each_ref, I'm worried that breaking apart the\nref list is going to cause noticeable overhead. But still, the\nregression I'm seeing seems way too big for that overhead, so I think\nsomething else is going on. We just need to find it.\n\n-Peff\n"},{"id":"191917","messageId":"20120522182157.GB20305@sigill.intra.peff.net","threadId":"30574","inReplyTo":"3b77e2a3-872a-41c1-9a51-0f219a549c04@email.android.com","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-22T18:21:57Z","receivedAt":"2012-05-22T18:21:57Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 21, 2012 at 11:51:16PM -0600, Martin Fick wrote:\n\n> >Anyway, my point is that we don't even have to talk about \"reasonable\"\n> >or \"absurd\". Git should be fast even on absurd cases, because 99% of\n> >the work has already been done, and the last 1% is easy.\n> \n> I hope you are right, but I don't quite completely share your\n> optimism.  Some of that last 1% is perhaps last exactly because it is\n> hard.  More specificaly, I am talking about the git protocol's ref\n> advertisement on connection.  This has been considered a known issue\n> for many years, yet it has not been fixed because it is hard to fix\n> since it requires breaking the protocol in a non backwards compatible\n> way.  I would be delighted if you had an easy fix for this rather\n> fundamental ref scaling issue? We talked with Junio and Shawn and they\n> agreed that it would be reasonable to put forward a proposal which\n> does break backwards compatibility. So if there is a chance that there\n> still may be another way, I hope it is found before this gets underway\n> (no, I don't really expect that to happen),\n\nI may be overly optimistic, but I think I may also have not communicated\nthe limits to my optimism. Right now, it is the case that some\noperations on many refs are just impossibly slow due to poor algorithm\nselection in the implementation. I am optimistic that we can drop those\nin favor of linear algorithms, or at least O(n lg n) algorithms in most\ncases. And that would bring these cases down from \"don't do that, it's\nbroken\" to \"it works, but obviously it's slower than not having a\nzillion refs\".\n\nI am not nearly as optimistic about the work scaling better than linear.\nThat is going to take some clever algorithms, as well as possibly some\ndesign tradeoffs. AFAIK, ref advertisement scales linearly. Which is\nprobably not acceptable over a slow link, and we could do better.\n\nBut in my mind, we are still doing the \"make it at least linear\" portion\nof the process. People aren't really using repos with tons of refs\nbecause they currently perform so poorly, so we don't yet have good data\non how to solve the \"better than linear\" problems. As the quadratic\nproblems clear up, hopefully the locations of (and solutions to) those\nother problems will be more clear.\n\n-Peff\n"},{"id":"191933","messageId":"7v7gw43rn9.fsf@alter.siamese.dyndns.org","threadId":"30574","inReplyTo":"20120521221702.GA22914@sigill.intra.peff.net","subject":"Re: [PATCH 1/5] fetch-pack: sort incoming heads","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-22T20:08:42Z","receivedAt":"2012-05-22T20:08:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> There's no reason to preserve the incoming order of the\n> heads we're requested to fetch. By having them sorted, we\n> can replace some of the quadratic algorithms with linear\n> ones.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> I actually wouldn't be surprised if these were typically sorted already,\n> as they frequently come from the ref-mapping functions, which in turn\n> process the lists we get from the remote. But we also might get random\n> junk on the command-line of fetch-pack, so we need to be careful.\n>\n>  builtin/fetch-pack.c | 7 +++++++\n>  1 file changed, 7 insertions(+)\n>\n> diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\n> index 10db15b..380743e 100644\n> --- a/builtin/fetch-pack.c\n> +++ b/builtin/fetch-pack.c\n> @@ -1057,6 +1057,11 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)\n>  \treturn ret;\n>  }\n>  \n> +static int compare_heads(const void *a, const void *b)\n> +{\n> +\treturn strcmp(*(const char **)a, *(const char **)b);\n> +}\n> +\n>  struct ref *fetch_pack(struct fetch_pack_args *my_args,\n>  \t\t       int fd[], struct child_process *conn,\n>  \t\t       const struct ref *ref,\n> @@ -1076,6 +1081,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,\n>  \t\t\tst.st_mtime = 0;\n>  \t}\n>  \n> +\tqsort(heads, nr_heads, sizeof(*heads), compare_heads);\n> +\n>  \tif (heads && nr_heads)\n>  \t\tnr_heads = remove_duplicates(nr_heads, heads);\n\nHrm, could heads and/or nr_heads be NULL/0 here when we try to run qsort()\nin this codepath?\n\n>  \tif (!ref) {\n"},{"id":"191934","messageId":"7v396s3ra5.fsf@alter.siamese.dyndns.org","threadId":"30574","inReplyTo":"20120521222329.GE22914@sigill.intra.peff.net","subject":"Re: [PATCH 5/5] fetch-pack: avoid quadratic loop in filter_refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-22T20:16:34Z","receivedAt":"2012-05-22T20:16:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> We have a list of refs that we want to compare against the\n> \"match\" array. The current code searches the match list\n> linearly, giving quadratic behavior over the number of refs\n> when you want to fetch all of them.\n>\n> Instead, we can compare the lists as we go, giving us linear\n> behavior.\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n\nNice.  Thanks.\n"},{"id":"191936","messageId":"20120522202336.GA31231@sigill.intra.peff.net","threadId":"30574","inReplyTo":"7v7gw43rn9.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 1/5] fetch-pack: sort incoming heads","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-22T20:23:36Z","receivedAt":"2012-05-22T20:23:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 22, 2012 at 01:08:42PM -0700, Junio C Hamano wrote:\n\n> > @@ -1076,6 +1081,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,\n> >  \t\t\tst.st_mtime = 0;\n> >  \t}\n> >  \n> > +\tqsort(heads, nr_heads, sizeof(*heads), compare_heads);\n> > +\n> >  \tif (heads && nr_heads)\n> >  \t\tnr_heads = remove_duplicates(nr_heads, heads);\n> \n> Hrm, could heads and/or nr_heads be NULL/0 here when we try to run qsort()\n> in this codepath?\n\nGood catch. I had originally put the qsort into remove_duplicates, but\nhoisted it out, as the second optimization depends on the sorting, too.\nheads can be NULL here (for example, if you run fetch-pack without any\narguments, and without --stdin; though why you would do so is a\nmystery, we should protect against it).\n\nA sane qsort would see that its second parameter is 0 and never try to\ndereference the array. But I'm not sure all qsort implementations we\nwill see are sane, so it's probably better to protect it by putting it\ninside the conditional block just below.\n\n-Peff\n"},{"id":"191957","messageId":"201205221619.31738.mfick@codeaurora.org","threadId":"30574","inReplyTo":"20120522182157.GB20305@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-05-22T22:19:30Z","receivedAt":"2012-05-22T22:19:30Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Tuesday, May 22, 2012 12:21:57 pm Jeff King wrote:\n> On Mon, May 21, 2012 at 11:51:16PM -0600, Martin Fick \nwrote:\n> AFAIK, ref advertisement scales linearly. Which is\n> probably not acceptable over a slow link, and we could\n> do better.\n\nRight, although it is not just a slow link issue.  Linear or \nnot, this problem does not scale, it needs to be based on N, \nthe number of refs which need updating, not N the number of \nrefs in the repo.\n\nI gave the following numbers to Junio and Shawn recently and \nI figure it is probably worth mentioning them here to \nperhaps give others some insights into just how bad this \nproblem can be...\n\nAndroid consists of approximately 400 projects, and if \nanyone tags their builds regularly, that means that they \nwill be tagging 400 projects per build.  We have something \nlike 10K tags on average across 400 projects, so when we do \na simple No Op sync just to see if all 400 projects are up \nto date, this yields about 200MB of data over the wire (4M \nrefs)!!!\n\nThat 200MB is using a -j4 on repo sync and it chews up about \n1.5 cores on a high end server to serve that 200MB for over \n1min.  Now imagine a build bot needing to build about 25 \nimages in parallel all just doing a No Op sync to see if \nthey are up to date!  That's 25 * 200MB = 5GB data and 25 * \n1.5 cores ~= 36 cores. That means our high end 24 core \nserver falls over all for a No Op.\n\nAs you can imagine, we really would like to see this \neliminated from our workflows.  If we want to check 400 \nprojects to see if they are up to date, it should be 400 \nrefs, not 400 * 10K,\n\n-Martin\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"191960","messageId":"7v8vgj3imy.fsf@alter.siamese.dyndns.org","threadId":"30574","inReplyTo":"201205221619.31738.mfick@codeaurora.org","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-22T23:23:17Z","receivedAt":"2012-05-22T23:23:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Fick <mfick@codeaurora.org> writes:\n\n> Android consists of approximately 400 projects, and if \n> anyone tags their builds regularly, that means that they \n> will be tagging 400 projects per build.  We have something \n> like 10K tags on average across 400 projects, so when we do \n> a simple No Op sync just to see if all 400 projects are up \n> to date, this yields about 200MB of data over the wire (4M \n> refs)!!!\n> ...\n> As you can imagine, we really would like to see this \n> eliminated from our workflows.  If we want to check 400 \n> projects to see if they are up to date, it should be 400 \n> refs, not 400 * 10K.\n\nI think we can ignore that 400 part from the above for now.  As they are\nindependent \"projects\", it is unreasonable to expect that any solution\nwould add costs less than linearly when you add more projects.  But it\nshould be possible to make the cost of update discovery comparable between\nthe cases where you have 10K existing refs that both ends have seen and\none ref got updated vs you started from 20K common refs.  The latter does\nnot have to cost twice (or 4 times if an inefficient way is quadratic).\n\nI think the assumption in your build-bot scenario needs to be a bit more\nclarified to give context.  I am assuming, when you say \"see if projects\nare up to date\", you mean your build-bot is interested in a single branch\nin each repository, possibly together with new tags that have become\nreachable from the updated tip of the branch (if the branch tip moved).  I\nalso assume that the build-bot polls very often and that is why 200MB (or\ndivided by 400 it would be 0.5MB, which still is a lot when you talk about\na single repository) hurts a lot.\n\nEverything below is what I think you already know about; I am giving an\noverview of _my_ understanding of the issue for the benefit of others (and\nhave you sanity check if I misunderstood your pain points).\n\nEven an attempt to optimize \"can we skip updating\" by asking \"ls-remote\"\nabout a single branch is futile with the current protocol, as we expect\nthe server to respond with the full ref advertisement and filter out the\nresult on our end.  In the upload-pack protocol, the serving side talks\nfirst and that is \"here are all the refs I have and their values\".  The\nother side that asks for objects does not have a way to tell it that it is\nonly interested in a subset, even if it wanted to.  Unlike the capability\nexchange that happens after the initial connection, there is no gap in\nthe protocol for the side that initiates the connection to tell the\nserving side to skip/delay the initial ref advertisement.\n\nWhat the above means is that the transition has to happen by keeping the\ncurrent upload-pack and a new protocol has to be invoked by a different\nprogram (\"upload-pack-2\" or something needs to be taught to the git-daemon\nand also invoked by ssh) even if an updated protocol is designed. The\nupdated connection initiator (i.e. ls-remote and fetch) may be able to try\nupload-pack-2 first and fall back to upload-pack after getting a failure,\nbut afaik nobody figured out if this is doable by checking if a failure\nsignal that comes from currently deployed software is detailed enough for\nour side to tell if the failure is because the other end does not support\nupload-pack-2 or because of some other failure (e.g. auth failed, no such\nrepo, etc.).  Regardless of auto-fallback, an updated connection initiator\nneeds a configuration switch to be explicitly told which protocol to talk\nto with which remote.\n\nWhat exact protocol \"upload-pack-2\" talks may be an interesting subject on\nits own.  It may still have the serving side talk first (probably show its\ncapabilities and tips of branches if there are not too many of them), or\nit may instead let the connection initiator talk first and ask for\nspecific set of refs.  But that is of lessor importance from the\nhigh-level point of view and I won't go into the details in this thread.\n"},{"id":"191965","messageId":"201205221846.38230.mfick@codeaurora.org","threadId":"30574","inReplyTo":"7v8vgj3imy.fsf@alter.siamese.dyndns.org","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-05-23T00:46:37Z","receivedAt":"2012-05-23T00:46:37Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Tuesday, May 22, 2012 05:23:17 pm Junio C Hamano wrote:\n> Martin Fick <mfick@codeaurora.org> writes:\n>\n> I think we can ignore that 400 part from the above for\n> now.  As they are independent \"projects\", it is\n> unreasonable to expect that any solution would add costs\n> less than linearly when you add more projects.  \n\nAs far as git is concerned, sure they are independent, but \nthe projects aren't really independent.  Separate repos were \nlikely selected for scalibility reasons in the first place, \nbut this ends up being a \"scale fail\" pattern.  I don't \nexpect git to fix this * 400 issue, but I want to highlight, \nhow difficult it is to make things scale in these cases and \nthat this problems is a natural multiplier when you split \nsomething into separate git repos because your tags tend to \nnow be multiplied.  So while 10K tags sound like a lot but \nmanageable for 1 repo, it ends up actually being 4M tags if \nyou split your repos.\n\n\n...\n> I think the assumption in your build-bot scenario needs\n> to be a bit more clarified to give context.  I am\n> assuming, when you say \"see if projects are up to date\",\n> you mean your build-bot is interested in a single branch\n> in each repository, possibly together with new tags that\n> have become reachable from the updated tip of the branch\n> (if the branch tip moved). \n\nJust the branch generally.\n\n\n> I also assume that the\n> build-bot polls very often and that is why 200MB (or\n> divided by 400 it would be 0.5MB, which still is a lot\n> when you talk about a single repository) hurts a lot.\n\nTo clarify for others (since you likely know), we serialize \nour submits, so the \"poll\" is before every build to ensure \nthat we are up to date with what just got merged.  In our \ncase we use Gerrit with slaves (read only Gerrit copies), so \nwe offload the \"update\" to the slave, which incurs the same \nhit, all though it is not quite a No Op but close (there \nwill have been a batch of commits added to a few projects).  \nBut then since the slave may be slightly behind the master \n(replication from the master to the slave takes time, \npartially because of the same ref advertisement problem), so \nwe want to verify the slave update by polling the master, \nwhich if replication was fast enough would be a No Op.  So, \nour attempts to scale by using slaves does not help very \nmuch since the real update and the No Op are almost \nidentical in their impacts... There are workarounds, but \nmostly hacks.\n\n\n...\n> Unlike the capability exchange that happens after the\n> initial connection, there is no gap in the protocol for\n> the side that initiates the connection to tell the\n> serving side to skip/delay the initial ref\n> advertisement.\n\nCrazy stupid suggestion: could the URI somehow be exploited \nto signal the option to disable advertisements?  What if the \npath part of the URI started with something like several \nslashes?  Older servers just strip the extra slashes right?  \nNewer servers could disable advertisements if they see the \nslashes.  Of course, this gets ugly if scripts add slashes \nand expect them to be stripped (old clients talking to new \nservers would probably then fail),\n\n-Martin\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"191966","messageId":"CACsJy8BwHd0JVJ0H-H8-ZHSFjwUb0=E1gJZR1fMSN--B6jdBow@mail.gmail.com","threadId":"30574","inReplyTo":"20120522170101.GA11600@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-23T01:20:21Z","receivedAt":"2012-05-23T01:20:21Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, May 23, 2012 at 12:01 AM, Jeff King <peff@peff.net> wrote:\n> On Tue, May 22, 2012 at 07:18:00PM +0700, Nguyen Thai Ngoc Duy wrote:\n>\n>> On Tue, May 22, 2012 at 12:45 AM, Jeff King <peff@peff.net> wrote:\n>> > The rails/rails network repository at GitHub (i.e., a master repo with\n>> > all of the objects and refs for all of the forks) has about 400K refs,\n>> > and has been the usual impetus for me finding and fixing these sorts of\n>> > quadratic problems.\n>>\n>> Off topic and pure speculation. With 400k refs, each one 20 byte in\n>> length, the pathname part only can take 7MB. Perhaps packed-refs\n>> should learn prefix compressing too, like index v4, to reduce size\n>> (and hopefully improve startup speed). Compressing refs/heads/ and\n>> refs/tags/ only could gain quite a bit already.\n>\n> In this case, the packed-refs file is 30MB. Even just gzipping it takes\n> it down to 2MB. As far as I know, we don't ever do random access on the\n> file, but instead just stream it into memory.\n\nI did not think really hard when I wrote what I wrote. File size is\nnot really a problem here. In index case, we do expensive sha-1 on the\nentire file so size matters. We don't do anything that expensive in\npacked-refs (, I think. Should we protect it with some sort of\nchecksum btw?). gzip can add more computation cost at startup. 30MB is\nprobably still ok.\n\nThough sending 2MB on the wire is way better than 30MB when we\nadvertise refs at cloning/fetching.\n-- \nDuy\n"},{"id":"192044","messageId":"4FBDBEEF.4030500@alum.mit.edu","threadId":"30574","inReplyTo":"7vaa105dah.fsf@alter.siamese.dyndns.org","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-24T04:54:07Z","receivedAt":"2012-05-24T04:54:07Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/22/2012 07:35 PM, Junio C Hamano wrote:\n> The current code reads the whole thing in upon first use of _any_ element\n> in the file, just like the index codepath does for the index file.\n>\n> But the calling pattern to the refs machinery is fairly well isolated and\n> all happens in refs.c file.  Especially thanks to the recent work by\n> Michael Haggerty, for \"I am about to create a new branch 'frotz'; do I\n> have 'refs/heads/frotz' or anything that begins with 'refs/heads/frotz/'?\"\n> kind of callers, it is reasonably easy to design a better structured\n> packed-refs file format to allow us to read only a subtree portion of\n> refs/ hierarchy, and plug that logic into the lazy ref population code.\n> Such a \"design a better packed-refs format for scalability to 400k refs\"\n> is a very well isolated project that has high chance of succeeding without\n> breaking things.  No code outside refs.c assumes that there is a flat\n> array of refs that records what was read from the packed-refs file and can\n> walk linearly over it, unlike the in-core index.\n\nEven with the current file format, it would not be so difficult to \nbisect the file, synchronizing on record boundaries by looking for the \nnext NL character.  Because of the way the file is sorted, it would also \nbe reasonably efficient to read whole subtrees in one slurp (e.g., for \nfor_each_ref() with a prefix argument).  Nontrivial modifications would \nof course not be possible without a rewrite.\n\nThere would need to be some intelligence built-in; after enough \nsingle-reference accesses come in a row, then the refs module should \nprobably take it upon itself to read the whole packed-refs file to speed \nup further lookups.\n\n> If you do \"for_each_ref()\" for everything (e.g. sending 'have' during the\n> object transfer, or repacking the whole repository), you would end up\n> needing to read the whole thing for obvious reasons.\n\nYes.  ISTM that any hope to avoid O(number of refs) problems when \nexchanging commits must involve using more intelligence about how \nreferences are related to each other topologically to improve the \nnegotiation about what needs to be transferred.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"192050","messageId":"20120524060451.GA13502@sigill.intra.peff.net","threadId":"30574","inReplyTo":"20120522202336.GA31231@sigill.intra.peff.net","subject":"Re: [PATCH 1/5] fetch-pack: sort incoming heads","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-24T06:04:51Z","receivedAt":"2012-05-24T06:04:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 22, 2012 at 04:23:36PM -0400, Jeff King wrote:\n\n> On Tue, May 22, 2012 at 01:08:42PM -0700, Junio C Hamano wrote:\n> \n> > > @@ -1076,6 +1081,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,\n> > >  \t\t\tst.st_mtime = 0;\n> > >  \t}\n> > >  \n> > > +\tqsort(heads, nr_heads, sizeof(*heads), compare_heads);\n> > > +\n> > >  \tif (heads && nr_heads)\n> > >  \t\tnr_heads = remove_duplicates(nr_heads, heads);\n> > \n> > Hrm, could heads and/or nr_heads be NULL/0 here when we try to run qsort()\n> > in this codepath?\n> [...]\n> A sane qsort would see that its second parameter is 0 and never try to\n> dereference the array. But I'm not sure all qsort implementations we\n> will see are sane, so it's probably better to protect it by putting it\n> inside the conditional block just below.\n\nI eye-balled what you queued in pu, and I wonder if you mis-read my\n\"just below\" as \"just below the existing line in the conditional\" and\nnot \"in the conditional that is just below the code we are talking\nabout\".\n\nI think we need this on top (or squashed in, but it looks like it is\nalready in next):\n\n-- >8 --\nSubject: fetch-pack: sort incoming heads list earlier\n\nCommit 4435968 started sorting heads fed to fetch-pack so\nthat later commits could use more optimized algorithms;\ncommit 7db8d53 switched the remove_duplicates function to\nsuch an algorithm.\n\nOf course, the sorting is more effective if you do it\n_before_ the algorithm in question.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI suspect that all parts of git feed the refs in sorted order already,\nwhich is why there were no test failures. But we should handle arbitrary\norder from the command-line.\n\n builtin/fetch-pack.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex 8a72473..b18ba05 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -1082,8 +1082,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,\n \t}\n \n \tif (heads && nr_heads) {\n-\t\tnr_heads = remove_duplicates(nr_heads, heads);\n \t\tqsort(heads, nr_heads, sizeof(*heads), compare_heads);\n+\t\tnr_heads = remove_duplicates(nr_heads, heads);\n \t}\n \n \tif (!ref) {\n-- \n1.7.10.1.25.g7031a0f\n"},{"id":"192061","messageId":"4FBE23FC.5070405@alum.mit.edu","threadId":"30574","inReplyTo":"20120522173355.GC11600@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-24T12:05:16Z","receivedAt":"2012-05-24T12:05:16Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/22/2012 07:33 PM, Jeff King wrote:\n> On Tue, May 22, 2012 at 03:28:32PM +0200, Michael Haggerty wrote:\n>\n>>> When I try it with both 'next' and v1.7.10, I see that the latter is\n>>> much faster.  I did my tests with a warm cache, but the interesting\n>>> number is the CPU time, which is quite different.\n>>\n>> I cannot reproduce anything as big as the performance regression that\n>> you see.  I did find a regression 9.5 s ->  10.1 s caused by\n>>\n>> 5fa044184 find_containing_dir(): use strbuf in implementation of this\n>> function\n>>\n>> It is fixed by the patch that I just sent to the mailing list [1],\n>> which sizes the strbuf in that function to strlen(refname) instead of\n>> PATH_MAX.  Since your experiments suggest that the performance\n>> regression is related to the size of the repository contents, it\n>> could be that the same test produces more memory pressure on your\n>> system and therefore a larger effect.  Please try the patch and tell\n>> me if it fixes the problem for you.\n>\n> That patch drops about a second off of the slow case, but the main\n> problem still remains. Just to be sure we are both doing the exact same\n> thing, here is a complete reproduction recipe:\n>\n>    GIT=/path/to/your/git/checkout\n>    RAILS=/path/to/unpacked/rails.git\n>\n>    cd $GIT&&\n>    git checkout 432ad41e60cedb87ceec446ab034d46a53f5f9d8^&&\n>    make&&\n>\n>    cd $RAILS&&\n>    time $GIT/bin-wrappers/git fetch . refs/*:refs/*&&\n>\n>    cd $GIT&&\n>    git checkout 432ad41e60cedb87ceec446ab034d46a53f5f9d8&&\n>    make&&\n>\n>    cd $RAILS&&\n>    time $GIT/bin-wrappers/git fetch . refs/*:refs/*\n>\n> produces:\n>\n>    [before]\n>    real    0m9.128s\n>    user    0m9.369s\n>    sys     0m0.976s\n>\n>    [after]\n>    real    0m15.926s\n>    user    0m16.181s\n>    sys     0m0.984s\n>\n> I don't think memory pressure is involved. The git process maxes out at\n> ~300M, and this machine has 7.5G available.\n>\n> I wonder why we are getting different results. Could it be compilation\n> options? As I mentioned, I compile with -O0, but I got similar results\n> with -O3.\n\nThanks for the idiot-proof reproduction steps.  I don't know what I was \ndoing differently last time, but now I can reproduce your slowdown.\n\nThe thing that triggers the problem is a reference directory \n(\"refs/remotes/8514/pull/\") with 3810 sub-namespaces \n(\"refs/remotes/8514/pull/1091\", \"refs/remotes/8514/pull/1092\", etc), \neach subnamespace containing only one or two references.  It wouldn't be \na problem having so many *references* in a namespace, because references \nare just added to the end of the directory unsorted, and typically only \nsorted once after all of them have been added.  But every time that a \nsub-namespace is accessed, the namespace has to be searched to see if \nthat sub-namespace already exists.  The searching requires the namespace \nto be sorted.  So, for example, when adding the following sequence of \nreferences:\n\n1. refs/remotes/8514/pull/1091/head\n2. refs/remotes/8514/pull/1091/merge\n3. refs/remotes/8514/pull/1092/head\n4. refs/remotes/8514/pull/1092/merge\n5. refs/remotes/8514/pull/1093/head\n6. refs/remotes/8514/pull/1093/merge\n\nAt step 1, sub-namespace \"refs/remotes/8514/pull/1091/\" is added to \n\"refs/remotes/8514/pull/\".  This makes the code think that \n\"refs/remotes/8514/pull/\" is unsorted.\n\nStep 2 is not problematic; the new references is added to \n\"refs/remotes/8514/pull/1091/\", but adding a reference doesn't require \nthe ref_dir to be sorted.\n\nAt step 3, namespace \"refs/remotes/8514/pull/\" is first checked to see \nif sub-namespace \"refs/remotes/8514/pull/1092/\" already exists.  This \nsearch requires namespace \"refs/remotes/8514/pull/\" to be sorted because \nstep 1 caused it to be considered unsorted.\n\nAgain at step 5, namespace \"refs/remotes/8514/pull/\" needs to be sorted, \nand so on every time a subnamespace is added.\n\nI will submit a patch shortly.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"192143","messageId":"201205241817.46034.mfick@codeaurora.org","threadId":"30574","inReplyTo":"20120521221417.GA22664@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-05-25T00:17:45Z","receivedAt":"2012-05-25T00:17:45Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Monday, May 21, 2012 04:14:17 pm Jeff King wrote:\n> On Mon, May 21, 2012 at 01:45:25PM -0400, Jeff King wrote:\n> Martin, let me know if this improves things for your\n> many-ref cases (and if you are still seeing slowness in\n> your repos with many refs, let me know which operations\n> cause it).\n\nPeff,\n\nI have not been ignoring you, I am sorry that I have not \nreplied yet.  Unfortunately, I am having a very hard time \ngetting conclusive tests with my large repo.  I making\nplenty of mistakes in what I think I am testing I believe,\nbut also I am having a hard time getting reproducible \nresults so far.  And some tests take quite a while, so it is \nnot always obvious what I might be doing wrong.\n\nI will let you know more when I figure out what I am doing \nwrong, but please know that I have been doing a lot of \ntesting and plan to post some results eventually.\n\nWere your tests mostly warm cache tests?\n\n-Martin\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"192145","messageId":"20120525003920.GB11300@sigill.intra.peff.net","threadId":"30574","inReplyTo":"201205241817.46034.mfick@codeaurora.org","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-25T00:39:20Z","receivedAt":"2012-05-25T00:39:20Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 24, 2012 at 06:17:45PM -0600, Martin Fick wrote:\n\n> On Monday, May 21, 2012 04:14:17 pm Jeff King wrote:\n> > On Mon, May 21, 2012 at 01:45:25PM -0400, Jeff King wrote:\n> > Martin, let me know if this improves things for your\n> > many-ref cases (and if you are still seeing slowness in\n> > your repos with many refs, let me know which operations\n> > cause it).\n> \n> I have not been ignoring you, I am sorry that I have not \n> replied yet.  Unfortunately, I am having a very hard time \n> getting conclusive tests with my large repo.  I making\n> plenty of mistakes in what I think I am testing I believe,\n> but also I am having a hard time getting reproducible \n> results so far.  And some tests take quite a while, so it is \n> not always obvious what I might be doing wrong.\n\nNo worries. I am pretty confident that the patches I supplied so far are\na good thing whether they help your case or not. So if you come back in\na month and show that they solved all your problems, then great. And if\nthey don't, then it will just show us what new problems we have to work\non. :)\n\n> Were your tests mostly warm cache tests?\n\nYes, exclusively warm. And all of the refs were packed, which makes the\nwarm/cold difference less interesting (it's one 30MB or so file).  I\ndon't think there's much point in thinking about the performance of 400K\nloose refs (which would be absolutely horrific cold-cache on most\ntraditional filesystems). If you have that many, you would want to keep\nthe bulk of them packed.\n\n-Peff\n"},{"id":"192147","messageId":"201205241854.56934.mfick@codeaurora.org","threadId":"30574","inReplyTo":"20120525003920.GB11300@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-05-25T00:54:56Z","receivedAt":"2012-05-25T00:54:56Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Thursday, May 24, 2012 06:39:20 pm Jeff King wrote:\n> On Thu, May 24, 2012 at 06:17:45PM -0600, Martin Fick \nwrote:\n> > Were your tests mostly warm cache tests?\n> \n> Yes, exclusively warm. And all of the refs were packed,\n> which makes the warm/cold difference less interesting\n> (it's one 30MB or so file).  I don't think there's much\n> point in thinking about the performance of 400K loose\n> refs (which would be absolutely horrific cold-cache on\n> most traditional filesystems). If you have that many,\n> you would want to keep the bulk of them packed.\n\nMostly true, except for one strange case still I think?\n\nWhen cloning a gerrit repo, users to not get the changes \nsince they are not under refs/heads but refs/changes.  So \nlater, if they choose to fetch refs/changes/*, all of those\nnew incoming refs are loose.  Yes, someone should pack those \nrefs right away, but I think it actually churns the hell out \nof my disk and takes a significant amount of time during the \ninitial fetch.  I am not certain about this, and the \nbehavior may depend on the filesystem in use, but I think \nthat this time might even be asynchronous (journals and \nall), it feels like my disk keeps churning for a while even \nafter this is over.  I believe that this might still be the \nworst case left with refs, and it can be pretty bad,\n\n-Martin\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"192148","messageId":"20120525010434.GA11861@sigill.intra.peff.net","threadId":"30574","inReplyTo":"201205241854.56934.mfick@codeaurora.org","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-25T01:04:34Z","receivedAt":"2012-05-25T01:04:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 24, 2012 at 06:54:56PM -0600, Martin Fick wrote:\n\n> > Yes, exclusively warm. And all of the refs were packed,\n> > which makes the warm/cold difference less interesting\n> > (it's one 30MB or so file).  I don't think there's much\n> > point in thinking about the performance of 400K loose\n> > refs (which would be absolutely horrific cold-cache on\n> > most traditional filesystems). If you have that many,\n> > you would want to keep the bulk of them packed.\n> \n> Mostly true, except for one strange case still I think?\n> \n> When cloning a gerrit repo, users to not get the changes \n> since they are not under refs/heads but refs/changes.  So \n> later, if they choose to fetch refs/changes/*, all of those\n> new incoming refs are loose.\n\nHmm. Yeah, clone will always write a packed-refs file, but I think \"git\nfetch\" will always write loose refs, under the assumption that the\nformer will be getting a lot more refs than the latter. But of course\nthat is only a guess. It would be nice if fetch could fetch straight\ninto packed refs if we are getting more than N items.\n\nWe'd have to give some thought to potential race conditions, though.\nUsually pack-refs isn't modifying the ref, so it can just write out the\nvalue to the packed-refs file, then delete the loose ref if nobody has\ntouched it since we wrote. But here we're combining it with a\nmodification, so I suspect there would be a race with another process\ntrying to modify it.\n\n> Yes, someone should pack those \n> refs right away, but I think it actually churns the hell out \n> of my disk and takes a significant amount of time during the \n> initial fetch.  I am not certain about this, and the \n> behavior may depend on the filesystem in use, but I think \n> that this time might even be asynchronous (journals and \n> all), it feels like my disk keeps churning for a while even \n> after this is over.  I believe that this might still be the \n> worst case left with refs, and it can be pretty bad,\n\nYeah, I wouldn't be surprised if this thrashes your disk. Writing\nhundreds of thousands of 40-byte files is one of the most awful loads\nfor many filesystems, since each file gets its own inode. I haven't\ntried btrfs, but my impression is that it can magically pack the data\nfrom many files into one node.\n\n-Peff\n"},{"id":"192149","messageId":"201205241932.37045.mfick@codeaurora.org","threadId":"30574","inReplyTo":"20120525010434.GA11861@sigill.intra.peff.net","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-05-25T01:32:36Z","receivedAt":"2012-05-25T01:32:36Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Thursday, May 24, 2012 07:04:34 pm Jeff King wrote:\n> On Thu, May 24, 2012 at 06:54:56PM -0600, Martin Fick \nwrote:\n> > > Yes, exclusively warm. And all of the refs were\n> We'd have to give some thought to potential race\n> conditions, though. Usually pack-refs isn't modifying\n> the ref, so it can just write out the value to the\n> packed-refs file, then delete the loose ref if nobody\n> has touched it since we wrote. But here we're combining\n> it with a modification, so I suspect there would be a\n> race with another process trying to modify it.\n\nYeah, I thought about that.  Could you just right the new \npacked-ref file with the new refs and the old refs which \nwere in the file already, then just delete any loose refs \nwhich were ones which were just added by this operation, \nonly if they have not changed?\n\nThis way, if someone else modifies one of the same refs, \nthey could just win?\n\n-Martin\n\n\n-- \nEmployee of Qualcomm Innovation Center, Inc. which is a \nmember of Code Aurora Forum\n"},{"id":"192152","messageId":"20120525065038.GA12249@sigill.intra.peff.net","threadId":"30574","inReplyTo":"201205241932.37045.mfick@codeaurora.org","subject":"Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-05-25T06:50:40Z","receivedAt":"2012-05-25T06:50:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 24, 2012 at 07:32:36PM -0600, Martin Fick wrote:\n\n> > > > Yes, exclusively warm. And all of the refs were\n> > We'd have to give some thought to potential race\n> > conditions, though. Usually pack-refs isn't modifying\n> > the ref, so it can just write out the value to the\n> > packed-refs file, then delete the loose ref if nobody\n> > has touched it since we wrote. But here we're combining\n> > it with a modification, so I suspect there would be a\n> > race with another process trying to modify it.\n> \n> Yeah, I thought about that.  Could you just right the new \n> packed-ref file with the new refs and the old refs which \n> were in the file already, then just delete any loose refs \n> which were ones which were just added by this operation, \n> only if they have not changed?\n> \n> This way, if someone else modifies one of the same refs, \n> they could just win?\n\nI spent a bit of time thinking on this and trying to come up with an\nexact sequence where we could lose the race, but I don't think we can\nlose data.  Either:\n\n  1. The loose ref is not changed afterwards, and we delete it, making\n     our packed version the official one.\n\n  2. The loose ref is changed, and we leave it, which means our packed\n     version is not interesting to anybody (the loose version takes\n     precedence). We have lost the race, and must consider our write a\n     failure.\n\nIt's OK to fail in (2); that is no different than the regular loose\ncase. And likewise, it's worth it to look at the other writer.\n\nThey might see our packed-refs file in place before we have a chance to\nmodify the loose ref. But that's OK, because they must double-check the\nexistence of the loose ref, and it will still be there. So they will\ntake that as the real value and ignore the packed value.\n\nAll of that is more or less the same set of rules that make \"git\npack-refs\" work at all. The only novel situation we are introducing here\nis that we might be writing a packed-ref without having an existing\nloose ref at all (whereas usually we would be packing an existing ref,\neither loose or packed). But I don't think it makes a difference.\n\nI might be wrong, though. In the course of writing this email, I kept\nthinking \"wait, but here's a race\", and then when I worked out the\ndetails, it was OK. So either I was not clever enough to find a race, or\nI am not clever enough to realize that there is not one. :)\n\n-Peff\n"}]}