[PATCH] Avoid a useless prefix lookup in strbuf_expand()

Currently the --prett=format prefix is looked up in a
tight loop in strbuf_expand(), if found is passed as parameter
to format_commit_item() that does another search using a
switch statement to select the proper operation according to
the kind of prefix.

Because the switch statement is already able to discard unknown
matches we don't need the prefix lookup before to call format_commit_item()

This patch removes an useless loop in a very fasth path,
used by, as example, by 'git log' with --pretty=format option

Signed-off-by: Marco Costalba <redacted>
---

This patch is somewhat experimental and is not intended to be merged as is.

That's what is missing:

- Matching of multi char prefixes is not 100% reliable, as example to match
  prefix "Cgreen" only the first 'C' and the third char 'e' is
checked, this could
  lead to aliases in case of malformed prefixes, as example something like
  "Cxxexxxx" will match the same.


- With this patch placeholders array defined in format_commit_message() becames
  useless. That code should be refactored to remove the vector and
perhaps add some
  stricter checking rules directly inside format_commit_item()


Anyhow with this patch we pass from


marco@localhost linux-2.6]$ time git log --topo-order --no-color
--parents -z --log-size --boundary
--pretty=format:"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b" HEAD > /dev/null
2.89user 0.07system 0:02.96elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+27154minor)pagefaults 0swaps


With the super optimized prefixcmp() patch (see the other thread)

to the current

[marco@localhost linux-2.6]$ time git log --topo-order --no-color
--parents -z --log-size --boundary
--pretty=format:"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b" HEAD > /dev/null
2.76user 0.08system 0:02.85elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+27153minor)pagefaults 0swaps


 pretty.c |   43 ++++++++++++++++++++++---------------------
 strbuf.c |   16 +++++++---------
 strbuf.h |    2 +-
 3 files changed, 30 insertions(+), 31 deletions(-)

diff --git a/pretty.c b/pretty.c
index 5b1078b..6225042 100644
--- a/pretty.c
+++ b/pretty.c

@@ -432,7 +432,7 @@ static void parse_commit_header(struct

format_commit_context *context)
 	context->commit_header_parsed = 1;
 }

-static void format_commit_item(struct strbuf *sb, const char *placeholder,
+static int format_commit_item(struct strbuf *sb, const char *placeholder,
                                void *context)
 {
 	struct format_commit_context *c = context;

@@ -446,20 +446,20 @@ static void format_commit_item(struct strbuf *sb,
 		switch (placeholder[3]) {
 		case 'd':	/* red */
 			strbuf_addstr(sb, "\033[31m");
-			return;
+			return 4;
 		case 'e':	/* green */
 			strbuf_addstr(sb, "\033[32m");
-			return;
+			return 6;
 		case 'u':	/* blue */
 			strbuf_addstr(sb, "\033[34m");
-			return;
+			return 5;
 		case 's':	/* reset color */
 			strbuf_addstr(sb, "\033[m");
-			return;
+			return 6;
 		}
 	case 'n':		/* newline */
 		strbuf_addch(sb, '\n');
-		return;
+		return 1;
 	}

 	/* these depend on the commit */

@@ -469,34 +469,34 @@ static void format_commit_item(struct strbuf *sb,
 	switch (placeholder[0]) {
 	case 'H':		/* commit hash */
 		strbuf_addstr(sb, sha1_to_hex(commit->object.sha1));
-		return;
+		return 1;
 	case 'h':		/* abbreviated commit hash */
 		if (add_again(sb, &c->abbrev_commit_hash))
-			return;
+			return 1;
 		strbuf_addstr(sb, find_unique_abbrev(commit->object.sha1,
 		                                     DEFAULT_ABBREV));
 		c->abbrev_commit_hash.len = sb->len - c->abbrev_commit_hash.off;
-		return;
+		return 1;
 	case 'T':		/* tree hash */
 		strbuf_addstr(sb, sha1_to_hex(commit->tree->object.sha1));
-		return;
+		return 1;
 	case 't':		/* abbreviated tree hash */
 		if (add_again(sb, &c->abbrev_tree_hash))
-			return;
+			return 1;
 		strbuf_addstr(sb, find_unique_abbrev(commit->tree->object.sha1,
 		                                     DEFAULT_ABBREV));
 		c->abbrev_tree_hash.len = sb->len - c->abbrev_tree_hash.off;
-		return;
+		return 1;
 	case 'P':		/* parent hashes */
 		for (p = commit->parents; p; p = p->next) {
 			if (p != commit->parents)
 				strbuf_addch(sb, ' ');
 			strbuf_addstr(sb, sha1_to_hex(p->item->object.sha1));
 		}
-		return;
+		return 1;
 	case 'p':		/* abbreviated parent hashes */
 		if (add_again(sb, &c->abbrev_parent_hashes))
-			return;
+			return 1;
 		for (p = commit->parents; p; p = p->next) {
 			if (p != commit->parents)
 				strbuf_addch(sb, ' ');

@@ -505,14 +505,14 @@ static void format_commit_item(struct strbuf *sb,
 		}
 		c->abbrev_parent_hashes.len = sb->len -
 		                              c->abbrev_parent_hashes.off;
-		return;
+		return 1;
 	case 'm':		/* left/right/bottom */
 		strbuf_addch(sb, (commit->object.flags & BOUNDARY)
 		                 ? '-'
 		                 : (commit->object.flags & SYMMETRIC_LEFT)
 		                 ? '<'
 		                 : '>');
-		return;
+		return 1;
 	}

 	/* For the rest we have to parse the commit header. */

@@ -522,22 +522,23 @@ static void format_commit_item(struct strbuf *sb,
 	switch (placeholder[0]) {
 	case 's':
 		strbuf_add(sb, msg + c->subject.off, c->subject.len);
-		return;
+		return 1;
 	case 'a':
 		format_person_part(sb, placeholder[1],
 		                   msg + c->author.off, c->author.len);
-		return;
+		return 2;
 	case 'c':
 		format_person_part(sb, placeholder[1],
 		                   msg + c->committer.off, c->committer.len);
-		return;
+		return 2;
 	case 'e':
 		strbuf_add(sb, msg + c->encoding.off, c->encoding.len);
-		return;
+		return 1;
 	case 'b':
 		strbuf_addstr(sb, msg + c->body_off);
-		return;
+		return 1;
 	}
+	return 0; /* unknown prefix */
 }

 void format_commit_message(const struct commit *commit,

diff --git a/strbuf.c b/strbuf.c
index b9b194b..3c2a3a7 100644
--- a/strbuf.c
+++ b/strbuf.c

@@ -141,7 +141,8 @@ void strbuf_expand(struct strbuf *sb, const char
                    const char **placeholders, expand_fn_t fn, void *context)
 {
 	for (;;) {
-		const char *percent, **p;
+		const char *percent;
+		int prefix_len;

 		percent = strchrnul(format, '%');
 		strbuf_add(sb, format, percent - format);

@@ -149,14 +150,11 @@ void strbuf_expand(struct strbuf *sb, const char
 			break;
 		format = percent + 1;

-		for (p = placeholders; *p; p++) {
-			if (!prefixcmp(format, *p))
-				break;
-		}
-		if (*p) {
-			fn(sb, *p, context);
-			format += strlen(*p);
-		} else
+		prefix_len = fn(sb, format, context);
+
+		if (prefix_len)
+			format += prefix_len;
+		else
 			strbuf_addch(sb, '%');
 	}
 }

diff --git a/strbuf.h b/strbuf.h
index 36d61db..e6d09fc 100644
--- a/strbuf.h
+++ b/strbuf.h

@@ -103,7 +103,7 @@ static inline void strbuf_addbuf(struct strbuf *sb,
 }
 extern void strbuf_adddup(struct strbuf *sb, size_t pos, size_t len);

-typedef void (*expand_fn_t) (struct strbuf *sb, const char

*placeholder, void *context);
+typedef int (*expand_fn_t) (struct strbuf *sb, const char
*placeholder, void *context);
 extern void strbuf_expand(struct strbuf *sb, const char *format,
const char **placeholders, expand_fn_t fn, void *context);

 __attribute__((format(printf,2,3)))
-- 
1.5.4.rc2.1.gec59-dirty

Marco Costalba schrieb:

Currently the --prett=format prefix is looked up in a
tight loop in strbuf_expand(), if found is passed as parameter
to format_commit_item() that does another search using a
switch statement to select the proper operation according to
the kind of prefix.

Because the switch statement is already able to discard unknown
matches we don't need the prefix lookup before to call format_commit_item()

This patch removes an useless loop in a very fasth path,
used by, as example, by 'git log' with --pretty=format option

Signed-off-by: Marco Costalba <redacted>
---

This patch is somewhat experimental and is not intended to be merged as is.

That's what is missing:

- Matching of multi char prefixes is not 100% reliable, as example to match
  prefix "Cgreen" only the first 'C' and the third char 'e' is
checked, this could
  lead to aliases in case of malformed prefixes, as example something like
  "Cxxexxxx" will match the same.

Well, you need to undo this optimization if you remove the loop that
makes sure that only valid placeholders are passed to the callback
function -- the result would be that you only move the prefixcmp() from
strbuf_expand() into the callbacks.

A better way to speed up strbuf_expand() may be to require the list of
placeholders to be sorted, their count to be passed on and then to
replace the sequential lookup with a binary search.  --pretty=format
currently recognizes 29 placeholders, which might be a high enough
number for a more complicated search method to pay off.

marco@localhost linux-2.6]$ time git log --topo-order --no-color
--parents -z --log-size --boundary
--pretty=format:"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b" HEAD > /dev/null

In your special case it would be even faster to simply reorder the list
with decreasing number of occurrence.  Of course it's hard to guess how
often a particular placeholder is used in the wild, but moving %n from
next to last to first place should be a safe bet.

René