Subject: Re: [PATCH 3/9] vcs-svn: implement perfect hash for node-prop keys

From: Jonathan Nieder <[email-masked]>
Date: Sat, 19 Mar 2011 03:51:38 -0500

David Barr wrote:

>  vcs-svn/svndump.c |   50 ++++++++++++++++++++++++++++++++------------------
>  1 files changed, 32 insertions(+), 18 deletions(-)

Alas.  But it's probably worth it for the chance to get rid of
knowledge of how to intern strings.

> --- a/vcs-svn/svndump.c
> +++ b/vcs-svn/svndump.c
[...]
> @@ -113,22 +107,38 @@ static void init_keys(void)
>  	keys.prop_delta = pool_intern("Prop-delta");
>  }
>  
> -static void handle_property(uint32_t key, const char *val, uint32_t len,
> +static void handle_property(const char *key, const char *val, uint32_t len,
>  				uint32_t *type_set)
>  {
> -	if (key == keys.svn_log) {
> +	const int key_len = strlen(key);
> +	switch (key_len) {
> +	case 7:
> +		if (memcmp(key, "svn:log", 7))
> +			break;

Crazy idea: to make it visible at a glance when the numbers are wrong,
one can do:

	switch (key_len + 1) {
	case sizeof("svn:log"):
		if (memcmp(key, "svn:log", strlen("svn:log")))
			break;

This only makes the redundancy more obvious, of course.  It could
be reduced a little with something like

 static int prefixcmp_len(const char *str, size_t str_len,
			  const char *prefix, size_t prefix_len)
 {
	if (prefix_len > str_len)
		return 1;
	return memcmp(str, prefix, prefix_len);
 }

but that's probably not worth the cognitive load.

[...]
> -	} else if (key == keys.svn_executable || key == keys.svn_special) {
> +		break;
> +	case 14:
> +		if (memcmp(key, "svn:executable", 14))
> +			break;
> +	case 11:
> +		if (key_len == 11 && memcmp(key, "svn:special", 11))
> +			break;

Maybe, to avoid an unnecessary /* fall through */:

	case sizeof("svn:executable"):
	case sizeof("svn:special"):
		if (key_len == strlen("svn:executable") &&
		    memcmp(key, "svn:executable", strlen(...)))
			break;
		if (key_len == strlen("svn:special") &&
		    memcmp(key, "svn:special", strlen("svn:special")))
			break;

>  		if (*type_set) {
[...]
> @@ -147,7 +157,7 @@ static void handle_property(uint32_t key, const char *val, uint32_t len,
>  
>  static void read_props(void)
>  {
> -	uint32_t key = ~0;
> +	char key[16] = {0};

Probably warrants a comment:

	/* the longest key we pay attention to is "<whatever>" */

>  	const char *t;
>  	/*
>  	 * NEEDSWORK: to support simple mode changes like
> @@ -175,16 +185,20 @@ static void read_props(void)
>  
>  		switch (type) {
>  		case 'K':
> -			key = pool_intern(val);
> -			continue;
>  		case 'D':
> -			key = pool_intern(val);
> +			if (len < sizeof(key))
> +				memcpy(key, val, len + 1);

What happens on I/O error, when val is NULL?  How about early EOF
or malformed input, when strlen(val) < len?

Some tests would also be a comfort.

I'm not so happy with the table of (at first glance) magic-seeming
numbers and the error handling looks a little tricky but aside from
those details this seems like a reasonable way to avoid some
complication without sacrificing speed.

Speaking of which, any hints for people who want to time this patch
(and other patches in the series)?

Thanks.
Jonathan