[PATCH 3/2] Avoid unnecessary strlen() calls

[Linus Torvalds <torvalds@linux-foundation.org>]

This is a micro-optimization that grew out of the mailing list discussion 
about "strlen()" showing up in profiles. 

We used to pass regular C strings around to the low-level tree walking 
routines, and while this worked fine, it meant that we needed to call 
strlen() on strings that the caller always actually knew the size of 
anyway.

So pass the length of the string down wih the string, and avoid 
unnecessary calls to strlen(). Also, when extracting a pathname from a 
tree entry, use "tree_entry_len()" instead of strlen(), since the length 
of the pathname is directly calculable from the decoded tree entry itself 
without having to actually do another strlen().

This shaves off another ~5-10% from some loads that are very tree 
intensive (notably doing commit filtering by a pathspec).

Signed-off-by: Linus Torvalds  <torvalds@linux-foundation.org>"
---

On Sat, 17 Mar 2007, Linus Torvalds wrote:
>
>  - we pass strings around as just C strings, even when we know their 
>    lengths. Prime example: look at tree-diff.c. And when you look at it, 
>    realize that *for*every*single*strlen* in that file except for the very 
>    last one (which is only used once per process for setup) we actually 
>    know the string length from before, but we (well, *I*) decided that it 
>    wasn't worth passing down as a parameter all the time.

So here's the patch.

It definitely cuts down on CPU usage, and I actually left one extra 
"strlen()" around, simply because I didn't want to mess with the exported 
interface of "diff_tree()".

But that other strlen() is also one that is done *once* for the whole 
tree, so from a performance standpoint it doesn't matter (we *could* have 
passed in that length too, but that would have involved more changes that 
simply aren't really useful).

Does it help? Yes it does. It takes another 5-10% off my test-case. 
"strlen()" still exists, but it's basically half of what it used to be 
because we now basically only call it when literally parsing the tree data 
itself (ie now it's ~8% of the total, and no longer the hottest entry.

Is it worth it? If it was just a random micro-optimization I might not 
care, but I guess it's not that ugly to pass an extra "baselen" around all 
the time. And that "tree_entry_len()" helper function is actually quite 
nice. So yeah, I'd suggest applying this one just because it's actually a 
perfectly fine patch and it does speed things up.

So it *is* very much a micro-optimization, but one that doesn't really 
make the code any uglier, so why not..

I still think that if we do these kinds of optimizations and they matter, 
that shows just how *well* we're actually doing here!

Anyway, Junio, it passes all the tests, as well as passing my "looks 
obviously correct" filter, so..

		Linus

---
diff --git a/tree-diff.c b/tree-diff.c
index c827582..f89b9d3 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -5,9 +5,8 @@
 #include "diff.h"
 #include "tree.h"
 
-static char *malloc_base(const char *base, const char *path, int pathlen)
+static char *malloc_base(const char *base, int baselen, const char *path, int pathlen)
 {
-	int baselen = strlen(base);
 	char *newbase = xmalloc(baselen + pathlen + 2);
 	memcpy(newbase, base, baselen);
 	memcpy(newbase + baselen, path, pathlen);
@@ -16,9 +15,9 @@ static char *malloc_base(const char *base, const char *path, int pathlen)
 }
 
 static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,
-		       const char *base);
+		       const char *base, int baselen);
 
-static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
+static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, int baselen, struct diff_options *opt)
 {
 	unsigned mode1, mode2;
 	const char *path1, *path2;
@@ -28,15 +27,15 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 	sha1 = tree_entry_extract(t1, &path1, &mode1);
 	sha2 = tree_entry_extract(t2, &path2, &mode2);
 
-	pathlen1 = strlen(path1);
-	pathlen2 = strlen(path2);
+	pathlen1 = tree_entry_len(path1, sha1);
+	pathlen2 = tree_entry_len(path2, sha2);
 	cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
 	if (cmp < 0) {
-		show_entry(opt, "-", t1, base);
+		show_entry(opt, "-", t1, base, baselen);
 		return -1;
 	}
 	if (cmp > 0) {
-		show_entry(opt, "+", t2, base);
+		show_entry(opt, "+", t2, base, baselen);
 		return 1;
 	}
 	if (!opt->find_copies_harder && !hashcmp(sha1, sha2) && mode1 == mode2)
@@ -47,14 +46,14 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 	 * file, we need to consider it a remove and an add.
 	 */
 	if (S_ISDIR(mode1) != S_ISDIR(mode2)) {
-		show_entry(opt, "-", t1, base);
-		show_entry(opt, "+", t2, base);
+		show_entry(opt, "-", t1, base, baselen);
+		show_entry(opt, "+", t2, base, baselen);
 		return 0;
 	}
 
 	if (opt->recursive && S_ISDIR(mode1)) {
 		int retval;
-		char *newbase = malloc_base(base, path1, pathlen1);
+		char *newbase = malloc_base(base, baselen, path1, pathlen1);
 		if (opt->tree_in_recursive)
 			opt->change(opt, mode1, mode2,
 				    sha1, sha2, base, path1);
@@ -67,20 +66,20 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 	return 0;
 }
 
-static int interesting(struct tree_desc *desc, const char *base, struct diff_options *opt)
+static int interesting(struct tree_desc *desc, const char *base, int baselen, struct diff_options *opt)
 {
 	const char *path;
+	const unsigned char *sha1;
 	unsigned mode;
 	int i;
-	int baselen, pathlen;
+	int pathlen;
 
 	if (!opt->nr_paths)
 		return 1;
 
-	(void)tree_entry_extract(desc, &path, &mode);
+	sha1 = tree_entry_extract(desc, &path, &mode);
 
-	pathlen = strlen(path);
-	baselen = strlen(base);
+	pathlen = tree_entry_len(path, sha1);
 
 	for (i=0; i < opt->nr_paths; i++) {
 		const char *match = opt->paths[i];
@@ -121,18 +120,18 @@ static int interesting(struct tree_desc *desc, const char *base, struct diff_opt
 }
 
 /* A whole sub-tree went away or appeared */
-static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base)
+static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base, int baselen)
 {
 	while (desc->size) {
-		if (interesting(desc, base, opt))
-			show_entry(opt, prefix, desc, base);
+		if (interesting(desc, base, baselen, opt))
+			show_entry(opt, prefix, desc, base, baselen);
 		update_tree_entry(desc);
 	}
 }
 
 /* A file entry went away or appeared */
 static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,
-		       const char *base)
+		       const char *base, int baselen)
 {
 	unsigned mode;
 	const char *path;
@@ -140,7 +139,8 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree
 
 	if (opt->recursive && S_ISDIR(mode)) {
 		enum object_type type;
-		char *newbase = malloc_base(base, path, strlen(path));
+		int pathlen = tree_entry_len(path, sha1);
+		char *newbase = malloc_base(base, baselen, path, pathlen);
 		struct tree_desc inner;
 		void *tree;
 
@@ -149,7 +149,7 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree
 			die("corrupt tree sha %s", sha1_to_hex(sha1));
 
 		inner.buf = tree;
-		show_tree(opt, prefix, &inner, newbase);
+		show_tree(opt, prefix, &inner, newbase, baselen + 1 + pathlen);
 
 		free(tree);
 		free(newbase);
@@ -160,26 +160,28 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree
 
 int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
 {
+	int baselen = strlen(base);
+
 	while (t1->size | t2->size) {
-		if (opt->nr_paths && t1->size && !interesting(t1, base, opt)) {
+		if (opt->nr_paths && t1->size && !interesting(t1, base, baselen, opt)) {
 			update_tree_entry(t1);
 			continue;
 		}
-		if (opt->nr_paths && t2->size && !interesting(t2, base, opt)) {
+		if (opt->nr_paths && t2->size && !interesting(t2, base, baselen, opt)) {
 			update_tree_entry(t2);
 			continue;
 		}
 		if (!t1->size) {
-			show_entry(opt, "+", t2, base);
+			show_entry(opt, "+", t2, base, baselen);
 			update_tree_entry(t2);
 			continue;
 		}
 		if (!t2->size) {
-			show_entry(opt, "-", t1, base);
+			show_entry(opt, "-", t1, base, baselen);
 			update_tree_entry(t1);
 			continue;
 		}
-		switch (compare_tree_entry(t1, t2, base, opt)) {
+		switch (compare_tree_entry(t1, t2, base, baselen, opt)) {
 		case -1:
 			update_tree_entry(t1);
 			continue;
diff --git a/tree-walk.c b/tree-walk.c
index 70f8999..a4a4e2a 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -32,7 +32,7 @@ static void entry_clear(struct name_entry *a)
 static void entry_extract(struct tree_desc *t, struct name_entry *a)
 {
 	a->sha1 = tree_entry_extract(t, &a->path, &a->mode);
-	a->pathlen = strlen(a->path);
+	a->pathlen = tree_entry_len(a->path, a->sha1);
 }
 
 void update_tree_entry(struct tree_desc *desc)
@@ -169,7 +169,7 @@ static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char
 
 		sha1 = tree_entry_extract(t, &entry, mode);
 		update_tree_entry(t);
-		entrylen = strlen(entry);
+		entrylen = tree_entry_len(entry, sha1);
 		if (entrylen > namelen)
 			continue;
 		cmp = memcmp(name, entry, entrylen);
diff --git a/tree-walk.h b/tree-walk.h
index e57befa..a0d7afd 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -13,6 +13,11 @@ struct name_entry {
 	int pathlen;
 };
 
+static inline int tree_entry_len(const char *name, const unsigned char *sha1)
+{
+	return (char *)sha1 - (char *)name - 1;
+}
+
 void update_tree_entry(struct tree_desc *);
 const unsigned char *tree_entry_extract(struct tree_desc *, const char **, unsigned int *);