git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH] merge: break out of all_strategy loop when strategy is found
@ 2023-01-08 18:39 Rose via GitGitGadget
  2023-01-09  5:14 ` Junio C Hamano
  2023-01-09 17:34 ` [PATCH v2] " Rose via GitGitGadget
  0 siblings, 2 replies; 4+ messages in thread
From: Rose via GitGitGadget @ 2023-01-08 18:39 UTC (permalink / raw)
  To: git; +Cc: Rose, Seija Kijin

From: Seija Kijin <doremylover123@gmail.com>

strncmp does not modify any of the memory,
so looping through all elements is a waste of resources.

Signed-off-by: Seija Kijin <doremylover123@gmail.com>
---
    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 doremylover123@gmail.com

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(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 0f093f2a4f2..5ab0feb47b6 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -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(&not_strategies, ent->name, ent->len);
 		}

base-commit: a38d39a4c50d1275833aba54c4dbdfce9e2e9ca1
-- 
gitgitgadget

^ permalink raw reply related	[flat|nested] 4+ messages in thread

* Re: [PATCH] merge: break out of all_strategy loop when strategy is found
  2023-01-08 18:39 [PATCH] merge: break out of all_strategy loop when strategy is found Rose via GitGitGadget
@ 2023-01-09  5:14 ` Junio C Hamano
  2023-01-09 17:34 ` [PATCH v2] " Rose via GitGitGadget
  1 sibling, 0 replies; 4+ messages in thread
From: Junio C Hamano @ 2023-01-09  5:14 UTC (permalink / raw)
  To: Rose via GitGitGadget; +Cc: git, Seija Kijin

"Rose via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Seija Kijin <doremylover123@gmail.com>
>
> 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.

>  builtin/merge.c | 7 +++++--
>  1 file changed, 5 insertions(+), 2 deletions(-)
>
> diff --git a/builtin/merge.c b/builtin/merge.c
> index 0f093f2a4f2..5ab0feb47b6 100644
> --- a/builtin/merge.c
> +++ b/builtin/merge.c
> @@ -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;
> +				}

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(-)

diff --git c/builtin/merge.c w/builtin/merge.c
index dd474371a2..2437aae6bc 100644
--- c/builtin/merge.c
+++ w/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've mentioned it before, but could you please drop the

    Rose <83477269+AtariDreams@users.noreply.github.com>

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.

^ permalink raw reply related	[flat|nested] 4+ messages in thread

* [PATCH v2] merge: break out of all_strategy loop when strategy is found
  2023-01-08 18:39 [PATCH] merge: break out of all_strategy loop when strategy is found Rose via GitGitGadget
  2023-01-09  5:14 ` Junio C Hamano
@ 2023-01-09 17:34 ` Rose via GitGitGadget
  2023-01-13 18:24   ` Junio C Hamano
  1 sibling, 1 reply; 4+ messages in thread
From: Rose via GitGitGadget @ 2023-01-09 17:34 UTC (permalink / raw)
  To: git; +Cc: Rose, Seija Kijin

From: Seija Kijin <doremylover123@gmail.com>

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 <doremylover123@gmail.com>
---
    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 doremylover123@gmail.com

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 <doremylover123@gmail.com>
      
       ## 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(-)

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;

base-commit: a38d39a4c50d1275833aba54c4dbdfce9e2e9ca1
-- 
gitgitgadget

^ permalink raw reply related	[flat|nested] 4+ messages in thread

* Re: [PATCH v2] merge: break out of all_strategy loop when strategy is found
  2023-01-09 17:34 ` [PATCH v2] " Rose via GitGitGadget
@ 2023-01-13 18:24   ` Junio C Hamano
  0 siblings, 0 replies; 4+ messages in thread
From: Junio C Hamano @ 2023-01-13 18:24 UTC (permalink / raw)
  To: Rose via GitGitGadget; +Cc: git, Seija Kijin

"Rose via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Seija Kijin <doremylover123@gmail.com>
>
> 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.

^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2023-01-13 18:28 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-01-08 18:39 [PATCH] merge: break out of all_strategy loop when strategy is found Rose via GitGitGadget
2023-01-09  5:14 ` Junio C Hamano
2023-01-09 17:34 ` [PATCH v2] " Rose via GitGitGadget
2023-01-13 18:24   ` Junio C Hamano

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).