merge: break out of all_strategy loop when strategy is found
PATCH 1/1 merge: break out of all_strategy loop when strategy is found
From: Seija Kijin <[email protected]>
strncmp does not modify any of the memory,
so looping through all elements is a waste of resources.
---
merge: break out of all_strategy loop when strategy is found
strncmp does not modify any of the memory, so looping through all elements is a waste of resources.
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1429%2FAtariDreams%2Fexit-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1429/AtariDreams/exit-v1
Pull-Request: https://github.com/git/git/pull/1429
builtin/merge.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)
builtin/merge.c +5 -2
@@ -189,9 +189,12 @@ static struct strategy *get_strategy(const char *name)int j, found =0 ;struct cmdname *ent = main_cmds.names[i];for (j =0 ; j <ARRAY_SIZE (all_strategy); j++) -if (!strncmp (ent->name, all_strategy[j].name, ent->len) - && !all_strategy[j].name[ent->len]) +if (!strncmp (ent->name, all_strategy[j].name, + ent->len) && + !all_strategy[j].name[ent->len]) { found =1 ; +break ; + }if (!found)add_cmdname (¬_strategies, ent->name, ent->len); }
base-commit: a38d39a4c50d1275833aba54c4dbdfce9e2e9ca1
Signature · 1 line
gitgitgadget
Quoted 4 lines · Rose via GitGitGadget
From: Seija Kijin <[email protected]>
strncmp does not modify any of the memory,
so looping through all elements is a waste of resources.
Modifying or not probably has little to do with why we may want to do this change.
Here, we are trying to see which commands that appear in the main_cmds table do not appear in the all_strategy[] table. The way we do so is by iterating over the main_cmds table, and for each of the command, if it is found in the all_strategy[] table. If there is one, then found bit is set. If there isn't, then found bit is left clear. After looping over all_strategy[] table, we act upon the value of the found bit.
So, as soon as we find one match in all_strategy[] table and flip the found bit on, in the loop we never clear the bit. So it does make sense to break out of that inner loop once we find a single match.
Once we find a match, there is no point to try finding the second match in the inner loop. Break out of the loop once we find the first match.
would be a more appropriate explanation.
Quoted 9 lines
builtin/merge.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)builtin/merge.c +0
-0@@ -189,9 +189,12 @@ static struct strategy *get_strategy(const char *name)int j, found =0 ;
builtin/merge.c static struct strategy *get_strategy(const char *name) · line 197
Quoted 10 lines
builtin/merge.c +5
-2struct cmdname *ent = main_cmds.names[i];for (j =0 ; j <ARRAY_SIZE (all_strategy); j++) -if (!strncmp (ent->name, all_strategy[j].name, ent->len) - && !all_strategy[j].name[ent->len]) +if (!strncmp (ent->name, all_strategy[j].name, + ent->len) && + !all_strategy[j].name[ent->len]) { found =1 ; +break ; + }
The above is not wrong per-se, but we can do the same with less damage to the code, e.g.
builtin/merge.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
builtin/merge.c +1 -1
@@ -188,7 +188,7 @@ static struct strategy *get_strategy(const char *name)for (i =0 ; i < main_cmds.cnt; i++) {int j, found =0 ;struct cmdname *ent = main_cmds.names[i]; -for (j =0 ; j <ARRAY_SIZE (all_strategy); j++) +for (j =0 ; !found && j <ARRAY_SIZE (all_strategy); j++)if (!strncmp (ent->name, all_strategy[j].name, ent->len) && !all_strategy[j].name[ent->len]) found =1 ;
I've mentioned it before, but could you please drop the
Rose <[email protected]>
address from the Cc: list? It is rude to force those who want to respond to you to remove the non-working address that is meant not to receive any responses.
Thanks.
PATCH v2 1/1 merge: break out of all_strategy loop when strategy is found
In reply to Rose via GitGitGadgetFrom: Seija Kijin <[email protected]>
strncmp does not modify any of the memory. Once we find a match, there is no point in trying to find the second match in the inner loop.
Break out of the loop once we
find the first match.
---
merge: break out of all_strategy loop when strategy is found
strncmp does not modify any of the memory, so looping through all elements is a waste of resources.
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1429%2FAtariDreams%2Fexit-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1429/AtariDreams/exit-v2
Pull-Request: https://github.com/git/git/pull/1429
Range-diff vs v1:
1: 82c1d021b2c ! 1: d93d4aff780 merge: break out of all_strategy loop when strategy is found
@@ Metadata
## Commit message ##
merge: break out of all_strategy loop when strategy is found
- strncmp does not modify any of the memory,
- so looping through all elements is a waste of resources.
+ strncmp does not modify any of the memory.
+ Once we find a match, there is no point
+ in trying to find the second match
+ in the inner loop.
+
+ Break out of the loop once we
+ find the first match.
## builtin/merge.c ##
@@ builtin/merge.c: static struct strategy *get_strategy(const char *name)
+ for (i = 0; i < main_cmds.cnt; i++) {
int j, found = 0;
struct cmdname *ent = main_cmds.names[i];
- for (j = 0; j < ARRAY_SIZE(all_strategy); j++)
-- if (!strncmp(ent->name, all_strategy[j].name, ent->len)
-- && !all_strategy[j].name[ent->len])
-+ if (!strncmp(ent->name, all_strategy[j].name,
-+ ent->len) &&
-+ !all_strategy[j].name[ent->len]) {
+- for (j = 0; j < ARRAY_SIZE(all_strategy); j++)
++ for (j = 0; !found && j < ARRAY_SIZE(all_strategy); j++)
+ if (!strncmp(ent->name, all_strategy[j].name, ent->len)
+ && !all_strategy[j].name[ent->len])
found = 1;
-+ break;
-+ }
- if (!found)
- add_cmdname(¬_strategies, ent->name, ent->len);
- }
builtin/merge.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
builtin/merge.c +1 -1
@@ -188,7 +188,7 @@ static struct strategy *get_strategy(const char *name)for (i =0 ; i < main_cmds.cnt; i++) {int j, found =0 ;struct cmdname *ent = main_cmds.names[i]; -for (j =0 ; j <ARRAY_SIZE (all_strategy); j++) +for (j =0 ; !found && j <ARRAY_SIZE (all_strategy); j++)if (!strncmp (ent->name, all_strategy[j].name, ent->len) && !all_strategy[j].name[ent->len]) found =1 ;
base-commit: a38d39a4c50d1275833aba54c4dbdfce9e2e9ca1
Signature · 1 line
gitgitgadget
Quoted 3 lines · Rose via GitGitGadget
From: Seija Kijin <[email protected]>
strncmp does not modify any of the memory.
It may be a correct statement, but so what? It does not seem to have relevance to this change.
builtin/merge.c static struct strategy *get_strategy(const char *name) · line 194
Quoted 13 lines
builtin/merge.c +1
-1@@ -188,7 +188,7 @@ static struct strategy *get_strategy(const char *name)for (i =0 ; i < main_cmds.cnt; i++) {int j, found =0 ;struct cmdname *ent = main_cmds.names[i]; -for (j =0 ; j <ARRAY_SIZE (all_strategy); j++) +for (j =0 ; !found && j <ARRAY_SIZE (all_strategy); j++)if (!strncmp (ent->name, all_strategy[j].name, ent->len) && !all_strategy[j].name[ent->len]) found =1 ;
I am not sure if this micro-optimization is worth it.
If this loop is so costly that it needs optimization, a better thing to do would be to rethink the way it filters main_cmds.names[] array with all_strategy[]. The latter is a fairly small, and more importantly, a constant set of known strategies, so there should be a more efficient way than O(n*m) nested loop.
The code churn has already costed us too much, mostly reviewer and maintainer time, for the value of the change itself. I'll queue the patch as-is, because this change is not making anything worse per-se, but primarily because I do not want the topic to take any more of our resources.
Thanks.