{"thread":{"id":"34331","subject":"[PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list","startedAt":"2013-07-02T23:53:48Z","lastAt":"2013-07-08T16:12:37Z","messageCount":12,"participants":["Brandon Casey","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"222423","messageId":"1372809228-2963-1-git-send-email-bcasey@nvidia.com","threadId":"34331","inReplyTo":null,"subject":"[PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list","fromName":"Brandon Casey","fromEmail":"bcasey@nvidia.com","sentAt":"2013-07-02T23:53:48Z","receivedAt":"2013-07-02T23:53:48Z","isPatch":true,"sender":{"key":"bcasey@nvidia.com","avatar":null},"body":"From: Brandon Casey <drafnel@gmail.com>\n\nWhen pushing, each ref in the local repository must be paired with a\nref advertised by the remote server.  Currently, this is performed by\nfirst applying the refspec to the local ref to transform the local ref\ninto the name of the remote ref, and then performing a linear search\nthrough the list of remote refs to see if the remote ref was advertised\nby the remote system.\n\nThis has O(n) complexity and makes match_push_refs() be an O(n^2)\noperation.  If there are many refs 100,000+, then this ref matching\ncan take a significant amount of time.  Let's populate a string_list\nwith the remote ref names to allow searching in O(log n) time and\nreduce the complexity of match_push_refs() to O(n log n).\n\nDry-run push of a repository with 121913 refs:\n\n        before     after\nreal    1m40.582s  0m0.804s\nuser    1m39.914s  0m0.515s\nsys     0m0.125s   0m0.106s\n\nSigned-off-by: Brandon Casey <drafnel@gmail.com>\n---\n remote.c | 26 ++++++++++++++++++++++++--\n 1 file changed, 24 insertions(+), 2 deletions(-)\n\ndiff --git a/remote.c b/remote.c\nindex 6f57830..b416b8e 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -1302,6 +1302,15 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \tfree(sent_tips.tip);\n }\n \n+static void prepare_searchable_ref_list(struct ref *ref, struct string_list *ref_list)\n+{\n+\tfor ( ; ref; ref = ref->next)\n+\t\tstring_list_append_nodup(ref_list, ref->name)->util = ref;\n+\n+\tsort_string_list(ref_list);\n+}\n+\n+\n /*\n  * Given the set of refs the local repository has, the set of refs the\n  * remote repository has, and the refspec used for push, determine\n@@ -1320,6 +1329,7 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \tint errs;\n \tstatic const char *default_refspec[] = { \":\", NULL };\n \tstruct ref *ref, **dst_tail = tail_ref(dst);\n+\tstruct string_list ref_list = STRING_LIST_INIT_NODUP;\n \n \tif (!nr_refspec) {\n \t\tnr_refspec = 1;\n@@ -1328,8 +1338,11 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \trs = parse_push_refspec(nr_refspec, (const char **) refspec);\n \terrs = match_explicit_refs(src, *dst, &dst_tail, rs, nr_refspec);\n \n+\tprepare_searchable_ref_list(*dst, &ref_list);\n+\n \t/* pick the remainder */\n \tfor (ref = src; ref; ref = ref->next) {\n+\t\tstruct string_list_item *dst_item;\n \t\tstruct ref *dst_peer;\n \t\tconst struct refspec *pat = NULL;\n \t\tchar *dst_name;\n@@ -1338,7 +1351,8 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\tif (!dst_name)\n \t\t\tcontinue;\n \n-\t\tdst_peer = find_ref_by_name(*dst, dst_name);\n+\t\tdst_item = string_list_lookup(&ref_list, dst_name);\n+\t\tdst_peer = dst_item ? dst_item->util : NULL;\n \t\tif (dst_peer) {\n \t\t\tif (dst_peer->peer_ref)\n \t\t\t\t/* We're already sending something to this ref. */\n@@ -1355,6 +1369,8 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\t\t/* Create a new one and link it */\n \t\t\tdst_peer = make_linked_ref(dst_name, &dst_tail);\n \t\t\thashcpy(dst_peer->new_sha1, ref->new_sha1);\n+\t\t\tstring_list_insert(&ref_list, dst_peer->name)->util =\n+\t\t\t\tdst_peer;\n \t\t}\n \t\tdst_peer->peer_ref = copy_ref(ref);\n \t\tdst_peer->force = pat->force;\n@@ -1362,6 +1378,8 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\tfree(dst_name);\n \t}\n \n+\tstring_list_clear(&ref_list, 0);\n+\n \tif (flags & MATCH_REFS_FOLLOW_TAGS)\n \t\tadd_missing_tags(src, dst, &dst_tail);\n \n@@ -1376,11 +1394,15 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \n \t\t\tsrc_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);\n \t\t\tif (src_name) {\n-\t\t\t\tif (!find_ref_by_name(src, src_name))\n+\t\t\t\tif (!ref_list.nr)\n+\t\t\t\t\tprepare_searchable_ref_list(src,\n+\t\t\t\t\t\t&ref_list);\n+\t\t\t\tif (!string_list_has_string(&ref_list, src_name))\n \t\t\t\t\tref->peer_ref = alloc_delete_ref();\n \t\t\t\tfree(src_name);\n \t\t\t}\n \t\t}\n+\t\tstring_list_clear(&ref_list, 0);\n \t}\n \tif (errs)\n \t\treturn -1;\n-- \n1.8.3.1.440.gc2bf105\n"},{"id":"222426","messageId":"20130703062332.GA16090@sigill.intra.peff.net","threadId":"34331","inReplyTo":"1372809228-2963-1-git-send-email-bcasey@nvidia.com","subject":"Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-03T06:23:32Z","receivedAt":"2013-07-03T06:23:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 02, 2013 at 04:53:48PM -0700, Brandon Casey wrote:\n\n> From: Brandon Casey <drafnel@gmail.com>\n> \n> When pushing, each ref in the local repository must be paired with a\n> ref advertised by the remote server.  Currently, this is performed by\n> first applying the refspec to the local ref to transform the local ref\n> into the name of the remote ref, and then performing a linear search\n> through the list of remote refs to see if the remote ref was advertised\n> by the remote system.\n> \n> This has O(n) complexity and makes match_push_refs() be an O(n^2)\n> operation.\n\nJust to be sure I understand correctly, is this actually O(m*n) where\n\"m\" is the number of local refs and \"n\" is the number of remote refs?\n\nFor a repository that repeatedly pushes everything it has to the remote,\nwe end up with m=n, but it would not necessarily be the case if you are\npushing a subset of your refs. But even pushing a small number of refs\ninto a repository with a very large number of refs would be\nunnecessarily slow, as we would do several O(n) lookups which could be\nO(log n). So it may speed things up even in the case of a normal-sized\nrepo pushing to a large one.\n\n> Dry-run push of a repository with 121913 refs:\n> \n>         before     after\n> real    1m40.582s  0m0.804s\n> user    1m39.914s  0m0.515s\n> sys     0m0.125s   0m0.106s\n\nVery nice. :)\n\n> Signed-off-by: Brandon Casey <drafnel@gmail.com>\n> ---\n>  remote.c | 26 ++++++++++++++++++++++++--\n>  1 file changed, 24 insertions(+), 2 deletions(-)\n\nPatch itself looks good to me, although...\n\n> @@ -1362,6 +1378,8 @@ int match_push_refs(struct ref *src, struct ref **dst,\n>  \t\tfree(dst_name);\n>  \t}\n>  \n> +\tstring_list_clear(&ref_list, 0);\n> +\n>  \tif (flags & MATCH_REFS_FOLLOW_TAGS)\n>  \t\tadd_missing_tags(src, dst, &dst_tail);\n>  \n> @@ -1376,11 +1394,15 @@ int match_push_refs(struct ref *src, struct ref **dst,\n>  \n>  \t\t\tsrc_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);\n>  \t\t\tif (src_name) {\n> -\t\t\t\tif (!find_ref_by_name(src, src_name))\n> +\t\t\t\tif (!ref_list.nr)\n> +\t\t\t\t\tprepare_searchable_ref_list(src,\n> +\t\t\t\t\t\t&ref_list);\n> +\t\t\t\tif (!string_list_has_string(&ref_list, src_name))\n\nThis hunk threw me for a bit, as it looked like we were lazily\ninitializing ref_list in case we had not done so earlier. But we would\nhave cleared it mid-way through the function (in the hunk above), and it\nis only that we are reusing the same ref_list for two different\npurposes.\n\nI do not feel strongly about it, but it might be a little more obvious\nto just declare a new variable in the block, like:\n\ndiff --git a/remote.c b/remote.c\nindex 75255af..53bef82 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -1399,6 +1399,7 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\tadd_missing_tags(src, dst, &dst_tail);\n \n \tif (send_prune) {\n+\t\tstruct string_list src_ref_index = STRING_LIST_INIT_NODUP;\n \t\t/* check for missing refs on the remote */\n \t\tfor (ref = *dst; ref; ref = ref->next) {\n \t\t\tchar *src_name;\n@@ -1409,15 +1410,15 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \n \t\t\tsrc_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);\n \t\t\tif (src_name) {\n-\t\t\t\tif (!ref_list.nr)\n+\t\t\t\tif (!src_ref_index.nr)\n \t\t\t\t\tprepare_searchable_ref_list(src,\n-\t\t\t\t\t\t&ref_list);\n-\t\t\t\tif (!string_list_has_string(&ref_list, src_name))\n+\t\t\t\t\t\t&src_ref_index);\n+\t\t\t\tif (!string_list_has_string(&src_ref_index, src_name))\n \t\t\t\t\tref->peer_ref = alloc_delete_ref();\n \t\t\t\tfree(src_name);\n \t\t\t}\n \t\t}\n-\t\tstring_list_clear(&ref_list, 0);\n+\t\tstring_list_clear(&src_ref_index, 0);\n \t}\n \tif (errs)\n \t\treturn -1;\n\nAnd similarly maybe call the outer ref_list dst_ref_index or something.\nI also note that we don't do the lazy-prepare for the other loop. I\nguess that is because we assume that \"src\" is always non-NULL?\n\n-Peff\n"},{"id":"222475","messageId":"CA+sFfMeDC=hc7QZhfSuQYsdBPzig5WANeTBhMxFZk=Pusq0QpA@mail.gmail.com","threadId":"34331","inReplyTo":"20130703062332.GA16090@sigill.intra.peff.net","subject":"Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list","fromName":"Brandon Casey","fromEmail":"drafnel@gmail.com","sentAt":"2013-07-03T18:12:10Z","receivedAt":"2013-07-03T18:12:10Z","isPatch":true,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"On Tue, Jul 2, 2013 at 11:23 PM, Jeff King <peff@peff.net> wrote:\n> On Tue, Jul 02, 2013 at 04:53:48PM -0700, Brandon Casey wrote:\n>\n>> From: Brandon Casey <drafnel@gmail.com>\n>>\n>> When pushing, each ref in the local repository must be paired with a\n>> ref advertised by the remote server.  Currently, this is performed by\n>> first applying the refspec to the local ref to transform the local ref\n>> into the name of the remote ref, and then performing a linear search\n>> through the list of remote refs to see if the remote ref was advertised\n>> by the remote system.\n>>\n>> This has O(n) complexity and makes match_push_refs() be an O(n^2)\n>> operation.\n>\n> Just to be sure I understand correctly, is this actually O(m*n) where\n> \"m\" is the number of local refs and \"n\" is the number of remote refs?\n\nYes, O(m*n) is more correct.  I think you understand completely.\n\n> For a repository that repeatedly pushes everything it has to the remote,\n> we end up with m=n, but it would not necessarily be the case if you are\n> pushing a subset of your refs. But even pushing a small number of refs\n> into a repository with a very large number of refs would be\n> unnecessarily slow, as we would do several O(n) lookups which could be\n> O(log n). So it may speed things up even in the case of a normal-sized\n> repo pushing to a large one.\n\nRight.  For repos with few refs on either side, I don't think there\nwill be any measurable difference.  When pushing a single ref to a\nrepo with a very large number of refs, we will see a very small net\nloss for the time required to prepare the string list (which grows\nlinearly with the number of remote refs).  After 2 or 3 refs, we\nshould see a net gain.\n\nSo we're really just improving our worst case performance here.\n\n>> Dry-run push of a repository with 121913 refs:\n>>\n>>         before     after\n>> real    1m40.582s  0m0.804s\n>> user    1m39.914s  0m0.515s\n>> sys     0m0.125s   0m0.106s\n>\n> Very nice. :)\n>\n>> Signed-off-by: Brandon Casey <drafnel@gmail.com>\n>> ---\n>>  remote.c | 26 ++++++++++++++++++++++++--\n>>  1 file changed, 24 insertions(+), 2 deletions(-)\n>\n> Patch itself looks good to me, although...\n>\n>> @@ -1362,6 +1378,8 @@ int match_push_refs(struct ref *src, struct ref **dst,\n>>               free(dst_name);\n>>       }\n>>\n>> +     string_list_clear(&ref_list, 0);\n>> +\n>>       if (flags & MATCH_REFS_FOLLOW_TAGS)\n>>               add_missing_tags(src, dst, &dst_tail);\n>>\n>> @@ -1376,11 +1394,15 @@ int match_push_refs(struct ref *src, struct ref **dst,\n>>\n>>                       src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);\n>>                       if (src_name) {\n>> -                             if (!find_ref_by_name(src, src_name))\n>> +                             if (!ref_list.nr)\n>> +                                     prepare_searchable_ref_list(src,\n>> +                                             &ref_list);\n>> +                             if (!string_list_has_string(&ref_list, src_name))\n>\n> This hunk threw me for a bit, as it looked like we were lazily\n> initializing ref_list in case we had not done so earlier. But we would\n> have cleared it mid-way through the function (in the hunk above), and it\n> is only that we are reusing the same ref_list for two different\n> purposes.\n>\n> I do not feel strongly about it, but it might be a little more obvious\n> to just declare a new variable in the block, like:\n>\n> diff --git a/remote.c b/remote.c\n> index 75255af..53bef82 100644\n> --- a/remote.c\n> +++ b/remote.c\n> @@ -1399,6 +1399,7 @@ int match_push_refs(struct ref *src, struct ref **dst,\n>                 add_missing_tags(src, dst, &dst_tail);\n>\n>         if (send_prune) {\n> +               struct string_list src_ref_index = STRING_LIST_INIT_NODUP;\n>                 /* check for missing refs on the remote */\n>                 for (ref = *dst; ref; ref = ref->next) {\n>                         char *src_name;\n> @@ -1409,15 +1410,15 @@ int match_push_refs(struct ref *src, struct ref **dst,\n>\n>                         src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);\n>                         if (src_name) {\n> -                               if (!ref_list.nr)\n> +                               if (!src_ref_index.nr)\n>                                         prepare_searchable_ref_list(src,\n> -                                               &ref_list);\n> -                               if (!string_list_has_string(&ref_list, src_name))\n> +                                               &src_ref_index);\n> +                               if (!string_list_has_string(&src_ref_index, src_name))\n>                                         ref->peer_ref = alloc_delete_ref();\n>                                 free(src_name);\n>                         }\n>                 }\n> -               string_list_clear(&ref_list, 0);\n> +               string_list_clear(&src_ref_index, 0);\n>         }\n>         if (errs)\n>                 return -1;\n>\n> And similarly maybe call the outer ref_list dst_ref_index or something.\n\nThat looks/sounds reasonable.\n\n> I also note that we don't do the lazy-prepare for the other loop. I\n> guess that is because we assume that \"src\" is always non-NULL?\n\nIt really wasn't a conscious decision to not do the lazy prepare in\nthe other loop.  I gave extra attention to the pruning block since I\nexpect that deleting refs is less common than updating refs, so we\nshould be able to avoid the cost of building the string list most of\nthe time.  But, I don't see a down side to doing the lazy prepare in\nthe other loop too, and in fact, it looks like we may be able to avoid\nbuilding the string list when only explicit refspecs are used.  So,\nyeah, we should lazy build in both loops.\n\n-Brandon\n"},{"id":"222481","messageId":"7vhagbfpwz.fsf@alter.siamese.dyndns.org","threadId":"34331","inReplyTo":"CA+sFfMeDC=hc7QZhfSuQYsdBPzig5WANeTBhMxFZk=Pusq0QpA@mail.gmail.com","subject":"Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-03T18:40:12Z","receivedAt":"2013-07-03T18:40:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Brandon Casey <drafnel@gmail.com> writes:\n\n> Right.  For repos with few refs on either side, I don't think there\n> will be any measurable difference.  When pushing a single ref to a\n> repo with a very large number of refs, we will see a very small net\n> loss for the time required to prepare the string list (which grows\n> linearly with the number of remote refs).  After 2 or 3 refs, we\n> should see a net gain.\n>\n> So we're really just improving our worst case performance here.\n\n... by penalizing the common case by how much?  If it is not too\nmuch, then this obviously would be a good change.\n\n> ...  But, I don't see a down side to doing the lazy prepare in\n> the other loop too, and in fact, it looks like we may be able to avoid\n> building the string list when only explicit refspecs are used.  So,\n> yeah, we should lazy build in both loops.\n\nOK, so will see a reroll sometime?\n"},{"id":"222483","messageId":"20130703190047.GA349@sigill.intra.peff.net","threadId":"34331","inReplyTo":"7vhagbfpwz.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-03T19:00:47Z","receivedAt":"2013-07-03T19:00:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 03, 2013 at 11:40:12AM -0700, Junio C Hamano wrote:\n\n> Brandon Casey <drafnel@gmail.com> writes:\n> \n> > Right.  For repos with few refs on either side, I don't think there\n> > will be any measurable difference.  When pushing a single ref to a\n> > repo with a very large number of refs, we will see a very small net\n> > loss for the time required to prepare the string list (which grows\n> > linearly with the number of remote refs).  After 2 or 3 refs, we\n> > should see a net gain.\n> >\n> > So we're really just improving our worst case performance here.\n> \n> ... by penalizing the common case by how much?  If it is not too\n> much, then this obviously would be a good change.\n\nI don't think by much. If we have \"m\" local refs to push and \"n\" remote\nrefs, right now we do O(m*n) work (\"m\" linear searches of the remote\nnamespace). With Brandon's patch, we do O(n log n) to build the index,\nplus O(m log n) for lookups.\n\nSo our break-even point is basically m = log n, and for m smaller than\nthat, we do more work building the index. Your absolute biggest\ndifference would be pushing a single ref to a repository with a very\nlarge number of refs.\n\nHere are the timings before and after Brandon's patch for pushing a\nno-op single ref from a normal repo to one with 370K refs (the same\npathological repo from the upload-pack tests). Times are\nbest-of-five.\n\n             before     after\n     real    0m1.087s   0m1.156s\n     user    0m1.344s   0m1.412s\n     sys     0m0.288s   0m0.284s\n\nSo it's measurable, but even on a pathological worst-case, we're talking\nabout 6% slowdown.\n\nYou could try to guess about when to build the index based on the size\nof \"m\" and \"n\", but I suspect you'd waste more time calculating whether\nto build the index than you would simply building it in most cases.\n\n-Peff\n"},{"id":"222485","messageId":"51D479BA.1070207@nvidia.com","threadId":"34331","inReplyTo":"7vhagbfpwz.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list","fromName":"Brandon Casey","fromEmail":"bcasey@nvidia.com","sentAt":"2013-07-03T19:21:30Z","receivedAt":"2013-07-03T19:21:30Z","isPatch":true,"sender":{"key":"bcasey@nvidia.com","avatar":null},"body":"On 7/3/2013 11:40 AM, Junio C Hamano wrote:\n> Brandon Casey <drafnel@gmail.com> writes:\n> \n>> Right.  For repos with few refs on either side, I don't think there\n>> will be any measurable difference.  When pushing a single ref to a\n>> repo with a very large number of refs, we will see a very small net\n>> loss for the time required to prepare the string list (which grows\n>> linearly with the number of remote refs).  After 2 or 3 refs, we\n>> should see a net gain.\n>>\n>> So we're really just improving our worst case performance here.\n> \n> ... by penalizing the common case by how much?  If it is not too\n> much, then this obviously would be a good change.\n\nFor something the size of the git repo, 5 branches, and pushing with\nmatching refspecs, I can't measure any difference.  The fastest time I\nrecord with or without this patch is the same:\n\n   $ time git push -n\n   real    0m0.178s\n   user    0m0.020s\n   sys     0m0.008s\n\nDitto, when only pushing a single branch.  Preparing the string list for\na repo with a \"normal\" number of refs has very little overhead.\n\nWhen the remote side has very many refs, then there is a small penalty\nwhen the local side is pushing very few refs.  But still, the penalty is\nsmall.\n\nMy measurements for pushing from a repo with a single local branch into\nmy 100000+ ref repo showed <10% hit and the numbers were in the tens of\nmilliseconds.\n\n        before    after\nreal    0m0.525s  0m0.566s\nuser    0m0.243s  0m0.279s\nsys     0m0.075s  0m0.099s\n\n>> ...  But, I don't see a down side to doing the lazy prepare in\n>> the other loop too, and in fact, it looks like we may be able to avoid\n>> building the string list when only explicit refspecs are used.  So,\n>> yeah, we should lazy build in both loops.\n> \n> OK, so will see a reroll sometime?\n\nYeah, I'll reroll.\n\n-Brandon\n"},{"id":"222491","messageId":"51D483F5.6020702@nvidia.com","threadId":"34331","inReplyTo":"20130703190047.GA349@sigill.intra.peff.net","subject":"Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list","fromName":"Brandon Casey","fromEmail":"bcasey@nvidia.com","sentAt":"2013-07-03T20:05:09Z","receivedAt":"2013-07-03T20:05:09Z","isPatch":true,"sender":{"key":"bcasey@nvidia.com","avatar":null},"body":"On 7/3/2013 12:00 PM, Jeff King wrote:\n> On Wed, Jul 03, 2013 at 11:40:12AM -0700, Junio C Hamano wrote:\n> \n>> Brandon Casey <drafnel@gmail.com> writes:\n>>\n>>> Right.  For repos with few refs on either side, I don't think there\n>>> will be any measurable difference.  When pushing a single ref to a\n>>> repo with a very large number of refs, we will see a very small net\n>>> loss for the time required to prepare the string list (which grows\n>>> linearly with the number of remote refs).  After 2 or 3 refs, we\n>>> should see a net gain.\n>>>\n>>> So we're really just improving our worst case performance here.\n>>\n>> ... by penalizing the common case by how much?  If it is not too\n>> much, then this obviously would be a good change.\n> \n> I don't think by much. If we have \"m\" local refs to push and \"n\" remote\n> refs, right now we do O(m*n) work (\"m\" linear searches of the remote\n> namespace). With Brandon's patch, we do O(n log n) to build the index,\n\nWhoops, yes, n log n, not linear as I misspoke.\n\n> plus O(m log n) for lookups.\n> \n> So our break-even point is basically m = log n, and for m smaller than\n> that, we do more work building the index. Your absolute biggest\n> difference would be pushing a single ref to a repository with a very\n> large number of refs.\n> \n> Here are the timings before and after Brandon's patch for pushing a\n> no-op single ref from a normal repo to one with 370K refs (the same\n> pathological repo from the upload-pack tests). Times are\n> best-of-five.\n> \n>              before     after\n>      real    0m1.087s   0m1.156s\n>      user    0m1.344s   0m1.412s\n>      sys     0m0.288s   0m0.284s\n> \n> So it's measurable, but even on a pathological worst-case, we're talking\n> about 6% slowdown.\n\nThat agrees with what I've observed.\n\n> You could try to guess about when to build the index based on the size\n> of \"m\" and \"n\", but I suspect you'd waste more time calculating whether\n> to build the index than you would simply building it in most cases.\n\nI agree, I don't think it's worth trying to guess when to build an index\nand when to just perform linear searches.  If building the payload for\neach element in the index was more expensive than just assigning to a\npointer, than it could be worth it, but we're not, so I don't think it\nis worth it.\n\n-Brandon\n"},{"id":"222496","messageId":"7v7gh7e6mh.fsf@alter.siamese.dyndns.org","threadId":"34331","inReplyTo":"51D479BA.1070207@nvidia.com","subject":"Re: [PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-03T20:22:14Z","receivedAt":"2013-07-03T20:22:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Brandon Casey <bcasey@nvidia.com> writes:\n\n>> ... by penalizing the common case by how much?  If it is not too\n>> much, then this obviously would be a good change.\n>\n> For something the size of the git repo, 5 branches, and pushing with\n> matching refspecs, I can't measure any difference.  The fastest time I\n> record with or without this patch is the same:\n>\n>    $ time git push -n\n>    real    0m0.178s\n>    user    0m0.020s\n>    sys     0m0.008s\n>\n> Ditto, when only pushing a single branch.  Preparing the string list for\n> a repo with a \"normal\" number of refs has very little overhead.\n\nMy repository git.git and Linus's kernel are not \"normal\".  It did\nnot matter so far to have O(n*m) when pushing to our histories.\n\nThe case that matters is for somebody to be pushing one (or a few)\nrefs against a repository with many many refs, like pushing a review\nrequest to Gerrit instance, which I think Martin has in mind.\n"},{"id":"222796","messageId":"1373266931-30391-1-git-send-email-drafnel@gmail.com","threadId":"34331","inReplyTo":"7v7gh7e6mh.fsf@alter.siamese.dyndns.org","subject":"[PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs","fromName":"Brandon Casey","fromEmail":"drafnel@gmail.com","sentAt":"2013-07-08T07:02:11Z","receivedAt":"2013-07-08T07:02:11Z","isPatch":true,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"When pushing using a matching refspec or a pattern refspec, each ref\nin the local repository must be paired with a ref advertised by the\nremote server.  This is accomplished by using the refspec to transform\nthe name of the local ref into the name it should have in the remote\nrepository, and then performing a linear search through the list of\nremote refs to see if the remote ref was advertised by the remote\nsystem.\n\nEach of these lookups has O(n) complexity and makes match_push_refs()\nbe an O(m*n) operation, where m is the number of local refs and n is\nthe number of remote refs.  If there are many refs 100,000+, then this\nref matching can take a significant amount of time.  Let's prepare an\nindex of the remote refs to allow searching in O(log n) time and\nreduce the complexity of match_push_refs() to O(m log n).\n\nWe prepare the index lazily so that it is only created when necessary.\nSo, there should be no impact when _not_ using a matching or pattern\nrefspec, i.e. when pushing using only explicit refspecs.\n\nDry-run push of a repository with 121,913 local and remote refs:\n\n        before     after\nreal    1m40.582s  0m0.804s\nuser    1m39.914s  0m0.515s\nsys     0m0.125s   0m0.106s\n\nThe creation of the index has overhead.  So, if there are very few\nlocal refs, then it could take longer to create the index than it\nwould have taken to just perform n linear lookups into the remote\nref space.  Using the index should provide some improvement when\nthe number of local refs is roughly greater than the log of the\nnumber of remote refs (i.e. m >= log n).  The pathological case is\nwhen there is a single local ref and very many remote refs.\n\nDry-run push of a repository with 121,913 remote refs and a single\nlocal ref:\n\n        before    after\nreal    0m0.525s  0m0.566s\nuser    0m0.243s  0m0.279s\nsys     0m0.075s  0m0.099s\n\nUsing an index takes 41 ms longer, or roughly 7.8% longer.\n\nJeff King measured a no-op push of a single ref into a remote repo\nwith 370,000 refs:\n\n        before    after\nreal    0m1.087s  0m1.156s\nuser    0m1.344s  0m1.412s\nsys     0m0.288s  0m0.284s\n\nUsing an index takes 69 ms longer, or roughly 6.3% longer.\n\nNone of the measurements above required transferring any objects to\nthe remote repository.  If the push required transferring objects and\nupdating the refs in the remote repository, the impact of preparing\nthe search index would be even smaller.\n\nNote, we refrain from using an index in the send_prune block since it\nis expected that the number of refs that are being pruned is more\ncommonly much smaller than the number of local refs (i.e. m << n,\nand particularly m < log(n), where m is the number of refs that\nshould be pruned and n is the number of local refs), so the overhead\nof creating the search index would likely exceed the benefit of using\nit.\n\nSigned-off-by: Brandon Casey <drafnel@gmail.com>\n---\n\nHere is the reroll with an updated commit message that hopefully\nprovides a little more detail to justify this change.  I removed\nthe use of the search index in the send_prune block since I think\nthat pruning many refs is an uncommon operation and the overhead\nof creating the index will more commonly exceed the benefit of\nusing it.\n\nThis version now lazily builds the search index in the first loop,\nso there should be no impact when pushing using explicit refspecs.\n\ne.g. pushing a change for review to Gerrit\n\n   $ git push origin HEAD:refs/for/master\n\nI suspect that this is the most common form of pushing and furthermore\nwill become the default once push.default defaults to 'current'.\n\nThe remaining push cases can be distilled into the following:\n\n  ref-count    impact\n  m >= log n   improved with this patch\n  m < log n    regressed with this patch roughly ~6-7%\n\nSo, I think what we have to consider is whether the improvement to\nsomething like 'git push --mirror' is worth the impact to an asymmetric\npush where the number of local refs is much smaller than the number of\nremote refs.  I'm not sure how common the latter really is though.\nGerrit does produce repositories with many refs on the remote end in\nthe refs/changes/ namespace, but do people commonly push to Gerrit\nusing matching or pattern refspecs?  Not sure, but I'd tend to think\nthat they don't.\n\n-Brandon\n\n remote.c | 20 +++++++++++++++++++-\n 1 file changed, 19 insertions(+), 1 deletion(-)\n\ndiff --git a/remote.c b/remote.c\nindex 6f57830..8bca65a 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -1302,6 +1302,14 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \tfree(sent_tips.tip);\n }\n \n+static void prepare_ref_index(struct string_list *ref_index, struct ref *ref)\n+{\n+\tfor ( ; ref; ref = ref->next)\n+\t\tstring_list_append_nodup(ref_index, ref->name)->util = ref;\n+\n+\tsort_string_list(ref_index);\n+}\n+\n /*\n  * Given the set of refs the local repository has, the set of refs the\n  * remote repository has, and the refspec used for push, determine\n@@ -1320,6 +1328,7 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \tint errs;\n \tstatic const char *default_refspec[] = { \":\", NULL };\n \tstruct ref *ref, **dst_tail = tail_ref(dst);\n+\tstruct string_list dst_ref_index = STRING_LIST_INIT_NODUP;\n \n \tif (!nr_refspec) {\n \t\tnr_refspec = 1;\n@@ -1330,6 +1339,7 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \n \t/* pick the remainder */\n \tfor (ref = src; ref; ref = ref->next) {\n+\t\tstruct string_list_item *dst_item;\n \t\tstruct ref *dst_peer;\n \t\tconst struct refspec *pat = NULL;\n \t\tchar *dst_name;\n@@ -1338,7 +1348,11 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\tif (!dst_name)\n \t\t\tcontinue;\n \n-\t\tdst_peer = find_ref_by_name(*dst, dst_name);\n+\t\tif (!dst_ref_index.nr)\n+\t\t\tprepare_ref_index(&dst_ref_index, *dst);\n+\n+\t\tdst_item = string_list_lookup(&dst_ref_index, dst_name);\n+\t\tdst_peer = dst_item ? dst_item->util : NULL;\n \t\tif (dst_peer) {\n \t\t\tif (dst_peer->peer_ref)\n \t\t\t\t/* We're already sending something to this ref. */\n@@ -1355,6 +1369,8 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\t\t/* Create a new one and link it */\n \t\t\tdst_peer = make_linked_ref(dst_name, &dst_tail);\n \t\t\thashcpy(dst_peer->new_sha1, ref->new_sha1);\n+\t\t\tstring_list_insert(&dst_ref_index,\n+\t\t\t\tdst_peer->name)->util = dst_peer;\n \t\t}\n \t\tdst_peer->peer_ref = copy_ref(ref);\n \t\tdst_peer->force = pat->force;\n@@ -1362,6 +1378,8 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\tfree(dst_name);\n \t}\n \n+\tstring_list_clear(&dst_ref_index, 0);\n+\n \tif (flags & MATCH_REFS_FOLLOW_TAGS)\n \t\tadd_missing_tags(src, dst, &dst_tail);\n \n-- \n1.8.1.1.252.gdb33759\n"},{"id":"222798","messageId":"20130708075007.GB25072@sigill.intra.peff.net","threadId":"34331","inReplyTo":"1373266931-30391-1-git-send-email-drafnel@gmail.com","subject":"Re: [PATCH v2] remote.c: avoid O(m*n) behavior in match_push_refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-08T07:50:09Z","receivedAt":"2013-07-08T07:50:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 08, 2013 at 12:02:11AM -0700, Brandon Casey wrote:\n\n> Here is the reroll with an updated commit message that hopefully\n> provides a little more detail to justify this change.  I removed\n> the use of the search index in the send_prune block since I think\n> that pruning many refs is an uncommon operation and the overhead\n> of creating the index will more commonly exceed the benefit of\n> using it.\n\nI don't know. I'd think that if you are using pruning, you might delete\na large chunk at one time (e.g., rearranging your ref hierarchy,\nfollowed by \"git push --mirror\"). But that is just my gut feeling. I\nhaven't actually run into this slow-down in the real world (we typically\nfetch from our giant repositories rather than push into them).\n\n> This version now lazily builds the search index in the first loop,\n> so there should be no impact when pushing using explicit refspecs.\n> \n> e.g. pushing a change for review to Gerrit\n> \n>    $ git push origin HEAD:refs/for/master\n> \n> I suspect that this is the most common form of pushing and furthermore\n> will become the default once push.default defaults to 'current'.\n\nNice.\n\n> The remaining push cases can be distilled into the following:\n> \n>   ref-count    impact\n>   m >= log n   improved with this patch\n>   m < log n    regressed with this patch roughly ~6-7%\n> \n> So, I think what we have to consider is whether the improvement to\n> something like 'git push --mirror' is worth the impact to an asymmetric\n> push where the number of local refs is much smaller than the number of\n> remote refs.  I'm not sure how common the latter really is though.\n> Gerrit does produce repositories with many refs on the remote end in\n> the refs/changes/ namespace, but do people commonly push to Gerrit\n> using matching or pattern refspecs?  Not sure, but I'd tend to think\n> that they don't.\n\nTo me it is not about what happens sometimes or not, but about having\nrunaway worst-case behavior that is unusable. The 6-7% increase (which\nis the absolute worst-case measurement we could come up with; in the\nreal world you would usually transfer actual objects, and connect over\nan actual network) is worth it, IMHO.\n\nSo I'd be in favor of applying this (possibly covering the send_prune\ncase, too). If somebody really wants to care about the 6-7%, they can\nbuild on top of your patch with heuristics to avoid indexing in the\nsmall cases.\n\n-Peff\n"},{"id":"222802","messageId":"1373273919-32005-1-git-send-email-drafnel@gmail.com","threadId":"34331","inReplyTo":"20130708075007.GB25072@sigill.intra.peff.net","subject":"[PATCH v2 w/prune index] remote.c: avoid O(m*n) behavior in match_push_refs","fromName":"Brandon Casey","fromEmail":"drafnel@gmail.com","sentAt":"2013-07-08T08:58:39Z","receivedAt":"2013-07-08T08:58:39Z","isPatch":true,"sender":{"key":"drafnel@gmail.com","avatar":"https://avatars.githubusercontent.com/u/921167?v=4"},"body":"When pushing using a matching refspec or a pattern refspec, each ref\nin the local repository must be paired with a ref advertised by the\nremote server.  This is accomplished by using the refspec to transform\nthe name of the local ref into the name it should have in the remote\nrepository, and then performing a linear search through the list of\nremote refs to see if the remote ref was advertised by the remote\nsystem.\n\nEach of these lookups has O(n) complexity and makes match_push_refs()\nbe an O(m*n) operation, where m is the number of local refs and n is\nthe number of remote refs.  If there are many refs 100,000+, then this\nref matching can take a significant amount of time.  Let's prepare an\nindex of the remote refs to allow searching in O(log n) time and\nreduce the complexity of match_push_refs() to O(m log n).\n\nWe prepare the index lazily so that it is only created when necessary.\nSo, there should be no impact when _not_ using a matching or pattern\nrefspec, i.e. when pushing using only explicit refspecs.\n\nDry-run push of a repository with 121,913 local and remote refs:\n\n        before     after\nreal    1m40.582s  0m0.804s\nuser    1m39.914s  0m0.515s\nsys     0m0.125s   0m0.106s\n\nThe creation of the index has overhead.  So, if there are very few\nlocal refs, then it could take longer to create the index than it\nwould have taken to just perform n linear lookups into the remote\nref space.  Using the index should provide some improvement when\nthe number of local refs is roughly greater than the log of the\nnumber of remote refs (i.e. m >= log n).  The pathological case is\nwhen there is a single local ref and very many remote refs.\n\nDry-run push of a repository with 121,913 remote refs and a single\nlocal ref:\n\n        before    after\nreal    0m0.525s  0m0.566s\nuser    0m0.243s  0m0.279s\nsys     0m0.075s  0m0.099s\n\nUsing an index takes 41 ms longer, or roughly 7.8% longer.\n\nJeff King measured a no-op push of a single ref into a remote repo\nwith 370,000 refs:\n\n        before    after\nreal    0m1.087s  0m1.156s\nuser    0m1.344s  0m1.412s\nsys     0m0.288s  0m0.284s\n\nUsing an index takes 69 ms longer, or roughly 6.3% longer.\n\nNone of the measurements above required transferring any objects to\nthe remote repository.  If the push required transferring objects and\nupdating the refs in the remote repository, the impact of preparing\nthe search index would be even smaller.\n\nA similar operation is performed in the reverse direction when pruning\nusing a matching or pattern refspec.  Let's avoid O(m*n) behavior in\nthe same way by lazily preparing an index on the local refs.\n\nSigned-off-by: Brandon Casey <drafnel@gmail.com>\n---\n\nOn Mon, Jul 8, 2013 at 12:50 AM, Jeff King <peff@peff.net> wrote:\n> On Mon, Jul 08, 2013 at 12:02:11AM -0700, Brandon Casey wrote:\n> \n> > Here is the reroll with an updated commit message that hopefully\n> > provides a little more detail to justify this change.  I removed\n> > the use of the search index in the send_prune block since I think\n> > that pruning many refs is an uncommon operation and the overhead\n> > of creating the index will more commonly exceed the benefit of\n> > using it.\n> \n> I don't know. I'd think that if you are using pruning, you might delete\n> a large chunk at one time (e.g., rearranging your ref hierarchy,\n> followed by \"git push --mirror\"). But that is just my gut feeling. I\n> haven't actually run into this slow-down in the real world (we typically\n> fetch from our giant repositories rather than push into them).\n\nFirstly, why are you still awake?!?! :)\n\nSecondly, fair enough.  I don't think the change to the pruning block\nwill have much impact in real repos either way.  In this block, the\nsearch is being performed on the local refs.  There would have to be\nmany refs on the local side for the generation of the index to be\nsignificant enough to notice.\n\nSo, I'm fine with using the index when pruning too to avoid worst-case\nbehavior when there are many local refs and many deletions.\n\n-Brandon\n\n remote.c | 27 +++++++++++++++++++++++++--\n 1 file changed, 25 insertions(+), 2 deletions(-)\n\ndiff --git a/remote.c b/remote.c\nindex 6f57830..efcba93 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -1302,6 +1302,14 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \tfree(sent_tips.tip);\n }\n \n+static void prepare_ref_index(struct string_list *ref_index, struct ref *ref)\n+{\n+\tfor ( ; ref; ref = ref->next)\n+\t\tstring_list_append_nodup(ref_index, ref->name)->util = ref;\n+\n+\tsort_string_list(ref_index);\n+}\n+\n /*\n  * Given the set of refs the local repository has, the set of refs the\n  * remote repository has, and the refspec used for push, determine\n@@ -1320,6 +1328,7 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \tint errs;\n \tstatic const char *default_refspec[] = { \":\", NULL };\n \tstruct ref *ref, **dst_tail = tail_ref(dst);\n+\tstruct string_list dst_ref_index = STRING_LIST_INIT_NODUP;\n \n \tif (!nr_refspec) {\n \t\tnr_refspec = 1;\n@@ -1330,6 +1339,7 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \n \t/* pick the remainder */\n \tfor (ref = src; ref; ref = ref->next) {\n+\t\tstruct string_list_item *dst_item;\n \t\tstruct ref *dst_peer;\n \t\tconst struct refspec *pat = NULL;\n \t\tchar *dst_name;\n@@ -1338,7 +1348,11 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\tif (!dst_name)\n \t\t\tcontinue;\n \n-\t\tdst_peer = find_ref_by_name(*dst, dst_name);\n+\t\tif (!dst_ref_index.nr)\n+\t\t\tprepare_ref_index(&dst_ref_index, *dst);\n+\n+\t\tdst_item = string_list_lookup(&dst_ref_index, dst_name);\n+\t\tdst_peer = dst_item ? dst_item->util : NULL;\n \t\tif (dst_peer) {\n \t\t\tif (dst_peer->peer_ref)\n \t\t\t\t/* We're already sending something to this ref. */\n@@ -1355,6 +1369,8 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\t\t/* Create a new one and link it */\n \t\t\tdst_peer = make_linked_ref(dst_name, &dst_tail);\n \t\t\thashcpy(dst_peer->new_sha1, ref->new_sha1);\n+\t\t\tstring_list_insert(&dst_ref_index,\n+\t\t\t\tdst_peer->name)->util = dst_peer;\n \t\t}\n \t\tdst_peer->peer_ref = copy_ref(ref);\n \t\tdst_peer->force = pat->force;\n@@ -1362,10 +1378,13 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \t\tfree(dst_name);\n \t}\n \n+\tstring_list_clear(&dst_ref_index, 0);\n+\n \tif (flags & MATCH_REFS_FOLLOW_TAGS)\n \t\tadd_missing_tags(src, dst, &dst_tail);\n \n \tif (send_prune) {\n+\t\tstruct string_list src_ref_index = STRING_LIST_INIT_NODUP;\n \t\t/* check for missing refs on the remote */\n \t\tfor (ref = *dst; ref; ref = ref->next) {\n \t\t\tchar *src_name;\n@@ -1376,11 +1395,15 @@ int match_push_refs(struct ref *src, struct ref **dst,\n \n \t\t\tsrc_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);\n \t\t\tif (src_name) {\n-\t\t\t\tif (!find_ref_by_name(src, src_name))\n+\t\t\t\tif (!src_ref_index.nr)\n+\t\t\t\t\tprepare_ref_index(&src_ref_index, src);\n+\t\t\t\tif (!string_list_has_string(&src_ref_index,\n+\t\t\t\t\t    src_name))\n \t\t\t\t\tref->peer_ref = alloc_delete_ref();\n \t\t\t\tfree(src_name);\n \t\t\t}\n \t\t}\n+\t\tstring_list_clear(&src_ref_index, 0);\n \t}\n \tif (errs)\n \t\treturn -1;\n-- \n1.8.1.1.252.gdb33759\n"},{"id":"222842","messageId":"7vmwpx1156.fsf@alter.siamese.dyndns.org","threadId":"34331","inReplyTo":"1373273919-32005-1-git-send-email-drafnel@gmail.com","subject":"Re: [PATCH v2 w/prune index] remote.c: avoid O(m*n) behavior in match_push_refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-08T16:12:37Z","receivedAt":"2013-07-08T16:12:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Brandon Casey <drafnel@gmail.com> writes:\n\n> ...\n> Using an index takes 41 ms longer, or roughly 7.8% longer.\n>\n> Jeff King measured a no-op push of a single ref into a remote repo\n> with 370,000 refs:\n>\n>         before    after\n> real    0m1.087s  0m1.156s\n> user    0m1.344s  0m1.412s\n> sys     0m0.288s  0m0.284s\n>\n> Using an index takes 69 ms longer, or roughly 6.3% longer.\n>\n> None of the measurements above required transferring any objects to\n> the remote repository.  If the push required transferring objects and\n> updating the refs in the remote repository, the impact of preparing\n> the search index would be even smaller.\n>\n> A similar operation is performed in the reverse direction when pruning\n> using a matching or pattern refspec.  Let's avoid O(m*n) behavior in\n> the same way by lazily preparing an index on the local refs.\n\nThanks.  Both the explanation and the code change makes sense to me.\n\nWill queue.\n"}]}