{"thread":{"id":"59053","subject":"[PATCH] merge: break out of all_strategy loop when strategy is found","startedAt":"2023-01-08T18:39:19Z","lastAt":"2023-01-13T18:28:18Z","messageCount":4,"participants":["Rose via GitGitGadget","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"469924","messageId":"pull.1429.git.git.1673203153257.gitgitgadget@gmail.com","threadId":"59053","inReplyTo":null,"subject":"[PATCH] merge: break out of all_strategy loop when strategy is found","fromName":"Rose via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-01-08T18:39:13Z","receivedAt":"2023-01-08T18:39:19Z","isPatch":true,"sender":{"key":"ckelsch@jgrcpa.com","avatar":null},"body":"From: Seija Kijin <doremylover123@gmail.com>\n\nstrncmp does not modify any of the memory,\nso looping through all elements is a waste of resources.\n\nSigned-off-by: Seija Kijin <doremylover123@gmail.com>\n---\n    merge: break out of all_strategy loop when strategy is found\n    \n    strncmp does not modify any of the memory, so looping through all\n    elements is a waste of resources.\n    \n    Signed-off-by: Seija Kijin doremylover123@gmail.com\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1429%2FAtariDreams%2Fexit-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1429/AtariDreams/exit-v1\nPull-Request: https://github.com/git/git/pull/1429\n\n builtin/merge.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/merge.c b/builtin/merge.c\nindex 0f093f2a4f2..5ab0feb47b6 100644\n--- a/builtin/merge.c\n+++ b/builtin/merge.c\n@@ -189,9 +189,12 @@ static struct strategy *get_strategy(const char *name)\n \t\t\tint j, found = 0;\n \t\t\tstruct cmdname *ent = main_cmds.names[i];\n \t\t\tfor (j = 0; j < ARRAY_SIZE(all_strategy); j++)\n-\t\t\t\tif (!strncmp(ent->name, all_strategy[j].name, ent->len)\n-\t\t\t\t\t\t&& !all_strategy[j].name[ent->len])\n+\t\t\t\tif (!strncmp(ent->name, all_strategy[j].name,\n+\t\t\t\t\t     ent->len) &&\n+\t\t\t\t    !all_strategy[j].name[ent->len]) {\n \t\t\t\t\tfound = 1;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\tif (!found)\n \t\t\t\tadd_cmdname(&not_strategies, ent->name, ent->len);\n \t\t}\n\nbase-commit: a38d39a4c50d1275833aba54c4dbdfce9e2e9ca1\n-- \ngitgitgadget\n"},{"id":"469944","messageId":"xmqqsfgkuw4z.fsf@gitster.g","threadId":"59053","inReplyTo":"pull.1429.git.git.1673203153257.gitgitgadget@gmail.com","subject":"Re: [PATCH] merge: break out of all_strategy loop when strategy is found","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-01-09T05:14:52Z","receivedAt":"2023-01-09T05:14:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Rose via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> From: Seija Kijin <doremylover123@gmail.com>\n>\n> strncmp does not modify any of the memory,\n> so looping through all elements is a waste of resources.\n\nModifying or not probably has little to do with why we may want to\ndo this change.\n\nHere, we are trying to see which commands that appear in the\nmain_cmds table do not appear in the all_strategy[] table.  The way\nwe do so is by iterating over the main_cmds table, and for each of\nthe command, if it is found in the all_strategy[] table.  If there\nis one, then found bit is set.  If there isn't, then found bit is\nleft clear.  After looping over all_strategy[] table, we act upon\nthe value of the found bit.\n\nSo, as soon as we find one match in all_strategy[] table and flip\nthe found bit on, in the loop we never clear the bit.  So it does\nmake sense to break out of that inner loop once we find a single\nmatch.\n\n    Once we find a match, there is no point to try finding the\n    second match in the inner loop.  Break out of the loop once we\n    find the first match.\n\nwould be a more appropriate explanation.\n\n>  builtin/merge.c | 7 +++++--\n>  1 file changed, 5 insertions(+), 2 deletions(-)\n>\n> diff --git a/builtin/merge.c b/builtin/merge.c\n> index 0f093f2a4f2..5ab0feb47b6 100644\n> --- a/builtin/merge.c\n> +++ b/builtin/merge.c\n> @@ -189,9 +189,12 @@ static struct strategy *get_strategy(const char *name)\n>  \t\t\tint j, found = 0;\n>  \t\t\tstruct cmdname *ent = main_cmds.names[i];\n>  \t\t\tfor (j = 0; j < ARRAY_SIZE(all_strategy); j++)\n> -\t\t\t\tif (!strncmp(ent->name, all_strategy[j].name, ent->len)\n> -\t\t\t\t\t\t&& !all_strategy[j].name[ent->len])\n> +\t\t\t\tif (!strncmp(ent->name, all_strategy[j].name,\n> +\t\t\t\t\t     ent->len) &&\n> +\t\t\t\t    !all_strategy[j].name[ent->len]) {\n>  \t\t\t\t\tfound = 1;\n> +\t\t\t\t\tbreak;\n> +\t\t\t\t}\n\nThe above is not wrong per-se, but we can do the same with less\ndamage to the code, e.g.\n\n builtin/merge.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git c/builtin/merge.c w/builtin/merge.c\nindex dd474371a2..2437aae6bc 100644\n--- c/builtin/merge.c\n+++ w/builtin/merge.c\n@@ -188,7 +188,7 @@ static struct strategy *get_strategy(const char *name)\n \t\tfor (i = 0; i < main_cmds.cnt; i++) {\n \t\t\tint j, found = 0;\n \t\t\tstruct cmdname *ent = main_cmds.names[i];\n-\t\t\tfor (j = 0; j < ARRAY_SIZE(all_strategy); j++)\n+\t\t\tfor (j = 0; !found && j < ARRAY_SIZE(all_strategy); j++)\n \t\t\t\tif (!strncmp(ent->name, all_strategy[j].name, ent->len)\n \t\t\t\t\t\t&& !all_strategy[j].name[ent->len])\n \t\t\t\t\tfound = 1;\n\n\nI've mentioned it before, but could you please drop the\n\n    Rose <83477269+AtariDreams@users.noreply.github.com>\n\naddress from the Cc: list?  It is rude to force those who want to\nrespond to you to remove the non-working address that is meant not\nto receive any responses.\n\nThanks.\n"},{"id":"469992","messageId":"pull.1429.v2.git.git.1673285669004.gitgitgadget@gmail.com","threadId":"59053","inReplyTo":"pull.1429.git.git.1673203153257.gitgitgadget@gmail.com","subject":"[PATCH v2] merge: break out of all_strategy loop when strategy is found","fromName":"Rose via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-01-09T17:34:28Z","receivedAt":"2023-01-09T17:35:38Z","isPatch":true,"sender":{"key":"ckelsch@jgrcpa.com","avatar":null},"body":"From: Seija Kijin <doremylover123@gmail.com>\n\nstrncmp does not modify any of the memory.\nOnce we find a match, there is no point\nin trying to find the second match\nin the inner loop.\n\nBreak out of the loop once we\nfind the first match.\n\nSigned-off-by: Seija Kijin <doremylover123@gmail.com>\n---\n    merge: break out of all_strategy loop when strategy is found\n    \n    strncmp does not modify any of the memory, so looping through all\n    elements is a waste of resources.\n    \n    Signed-off-by: Seija Kijin doremylover123@gmail.com\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1429%2FAtariDreams%2Fexit-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1429/AtariDreams/exit-v2\nPull-Request: https://github.com/git/git/pull/1429\n\nRange-diff vs v1:\n\n 1:  82c1d021b2c ! 1:  d93d4aff780 merge: break out of all_strategy loop when strategy is found\n     @@ Metadata\n       ## Commit message ##\n          merge: break out of all_strategy loop when strategy is found\n      \n     -    strncmp does not modify any of the memory,\n     -    so looping through all elements is a waste of resources.\n     +    strncmp does not modify any of the memory.\n     +    Once we find a match, there is no point\n     +    in trying to find the second match\n     +    in the inner loop.\n     +\n     +    Break out of the loop once we\n     +    find the first match.\n      \n          Signed-off-by: Seija Kijin <doremylover123@gmail.com>\n      \n       ## builtin/merge.c ##\n      @@ builtin/merge.c: static struct strategy *get_strategy(const char *name)\n     + \t\tfor (i = 0; i < main_cmds.cnt; i++) {\n       \t\t\tint j, found = 0;\n       \t\t\tstruct cmdname *ent = main_cmds.names[i];\n     - \t\t\tfor (j = 0; j < ARRAY_SIZE(all_strategy); j++)\n     --\t\t\t\tif (!strncmp(ent->name, all_strategy[j].name, ent->len)\n     --\t\t\t\t\t\t&& !all_strategy[j].name[ent->len])\n     -+\t\t\t\tif (!strncmp(ent->name, all_strategy[j].name,\n     -+\t\t\t\t\t     ent->len) &&\n     -+\t\t\t\t    !all_strategy[j].name[ent->len]) {\n     +-\t\t\tfor (j = 0; j < ARRAY_SIZE(all_strategy); j++)\n     ++\t\t\tfor (j = 0; !found && j < ARRAY_SIZE(all_strategy); j++)\n     + \t\t\t\tif (!strncmp(ent->name, all_strategy[j].name, ent->len)\n     + \t\t\t\t\t\t&& !all_strategy[j].name[ent->len])\n       \t\t\t\t\tfound = 1;\n     -+\t\t\t\t\tbreak;\n     -+\t\t\t\t}\n     - \t\t\tif (!found)\n     - \t\t\t\tadd_cmdname(&not_strategies, ent->name, ent->len);\n     - \t\t}\n\n\n builtin/merge.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/builtin/merge.c b/builtin/merge.c\nindex 0f093f2a4f2..74de2ebd2b3 100644\n--- a/builtin/merge.c\n+++ b/builtin/merge.c\n@@ -188,7 +188,7 @@ static struct strategy *get_strategy(const char *name)\n \t\tfor (i = 0; i < main_cmds.cnt; i++) {\n \t\t\tint j, found = 0;\n \t\t\tstruct cmdname *ent = main_cmds.names[i];\n-\t\t\tfor (j = 0; j < ARRAY_SIZE(all_strategy); j++)\n+\t\t\tfor (j = 0; !found && j < ARRAY_SIZE(all_strategy); j++)\n \t\t\t\tif (!strncmp(ent->name, all_strategy[j].name, ent->len)\n \t\t\t\t\t\t&& !all_strategy[j].name[ent->len])\n \t\t\t\t\tfound = 1;\n\nbase-commit: a38d39a4c50d1275833aba54c4dbdfce9e2e9ca1\n-- \ngitgitgadget\n"},{"id":"470297","messageId":"xmqqbkn247jd.fsf@gitster.g","threadId":"59053","inReplyTo":"pull.1429.v2.git.git.1673285669004.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] merge: break out of all_strategy loop when strategy is found","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-01-13T18:24:22Z","receivedAt":"2023-01-13T18:28:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Rose via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> From: Seija Kijin <doremylover123@gmail.com>\n>\n> strncmp does not modify any of the memory.\n\nIt may be a correct statement, but so what?  It does not seem to\nhave relevance to this change.\n\n> diff --git a/builtin/merge.c b/builtin/merge.c\n> index 0f093f2a4f2..74de2ebd2b3 100644\n> --- a/builtin/merge.c\n> +++ b/builtin/merge.c\n> @@ -188,7 +188,7 @@ static struct strategy *get_strategy(const char *name)\n>  \t\tfor (i = 0; i < main_cmds.cnt; i++) {\n>  \t\t\tint j, found = 0;\n>  \t\t\tstruct cmdname *ent = main_cmds.names[i];\n> -\t\t\tfor (j = 0; j < ARRAY_SIZE(all_strategy); j++)\n> +\t\t\tfor (j = 0; !found && j < ARRAY_SIZE(all_strategy); j++)\n>  \t\t\t\tif (!strncmp(ent->name, all_strategy[j].name, ent->len)\n>  \t\t\t\t\t\t&& !all_strategy[j].name[ent->len])\n>  \t\t\t\t\tfound = 1;\n\nI am not sure if this micro-optimization is worth it.  \n\nIf this loop is so costly that it needs optimization, a better thing\nto do would be to rethink the way it filters main_cmds.names[] array\nwith all_strategy[].  The latter is a fairly small, and more\nimportantly, a constant set of known strategies, so there should be\na more efficient way than O(n*m) nested loop.\n\nThe code churn has already costed us too much, mostly reviewer and\nmaintainer time, for the value of the change itself.  I'll queue the\npatch as-is, because this change is not making anything worse\nper-se, but primarily because I do not want the topic to take any\nmore of our resources.\n\nThanks.\n"}]}