{"thread":{"id":"11429","subject":"[PATCH] Avoid a useless prefix lookup in strbuf_expand()","startedAt":"2007-12-30T13:46:58Z","lastAt":"2008-01-03T10:06:21Z","messageCount":5,"participants":["Marco Costalba","René Scharfe","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"64220","messageId":"e5bfff550712300546o167c460bl4628d87f8a4e14db@mail.gmail.com","threadId":"11429","inReplyTo":null,"subject":"[PATCH] Avoid a useless prefix lookup in strbuf_expand()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-30T13:46:58Z","receivedAt":"2007-12-30T13:46:58Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"Currently the --prett=format prefix is looked up in a\ntight loop in strbuf_expand(), if found is passed as parameter\nto format_commit_item() that does another search using a\nswitch statement to select the proper operation according to\nthe kind of prefix.\n\nBecause the switch statement is already able to discard unknown\nmatches we don't need the prefix lookup before to call format_commit_item()\n\nThis patch removes an useless loop in a very fasth path,\nused by, as example, by 'git log' with --pretty=format option\n\nSigned-off-by: Marco Costalba <mcostalba@gmail.com>\n---\n\nThis patch is somewhat experimental and is not intended to be merged as is.\n\nThat's what is missing:\n\n- Matching of multi char prefixes is not 100% reliable, as example to match\n  prefix \"Cgreen\" only the first 'C' and the third char 'e' is\nchecked, this could\n  lead to aliases in case of malformed prefixes, as example something like\n  \"Cxxexxxx\" will match the same.\n\n\n- With this patch placeholders array defined in format_commit_message() becames\n  useless. That code should be refactored to remove the vector and\nperhaps add some\n  stricter checking rules directly inside format_commit_item()\n\n\nAnyhow with this patch we pass from\n\n\nmarco@localhost linux-2.6]$ time git log --topo-order --no-color\n--parents -z --log-size --boundary\n--pretty=format:\"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b\" HEAD > /dev/null\n2.89user 0.07system 0:02.96elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+27154minor)pagefaults 0swaps\n\n\nWith the super optimized prefixcmp() patch (see the other thread)\n\nto the current\n\n[marco@localhost linux-2.6]$ time git log --topo-order --no-color\n--parents -z --log-size --boundary\n--pretty=format:\"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b\" HEAD > /dev/null\n2.76user 0.08system 0:02.85elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+27153minor)pagefaults 0swaps\n\n\n pretty.c |   43 ++++++++++++++++++++++---------------------\n strbuf.c |   16 +++++++---------\n strbuf.h |    2 +-\n 3 files changed, 30 insertions(+), 31 deletions(-)\n\ndiff --git a/pretty.c b/pretty.c\nindex 5b1078b..6225042 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -432,7 +432,7 @@ static void parse_commit_header(struct\nformat_commit_context *context)\n \tcontext->commit_header_parsed = 1;\n }\n\n-static void format_commit_item(struct strbuf *sb, const char *placeholder,\n+static int format_commit_item(struct strbuf *sb, const char *placeholder,\n                                void *context)\n {\n \tstruct format_commit_context *c = context;\n@@ -446,20 +446,20 @@ static void format_commit_item(struct strbuf *sb,\n \t\tswitch (placeholder[3]) {\n \t\tcase 'd':\t/* red */\n \t\t\tstrbuf_addstr(sb, \"\\033[31m\");\n-\t\t\treturn;\n+\t\t\treturn 4;\n \t\tcase 'e':\t/* green */\n \t\t\tstrbuf_addstr(sb, \"\\033[32m\");\n-\t\t\treturn;\n+\t\t\treturn 6;\n \t\tcase 'u':\t/* blue */\n \t\t\tstrbuf_addstr(sb, \"\\033[34m\");\n-\t\t\treturn;\n+\t\t\treturn 5;\n \t\tcase 's':\t/* reset color */\n \t\t\tstrbuf_addstr(sb, \"\\033[m\");\n-\t\t\treturn;\n+\t\t\treturn 6;\n \t\t}\n \tcase 'n':\t\t/* newline */\n \t\tstrbuf_addch(sb, '\\n');\n-\t\treturn;\n+\t\treturn 1;\n \t}\n\n \t/* these depend on the commit */\n@@ -469,34 +469,34 @@ static void format_commit_item(struct strbuf *sb,\n \tswitch (placeholder[0]) {\n \tcase 'H':\t\t/* commit hash */\n \t\tstrbuf_addstr(sb, sha1_to_hex(commit->object.sha1));\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'h':\t\t/* abbreviated commit hash */\n \t\tif (add_again(sb, &c->abbrev_commit_hash))\n-\t\t\treturn;\n+\t\t\treturn 1;\n \t\tstrbuf_addstr(sb, find_unique_abbrev(commit->object.sha1,\n \t\t                                     DEFAULT_ABBREV));\n \t\tc->abbrev_commit_hash.len = sb->len - c->abbrev_commit_hash.off;\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'T':\t\t/* tree hash */\n \t\tstrbuf_addstr(sb, sha1_to_hex(commit->tree->object.sha1));\n-\t\treturn;\n+\t\treturn 1;\n \tcase 't':\t\t/* abbreviated tree hash */\n \t\tif (add_again(sb, &c->abbrev_tree_hash))\n-\t\t\treturn;\n+\t\t\treturn 1;\n \t\tstrbuf_addstr(sb, find_unique_abbrev(commit->tree->object.sha1,\n \t\t                                     DEFAULT_ABBREV));\n \t\tc->abbrev_tree_hash.len = sb->len - c->abbrev_tree_hash.off;\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'P':\t\t/* parent hashes */\n \t\tfor (p = commit->parents; p; p = p->next) {\n \t\t\tif (p != commit->parents)\n \t\t\t\tstrbuf_addch(sb, ' ');\n \t\t\tstrbuf_addstr(sb, sha1_to_hex(p->item->object.sha1));\n \t\t}\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'p':\t\t/* abbreviated parent hashes */\n \t\tif (add_again(sb, &c->abbrev_parent_hashes))\n-\t\t\treturn;\n+\t\t\treturn 1;\n \t\tfor (p = commit->parents; p; p = p->next) {\n \t\t\tif (p != commit->parents)\n \t\t\t\tstrbuf_addch(sb, ' ');\n@@ -505,14 +505,14 @@ static void format_commit_item(struct strbuf *sb,\n \t\t}\n \t\tc->abbrev_parent_hashes.len = sb->len -\n \t\t                              c->abbrev_parent_hashes.off;\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'm':\t\t/* left/right/bottom */\n \t\tstrbuf_addch(sb, (commit->object.flags & BOUNDARY)\n \t\t                 ? '-'\n \t\t                 : (commit->object.flags & SYMMETRIC_LEFT)\n \t\t                 ? '<'\n \t\t                 : '>');\n-\t\treturn;\n+\t\treturn 1;\n \t}\n\n \t/* For the rest we have to parse the commit header. */\n@@ -522,22 +522,23 @@ static void format_commit_item(struct strbuf *sb,\n \tswitch (placeholder[0]) {\n \tcase 's':\n \t\tstrbuf_add(sb, msg + c->subject.off, c->subject.len);\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'a':\n \t\tformat_person_part(sb, placeholder[1],\n \t\t                   msg + c->author.off, c->author.len);\n-\t\treturn;\n+\t\treturn 2;\n \tcase 'c':\n \t\tformat_person_part(sb, placeholder[1],\n \t\t                   msg + c->committer.off, c->committer.len);\n-\t\treturn;\n+\t\treturn 2;\n \tcase 'e':\n \t\tstrbuf_add(sb, msg + c->encoding.off, c->encoding.len);\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'b':\n \t\tstrbuf_addstr(sb, msg + c->body_off);\n-\t\treturn;\n+\t\treturn 1;\n \t}\n+\treturn 0; /* unknown prefix */\n }\n\n void format_commit_message(const struct commit *commit,\ndiff --git a/strbuf.c b/strbuf.c\nindex b9b194b..3c2a3a7 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -141,7 +141,8 @@ void strbuf_expand(struct strbuf *sb, const char\n                    const char **placeholders, expand_fn_t fn, void *context)\n {\n \tfor (;;) {\n-\t\tconst char *percent, **p;\n+\t\tconst char *percent;\n+\t\tint prefix_len;\n\n \t\tpercent = strchrnul(format, '%');\n \t\tstrbuf_add(sb, format, percent - format);\n@@ -149,14 +150,11 @@ void strbuf_expand(struct strbuf *sb, const char\n \t\t\tbreak;\n \t\tformat = percent + 1;\n\n-\t\tfor (p = placeholders; *p; p++) {\n-\t\t\tif (!prefixcmp(format, *p))\n-\t\t\t\tbreak;\n-\t\t}\n-\t\tif (*p) {\n-\t\t\tfn(sb, *p, context);\n-\t\t\tformat += strlen(*p);\n-\t\t} else\n+\t\tprefix_len = fn(sb, format, context);\n+\n+\t\tif (prefix_len)\n+\t\t\tformat += prefix_len;\n+\t\telse\n \t\t\tstrbuf_addch(sb, '%');\n \t}\n }\ndiff --git a/strbuf.h b/strbuf.h\nindex 36d61db..e6d09fc 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -103,7 +103,7 @@ static inline void strbuf_addbuf(struct strbuf *sb,\n }\n extern void strbuf_adddup(struct strbuf *sb, size_t pos, size_t len);\n\n-typedef void (*expand_fn_t) (struct strbuf *sb, const char\n*placeholder, void *context);\n+typedef int (*expand_fn_t) (struct strbuf *sb, const char\n*placeholder, void *context);\n extern void strbuf_expand(struct strbuf *sb, const char *format,\nconst char **placeholders, expand_fn_t fn, void *context);\n\n __attribute__((format(printf,2,3)))\n-- \n1.5.4.rc2.1.gec59-dirty\n"},{"id":"64342","messageId":"477BD3B4.2070708@lsrfire.ath.cx","threadId":"11429","inReplyTo":"e5bfff550712300546o167c460bl4628d87f8a4e14db@mail.gmail.com","subject":"Re: [PATCH] Avoid a useless prefix lookup in strbuf_expand()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-01-02T18:11:00Z","receivedAt":"2008-01-02T18:11:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Marco Costalba schrieb:\n> Currently the --prett=format prefix is looked up in a\n> tight loop in strbuf_expand(), if found is passed as parameter\n> to format_commit_item() that does another search using a\n> switch statement to select the proper operation according to\n> the kind of prefix.\n> \n> Because the switch statement is already able to discard unknown\n> matches we don't need the prefix lookup before to call format_commit_item()\n> \n> This patch removes an useless loop in a very fasth path,\n> used by, as example, by 'git log' with --pretty=format option\n> \n> Signed-off-by: Marco Costalba <mcostalba@gmail.com>\n> ---\n> \n> This patch is somewhat experimental and is not intended to be merged as is.\n> \n> That's what is missing:\n> \n> - Matching of multi char prefixes is not 100% reliable, as example to match\n>   prefix \"Cgreen\" only the first 'C' and the third char 'e' is\n> checked, this could\n>   lead to aliases in case of malformed prefixes, as example something like\n>   \"Cxxexxxx\" will match the same.\n\nWell, you need to undo this optimization if you remove the loop that\nmakes sure that only valid placeholders are passed to the callback\nfunction -- the result would be that you only move the prefixcmp() from\nstrbuf_expand() into the callbacks.\n\nA better way to speed up strbuf_expand() may be to require the list of\nplaceholders to be sorted, their count to be passed on and then to\nreplace the sequential lookup with a binary search.  --pretty=format\ncurrently recognizes 29 placeholders, which might be a high enough\nnumber for a more complicated search method to pay off.\n\n> marco@localhost linux-2.6]$ time git log --topo-order --no-color\n> --parents -z --log-size --boundary\n> --pretty=format:\"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b\" HEAD > /dev/null\n\nIn your special case it would be even faster to simply reorder the list\nwith decreasing number of occurrence.  Of course it's hard to guess how\noften a particular placeholder is used in the wild, but moving %n from\nnext to last to first place should be a safe bet.\n\nRené\n"},{"id":"64363","messageId":"477C301D.7060509@lsrfire.ath.cx","threadId":"11429","inReplyTo":"e5bfff550801021027i6d6a399cob96ae3c840661884@mail.gmail.com","subject":"Re: [PATCH] Avoid a useless prefix lookup in strbuf_expand()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-01-03T00:45:17Z","receivedAt":"2008-01-03T00:45:17Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Marco Costalba schrieb:\n> If we go on complex stuff then we can bite the bullet and use a text\n> matcher state machine, but again, I still think that the best way is\n> to avoid the 99% unusless loop and use only a (slightly) beefed up\n> switch case instead.\n> \n> I would think you agree with me that searching if a string is found in\n> a string vector then pass the _same_ string to another function that\n> (practically) redoes *the same* check using a switch statement is not\n> the best optimization one can think about.\n\nThe loop makes implementing the callback function a bit easier, since\nyou don't need to cover all cases; the input is already checked by\nstrbuf_expand().\n\nAnyway, here's your patch again with a few small changes: the\nplaceholders array is gone as you suggested, the cases for %Cx, %ax and\n%cx are check for unknown placeholders and the callback function returns\nthe number of bytes it consumed as size_t.\n\nAll in all: less code, slightly more complex callback functions (needs\nto return the length of the consumed placeholder or 0 if the input\ndoesn't match a placeholder) and increased speed.  I have to admit that\nI start to like it. :-)\n\nI tried to cover all cases of valid and invalid input; did I miss any?\n\nRené\n\n\n pretty.c |  143 ++++++++++++++++++++++++++------------------------------------\n strbuf.c |   19 ++++-----\n strbuf.h |    4 +-\n 3 files changed, 70 insertions(+), 96 deletions(-)\n\ndiff --git a/pretty.c b/pretty.c\nindex 5b1078b..c0e9c8a 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -282,8 +282,8 @@ static char *logmsg_reencode(const struct commit *commit,\n \treturn out;\n }\n \n-static void format_person_part(struct strbuf *sb, char part,\n-                               const char *msg, int len)\n+static size_t format_person_part(struct strbuf *sb, char part,\n+                                 const char *msg, int len)\n {\n \tint start, end, tz = 0;\n \tunsigned long date;\n@@ -297,36 +297,36 @@ static void format_person_part(struct strbuf *sb, char part,\n \t\tend--;\n \tif (part == 'n') {\t/* name */\n \t\tstrbuf_add(sb, msg, end);\n-\t\treturn;\n+\t\treturn 1;\n \t}\n \n \tif (start >= len)\n-\t\treturn;\n+\t\treturn 1;\n \n \t/* parse email */\n \tfor (end = start + 1; end < len && msg[end] != '>'; end++)\n \t\t; /* do nothing */\n \n \tif (end >= len)\n-\t\treturn;\n+\t\treturn 1;\n \n \tif (part == 'e') {\t/* email */\n \t\tstrbuf_add(sb, msg + start, end - start);\n-\t\treturn;\n+\t\treturn 1;\n \t}\n \n \t/* parse date */\n \tfor (start = end + 1; start < len && isspace(msg[start]); start++)\n \t\t; /* do nothing */\n \tif (start >= len)\n-\t\treturn;\n+\t\treturn 1;\n \tdate = strtoul(msg + start, &ep, 10);\n \tif (msg + start == ep)\n-\t\treturn;\n+\t\treturn 1;\n \n \tif (part == 't') {\t/* date, UNIX timestamp */\n \t\tstrbuf_add(sb, msg + start, ep - (msg + start));\n-\t\treturn;\n+\t\treturn 1;\n \t}\n \n \t/* parse tz */\n@@ -341,17 +341,19 @@ static void format_person_part(struct strbuf *sb, char part,\n \tswitch (part) {\n \tcase 'd':\t/* date */\n \t\tstrbuf_addstr(sb, show_date(date, tz, DATE_NORMAL));\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'D':\t/* date, RFC2822 style */\n \t\tstrbuf_addstr(sb, show_date(date, tz, DATE_RFC2822));\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'r':\t/* date, relative */\n \t\tstrbuf_addstr(sb, show_date(date, tz, DATE_RELATIVE));\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'i':\t/* date, ISO 8601 */\n \t\tstrbuf_addstr(sb, show_date(date, tz, DATE_ISO8601));\n-\t\treturn;\n+\t\treturn 1;\n \t}\n+\n+\treturn 0;\t/* unknown person part */\n }\n \n struct chunk {\n@@ -432,8 +434,8 @@ static void parse_commit_header(struct format_commit_context *context)\n \tcontext->commit_header_parsed = 1;\n }\n \n-static void format_commit_item(struct strbuf *sb, const char *placeholder,\n-                               void *context)\n+static size_t format_commit_item(struct strbuf *sb, const char *placeholder,\n+                                 void *context)\n {\n \tstruct format_commit_context *c = context;\n \tconst struct commit *commit = c->commit;\n@@ -443,23 +445,23 @@ static void format_commit_item(struct strbuf *sb, const char *placeholder,\n \t/* these are independent of the commit */\n \tswitch (placeholder[0]) {\n \tcase 'C':\n-\t\tswitch (placeholder[3]) {\n-\t\tcase 'd':\t/* red */\n+\t\tif (!prefixcmp(placeholder + 1, \"red\")) {\n \t\t\tstrbuf_addstr(sb, \"\\033[31m\");\n-\t\t\treturn;\n-\t\tcase 'e':\t/* green */\n+\t\t\treturn 4;\n+\t\t} else if (!prefixcmp(placeholder + 1, \"green\")) {\n \t\t\tstrbuf_addstr(sb, \"\\033[32m\");\n-\t\t\treturn;\n-\t\tcase 'u':\t/* blue */\n+\t\t\treturn 6;\n+\t\t} else if (!prefixcmp(placeholder + 1, \"blue\")) {\n \t\t\tstrbuf_addstr(sb, \"\\033[34m\");\n-\t\t\treturn;\n-\t\tcase 's':\t/* reset color */\n+\t\t\treturn 5;\n+\t\t} else if (!prefixcmp(placeholder + 1, \"reset\")) {\n \t\t\tstrbuf_addstr(sb, \"\\033[m\");\n-\t\t\treturn;\n-\t\t}\n+\t\t\treturn 6;\n+\t\t} else\n+\t\t\treturn 0;\n \tcase 'n':\t\t/* newline */\n \t\tstrbuf_addch(sb, '\\n');\n-\t\treturn;\n+\t\treturn 1;\n \t}\n \n \t/* these depend on the commit */\n@@ -469,34 +471,34 @@ static void format_commit_item(struct strbuf *sb, const char *placeholder,\n \tswitch (placeholder[0]) {\n \tcase 'H':\t\t/* commit hash */\n \t\tstrbuf_addstr(sb, sha1_to_hex(commit->object.sha1));\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'h':\t\t/* abbreviated commit hash */\n \t\tif (add_again(sb, &c->abbrev_commit_hash))\n-\t\t\treturn;\n+\t\t\treturn 1;\n \t\tstrbuf_addstr(sb, find_unique_abbrev(commit->object.sha1,\n \t\t                                     DEFAULT_ABBREV));\n \t\tc->abbrev_commit_hash.len = sb->len - c->abbrev_commit_hash.off;\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'T':\t\t/* tree hash */\n \t\tstrbuf_addstr(sb, sha1_to_hex(commit->tree->object.sha1));\n-\t\treturn;\n+\t\treturn 1;\n \tcase 't':\t\t/* abbreviated tree hash */\n \t\tif (add_again(sb, &c->abbrev_tree_hash))\n-\t\t\treturn;\n+\t\t\treturn 1;\n \t\tstrbuf_addstr(sb, find_unique_abbrev(commit->tree->object.sha1,\n \t\t                                     DEFAULT_ABBREV));\n \t\tc->abbrev_tree_hash.len = sb->len - c->abbrev_tree_hash.off;\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'P':\t\t/* parent hashes */\n \t\tfor (p = commit->parents; p; p = p->next) {\n \t\t\tif (p != commit->parents)\n \t\t\t\tstrbuf_addch(sb, ' ');\n \t\t\tstrbuf_addstr(sb, sha1_to_hex(p->item->object.sha1));\n \t\t}\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'p':\t\t/* abbreviated parent hashes */\n \t\tif (add_again(sb, &c->abbrev_parent_hashes))\n-\t\t\treturn;\n+\t\t\treturn 1;\n \t\tfor (p = commit->parents; p; p = p->next) {\n \t\t\tif (p != commit->parents)\n \t\t\t\tstrbuf_addch(sb, ' ');\n@@ -505,14 +507,14 @@ static void format_commit_item(struct strbuf *sb, const char *placeholder,\n \t\t}\n \t\tc->abbrev_parent_hashes.len = sb->len -\n \t\t                              c->abbrev_parent_hashes.off;\n-\t\treturn;\n+\t\treturn 1;\n \tcase 'm':\t\t/* left/right/bottom */\n \t\tstrbuf_addch(sb, (commit->object.flags & BOUNDARY)\n \t\t                 ? '-'\n \t\t                 : (commit->object.flags & SYMMETRIC_LEFT)\n \t\t                 ? '<'\n \t\t                 : '>');\n-\t\treturn;\n+\t\treturn 1;\n \t}\n \n \t/* For the rest we have to parse the commit header. */\n@@ -520,66 +522,41 @@ static void format_commit_item(struct strbuf *sb, const char *placeholder,\n \t\tparse_commit_header(c);\n \n \tswitch (placeholder[0]) {\n-\tcase 's':\n+\tcase 's':\t\t/* subject */\n \t\tstrbuf_add(sb, msg + c->subject.off, c->subject.len);\n-\t\treturn;\n-\tcase 'a':\n-\t\tformat_person_part(sb, placeholder[1],\n-\t\t                   msg + c->author.off, c->author.len);\n-\t\treturn;\n-\tcase 'c':\n-\t\tformat_person_part(sb, placeholder[1],\n-\t\t                   msg + c->committer.off, c->committer.len);\n-\t\treturn;\n-\tcase 'e':\n+\t\treturn 1;\n+\tcase 'a':\t\t/* author ... */\n+\t\tif (format_person_part(sb, placeholder[1],\n+\t\t                       msg + c->author.off,\n+\t\t                       c->author.len))\n+\t\t\treturn 2;\n+\t\telse\n+\t\t\treturn 0;\n+\tcase 'c':\t\t/* committer ... */\n+\t\tif (format_person_part(sb, placeholder[1],\n+\t\t                       msg + c->committer.off,\n+\t\t                       c->committer.len))\n+\t\t\treturn 2;\n+\t\telse\n+\t\t\treturn 0;\n+\tcase 'e':\t\t/* encoding */\n \t\tstrbuf_add(sb, msg + c->encoding.off, c->encoding.len);\n-\t\treturn;\n-\tcase 'b':\n+\t\treturn 1;\n+\tcase 'b':\t\t/* body */\n \t\tstrbuf_addstr(sb, msg + c->body_off);\n-\t\treturn;\n+\t\treturn 1;\n \t}\n+\treturn 0;\t\t/* unknown placeholder */\n }\n \n void format_commit_message(const struct commit *commit,\n                            const void *format, struct strbuf *sb)\n {\n-\tconst char *placeholders[] = {\n-\t\t\"H\",\t\t/* commit hash */\n-\t\t\"h\",\t\t/* abbreviated commit hash */\n-\t\t\"T\",\t\t/* tree hash */\n-\t\t\"t\",\t\t/* abbreviated tree hash */\n-\t\t\"P\",\t\t/* parent hashes */\n-\t\t\"p\",\t\t/* abbreviated parent hashes */\n-\t\t\"an\",\t\t/* author name */\n-\t\t\"ae\",\t\t/* author email */\n-\t\t\"ad\",\t\t/* author date */\n-\t\t\"aD\",\t\t/* author date, RFC2822 style */\n-\t\t\"ar\",\t\t/* author date, relative */\n-\t\t\"at\",\t\t/* author date, UNIX timestamp */\n-\t\t\"ai\",\t\t/* author date, ISO 8601 */\n-\t\t\"cn\",\t\t/* committer name */\n-\t\t\"ce\",\t\t/* committer email */\n-\t\t\"cd\",\t\t/* committer date */\n-\t\t\"cD\",\t\t/* committer date, RFC2822 style */\n-\t\t\"cr\",\t\t/* committer date, relative */\n-\t\t\"ct\",\t\t/* committer date, UNIX timestamp */\n-\t\t\"ci\",\t\t/* committer date, ISO 8601 */\n-\t\t\"e\",\t\t/* encoding */\n-\t\t\"s\",\t\t/* subject */\n-\t\t\"b\",\t\t/* body */\n-\t\t\"Cred\",\t\t/* red */\n-\t\t\"Cgreen\",\t/* green */\n-\t\t\"Cblue\",\t/* blue */\n-\t\t\"Creset\",\t/* reset color */\n-\t\t\"n\",\t\t/* newline */\n-\t\t\"m\",\t\t/* left/right/bottom */\n-\t\tNULL\n-\t};\n \tstruct format_commit_context context;\n \n \tmemset(&context, 0, sizeof(context));\n \tcontext.commit = commit;\n-\tstrbuf_expand(sb, format, placeholders, format_commit_item, &context);\n+\tstrbuf_expand(sb, format, format_commit_item, &context);\n }\n \n static void pp_header(enum cmit_fmt fmt,\ndiff --git a/strbuf.c b/strbuf.c\nindex b9b194b..7bb087c 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -137,11 +137,12 @@ void strbuf_addf(struct strbuf *sb, const char *fmt, ...)\n \tstrbuf_setlen(sb, sb->len + len);\n }\n \n-void strbuf_expand(struct strbuf *sb, const char *format,\n-                   const char **placeholders, expand_fn_t fn, void *context)\n+void strbuf_expand(struct strbuf *sb, const char *format, expand_fn_t fn,\n+                   void *context)\n {\n \tfor (;;) {\n-\t\tconst char *percent, **p;\n+\t\tconst char *percent;\n+\t\tsize_t consumed;\n \n \t\tpercent = strchrnul(format, '%');\n \t\tstrbuf_add(sb, format, percent - format);\n@@ -149,14 +150,10 @@ void strbuf_expand(struct strbuf *sb, const char *format,\n \t\t\tbreak;\n \t\tformat = percent + 1;\n \n-\t\tfor (p = placeholders; *p; p++) {\n-\t\t\tif (!prefixcmp(format, *p))\n-\t\t\t\tbreak;\n-\t\t}\n-\t\tif (*p) {\n-\t\t\tfn(sb, *p, context);\n-\t\t\tformat += strlen(*p);\n-\t\t} else\n+\t\tconsumed = fn(sb, format, context);\n+\t\tif (consumed)\n+\t\t\tformat += consumed;\n+\t\telse\n \t\t\tstrbuf_addch(sb, '%');\n \t}\n }\ndiff --git a/strbuf.h b/strbuf.h\nindex 36d61db..faec229 100644\n--- a/strbuf.h\n+++ b/strbuf.h\n@@ -103,8 +103,8 @@ static inline void strbuf_addbuf(struct strbuf *sb, struct strbuf *sb2) {\n }\n extern void strbuf_adddup(struct strbuf *sb, size_t pos, size_t len);\n \n-typedef void (*expand_fn_t) (struct strbuf *sb, const char *placeholder, void *context);\n-extern void strbuf_expand(struct strbuf *sb, const char *format, const char **placeholders, expand_fn_t fn, void *context);\n+typedef size_t (*expand_fn_t) (struct strbuf *sb, const char *placeholder, void *context);\n+extern void strbuf_expand(struct strbuf *sb, const char *format, expand_fn_t fn, void *context);\n \n __attribute__((format(printf,2,3)))\n extern void strbuf_addf(struct strbuf *sb, const char *fmt, ...);\n"},{"id":"64377","messageId":"7vr6gztgwn.fsf@gitster.siamese.dyndns.org","threadId":"11429","inReplyTo":"477C301D.7060509@lsrfire.ath.cx","subject":"Re: [PATCH] Avoid a useless prefix lookup in strbuf_expand()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-03T09:08:56Z","receivedAt":"2008-01-03T09:08:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n\n> The loop makes implementing the callback function a bit easier, since\n> you don't need to cover all cases; the input is already checked by\n> strbuf_expand().\n>\n> Anyway, here's your patch again with a few small changes: the\n> placeholders array is gone as you suggested, the cases for %Cx, %ax and\n> %cx are check for unknown placeholders and the callback function returns\n> the number of bytes it consumed as size_t.\n>\n> All in all: less code, slightly more complex callback functions (needs\n> to return the length of the consumed placeholder or 0 if the input\n> doesn't match a placeholder) and increased speed.  I have to admit that\n> I start to like it. :-)\n\nI'll let Marco bench it and hopefully Ack with an updated\n(final) commit log message.\n\nI think Dscho and Marco's earlier prefixcmp() optimization to\navoid strlen() can stay, but with \"inline\" removed.  That should\nbe equivalent to the version before the optimization, both from\nthe point of view of the code footprint and callchain length,\nbut still avoid strlen() cost.\n\nDue to lack of better place the patch below moves it to strbuf.c\nwhich probably is the closest collection of \"stringy\" stuff.\n\n$ size git ;# with the attached patch\n   text    data     bss     dec     hex filename\n 731144   13456  263464 1008064   f61c0 git\n$ size ../git.build/git ;# before Dscho's patch\n   text    data     bss     dec     hex filename\n 731272   13456  263464 1008192   f6240 ../git.build/git\n$ size ~/bin/git ;# with Dscho's patch\n   text    data     bss     dec     hex filename\n 740736   13456  263464 1017656   f8738 /home/junio/bin/git\n\nYou earlier said 2,620,938 vs 2,640,450 and I think you meant\nwhat \"ls -l\" reports.  I suspect it is not a very good measure,\nbut the numbers here are:\n\n$ ls -l git ;# with the attached patch\n-rwxrwxr-x 83 junio src 3345237 2008-01-03 00:53 git\n$ ls -l ../git.build/git ;# before Dscho's patch\n-rwxrwxr-x 83 junio src 3364803 2008-01-03 01:01 ../git.build/git\n$ ls -l ~/bin/git ;# with Dscho's patch\n-rwxr-xr-x 83 junio src 3389299 2008-01-02 15:18 /home/junio/bin/git\n\n-- >8 --\nUninline prefixcmp()\n\nNow the routine is an open-coded loop that avoids an extra\nstrlen() in the previous implementation, it got a bit too big to\nbe inlined.  Uninlining it makes code footprint smaller but the\nresult still retains the avoidance of strlen() cost.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n git-compat-util.h |   11 ++---------\n strbuf.c          |    9 +++++++++\n 2 files changed, 11 insertions(+), 9 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 7059cbd..b6ef544 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -122,6 +122,8 @@ extern void set_die_routine(void (*routine)(const char *err, va_list params) NOR\n extern void set_error_routine(void (*routine)(const char *err, va_list params));\n extern void set_warn_routine(void (*routine)(const char *warn, va_list params));\n \n+extern int prefixcmp(const char *str, const char *prefix);\n+\n #ifdef NO_MMAP\n \n #ifndef PROT_READ\n@@ -396,15 +398,6 @@ static inline int sane_case(int x, int high)\n \treturn x;\n }\n \n-static inline int prefixcmp(const char *str, const char *prefix)\n-{\n-\tfor (; ; str++, prefix++)\n-\t\tif (!*prefix)\n-\t\t\treturn 0;\n-\t\telse if (*str != *prefix)\n-\t\t\treturn (unsigned char)*prefix - (unsigned char)*str;\n-}\n-\n static inline int strtoul_ui(char const *s, int base, unsigned int *result)\n {\n \tunsigned long ul;\ndiff --git a/strbuf.c b/strbuf.c\nindex b9b194b..5efcfc8 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -1,5 +1,14 @@\n #include \"cache.h\"\n \n+int prefixcmp(const char *str, const char *prefix)\n+{\n+\tfor (; ; str++, prefix++)\n+\t\tif (!*prefix)\n+\t\t\treturn 0;\n+\t\telse if (*str != *prefix)\n+\t\t\treturn (unsigned char)*prefix - (unsigned char)*str;\n+}\n+\n /*\n  * Used as the default ->buf value, so that people can always assume\n  * buf is non NULL and ->buf is NUL terminated even for a freshly\n"},{"id":"64382","messageId":"e5bfff550801030206h1230f203oda58d168c9882b1c@mail.gmail.com","threadId":"11429","inReplyTo":"7vr6gztgwn.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Avoid a useless prefix lookup in strbuf_expand()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2008-01-03T10:06:21Z","receivedAt":"2008-01-03T10:06:21Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Jan 3, 2008 10:08 AM, Junio C Hamano <gitster@pobox.com> wrote:\n>\n>\n> I'll let Marco bench it and hopefully Ack with an updated\n> (final) commit log message.\n>\n\nI will bench today and post the results.\n\nMarco\n"}]}