[v2] merge: break out of all_strategy loop when strategy is found

Commit Message

Seija Kijin Jan. 9, 2023, 5:34 p.m. UTC

From: Seija Kijin <[e-mail]>

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.

Signed-off-by: Seija Kijin <[e-mail]>
---
    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.
    
    Signed-off-by: Seija Kijin [e-mail]

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.
      
          Signed-off-by: Seija Kijin <[e-mail]>
      
       ## 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(&not_strategies, ent->name, ent->len);
     - 		}


 builtin/merge.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)


base-commit: a38d39a4c50d1275833aba54c4dbdfce9e2e9ca1

Comments

Junio C Hamano Jan. 13, 2023, 6:24 p.m. UTC | #1

"Rose via GitGitGadget" <[e-mail]> writes:

> From: Seija Kijin <[e-mail]>
>
> 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.

> diff --git a/builtin/merge.c b/builtin/merge.c
> index 0f093f2a4f2..74de2ebd2b3 100644
> --- a/builtin/merge.c
> +++ b/builtin/merge.c
> @@ -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.

Patch

diff --git a/builtin/merge.c b/builtin/merge.c
index 0f093f2a4f2..74de2ebd2b3 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -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;