{"thread":{"id":"28374","subject":"[PATCH] fetch: avoid quadratic loop checking for updated submodules","startedAt":"2011-09-12T19:56:52Z","lastAt":"2011-09-14T18:29:33Z","messageCount":17,"participants":["Jeff King","Junio C Hamano","Christian Couder","Jens Lehmann","Marc Branchaud"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"175354","messageId":"20110912195652.GA27850@sigill.intra.peff.net","threadId":"28374","inReplyTo":null,"subject":"[PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-09-12T19:56:52Z","receivedAt":"2011-09-12T19:56:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Recent versions of git can be slow to fetch repositories with a\nlarge number of refs (or when they already have a large\nnumber of refs). For example, GitHub makes pull-requests\navailable as refs, which can lead to a large number of\navailable refs. This slowness goes away when submodule\nrecursion is turned off:\n\n  $ git ls-remote git://github.com/rails/rails.git | wc -l\n  3034\n\n  [this takes ~10 seconds of CPU time to complete]\n  git fetch --recurse-submodules=no \\\n    git://github.com/rails/rails.git \"refs/*:refs/*\"\n\n  [this still isn't done after 10 _minutes_ of pegging the CPU]\n  git fetch \\\n    git://github.com/rails/rails.git \"refs/*:refs/*\"\n\nYou can produce a quicker and simpler test case like this:\n\n  doit() {\n    head=`git rev-parse HEAD`\n    for i in `seq 1 $1`; do\n      echo $head refs/heads/ref$i\n    done >.git/packed-refs\n    echo \"==> $1\"\n    rm -rf dest\n    git init -q --bare dest &&\n      (cd dest && time git.compile fetch -q .. refs/*:refs/*)\n  }\n\n  rm -rf repo\n  git init -q repo && cd repo &&\n  >file && git add file && git commit -q -m one\n\n  doit 100\n  doit 200\n  doit 400\n  doit 800\n  doit 1600\n  doit 3200\n\nWhich yields timings like:\n\n  # refs  seconds of CPU\n     100            0.06\n     200            0.24\n     400            0.95\n     800            3.39\n    1600           13.66\n    3200           54.09\n\nNotice that although the number of refs doubles in each\ntrial, the CPU time spent quadruples.\n\nThe problem is that the submodule recursion code works\nsomething like:\n\n  - for each ref we fetch\n    - for each commit in git rev-list $new_sha1 --not --all\n      - add modified submodules to list\n  - fetch any newly referenced submodules\n\nBut that means if we fetch N refs, we start N revision\nwalks. Worse, because we use \"--all\", the number of refs we\nmust process that constitute \"--all\" keeps growing, too. And\nyou end up doing O(N^2) ref resolutions.\n\nInstead, this patch structures the code like this:\n\n  - for each sha1 we already have\n    - add $old_sha1 to list $old\n  - for each ref we fetch\n    - add $new_sha1 to list $new\n  - for each commit in git rev-list $new --not $old\n    - add modified submodules to list\n  - fetch any newly referenced submodules\n\nThis yields timings like:\n\n  # refs  seconds of CPU\n  100               0.00\n  200               0.04\n  400               0.04\n  800               0.10\n  1600              0.21\n  3200              0.39\n\nNote that the amount of effort doubles as the number of refs\ndoubles. Similarly, the fetch of rails.git takes about as\nmuch time as it does with --recurse-submodules=no.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n submodule.c |   76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++----\n 1 files changed, 71 insertions(+), 5 deletions(-)\n\ndiff --git a/submodule.c b/submodule.c\nindex 7a76edf..00aeb71 100644\n--- a/submodule.c\n+++ b/submodule.c\n@@ -8,12 +8,17 @@\n #include \"diffcore.h\"\n #include \"refs.h\"\n #include \"string-list.h\"\n+#include \"sha1-array.h\"\n \n static struct string_list config_name_for_path;\n static struct string_list config_fetch_recurse_submodules_for_name;\n static struct string_list config_ignore_for_name;\n static int config_fetch_recurse_submodules = RECURSE_SUBMODULES_ON_DEMAND;\n static struct string_list changed_submodule_paths;\n+static int initialized_fetch_ref_tips;\n+static struct sha1_array ref_tips_before_fetch;\n+static struct sha1_array ref_tips_after_fetch;\n+\n /*\n  * The following flag is set if the .gitmodules file is unmerged. We then\n  * disable recursion for all submodules where .git/config doesn't have a\n@@ -474,16 +479,71 @@ static void submodule_collect_changed_cb(struct diff_queue_struct *q,\n \t}\n }\n \n+static int add_sha1_to_array(const char *ref, const unsigned char *sha1,\n+\t\t\t     int flags, void *data)\n+{\n+\tsha1_array_append(data, sha1);\n+\treturn 0;\n+}\n+\n void check_for_new_submodule_commits(unsigned char new_sha1[20])\n {\n+\tif (!initialized_fetch_ref_tips) {\n+\t\tfor_each_ref(add_sha1_to_array, &ref_tips_before_fetch);\n+\t\tinitialized_fetch_ref_tips = 1;\n+\t}\n+\n+\tsha1_array_append(&ref_tips_after_fetch, new_sha1);\n+}\n+\n+struct argv_array {\n+\tconst char **argv;\n+\tunsigned int argc;\n+\tunsigned int alloc;\n+};\n+\n+static void init_argv(struct argv_array *array)\n+{\n+\tarray->argv = NULL;\n+\tarray->argc = 0;\n+\tarray->alloc = 0;\n+}\n+\n+static void push_argv(struct argv_array *array, const char *value)\n+{\n+\tALLOC_GROW(array->argv, array->argc + 2, array->alloc);\n+\tarray->argv[array->argc++] = xstrdup(value);\n+\tarray->argv[array->argc] = NULL;\n+}\n+\n+static void clear_argv(struct argv_array *array)\n+{\n+\tint i;\n+\tfor (i = 0; i < array->argc; i++)\n+\t\tfree((char **)array->argv[i]);\n+\tfree(array->argv);\n+\tinit_argv(array);\n+}\n+\n+static void add_sha1_to_argv(const unsigned char sha1[20], void *data)\n+{\n+\tpush_argv(data, sha1_to_hex(sha1));\n+}\n+\n+static void calculate_changed_submodule_paths() {\n \tstruct rev_info rev;\n \tstruct commit *commit;\n-\tconst char *argv[] = {NULL, NULL, \"--not\", \"--all\", NULL};\n-\tint argc = ARRAY_SIZE(argv) - 1;\n+\tstruct argv_array argv;\n \n \tinit_revisions(&rev, NULL);\n-\targv[1] = xstrdup(sha1_to_hex(new_sha1));\n-\tsetup_revisions(argc, argv, &rev, NULL);\n+\tinit_argv(&argv);\n+\tpush_argv(&argv, \"--\"); /* argv[0] program name */\n+\tsha1_array_for_each_unique(&ref_tips_after_fetch,\n+\t\t\t\t   add_sha1_to_argv, &argv);\n+\tpush_argv(&argv, \"--not\");\n+\tsha1_array_for_each_unique(&ref_tips_before_fetch,\n+\t\t\t\t   add_sha1_to_argv, &argv);\n+\tsetup_revisions(argv.argc, argv.argv, &rev, NULL);\n \tif (prepare_revision_walk(&rev))\n \t\tdie(\"revision walk setup failed\");\n \n@@ -507,7 +567,11 @@ void check_for_new_submodule_commits(unsigned char new_sha1[20])\n \t\t\tparent = parent->next;\n \t\t}\n \t}\n-\tfree((char *)argv[1]);\n+\n+\tclear_argv(&argv);\n+\tsha1_array_clear(&ref_tips_before_fetch);\n+\tsha1_array_clear(&ref_tips_after_fetch);\n+\tinitialized_fetch_ref_tips = 0;\n }\n \n int fetch_populated_submodules(int num_options, const char **options,\n@@ -541,6 +605,8 @@ int fetch_populated_submodules(int num_options, const char **options,\n \tcp.git_cmd = 1;\n \tcp.no_stdin = 1;\n \n+\tcalculate_changed_submodule_paths();\n+\n \tfor (i = 0; i < active_nr; i++) {\n \t\tstruct strbuf submodule_path = STRBUF_INIT;\n \t\tstruct strbuf submodule_git_dir = STRBUF_INIT;\n-- \n1.7.6.10.g62f04\n"},{"id":"175358","messageId":"7vwrdd5x61.fsf@alter.siamese.dyndns.org","threadId":"28374","inReplyTo":"20110912195652.GA27850@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-09-12T20:21:42Z","receivedAt":"2011-09-12T20:21: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> Instead, this patch structures the code like this:\n\nYup, I agree that's the right way to do the other half of the issue.\n\nWill queue for 1.7.6.X series, but I've already pushed out 1.7.6.3\nso... ;-)\n"},{"id":"175359","messageId":"7vr53l5u7h.fsf@alter.siamese.dyndns.org","threadId":"28374","inReplyTo":"20110912195652.GA27850@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-09-12T21:25:38Z","receivedAt":"2011-09-12T21:25:38Z","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> +struct argv_array {\n> +\tconst char **argv;\n> +\tunsigned int argc;\n> +\tunsigned int alloc;\n> +};\n> +\n> ...\n> +static void calculate_changed_submodule_paths() {\n\nLocally fixed while queueing; no need to resend:\n\n        static void calculate_changed_submodule_paths(void)\n        {\n\n>  \tstruct rev_info rev;\n>  \tstruct commit *commit;\n> -\tconst char *argv[] = {NULL, NULL, \"--not\", \"--all\", NULL};\n> -\tint argc = ARRAY_SIZE(argv) - 1;\n> +\tstruct argv_array argv;\n>  \n>  \tinit_revisions(&rev, NULL);\n> -\targv[1] = xstrdup(sha1_to_hex(new_sha1));\n> -\tsetup_revisions(argc, argv, &rev, NULL);\n> +\tinit_argv(&argv);\n> +\tpush_argv(&argv, \"--\"); /* argv[0] program name */\n> +\tsha1_array_for_each_unique(&ref_tips_after_fetch,\n> +\t\t\t\t   add_sha1_to_argv, &argv);\n> +\tpush_argv(&argv, \"--not\");\n> +\tsha1_array_for_each_unique(&ref_tips_before_fetch,\n> +\t\t\t\t   add_sha1_to_argv, &argv);\n> +\tsetup_revisions(argv.argc, argv.argv, &rev, NULL);\n\nI initially thought \"eh, what if we have very many refs that may not fit\non the command line\", but this is running the internal rev-list, so there\nis no such issue.\n\nI however have to wonder if the use of object flags done by this revision\nwalking need to be cleared to prevent them from interfering with the\nancestry walking done in find_common(). Shouldn't this be done in a\nsubprocess \"rev-list\" that is fed these positive and negative refs from\nits standard input?\n\nThe patch does not make things worse in any sense, so I'll queue it but I\nhave this suspicion that fetching in a superproject that uses submodules\nmay be broken in the versions of Git with these internal revision walking.\n"},{"id":"175360","messageId":"20110912224934.GA28994@sigill.intra.peff.net","threadId":"28374","inReplyTo":"7vr53l5u7h.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-09-12T22:49:34Z","receivedAt":"2011-09-12T22:49:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Sep 12, 2011 at 02:25:38PM -0700, Junio C Hamano wrote:\n\n> > +static void calculate_changed_submodule_paths() {\n> \n> Locally fixed while queueing; no need to resend:\n> \n>         static void calculate_changed_submodule_paths(void)\n>         {\n\nOops, thanks. Old habits die hard, I guess. :)\n\n> I initially thought \"eh, what if we have very many refs that may not fit\n> on the command line\", but this is running the internal rev-list, so there\n> is no such issue.\n> \n> I however have to wonder if the use of object flags done by this revision\n> walking need to be cleared to prevent them from interfering with the\n> ancestry walking done in find_common(). Shouldn't this be done in a\n> subprocess \"rev-list\" that is fed these positive and negative refs from\n> its standard input?\n\nMaybe. I haven't noticed any such breakage. I don't know if it's because\nit's not there, or we don't have sufficient test cases. But if it were a\nproblem, it would be pretty severe, wouldn't it? The traversal is done\nwhether you actually have submodules or not, so lots of people should be\nseeing it.\n\nI tried to keep the patch as minimal as possible.  If I were writing\nfrom scratch, I think my strategy would be to actually start a\ntraversal, and mark the commit objects themselves as we find them. I.e.,\nthe two steps would be:\n\n  - start a traversal\n  - for each existing ref\n    - lookup_commit_reference, mark as SEEN\n  - for each new commit we fetched\n    - walk commits from $new_sha1 until we hit SEEN, marking each as\n      SEEN as we go.\n\nIOW, instead of keeping \"before\" and \"after\" lists, just mark the\ncommits. But that perhaps exacerbates the protential problem you\nmentioned (though we could maybe just use a different flag than SEEN).\n\nTo be honest, the whole submodule recursion thing seems a bit confusing\nto me. We walk every commit we just fetched looking for it to introduce\na change in a submodule. But we don't actually remember the sha1 it\nchanged to. And even if we did, we can't just ask a remote for a sha1,\nanyway. So with a set of changes like:\n\n  [assume submodule at commit A, superproject at commit B]\n\n  1. Make commit C in submodule repo.\n\n  2. Make commit D in superproject repo.\n\n  3. Make commit E in submodule repo.\n\n  4. Make commit F in superproject repo.\n\nwhat does it buy us to find out that the submodule changed from \"A\" to\n\"C\"? We can't actually fetch it. We can only fetch the tips of the\nsubmodule and hope that they include everything we wanted (i.e., both C\nand E; which might not be the case of E rewound and is not a descendant\nof C).\n\nSo since we must accept that we can't necessarily get every intermediate\nstep, I wonder if we are simply better off diffing the \"before\" and\n\"after\" state of a particular ref, rather than traversing. It's way\ncheaper, and is just as likely to give us the same information (i.e.,\nwhich submodule paths had changed commits). It can be fooled by rewinds,\ntoo, of course:\n\n  1. Make commit C in submodule repo.\n\n  2. Make commit D in superproject repo.\n\n  3. Rewind submodule repo back to A.\n\n  4. Make commit E in superproject repo.\n\nBut in that case, you probably can't get commit \"C\" from the submodule\nanyway, so knowing about it is unlikely to help.\n\nI dunno. Maybe there is more going on. This is the first time I've\nlooked at the problem.\n\nAlso also. I was a little turned off by the fact that every fetch is\ngoing to do the equivalent of \"git log --raw -m $new --not $old\",\nwhether you have submodules or not. If you fetch a lot of history, this\nis a non-trivial price to pay. Is there some way we can detect whether\nsubmodules are being used at all, and not even bother with this\ntraversal otherwise? Like checking whether .gitmodules exists? I know\nvirtually nothing about how submodules work.\n\n-Peff\n"},{"id":"175361","messageId":"7vboup4azh.fsf@alter.siamese.dyndns.org","threadId":"28374","inReplyTo":"20110912224934.GA28994@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-09-12T23:06:10Z","receivedAt":"2011-09-12T23:06:10Z","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> Also also. I was a little turned off by the fact that every fetch is\n> going to do the equivalent of \"git log --raw -m $new --not $old\",\n> whether you have submodules or not.\n\nNotice I called your patch solving \"the other half\"?\nSee http://thread.gmane.org/gmane.comp.version-control.git/181101\n"},{"id":"175372","messageId":"20110912232519.GA30020@sigill.intra.peff.net","threadId":"28374","inReplyTo":"7vboup4azh.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-09-12T23:25:19Z","receivedAt":"2011-09-12T23:25:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Sep 12, 2011 at 04:06:10PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > Also also. I was a little turned off by the fact that every fetch is\n> > going to do the equivalent of \"git log --raw -m $new --not $old\",\n> > whether you have submodules or not.\n> \n> Notice I called your patch solving \"the other half\"?\n> See http://thread.gmane.org/gmane.comp.version-control.git/181101\n\nOh, heh. I totally missed that thread. I don't usually pay attention to\nsubmodule patches, and came at this completely from the \"why is git\nfetch so slow\" angle. Glad to see Jens and I are meeting in the middle.\n:)\n\n-Peff\n"},{"id":"175375","messageId":"7vsjo11gl9.fsf@alter.siamese.dyndns.org","threadId":"28374","inReplyTo":"20110912224934.GA28994@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-09-12T23:33:22Z","receivedAt":"2011-09-12T23:33:22Z","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> To be honest, the whole submodule recursion thing seems a bit confusing\n> to me....\n> So since we must accept that we can't necessarily get every intermediate\n> step, I wonder if we are simply better off diffing the \"before\" and\n> \"after\" state of a particular ref, rather than traversing.\n\nYes, exactly my thought.\n\nIt would be far cheaper to look at a single final tree and enumerate all\nthe submodules, which would give you pessimistically the maximum set that\ncould possibly be relevant, than running millions of pairwise diff trees.\n\nBy the way, I think the submodule traversal won't hurt the correctness of\nthe primary traversal because that happens _after_ we fetch the object\nstream.\n\nThe submodule traversal _may_ be getting an incorrect result, though, for\nthe same reason.\n"},{"id":"175405","messageId":"CAP8UFD3ULs9YLCaaJYGo-_A=KqO4yFy3WHJmO5b_hyRSPzA-Vg@mail.gmail.com","threadId":"28374","inReplyTo":"20110912195652.GA27850@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2011-09-13T16:40:07Z","receivedAt":"2011-09-13T16:40:07Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi Peff,\n\nOn Mon, Sep 12, 2011 at 9:56 PM, Jeff King <peff@peff.net> wrote:\n> diff --git a/submodule.c b/submodule.c\n> index 7a76edf..00aeb71 100644\n> --- a/submodule.c\n> +++ b/submodule.c\n> @@ -8,12 +8,17 @@\n>  #include \"diffcore.h\"\n>  #include \"refs.h\"\n>  #include \"string-list.h\"\n> +#include \"sha1-array.h\"\n\nNice to see you reuse sha1-array!\n\n[...]\n\n> +struct argv_array {\n> +       const char **argv;\n> +       unsigned int argc;\n> +       unsigned int alloc;\n> +};\n\nBut there is already such a struct in bisect.c!\n\n> +static void init_argv(struct argv_array *array)\n> +{\n> +       array->argv = NULL;\n> +       array->argc = 0;\n> +       array->alloc = 0;\n> +}\n> +\n> +static void push_argv(struct argv_array *array, const char *value)\n> +{\n> +       ALLOC_GROW(array->argv, array->argc + 2, array->alloc);\n> +       array->argv[array->argc++] = xstrdup(value);\n> +       array->argv[array->argc] = NULL;\n> +}\n> +\n> +static void clear_argv(struct argv_array *array)\n> +{\n> +       int i;\n> +       for (i = 0; i < array->argc; i++)\n> +               free((char **)array->argv[i]);\n> +       free(array->argv);\n> +       init_argv(array);\n> +}\n> +\n> +static void add_sha1_to_argv(const unsigned char sha1[20], void *data)\n> +{\n> +       push_argv(data, sha1_to_hex(sha1));\n> +}\n\nSo it would be nice if you could refactor this and the argv_array\nfunctions in bisect.c in the same way you refactored sha1-array.\n\nThanks,\nChristian.\n"},{"id":"175409","messageId":"20110913171506.GA32251@sigill.intra.peff.net","threadId":"28374","inReplyTo":"CAP8UFD3ULs9YLCaaJYGo-_A=KqO4yFy3WHJmO5b_hyRSPzA-Vg@mail.gmail.com","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-09-13T17:15:06Z","receivedAt":"2011-09-13T17:15:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 13, 2011 at 06:40:07PM +0200, Christian Couder wrote:\n\n> > +struct argv_array {\n> > +       const char **argv;\n> > +       unsigned int argc;\n> > +       unsigned int alloc;\n> > +};\n> \n> But there is already such a struct in bisect.c!\n\nHeh. I completely missed that. As I was writing it, I realized it would\nbe a good thing to factor out, but most of the argv builders I checked\nweren't dynamic at all (they knew up front how big argv would need to be\nbecause they were copying).\n\nAs it turns out, our implementations are remarkably similar considering\nI hadn't read yours. It must mean they're both obviously correct. :)\n\n> So it would be nice if you could refactor this and the argv_array\n> functions in bisect.c in the same way you refactored sha1-array.\n\nWill do. Junio, do you want me to re-roll the quadratic fix, or just\nbuild the refactoring on top?\n\n-Peff\n"},{"id":"175414","messageId":"7vpqj4wdkt.fsf@alter.siamese.dyndns.org","threadId":"28374","inReplyTo":"20110913171506.GA32251@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-09-13T17:34:58Z","receivedAt":"2011-09-13T17:34:58Z","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> Will do. Junio, do you want me to re-roll the quadratic fix, or just\n> build the refactoring on top?\n\nThe latter would be fine and it probably is not even urgent.\n\nThanks.\n"},{"id":"175417","messageId":"4E6FAB46.30508@web.de","threadId":"28374","inReplyTo":"20110912224934.GA28994@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jens Lehmann","fromEmail":"jens.lehmann@web.de","sentAt":"2011-09-13T19:13:10Z","receivedAt":"2011-09-13T19:13:10Z","isPatch":true,"sender":{"key":"jens.lehmann@web.de","avatar":"https://avatars.githubusercontent.com/u/135220?v=4"},"body":"Am 13.09.2011 00:49, schrieb Jeff King:\n> So with a set of changes like:\n> \n>   [assume submodule at commit A, superproject at commit B]\n> \n>   1. Make commit C in submodule repo.\n> \n>   2. Make commit D in superproject repo.\n> \n>   3. Make commit E in submodule repo.\n> \n>   4. Make commit F in superproject repo.\n> \n> what does it buy us to find out that the submodule changed from \"A\" to\n> \"C\"? We can't actually fetch it. We can only fetch the tips of the\n> submodule and hope that they include everything we wanted (i.e., both C\n> and E; which might not be the case of E rewound and is not a descendant\n> of C).\n\nYes. But working with submodules in my experience only then works well\nwhen you never drop a submodule commit recorded in any superproject. At\nmy dayjob we have the convention: You may only record commits that are\non the submodule's master - or another never to be rewound integration\nbranch - in the superproject. That gives us all needed commits in a\nsimple fetch.\n\n> So since we must accept that we can't necessarily get every intermediate\n> step, I wonder if we are simply better off diffing the \"before\" and\n> \"after\" state of a particular ref, rather than traversing. It's way\n> cheaper, and is just as likely to give us the same information (i.e.,\n> which submodule paths had changed commits).\n\nThe real world use case I have for that is that when a bug introduced by\na new submodule commit is detected later on, the superproject's fix\nrecords an older submodule commit to remove the problematic change from\nthe superproject. But the submodule's branch isn't rewound (as that is\nmost probably master) but a fix is applied on top of it. Then that one\ngets tested and - if it was found ok - recorded in the superproject.\n\nChanges like this could be overlooked if you only compare \"before\" and\n\"after\" instead of traversing, leading to not fetching a submodule which\ndoes have new commits that are used in the newly fetched superproject's\ncommits. I'd like to have on-demand fetch keep the correct solution of\ntraversing unless we have good reasons against it, especially as teaching\ncheckout & friends to recursively update submodules too depends on all\nneeded commits being present.\n"},{"id":"175419","messageId":"4E6FB05C.6010202@web.de","threadId":"28374","inReplyTo":"7vwrdd5x61.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jens Lehmann","fromEmail":"jens.lehmann@web.de","sentAt":"2011-09-13T19:34:52Z","receivedAt":"2011-09-13T19:34:52Z","isPatch":true,"sender":{"key":"jens.lehmann@web.de","avatar":"https://avatars.githubusercontent.com/u/135220?v=4"},"body":"Am 12.09.2011 22:21, schrieb Junio C Hamano:\n> Jeff King <peff@peff.net> writes:\n> \n>> Instead, this patch structures the code like this:\n> \n> Yup, I agree that's the right way to do the other half of the issue.\n\nAck from me too! I tested it on the repo with 3k refs and the time went\ndown from 142s to 1s (when applied to 3793ac56b4, as later versions of\nmaster contain my other half which would skip Peff's code).\n\nOn current master including my other half this takes 0.90s, while running\nwith Peff's code on top of 3793ac56b4 it takes .96s. That is 6 hundreds\nof a second (7%) extra for not having to worry if one must run \"git fetch\n--recurse-submodules\" or not.\n"},{"id":"175430","messageId":"20110913221745.GB24549@sigill.intra.peff.net","threadId":"28374","inReplyTo":"4E6FAB46.30508@web.de","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-09-13T22:17:45Z","receivedAt":"2011-09-13T22:17:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 13, 2011 at 09:13:10PM +0200, Jens Lehmann wrote:\n\n> The real world use case I have for that is that when a bug introduced by\n> a new submodule commit is detected later on, the superproject's fix\n> records an older submodule commit to remove the problematic change from\n> the superproject. But the submodule's branch isn't rewound (as that is\n> most probably master) but a fix is applied on top of it. Then that one\n> gets tested and - if it was found ok - recorded in the superproject.\n\nOK, that makes sense. It is a \"rewind\" from the perspective of the\nsuperproject, but there is never a fork; because the submodule didn't\nrewind, when we do get a new submodule state in the superproject, it\nwill be a fast forward from the old state.\n\nThat is a reasonable use case.\n\nIt's still probably a minority case, and we have to pay for the full\ntraversal each time, which is annoying. But now that it's turned off by\ndefault if you don't have any submodules, I'm less concerned about the\nperformance impact. And superproject repositories are probably not going\nto have the same number of commits as submodule repositories, so it may\nbe less of an issue.\n\nOne thing that could make it slightly less expensive (but I wouldn't\nworry about implementing until it becomes an issue): you do a full diff\nand collect any changed GITLINK entries, and then compare the paths we\nget with the submodule config. Couldn't you instead do something like\nthis:\n\n  - let S = set of submodule paths that we care about, from the config\n  - start the \"git rev-list $new --not $old\" traversal, as we do now\n  - for each commit\n    - diff using a pathspec of S\n    - for each changed entry\n      - add it to the set of changed submodules\n      - remove it from S\n    - if S is empty, break\n\nThat has two advantages:\n\n  1. We limit the diff by pathspec, which means we can avoid looking at\n     irrelevant parts of the tree (we don't do this yet, but hopefully\n     we will in the future).\n\n  2. You can break out of the traversal early if you already know you\n     have changes in each submodule of interest.\n\n> Changes like this could be overlooked if you only compare \"before\" and\n> \"after\" instead of traversing, leading to not fetching a submodule which\n> does have new commits that are used in the newly fetched superproject's\n> commits. I'd like to have on-demand fetch keep the correct solution of\n> traversing unless we have good reasons against it, especially as teaching\n> checkout & friends to recursively update submodules too depends on all\n> needed commits being present.\n\nOut of curiosity, what happens if we don't have such a commit? I know\nyou said that your policy is never to rewind a submodule's commit that\nhas been published in a superproject, and I think that's the only sane\nthing to do. But it's not enforced by git itself, and I wonder how badly\nwe break if it does happen (i.e., I'm hoping the answer is \"you can't\ndiff or checkout superproject revisions that reference the missing bit\"\nand not \"git log crashes when it gets to that point in history\").\n\n-Peff\n"},{"id":"175471","messageId":"4E70AA19.6060701@xiplink.com","threadId":"28374","inReplyTo":"20110913221745.GB24549@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Marc Branchaud","fromEmail":"marcnarc@xiplink.com","sentAt":"2011-09-14T13:20:25Z","receivedAt":"2011-09-14T13:20:25Z","isPatch":true,"sender":{"key":"marcnarc@xiplink.com","avatar":"https://avatars.githubusercontent.com/u/14980203?v=4"},"body":"On 11-09-13 06:17 PM, Jeff King wrote:\n> \n> And superproject repositories are probably not going\n> to have the same number of commits as submodule repositories, so it may\n> be less of an issue.\n\nJust a side note:  I don't think this is a safe assumption.  It's certainly\nnot the case in our repo, where the submodules are infrequently updated.\n\n\t\tM.\n"},{"id":"175485","messageId":"4E70F1BD.70804@web.de","threadId":"28374","inReplyTo":"4E6FB05C.6010202@web.de","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jens Lehmann","fromEmail":"jens.lehmann@web.de","sentAt":"2011-09-14T18:26:05Z","receivedAt":"2011-09-14T18:26:05Z","isPatch":true,"sender":{"key":"jens.lehmann@web.de","avatar":"https://avatars.githubusercontent.com/u/135220?v=4"},"body":"Am 13.09.2011 21:34, schrieb Jens Lehmann:\n> Am 12.09.2011 22:21, schrieb Junio C Hamano:\n>> Jeff King <peff@peff.net> writes:\n>>\n>>> Instead, this patch structures the code like this:\n>>\n>> Yup, I agree that's the right way to do the other half of the issue.\n> \n> Ack from me too! I tested it on the repo with 3k refs and the time went\n> down from 142s to 1s (when applied to 3793ac56b4, as later versions of\n> master contain my other half which would skip Peff's code).\n> \n> On current master including my other half this takes 0.90s, while running\n> with Peff's code on top of 3793ac56b4 it takes .96s. That is 6 hundreds\n> of a second (7%) extra for not having to worry if one must run \"git fetch\n> --recurse-submodules\" or not.\n\nJust for the record: Martin Fick was so kind to run Peff's fix (without my\nhalf) on his 100k refs repo that showed this regression. Here are the results\nof some test runs:\n\n 1.7.7.rc0.189.gab72a\n\n    10m8.133s  9m7.971s  8m16.600s 13m57.821s\n     8m34.974s 8m41.527s\n\n\n 1.7.7.rc0.189.gab72a  --no-recurse-submodules\n\n    10m43.833s  7m41.283s 8m17.889s  8m4.549s\n    8m12.668s  7m59.180s\n\nThe fastest runs are 8% apart, which is pretty much the same slowdown as in\nthe 3k ref repo. Looks like we do have O(n) now :-)\n"},{"id":"175486","messageId":"4E70F224.2080401@web.de","threadId":"28374","inReplyTo":"20110913221745.GB24549@sigill.intra.peff.net","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jens Lehmann","fromEmail":"jens.lehmann@web.de","sentAt":"2011-09-14T18:27:48Z","receivedAt":"2011-09-14T18:27:48Z","isPatch":true,"sender":{"key":"jens.lehmann@web.de","avatar":"https://avatars.githubusercontent.com/u/135220?v=4"},"body":"Am 14.09.2011 00:17, schrieb Jeff King:\n> One thing that could make it slightly less expensive (but I wouldn't\n> worry about implementing until it becomes an issue): you do a full diff\n> and collect any changed GITLINK entries, and then compare the paths we\n> get with the submodule config. Couldn't you instead do something like\n> this:\n> \n>   - let S = set of submodule paths that we care about, from the config\n>   - start the \"git rev-list $new --not $old\" traversal, as we do now\n>   - for each commit\n>     - diff using a pathspec of S\n>     - for each changed entry\n>       - add it to the set of changed submodules\n>       - remove it from S\n>     - if S is empty, break\n> \n> That has two advantages:\n> \n>   1. We limit the diff by pathspec, which means we can avoid looking at\n>      irrelevant parts of the tree (we don't do this yet, but hopefully\n>      we will in the future).\n> \n>   2. You can break out of the traversal early if you already know you\n>      have changes in each submodule of interest.\n\nI think this would work for the functionality which is implemented right\nnow. But with Frederik's gitfile work I hope to enable git to support\nsubmodules being moved around in the work tree rather soonish. Then we\nwould be blind for any changes in the new location. Until it hurts us\nI'd prefer to stay with the correct version, even if it is a bit slower.\n\n> Out of curiosity, what happens if we don't have such a commit? I know\n> you said that your policy is never to rewind a submodule's commit that\n> has been published in a superproject, and I think that's the only sane\n> thing to do. But it's not enforced by git itself, and I wonder how badly\n> we break if it does happen (i.e., I'm hoping the answer is \"you can't\n> diff or checkout superproject revisions that reference the missing bit\"\n> and not \"git log crashes when it gets to that point in history\").\n\nNo worries, nothing bad happens in that case.\n"},{"id":"175488","messageId":"20110914182933.GA15884@sigill.intra.peff.net","threadId":"28374","inReplyTo":"4E70F224.2080401@web.de","subject":"Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-09-14T18:29:33Z","receivedAt":"2011-09-14T18:29:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 14, 2011 at 08:27:48PM +0200, Jens Lehmann wrote:\n\n> Am 14.09.2011 00:17, schrieb Jeff King:\n> > One thing that could make it slightly less expensive (but I wouldn't\n> > worry about implementing until it becomes an issue): you do a full diff\n> [...]\n\n> I think this would work for the functionality which is implemented right\n> now. But with Frederik's gitfile work I hope to enable git to support\n> submodules being moved around in the work tree rather soonish. Then we\n> would be blind for any changes in the new location. Until it hurts us\n> I'd prefer to stay with the correct version, even if it is a bit slower.\n\nAgreed. Let's worry about it if and when it becomes a performance issue.\n\nThanks for putting up my with my total cluelessness regarding what's\nhappening in submodules. ;)\n\n-Peff\n"}]}