git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Linus Torvalds <torvalds@linux-foundation.org>
Date
Mar 18, 2007, 03:06 UTC
Message-ID
<Pine.LNX.4.64.0703171949190.6730@woody.linux-foundation.org>
In-Reply-To
<Pine.LNX.4.64.0703171911120.6730@woody.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:
Show 7 quoted lines
>
>  - 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 *);
Previous: Nicolas PitreNext: Junio C Hamano
Message 50 of 79 in “cleaner/better zlib sources?”
  1. Linus TorvaldsMar 16, 2007
  2. Shawn O. PearceMar 16, 2007
  3. Jeff GarzikMar 16, 2007
  4. Matt MackallMar 16, 2007
  5. Linus TorvaldsMar 16, 2007
  6. Linus TorvaldsMar 16, 2007
  7. Davide LibenziMar 16, 2007
  8. Linus TorvaldsMar 16, 2007
  9. Davide LibenziMar 16, 2007
  10. Linus TorvaldsMar 16, 2007
  11. Davide LibenziMar 16, 2007
  12. Linus TorvaldsMar 16, 2007
  13. Davide LibenziMar 16, 2007
  14. Linus TorvaldsMar 17, 2007
  15. Linus TorvaldsMar 17, 2007
  16. Nicolas PitreMar 17, 2007
  17. Shawn O. PearceMar 17, 2007
  18. Linus TorvaldsMar 17, 2007
  19. Linus TorvaldsMar 17, 2007
  20. 1/2 Make trivial wrapper functions around delta base generation and freeingLinus Torvalds, Mar 17, 2007
  21. 2/2 Implement a simple delta_base cacheLinus Torvalds, Mar 17, 2007
  22. Linus TorvaldsMar 17, 2007
  23. Junio C HamanoMar 17, 2007
  24. Linus TorvaldsMar 17, 2007
  25. Linus TorvaldsMar 17, 2007
  26. Nicolas PitreMar 18, 2007
  27. Junio C HamanoMar 18, 2007
  28. Junio C HamanoMar 17, 2007
  29. Linus TorvaldsMar 17, 2007
  30. Jon SmirlMar 17, 2007
  31. Morten WelinderMar 18, 2007
  32. Linus TorvaldsMar 18, 2007
  33. Nicolas PitreMar 18, 2007
  34. Linus TorvaldsMar 18, 2007
  35. Nicolas PitreMar 18, 2007
  36. Linus TorvaldsMar 18, 2007
  37. Nicolas PitreMar 18, 2007
  38. Linus TorvaldsMar 18, 2007
  39. Julian PhillipsMar 18, 2007
  40. Linus TorvaldsMar 18, 2007
  41. Robin RosenbergMar 18, 2007
  42. Linus TorvaldsMar 18, 2007
  43. Robin RosenbergMar 18, 2007
  44. Shawn O. PearceMar 18, 2007
  45. David BrodskyMar 19, 2007
  46. Robin RosenbergMar 20, 2007
  47. David BrodskyMar 20, 2007
  48. Linus TorvaldsMar 21, 2007
  49. Nicolas PitreMar 21, 2007
  50. 3/2 Avoid unnecessary strlen() callsLinus Torvalds, Mar 18, 2007
  51. Junio C HamanoMar 18, 2007
  52. Linus TorvaldsMar 18, 2007
  53. Linus TorvaldsMar 18, 2007
  54. Shawn O. PearceMar 18, 2007
  55. Linus TorvaldsMar 18, 2007
  56. Johannes SchindelinMar 20, 2007
  57. Shawn O. PearceMar 20, 2007
  58. Shawn O. PearceMar 20, 2007
  59. Linus TorvaldsMar 20, 2007
  60. Shawn O. PearceMar 20, 2007
  61. Linus TorvaldsMar 20, 2007
  62. Junio C HamanoMar 20, 2007
  63. Junio C HamanoMar 20, 2007
  64. Linus TorvaldsMar 20, 2007
  65. Shawn O. PearceMar 20, 2007
  66. Linus TorvaldsMar 20, 2007
  67. Linus TorvaldsMar 18, 2007
  68. Avi KivityMar 18, 2007
  69. Linus TorvaldsMar 17, 2007
  70. Jeff GarzikMar 16, 2007
  71. Matt MackallMar 16, 2007
  72. Linus TorvaldsMar 16, 2007
  73. Nicolas PitreMar 16, 2007
  74. Shawn O. PearceMar 16, 2007
  75. Nicolas PitreMar 16, 2007
  76. Linus TorvaldsMar 16, 2007
  77. Nicolas PitreMar 16, 2007
  78. Davide LibenziMar 16, 2007
  79. Davide LibenziMar 16, 2007

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.