[PATCH] builtins: search builtin commands via binary search.

There are currently 115 commands built into the git executable.
Before this commit, it was iterated over these commands in a linear
order, i.e. each command was checked.

As it turns out the commands are already sorted alphabetically, it is easy
to perform a binary search instead of linear searching.
This results in 7 lookups in the worst case.

Signed-off-by: Stefan Beller <redacted>
---
 git.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)

diff --git a/git.c b/git.c
index 2025f77..0d7a9b5 100644
--- a/git.c
+++ b/git.c

@@ -309,9 +309,18 @@ static int run_builtin(struct cmd_struct *p, int argc, const char **argv)
 	return 0;
 }
 
+static int compare_internal_command(const void *a, const void *b) {
+	/* The first parameter is of type char* describing the name,
+	   the second is a struct cmd_struct */
+	const char *name = (const char*)a;
+	const struct cmd_struct *cmd_struct = (struct cmd_struct*)b;
+	return strcmp(name, cmd_struct->cmd);
+}
+
 static void handle_internal_command(int argc, const char **argv)
 {
 	const char *cmd = argv[0];
+	/* commands must be sorted alphabetically */
 	static struct cmd_struct commands[] = {
 		{ "add", cmd_add, RUN_SETUP | NEED_WORK_TREE },
 		{ "annotate", cmd_annotate, RUN_SETUP },

@@ -447,12 +456,12 @@ static void handle_internal_command(int argc, const char **argv)
 		argv[0] = cmd = "help";
 	}
 
-	for (i = 0; i < ARRAY_SIZE(commands); i++) {
-		struct cmd_struct *p = commands+i;
-		if (strcmp(p->cmd, cmd))
-			continue;
+	struct cmd_struct *p = (struct cmd_struct *)bsearch(cmd, commands,
+				ARRAY_SIZE(commands), sizeof(struct cmd_struct),
+				compare_internal_command);
+
+	if (p)
 		exit(run_builtin(p, argc, argv));
-	}
 }
 
 static void execv_dashed_external(const char **argv)

-- 
1.8.4.rc0.1.g8f6a3e5

Hi,

Stefan Beller wrote:

Style:

	/*
	 * Multi-line comments in git look like this, with an initial
	 * "/*" line, a leading "*" on each line with text, and a line
	 * with '*' '/' at the end.
	 */

[...]

No need to cast --- this is C.

Fun.  Does this result in a measurable speedup, or is it just for more
pleasant reading?

Thanks and hope that helps,
Jonathan

On Fri, Jul 26, 2013 at 4:50 PM, Stefan Beller
[off-list ref] wrote:

Comments typically exist to elucidate something non-obvious in the
code, however, in this case the code and comment say the same thing,
making the comment redundant. Such redundancy can make code harder to
read since the reader has to take extra time to figure out if the
comment is really explaining something not obvious in the code. Thus,
this comment can be removed without loss of clarity.

+       return strcmp(name, cmd_struct->cmd);
+}
+
 static void handle_internal_command(int argc, const char **argv)
 {
        const char *cmd = argv[0];
+       /* commands must be sorted alphabetically */
        static struct cmd_struct commands[] = {

This new comment, on the other hand does explain something not obvious
at this point in the code.

Since this will break down if the commands[] array becomes unsorted,
it would make sense to protect against such a failure. For instance,
you could add a check in Makefile which triggers when git.c is edited.
It might do something like this:

  awk '/cmd_struct commands/,/};/ { if (match($2,/"/)) print $2 }'
    <git.c >builtin.actual &&
  sort <builtin.actual >builtin.expect &&
  cmp -s builtin.expect builtin.actual &&
  rm builtin.expect builtin.actual

+
+       if (p)
                exit(run_builtin(p, argc, argv));
-       }
 }

 static void execv_dashed_external(const char **argv)
--

On 07/26/2013 10:57 PM, Jonathan Nieder wrote:

Hi,

Stefan Beller wrote:

quoted

--- a/git.c
+++ b/git.c

@@ -309,9 +309,18 @@ static int run_builtin(struct cmd_struct *p, int argc, const char **argv)
 	return 0;
 }
 
+static int compare_internal_command(const void *a, const void *b) {
+	/* The first parameter is of type char* describing the name,
+	   the second is a struct cmd_struct */

Style:

	/*
	 * Multi-line comments in git look like this, with an initial
	 * "/*" line, a leading "*" on each line with text, and a line
	 * with '*' '/' at the end.
	 */

[...]

Thanks for noting, however as Eric points out, that comment was not enlightening, so I removed it.

quoted

@@ -447,12 +456,12 @@ static void handle_internal_command(int argc, const char **argv)
 		argv[0] = cmd = "help";
 	}
 
-	for (i = 0; i < ARRAY_SIZE(commands); i++) {
-		struct cmd_struct *p = commands+i;
-		if (strcmp(p->cmd, cmd))
-			continue;
+	struct cmd_struct *p = (struct cmd_struct *)bsearch(cmd, commands,
+				ARRAY_SIZE(commands), sizeof(struct cmd_struct),
+				compare_internal_command);

No need to cast --- this is C.

Also removed.

Fun.  Does this result in a measurable speedup, or is it just for more
pleasant reading?

Thanks and hope that helps,
Jonathan

premature optimization is the root of all evil....
I tried hard to come up with a benchmark, but this is lost in the
noise. I could not figure out a way to reproducably make sure this
patch is really faster.
So I tried to `time git add COPYING` to show it's not getting slower
for the first entries in the list as well as `git fast-external-command`
whereas the fast-external-command is just an int main() {return 0; }
to check if the external commands, which are executed after searching 
through all the internals come up faster.

However I could not find a speedup.
So if the patch is accepted, it would only be for readability.

I was fiddling around with make now to include the suggestion of Eric to
check the arguments for being sorted in make. However I do not 
seem to fully understand the syntax yet.
My approach would have been:

sorted_internal_cmds: git.c
	{ awk '/cmd_struct commands/,/};/ { if (match($2,/"/)) print $2 }' <git.c >builtin.actual && \
	sort <builtin.actual >builtin.expect && \
	cmp -s builtin.expect builtin.actual && \
	rm builtin.expect builtin.actual \
	}

all:: sorted_internal_cmds

But then there is 
$ make 
...
	}
/bin/sh: 5: Syntax error: end of file unexpected (expecting "}")

So I suspect the { within the shell code inside the awk parameter is messing up?

Thanks,
Stefan

There are currently 115 commands built into the git executable.
Before this commit, it was iterated over these commands in a linear
order, i.e. each command was checked.

As it turns out the commands are already sorted alphabetically, it is easy
to perform a binary search instead of linear searching.
This results in 7 lookups in the worst case.

Signed-off-by: Stefan Beller <redacted>
---
 git.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/git.c b/git.c
index 2025f77..6d4de2b 100644
--- a/git.c
+++ b/git.c

@@ -309,9 +309,14 @@ static int run_builtin(struct cmd_struct *p, int argc, const char **argv)
 	return 0;
 }
 
+static int compare_internal_command(const void *name, const void *cmd) {
+	return strcmp((const char*)name, ((const struct cmd_struct*)cmd)->cmd);
+}
+
 static void handle_internal_command(int argc, const char **argv)
 {
 	const char *cmd = argv[0];
+	/* commands must be sorted alphabetically for binary search */
 	static struct cmd_struct commands[] = {
 		{ "add", cmd_add, RUN_SETUP | NEED_WORK_TREE },
 		{ "annotate", cmd_annotate, RUN_SETUP },

@@ -447,12 +452,12 @@ static void handle_internal_command(int argc, const char **argv)
 		argv[0] = cmd = "help";
 	}
 
-	for (i = 0; i < ARRAY_SIZE(commands); i++) {
-		struct cmd_struct *p = commands+i;
-		if (strcmp(p->cmd, cmd))
-			continue;
+	struct cmd_struct *p = bsearch(cmd, commands,
+				ARRAY_SIZE(commands), sizeof(struct cmd_struct),
+				compare_internal_command);
+
+	if (p)
 		exit(run_builtin(p, argc, argv));
-	}
 }
 
 static void execv_dashed_external(const char **argv)

-- 
1.8.4.rc0.1.g8f6a3e5

On Sat, Jul 27, 2013 at 4:49 AM, Stefan Beller
[off-list ref] wrote:

I was fiddling around with make now to include the suggestion of Eric to
check the arguments for being sorted in make. However I do not
seem to fully understand the syntax yet.
My approach would have been:

sorted_internal_cmds: git.c
        { awk '/cmd_struct commands/,/};/ { if (match($2,/"/)) print $2 }' <git.c >builtin.actual && \
        sort <builtin.actual >builtin.expect && \
        cmp -s builtin.expect builtin.actual && \
        rm builtin.expect builtin.actual \
        }

all:: sorted_internal_cmds

But then there is
$ make
...
        }
/bin/sh: 5: Syntax error: end of file unexpected (expecting "}")

So I suspect the { within the shell code inside the awk parameter is messing up?

As Andreas noted, you need a semicolon before the closing shell '}',
however it's not clear why you added the braces since they are not
needed. The following works (after fixing whitespace corruption):

-->8--

diff --git a/Makefile b/Makefile
index ef442eb..82e727c 100644
--- a/Makefile
+++ b/Makefile

@@ -1681,6 +1681,15 @@ shell_compatibility_test:

please_set_SHELL_PATH_to_a_more_modern_shell
 strip: $(PROGRAMS) git$X
  $(STRIP) $(STRIP_OPTS) $^

+.PHONY: sorted_internal_cmds
+all:: sorted_internal_cmds
+
+sorted_internal_cmds: git.c
+ @awk '/cmd_struct commands/,/};/ { if (match($$2,/"/)) print $$2 }'
<git.c >builtin.actual && \
+ sort <builtin.actual >builtin.expect && \
+ cmp -s builtin.expect builtin.actual && \
+ rm builtin.expect builtin.actual
+
 ### Target-specific flags and dependencies

 # The generic compilation pattern rule and automatically
-->8--

Note the $$2 in awk expression. Also the .PHONY is a good idea.

However, perhaps, it is better for this check to be part of the test
suite. It might look like this (after fixing whitespace corruption):

-->8--

diff --git a/t/t0000-basic.sh b/t/t0000-basic.sh
index 10be52b..e5ba504 100755
--- a/t/t0000-basic.sh
+++ b/t/t0000-basic.sh

@@ -387,6 +387,14 @@ test_expect_success 'tests clean up even on failures' "
 ################################################################
 # Basics of the basics

+# git.c commands[] of builtins is properly sorted
+test_expect_success 'builtin commands[] sorted' '
+ awk "/cmd_struct commands/,/};/ { if (match(\$2,/\"/)) print \$2 }" \
+ <../../git.c >actual && \
+ sort <actual >expect && \
+ test_cmp expect actual
+'
+
 # updating a new file without --add should fail.
 test_expect_success 'git update-index without --add should fail adding' '
  test_must_fail git update-index should-be-empty
-->8--

I'm not sure that referencing ../../git.c from within the test suite
is kosher. Perhaps Jonathan can say something about that.