[PATCH] Optimize common pattern of alloc_ref from string

[PATCH] Optimize common pattern of alloc_ref from string

[kkowalczyk]

From: Krzysztof Kowalczyk <kkowalczyk@gmail.com>

As a byproduct, fixes one place where string wasn't properly terminated.
Signed-off-by: Krzysztof Kowalczyk <kkowalczyk@gmail.com>
---
 builtin-fetch.c |    6 ++----
 http-push.c     |    6 ++----
 remote.c        |   28 +++++++++++++++-------------
 remote.h        |    2 ++
 transport.c     |    6 ++----
 walker.c        |    3 +--
 6 files changed, 24 insertions(+), 27 deletions(-)

diff --git a/builtin-fetch.c b/builtin-fetch.c
index e56617e..f6584ec 100644
--- a/builtin-fetch.c
+++ b/builtin-fetch.c
@@ -508,10 +508,8 @@ static void find_non_local_tags(struct transport *transport,
 		     will_fetch(head, ref->old_sha1))) {
 			path_list_insert(ref_name, &new_refs);
 
-			rm = alloc_ref(strlen(ref_name) + 1);
-			strcpy(rm->name, ref_name);
-			rm->peer_ref = alloc_ref(strlen(ref_name) + 1);
-			strcpy(rm->peer_ref->name, ref_name);
+			rm = alloc_ref_from_str(ref_name);
+			rm->peer_ref = alloc_ref_from_str(ref_name);
 			hashcpy(rm->old_sha1, ref_sha1);
 
 			**tail = rm;
diff --git a/http-push.c b/http-push.c
index 939a764..42727c8 100644
--- a/http-push.c
+++ b/http-push.c
@@ -1761,8 +1761,7 @@ static void one_remote_ref(char *refname)
 	struct ref *ref;
 	struct object *obj;
 
-	ref = alloc_ref(strlen(refname) + 1);
-	strcpy(ref->name, refname);
+	ref = alloc_ref_from_str(refname);
 
 	if (http_fetch_ref(remote->url, ref) != 0) {
 		fprintf(stderr,
@@ -1894,8 +1893,7 @@ static void add_remote_info_ref(struct remote_ls_ctx *ls)
 	char *ref_info;
 	struct ref *ref;
 
-	ref = alloc_ref(strlen(ls->dentry_name) + 1);
-	strcpy(ref->name, ls->dentry_name);
+	ref = alloc_ref_from_str(ls->dentry_name);
 
 	if (http_fetch_ref(remote->url, ref) != 0) {
 		fprintf(stderr,
diff --git a/remote.c b/remote.c
index 6b480cb..4d3e0c7 100644
--- a/remote.c
+++ b/remote.c
@@ -691,6 +691,18 @@ struct ref *alloc_ref(unsigned namelen)
 	return ret;
 }
 
+struct ref *alloc_ref_from_str(const char* str)
+{
+	struct ref *ret;
+	unsigned len = strlen(str) + 1;
+	char *tmp = xmalloc(sizeof(struct ref) + len);
+	ret = (struct ref*)tmp;
+	memset(tmp, 0, sizeof(struct ref));
+	tmp += sizeof(struct ref);
+	memcpy(tmp, str, len);
+	return ret;
+}
+
 static struct ref *copy_ref(const struct ref *ref)
 {
 	struct ref *ret = xmalloc(sizeof(struct ref) + strlen(ref->name) + 1);
@@ -797,7 +809,6 @@ static struct ref *try_explicit_object_name(const char *name)
 {
 	unsigned char sha1[20];
 	struct ref *ref;
-	int len;
 
 	if (!*name) {
 		ref = alloc_ref(20);
@@ -807,21 +818,14 @@ static struct ref *try_explicit_object_name(const char *name)
 	}
 	if (get_sha1(name, sha1))
 		return NULL;
-	len = strlen(name) + 1;
-	ref = alloc_ref(len);
-	memcpy(ref->name, name, len);
+	ref = alloc_ref_from_str(name);
 	hashcpy(ref->new_sha1, sha1);
 	return ref;
 }
 
 static struct ref *make_linked_ref(const char *name, struct ref ***tail)
 {
-	struct ref *ret;
-	size_t len;
-
-	len = strlen(name) + 1;
-	ret = alloc_ref(len);
-	memcpy(ret->name, name, len);
+	struct ref *ret = alloc_ref_from_str(name);
 	tail_link_ref(ret, tail);
 	return ret;
 }
@@ -1125,9 +1129,7 @@ static struct ref *get_local_ref(const char *name)
 		return NULL;
 
 	if (!prefixcmp(name, "refs/")) {
-		ret = alloc_ref(strlen(name) + 1);
-		strcpy(ret->name, name);
-		return ret;
+		return alloc_ref_from_str(name);
 	}
 
 	if (!prefixcmp(name, "heads/") ||
diff --git a/remote.h b/remote.h
index 75d006b..2ee83a3 100644
--- a/remote.h
+++ b/remote.h
@@ -54,6 +54,8 @@ struct refspec {
 
 struct ref *alloc_ref(unsigned namelen);
 
+struct ref *alloc_ref_from_str(const char* str);
+
 struct ref *copy_ref_list(const struct ref *ref);
 
 int check_ref_type(const struct ref *ref, int flags);
diff --git a/transport.c b/transport.c
index b012a28..1bc16f2 100644
--- a/transport.c
+++ b/transport.c
@@ -504,8 +504,7 @@ static struct ref *get_refs_via_curl(struct transport *transport)
 
 	strbuf_release(&buffer);
 
-	ref = alloc_ref(strlen("HEAD") + 1);
-	strcpy(ref->name, "HEAD");
+	ref = alloc_ref_from_str("HEAD");
 	if (!walker->fetch_ref(walker, ref) &&
 	    !resolve_remote_symref(ref, refs)) {
 		ref->next = refs;
@@ -546,9 +545,8 @@ static struct ref *get_refs_from_bundle(struct transport *transport)
 		die ("Could not read bundle '%s'.", transport->url);
 	for (i = 0; i < data->header.references.nr; i++) {
 		struct ref_list_entry *e = data->header.references.list + i;
-		struct ref *ref = alloc_ref(strlen(e->name) + 1);
+		struct ref *ref = alloc_ref_from_str(e->name);
 		hashcpy(ref->old_sha1, e->sha1);
-		strcpy(ref->name, e->name);
 		ref->next = result;
 		result = ref;
 	}
diff --git a/walker.c b/walker.c
index fa96a7c..31de6c1 100644
--- a/walker.c
+++ b/walker.c
@@ -190,8 +190,7 @@ static int interpret_target(struct walker *walker, char *target, unsigned char *
 	if (!get_sha1_hex(target, sha1))
 		return 0;
 	if (!check_ref_format(target)) {
-		struct ref *ref = alloc_ref(strlen(target));
-		strcpy(ref->name, target);
+		struct ref *ref = alloc_ref_from_str(target);
 		if (!walker->fetch_ref(walker, ref)) {
 			hashcpy(sha1, ref->old_sha1);
 			free(ref);
-- 
1.5.4.5

Re: [PATCH] Optimize common pattern of alloc_ref from string

[Jeff King]

On Sat, May 10, 2008 at 04:26:58PM -0700, kkowalczyk@gmail.com wrote:

> As a byproduct, fixes one place where string wasn't properly terminated.

Great. Does this fix a user-visible bug? It would be nice to mention in
the commit log _which_ place (though after reading the patch carefully,
it looks like the one interpret_target) so that people looking at the
commit later can understand exactly what was fixed.

> -	ref = alloc_ref(strlen(refname) + 1);
> -	strcpy(ref->name, refname);
> +	ref = alloc_ref_from_str(refname);

So this turns a 2-line construct into a 1-line construct...

> +struct ref *alloc_ref_from_str(const char* str)
> +{
> +	struct ref *ret;
> +	unsigned len = strlen(str) + 1;
> +	char *tmp = xmalloc(sizeof(struct ref) + len);
> +	ret = (struct ref*)tmp;
> +	memset(tmp, 0, sizeof(struct ref));
> +	tmp += sizeof(struct ref);
> +	memcpy(tmp, str, len);
> +	return ret;
> +}

But why do we need an 8-line function to do it?

The only difference I can see over

  struct ref *alloc_ref_from_str(const char *str)
  {
    unsigned len = strlen(str) + 1;
    struct ref *ret = alloc_ref(len);
    memcpy(ret->name, str, len);
    return ret;
  }

is that we avoid memsetting the name portion of the struct to 0 before
copying to it. It seems like an unproven micro-optimization that makes
it a bit harder to read.

-Peff

Re: [PATCH] Optimize common pattern of alloc_ref from string

[Krzysztof Kowalczyk]

On Sat, May 10, 2008 at 4:39 PM, Jeff King <peff@peff.net> wrote:
> On Sat, May 10, 2008 at 04:26:58PM -0700, kkowalczyk@gmail.com wrote:
>
>> As a byproduct, fixes one place where string wasn't properly terminated.
>
> Great. Does this fix a user-visible bug? It would be nice to mention in
> the commit log _which_ place (though after reading the patch carefully,
> it looks like the one interpret_target) so that people looking at the
> commit later can understand exactly what was fixed.

It was a subtle memory corruption that wouldn't cause problems in
99.99% cases, but valgrind would probably catch it. And yes, it's the
interp_target().

>> -     ref = alloc_ref(strlen(refname) + 1);
>> -     strcpy(ref->name, refname);
>> +     ref = alloc_ref_from_str(refname);
>
> So this turns a 2-line construct into a 1-line construct...

And avoids future prossible mistakes with not terminating the string,
like the one just commited.

>> +struct ref *alloc_ref_from_str(const char* str)
>> +{
>> +     struct ref *ret;
>> +     unsigned len = strlen(str) + 1;
>> +     char *tmp = xmalloc(sizeof(struct ref) + len);
>> +     ret = (struct ref*)tmp;
>> +     memset(tmp, 0, sizeof(struct ref));
>> +     tmp += sizeof(struct ref);
>> +     memcpy(tmp, str, len);
>> +     return ret;
>> +}
>
> But why do we need an 8-line function to do it?
>
> The only difference I can see over
>
>  struct ref *alloc_ref_from_str(const char *str)
>  {
>    unsigned len = strlen(str) + 1;
>    struct ref *ret = alloc_ref(len);
>    memcpy(ret->name, str, len);
>    return ret;
>  }
>
> is that we avoid memsetting the name portion of the struct to 0 before
> copying to it. It seems like an unproven micro-optimization that makes
> it a bit harder to read.

You're absolutely right - it's a micro-optimization and your version
might be preferred for clarity. This is the first time I submit a
patch to git so I don't have a good feel for what kind of treadoffs
people find acceptable.

I should also mention that
static struct ref *try_explicit_object_name(const char *name)
{
	unsigned char sha1[20];
	struct ref *ref;

	if (!*name) {
		ref = alloc_ref(20);
		strcpy(ref->name, "(delete)");
		hashclr(ref->new_sha1);
		return ref;
	}
...

could also be replaced with alloc_ref_str() - I just wasn't 100% sure
if overallocating 10 bytes (20 - strlen("(delete)")) was just sloppy
code or does other code relies on that (which is unlikely and if true
then it wouldn't be good).

Regards,

-- kjk

Re: [PATCH] Optimize common pattern of alloc_ref from string

[Jeff King]

On Sat, May 10, 2008 at 05:30:56PM -0700, Krzysztof Kowalczyk wrote:

> >> -     ref = alloc_ref(strlen(refname) + 1);
> >> -     strcpy(ref->name, refname);
> >> +     ref = alloc_ref_from_str(refname);
> >
> > So this turns a 2-line construct into a 1-line construct...
> 
> And avoids future prossible mistakes with not terminating the string,
> like the one just commited.

Yes. Please don't interpret my comment as "this change isn't worth it";
I meant it as "yes, it is good to be simplifying and making this part
less error prone; I just want to nitpick your exact implementation".

> You're absolutely right - it's a micro-optimization and your version
> might be preferred for clarity. This is the first time I submit a
> patch to git so I don't have a good feel for what kind of treadoffs
> people find acceptable.

OK. Ultimately it is up to Junio. I think your version is a bit complex,
but at the very least it contains that complexity neatly in one function.

Actually, the version I posted actually has an optimization, too (it
remembers the strlen calculation to reuse it). I think the simplest
would just be:

  struct ref *alloc_ref_from_str(cons char *str)
  {
    struct ref *ret = alloc_ref(strlen(str) + 1);
    strcpy(ret->name, str);
    return ret;
  }

But really my main worry is that now we have _two_ functions which
allocate refs, so if "struct ref" ever grows a new field that needs
initializing, it has to go in two places (whereas if alloc_ref_from_str
calls alloc_ref, it works automatically).

> I should also mention that
> static struct ref *try_explicit_object_name(const char *name)
> {
> 	unsigned char sha1[20];
> 	struct ref *ref;
> 
> 	if (!*name) {
> 		ref = alloc_ref(20);
> 		strcpy(ref->name, "(delete)");
> 		hashclr(ref->new_sha1);
> 		return ref;
> 	}
> ...
> 
> could also be replaced with alloc_ref_str() - I just wasn't 100% sure
> if overallocating 10 bytes (20 - strlen("(delete)")) was just sloppy
> code or does other code relies on that (which is unlikely and if true
> then it wouldn't be good).

It looks like just slop, and should probably be fixed at the same time.
There are also quite a number of:

  ret = alloc_ref(strlen(name) + 6);
  sprintf(ret->name, "refs/%s", name);

which are error-prone and owuld be nice to fix. However, I don't think
there is an easy way short of making ref->name a strbuf. And now it
seems we are getting into a lot of code churn for a relatively small
benefit.

-Peff

Re: [PATCH] Optimize common pattern of alloc_ref from string

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> But really my main worry is that now we have _two_ functions which
> allocate refs, so if "struct ref" ever grows a new field that needs
> initializing, it has to go in two places (whereas if alloc_ref_from_str
> calls alloc_ref, it works automatically).

This is a very good point.  We really do not want a micro-optimization in
a way that hurts maintainability.

Krzysztof's patch has the new function with the duplicated allocation
implementation between the base allocator function and the existing
copy_ref() function which also has yet another duplicated allocation
implementation.  When somebody needs to modify one, it is likely to be
noticed that these three go hand-in-hand, hopefully ;-).

By the way, why isn't alloc_ref() doing xcalloc(), I have to wonder...

Re: [PATCH] Optimize common pattern of alloc_ref from string

[Krzysztof Kowalczyk]

On Sun, May 11, 2008 at 11:39 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Jeff King <peff@peff.net> writes:
>
>> But really my main worry is that now we have _two_ functions which
>> allocate refs, so if "struct ref" ever grows a new field that needs
>> initializing, it has to go in two places (whereas if alloc_ref_from_str
>> calls alloc_ref, it works automatically).
>
> This is a very good point.  We really do not want a micro-optimization in
> a way that hurts maintainability.
>
> Krzysztof's patch has the new function with the duplicated allocation
> implementation between the base allocator function and the existing
> copy_ref() function which also has yet another duplicated allocation
> implementation.  When somebody needs to modify one, it is likely to be
> noticed that these three go hand-in-hand, hopefully ;-).
>
> By the way, why isn't alloc_ref() doing xcalloc(), I have to wonder...

I've sent updated patch that incorporates the feedback. Changes wrt.
to this patch:
* simpler version of alloc_ref_from_str() per Jeff's suggestion
* switches alloc_ref() to xcalloc() per Junio's suggestion
* uses alloc_ref_from_str() in one more place
* better (?) commit message

-- kjk

Re: [PATCH] Optimize common pattern of alloc_ref from string

[Junio C Hamano]

Thanks.  I've already queued this instead, as it is not about
"Optimization" but about refactoring.

I am actually very tempted to relabel it as "Fix underallocation in
interpret_target()" and describe the refactoring just as a side-effect,
but the commit is already buried deep in my outgoing queue for "master",
and I do not think it is worth delaying today's pushout for rewording the
commit log message again.

-- >8 --
From: Krzysztof Kowalczyk <kkowalczyk@gmail.com>
Date: Sat, 10 May 2008 16:26:58 -0700
Subject: [PATCH] alloc_ref_from_str(): factor out a common pattern of alloc_ref from string

Also fix an underallocation in walker.c::interpret_target().

Signed-off-by: Krzysztof Kowalczyk <kkowalczyk@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin-fetch.c |    6 ++----
 http-push.c     |    6 ++----
 remote.c        |   23 ++++++++++-------------
 remote.h        |    2 ++
 transport.c     |    6 ++----
 walker.c        |    3 +--
 6 files changed, 19 insertions(+), 27 deletions(-)

diff --git a/builtin-fetch.c b/builtin-fetch.c
index e56617e..f6584ec 100644
--- a/builtin-fetch.c
+++ b/builtin-fetch.c
@@ -508,10 +508,8 @@ static void find_non_local_tags(struct transport *transport,
 		     will_fetch(head, ref->old_sha1))) {
 			path_list_insert(ref_name, &new_refs);
 
-			rm = alloc_ref(strlen(ref_name) + 1);
-			strcpy(rm->name, ref_name);
-			rm->peer_ref = alloc_ref(strlen(ref_name) + 1);
-			strcpy(rm->peer_ref->name, ref_name);
+			rm = alloc_ref_from_str(ref_name);
+			rm->peer_ref = alloc_ref_from_str(ref_name);
 			hashcpy(rm->old_sha1, ref_sha1);
 
 			**tail = rm;
diff --git a/http-push.c b/http-push.c
index 939a764..42727c8 100644
--- a/http-push.c
+++ b/http-push.c
@@ -1761,8 +1761,7 @@ static void one_remote_ref(char *refname)
 	struct ref *ref;
 	struct object *obj;
 
-	ref = alloc_ref(strlen(refname) + 1);
-	strcpy(ref->name, refname);
+	ref = alloc_ref_from_str(refname);
 
 	if (http_fetch_ref(remote->url, ref) != 0) {
 		fprintf(stderr,
@@ -1894,8 +1893,7 @@ static void add_remote_info_ref(struct remote_ls_ctx *ls)
 	char *ref_info;
 	struct ref *ref;
 
-	ref = alloc_ref(strlen(ls->dentry_name) + 1);
-	strcpy(ref->name, ls->dentry_name);
+	ref = alloc_ref_from_str(ls->dentry_name);
 
 	if (http_fetch_ref(remote->url, ref) != 0) {
 		fprintf(stderr,
diff --git a/remote.c b/remote.c
index 6b480cb..91cbb72 100644
--- a/remote.c
+++ b/remote.c
@@ -691,6 +691,13 @@ struct ref *alloc_ref(unsigned namelen)
 	return ret;
 }
 
+struct ref *alloc_ref_from_str(const char* str)
+{
+	struct ref *ret = alloc_ref(strlen(str) + 1);
+	strcpy(ret->name, str);
+	return ret;
+}
+
 static struct ref *copy_ref(const struct ref *ref)
 {
 	struct ref *ret = xmalloc(sizeof(struct ref) + strlen(ref->name) + 1);
@@ -797,7 +804,6 @@ static struct ref *try_explicit_object_name(const char *name)
 {
 	unsigned char sha1[20];
 	struct ref *ref;
-	int len;
 
 	if (!*name) {
 		ref = alloc_ref(20);
@@ -807,21 +813,14 @@ static struct ref *try_explicit_object_name(const char *name)
 	}
 	if (get_sha1(name, sha1))
 		return NULL;
-	len = strlen(name) + 1;
-	ref = alloc_ref(len);
-	memcpy(ref->name, name, len);
+	ref = alloc_ref_from_str(name);
 	hashcpy(ref->new_sha1, sha1);
 	return ref;
 }
 
 static struct ref *make_linked_ref(const char *name, struct ref ***tail)
 {
-	struct ref *ret;
-	size_t len;
-
-	len = strlen(name) + 1;
-	ret = alloc_ref(len);
-	memcpy(ret->name, name, len);
+	struct ref *ret = alloc_ref_from_str(name);
 	tail_link_ref(ret, tail);
 	return ret;
 }
@@ -1125,9 +1124,7 @@ static struct ref *get_local_ref(const char *name)
 		return NULL;
 
 	if (!prefixcmp(name, "refs/")) {
-		ret = alloc_ref(strlen(name) + 1);
-		strcpy(ret->name, name);
-		return ret;
+		return alloc_ref_from_str(name);
 	}
 
 	if (!prefixcmp(name, "heads/") ||
diff --git a/remote.h b/remote.h
index 75d006b..2ee83a3 100644
--- a/remote.h
+++ b/remote.h
@@ -54,6 +54,8 @@ struct refspec {
 
 struct ref *alloc_ref(unsigned namelen);
 
+struct ref *alloc_ref_from_str(const char* str);
+
 struct ref *copy_ref_list(const struct ref *ref);
 
 int check_ref_type(const struct ref *ref, int flags);
diff --git a/transport.c b/transport.c
index b012a28..1bc16f2 100644
--- a/transport.c
+++ b/transport.c
@@ -504,8 +504,7 @@ static struct ref *get_refs_via_curl(struct transport *transport)
 
 	strbuf_release(&buffer);
 
-	ref = alloc_ref(strlen("HEAD") + 1);
-	strcpy(ref->name, "HEAD");
+	ref = alloc_ref_from_str("HEAD");
 	if (!walker->fetch_ref(walker, ref) &&
 	    !resolve_remote_symref(ref, refs)) {
 		ref->next = refs;
@@ -546,9 +545,8 @@ static struct ref *get_refs_from_bundle(struct transport *transport)
 		die ("Could not read bundle '%s'.", transport->url);
 	for (i = 0; i < data->header.references.nr; i++) {
 		struct ref_list_entry *e = data->header.references.list + i;
-		struct ref *ref = alloc_ref(strlen(e->name) + 1);
+		struct ref *ref = alloc_ref_from_str(e->name);
 		hashcpy(ref->old_sha1, e->sha1);
-		strcpy(ref->name, e->name);
 		ref->next = result;
 		result = ref;
 	}
diff --git a/walker.c b/walker.c
index fa96a7c..31de6c1 100644
--- a/walker.c
+++ b/walker.c
@@ -190,8 +190,7 @@ static int interpret_target(struct walker *walker, char *target, unsigned char *
 	if (!get_sha1_hex(target, sha1))
 		return 0;
 	if (!check_ref_format(target)) {
-		struct ref *ref = alloc_ref(strlen(target));
-		strcpy(ref->name, target);
+		struct ref *ref = alloc_ref_from_str(target);
 		if (!walker->fetch_ref(walker, ref)) {
 			hashcpy(sha1, ref->old_sha1);
 			free(ref);
-- 
1.5.5.1.294.g7b425

Re: [PATCH] Optimize common pattern of alloc_ref from string

[Johannes Schindelin]

Hi,

On Sat, 10 May 2008, kkowalczyk@gmail.com wrote:

> diff --git a/builtin-fetch.c b/builtin-fetch.c
> index e56617e..f6584ec 100644
> --- a/builtin-fetch.c
> +++ b/builtin-fetch.c
> @@ -508,10 +508,8 @@ static void find_non_local_tags(struct transport *transport,
>  		     will_fetch(head, ref->old_sha1))) {
>  			path_list_insert(ref_name, &new_refs);
>  
> -			rm = alloc_ref(strlen(ref_name) + 1);
> -			strcpy(rm->name, ref_name);
> -			rm->peer_ref = alloc_ref(strlen(ref_name) + 1);
> -			strcpy(rm->peer_ref->name, ref_name);
> +			rm = alloc_ref_from_str(ref_name);
> +			rm->peer_ref = alloc_ref_from_str(ref_name);

Thanks.  This was on my ever-growing TODO list (actually, fix alloc_ref() 
to take the string length instead of the size to be allocated).

Together with the comments from Peff I am very positive on this patch.

Thanks,
Dscho