{"thread":{"id":"11989","subject":"[PATCH TAKE 2] Avoid a useless prefix lookup in strbuf_expand()","startedAt":"2008-02-09T14:40:19Z","lastAt":"2008-02-10T10:52:58Z","messageCount":6,"participants":["Marco Costalba","Junio C Hamano","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"68090","messageId":"1202568019-20200-1-git-send-email-mcostalba@gmail.com","threadId":"11989","inReplyTo":null,"subject":"[PATCH TAKE 2] Avoid a useless prefix lookup in strbuf_expand()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2008-02-09T14:40:19Z","receivedAt":"2008-02-09T14:40:19Z","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 prefix is found is then\nused as argument for format_commit_item() that does another\nsearch by a switch statement to select the proper operation.\n\nBecause the switch statement is already able to discard\nunknown matches we don't need the prefix lookup before\nto call format_commit_item()\n\nThis patch removes an useless loop in a very fast path,\nused by, as example, by 'git log' with --pretty=format option\n\nSigned-off-by: Marco Costalba <mcostalba@gmail.com>\n---\n\nNew patch with Junio suggestions included.\n\nApply above 'next' branch\n\n\n pretty.c |  167 ++++++++++++++++++++++++++-----------------------------------\n strbuf.c |   19 +++----\n strbuf.h |    4 +-\n 3 files changed, 81 insertions(+), 109 deletions(-)\n\ndiff --git a/pretty.c b/pretty.c\nindex b987ff2..aed32f2 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -282,59 +282,57 @@ 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+static size_t format_person_part(struct strbuf *sb, char part,\n                                const char *msg, int len)\n {\n+\tconst int placeholder_len = 2; /* currently all placeholders have same length */\n \tint start, end, tz = 0;\n-\tunsigned long date;\n+\tunsigned long date = 0;\n \tchar *ep;\n \n-\t/* parse name */\n+\t/* advance 'end' to point to email start delimiter */\n \tfor (end = 0; end < len && msg[end] != '<'; end++)\n \t\t; /* do nothing */\n-\t/*\n-\t * If it does not even have a '<' and '>', that is\n-\t * quite a bogus commit author and we discard it;\n-\t * this is in line with add_user_info() that is used\n-\t * in the normal codepath.  When end points at the '<'\n-\t * that we found, it should have matching '>' later,\n-\t * which means start (beginning of email address) must\n-\t * be strictly below len.\n+\n+\t/* When end points at the '<' that we found, it should have\n+\t * matching '>' later, which means 'end' must be strictly\n+\t * below len - 1.\n \t */\n-\tstart = end + 1;\n-\tif (start >= len - 1)\n-\t\treturn;\n-\twhile (end > 0 && isspace(msg[end - 1]))\n-\t\tend--;\n+\tif (end >= len - 2)\n+\t\tgoto skip;\n+\n \tif (part == 'n') {\t/* name */\n+\t\twhile (end > 0 && isspace(msg[end - 1]))\n+\t\t\tend--;\n \t\tstrbuf_add(sb, msg, end);\n-\t\treturn;\n+\t\treturn placeholder_len;\n \t}\n+\tstart = ++end; /* save email start position */\n \n-\t/* parse email */\n-\tfor (end = start; end < len && msg[end] != '>'; end++)\n+\t/* advance 'end' to point to email end delimiter */\n+\tfor ( ; end < len && msg[end] != '>'; end++)\n \t\t; /* do nothing */\n \n \tif (end >= len)\n-\t\treturn;\n+\t\tgoto skip;\n \n \tif (part == 'e') {\t/* email */\n \t\tstrbuf_add(sb, msg + start, end - start);\n-\t\treturn;\n+\t\treturn placeholder_len;\n \t}\n \n-\t/* parse date */\n+\t/* advance 'start' to point to date start delimiter */\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\tgoto skip;\n \tdate = strtoul(msg + start, &ep, 10);\n \tif (msg + start == ep)\n-\t\treturn;\n+\t\tgoto skip;\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 placeholder_len;\n \t}\n \n \t/* parse tz */\n@@ -349,17 +347,27 @@ 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 placeholder_len;\n \tcase 'D':\t/* date, RFC2822 style */\n \t\tstrbuf_addstr(sb, show_date(date, tz, DATE_RFC2822));\n-\t\treturn;\n+\t\treturn placeholder_len;\n \tcase 'r':\t/* date, relative */\n \t\tstrbuf_addstr(sb, show_date(date, tz, DATE_RELATIVE));\n-\t\treturn;\n+\t\treturn placeholder_len;\n \tcase 'i':\t/* date, ISO 8601 */\n \t\tstrbuf_addstr(sb, show_date(date, tz, DATE_ISO8601));\n-\t\treturn;\n+\t\treturn placeholder_len;\n \t}\n+\n+skip:\n+\t/* bougus commit, 'sb' cannot be updated, but\n+\t * still we need to compute a valid return value.\n+\t */\n+\tif (   part == 'n' || part == 'e' || part == 't' || part == 'd'\n+\t    || part == 'D' || part == 'r' || part == 'i')\n+\t\treturn placeholder_len;\n+\n+\treturn 0; /* unknown placeholder */\n }\n \n struct chunk {\n@@ -440,7 +448,7 @@ 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+static size_t format_commit_item(struct strbuf *sb, const char *placeholder,\n                                void *context)\n {\n \tstruct format_commit_context *c = context;\n@@ -451,23 +459,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@@ -477,34 +485,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@@ -513,14 +521,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@@ -528,66 +536,33 @@ 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/* 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\treturn 1;\n+\tcase 'a':\t/* author ... */\n+\t\treturn format_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+\tcase 'c':\t/* committer ... */\n+\t\treturn format_person_part(sb, placeholder[1],\n \t\t                   msg + c->committer.off, c->committer.len);\n-\t\treturn;\n-\tcase 'e':\n+\tcase 'e':\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/* body */\n \t\tstrbuf_addstr(sb, msg + c->body_off);\n-\t\treturn;\n+\t\treturn 1;\n \t}\n+\treturn 0;\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 5efcfc8..32ab8e5 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -146,11 +146,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@@ -158,14 +159,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-- \n1.5.4.1220.g1a838\n"},{"id":"68152","messageId":"7vr6fl5yhz.fsf@gitster.siamese.dyndns.org","threadId":"11989","inReplyTo":"1202568019-20200-1-git-send-email-mcostalba@gmail.com","subject":"Re: [PATCH TAKE 2] Avoid a useless prefix lookup in strbuf_expand()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-10T02:36:08Z","receivedAt":"2008-02-10T02:36:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Marco Costalba <mcostalba@gmail.com> writes:\n\n> Currently the --prett=format prefix is looked up in a\n\ns/prett/&y/;\n\n> New patch with Junio suggestions included.\n\nHmph, this is a blast from the past.\n\nI do recall pointing out that a rather common \"format:%an <%ae>\"\nends up parsing the same line twice, and mentioned we may want\nto memoise the first call's result in the format_commit_context\nstructure, but what else did I suggest???\n\nAnyway, I'll take a look later.  Thanks.\n"},{"id":"68155","messageId":"alpine.LSU.1.00.0802100252030.11591@racer.site","threadId":"11989","inReplyTo":"1202568019-20200-1-git-send-email-mcostalba@gmail.com","subject":"Re: [PATCH TAKE 2] Avoid a useless prefix lookup in strbuf_expand()","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-02-10T02:52:21Z","receivedAt":"2008-02-10T02:52:21Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 9 Feb 2008, Marco Costalba wrote:\n\n> +\t/* bougus commit, 'sb' cannot be updated, but\n\ns/bougus/bogus/\n\nCiao,\nDscho\n"},{"id":"68177","messageId":"e5bfff550802092259u4139312cufc4756e9d81f4154@mail.gmail.com","threadId":"11989","inReplyTo":"7vr6fl5yhz.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH TAKE 2] Avoid a useless prefix lookup in strbuf_expand()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2008-02-10T06:59:45Z","receivedAt":"2008-02-10T06:59:45Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Feb 10, 2008 3:36 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Marco Costalba <mcostalba@gmail.com> writes:\n>\n> > Currently the --prett=format prefix is looked up in a\n>\n> s/prett/&y/;\n>\n> > New patch with Junio suggestions included.\n>\n> Hmph, this is a blast from the past.\n>\n> I do recall pointing out that a rather common \"format:%an <%ae>\"\n> ends up parsing the same line twice, and mentioned we may want\n> to memoise the first call's result in the format_commit_context\n> structure, but what else did I suggest???\n>\n\nPlease read thread: \"[PATCH RESEND] Avoid a useless prefix lookup in\nstrbuf_expand()\"\n\nyou will find your suggestions and following answers.\n\n> Anyway, I'll take a look later.  Thanks.\n>\n\nThanks\nMarco\n"},{"id":"68178","messageId":"e5bfff550802092300i38408493r4d5758c1fc16b0d5@mail.gmail.com","threadId":"11989","inReplyTo":"alpine.LSU.1.00.0802100252030.11591@racer.site","subject":"Re: [PATCH TAKE 2] Avoid a useless prefix lookup in strbuf_expand()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2008-02-10T07:00:23Z","receivedAt":"2008-02-10T07:00:23Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Feb 10, 2008 3:52 AM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> Hi,\n>\n> On Sat, 9 Feb 2008, Marco Costalba wrote:\n>\n> > +     /* bougus commit, 'sb' cannot be updated, but\n>\n> s/bougus/bogus/\n>\n\nYes :-) you are right.\n\nThanks\n"},{"id":"68192","messageId":"7v4pchgk1h.fsf@gitster.siamese.dyndns.org","threadId":"11989","inReplyTo":"e5bfff550802092259u4139312cufc4756e9d81f4154@mail.gmail.com","subject":"Re: [PATCH TAKE 2] Avoid a useless prefix lookup in strbuf_expand()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-10T10:52:58Z","receivedAt":"2008-02-10T10:52:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" <mcostalba@gmail.com> writes:\n\n> On Feb 10, 2008 3:36 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> ...\n>> I do recall pointing out that a rather common \"format:%an <%ae>\"\n>> ends up parsing the same line twice, and mentioned we may want\n>> to memoise the first call's result in the format_commit_context\n>> structure, but what else did I suggest???\n>>\n>\n> Please read thread: \"[PATCH RESEND] Avoid a useless prefix lookup in\n> strbuf_expand()\"\n>\n> you will find your suggestions and following answers.\n\nYeah, I mentioned the comment needing to be adjusted (which you\ndid in this round), asked a minor question about the code (you\nanswered in the thread), besides pointing out that a rather\ncommon \"format:%an <%ae>\" being inefficient (which you brushed\naside, claiming that is a special case).\n\nI've touched-up a few typoes and style glitches and will park\nthis on 'pu' for now.\n"}]}