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

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Mar 19, 2011, 08:51 UTC
Message-ID: <20110319085138.GB6706@elie>
In-Reply-To: <1300518231-20008-4-git-send-email-david.barr@cordelta.com>

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

[...]

Show 14 quoted lines

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

[...]

Show 8 quoted lines

> -	} 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) {

[...]

Show 6 quoted lines

> @@ -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>" */

Show 13 quoted lines

>  	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