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

From: Eric Sunshine <sunshine@sunshineco.com>
Date: Jul 27, 2013, 00:26 UTC
Message-ID: <CAPig+cRO4tBi21zPpw3i+9E3xvvJQDmc=CFU5Xyy7zhoJi1Fhg@mail.gmail.com>
In-Reply-To: <1374871850-24323-1-git-send-email-stefanbeller@googlemail.com>

On Fri, Jul 26, 2013 at 4:50 PM, Stefan Beller <stefanbeller@googlemail.com> wrote:

Show 26 quoted lines

> 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 <stefanbeller@googlemail.com>
> ---
>  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;

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.

Show 8 quoted lines

> +       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.

Show 13 quoted lines

>                 { "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);

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

Show 8 quoted lines

> +
> +       if (p)
>                 exit(run_builtin(p, argc, argv));
> -       }
>  }
>
>  static void execv_dashed_external(const char **argv)
> --