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

From: Stefan Beller <stefanbeller@googlemail.com>
Date: Jul 27, 2013, 08:49 UTC
Message-ID: <51F38997.9010507@googlemail.com>
In-Reply-To: <20130726205737.GI14690@google.com>

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

Show 23 quoted lines

> Hi,
> 
> Stefan Beller wrote:
> 
>> --- 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.

Show 13 quoted lines

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

Show 7 quoted lines

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