{"thread":{"id":"11422","subject":"[PATCH] Speedup prefixcmp() common case","startedAt":"2007-12-29T18:01:08Z","lastAt":"2008-01-03T00:45:14Z","messageCount":20,"participants":["Marco Costalba","Johannes Schindelin","Junio C Hamano","Andy Parkins","Pierre Habouzit","René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"64181","messageId":"e5bfff550712291001q5f246ceah6700b98308fb96f1@mail.gmail.com","threadId":"11422","inReplyTo":null,"subject":"[PATCH] Speedup prefixcmp() common case","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-29T18:01:08Z","receivedAt":"2007-12-29T18:01:08Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"In case the prefix string is a single char avoid a\ncostly call to strlen() + strncmp()\n\nWith this patch git log with --pretty=format option\nis 10% faster\n\nSigned-off-by: Marco Costalba \n---\n\nSome profiling of git-log shows that strbuf_expand() is\ncalled for each commit, and every time checks the\nplaceholders vector against the current one.\n\nThis check is done calling prefixcmp() in a tight loop.\nSpeeding up prefixcmp() speeds up the whole git-log thing.\n\nNOTE I: I have tried to perform the single char check\ndirectly in the loop, so to avoid to modify prefixcmp()\nbut the results, although better then the vanilla case,\nare not so good. This means that there are other fast\npaths that benefit from this optimization of prefixcmp().\n\nNOTE II: currently for _each_ commit is done the whole\ncheck of the --pretty=format against the placeholders vector.\nThis is clearly suboptimal because the custom format\n_never changes_ for the whole git-log run, so some\ncaching of the parsed format would be surely effective.\n\nAnyhow, as I said before, this change seems to positively\nimpact other paths apart from the loop in strbuf_expand()\nso it seems worth to have anyway.\n\n\n git-compat-util.h | 4 ++++\n 1 files changed, 4 insertions(+), 0 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 79eb10e..e26b684 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -398,6 +398,10 @@ static inline int sane_case\n\n static inline int prefixcmp(const char *str, const char *prefix)\n {\n+\t// shortcut common case of a single char prefix\n+\tif (prefix && *(prefix + 1) == '\\0' && str)\n+\t\treturn *str - *prefix;\n+\n \treturn strncmp(str, prefix, strlen(prefix));\n }\n\n-- \n1.5.4.rc2-dirty\n"},{"id":"64185","messageId":"Pine.LNX.4.64.0712292019450.14355@wbgn129.biozentrum.uni-wuerzburg.de","threadId":"11422","inReplyTo":"e5bfff550712291001q5f246ceah6700b98308fb96f1@mail.gmail.com","subject":"[PATCH] Optimize prefixcmp()","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-12-29T19:22:14Z","receivedAt":"2007-12-29T19:22:14Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nCertain codepaths (notably \"git log --pretty=format...\") use\nprefixcmp() extensively, with very short prefixes. In those cases,\ncalling strlen() is a wasteful operation, so avoid it.\n\nInitial patch by Marco Costalba.\n\nSigned-off-by: Johannes Schindelin \n---\n\n\tOn Sat, 29 Dec 2007, Marco Costalba wrote:\n\n\t> In case the prefix string is a single char avoid a costly call \n\t> to strlen() + strncmp()\n\n\tCould you test this patch, please?\n\n\tNot only does it avoid the strlen() call also for longer prefixes; \n\tit also avoids a C++ comment.\n\n git-compat-util.h | 6 +++++-\n 1 files changed, 5 insertions(+), 1 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 79eb10e..7059cbd 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -398,7 +398,11 @@ static inline int sane_case(int x, int high)\n \n static inline int prefixcmp(const char *str, const char *prefix)\n {\n-\treturn strncmp(str, prefix, strlen(prefix));\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-- \n1.5.2.rc0.4321.gd618\n"},{"id":"64187","messageId":"7v63yhb8kf.fsf@gitster.siamese.dyndns.org","threadId":"11422","inReplyTo":"e5bfff550712291001q5f246ceah6700b98308fb96f1@mail.gmail.com","subject":"Re: [PATCH] Speedup prefixcmp() common case","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-12-29T19:32:48Z","receivedAt":"2007-12-29T19:32:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" writes:\n\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 79eb10e..e26b684 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -398,6 +398,10 @@ static inline int sane_case\n>\n> static inline int prefixcmp(const char *str, const char *prefix)\n> {\n> +\t// shortcut common case of a single char prefix\n> +\tif (prefix && *(prefix + 1) == '\\0' && str)\n> +\t\treturn *str - *prefix;\n> +\n\nWhy isn't it like this?\n\n\tif (!prefix[1])\n\t\treturn *str - *prefix;\n\n> \treturn strncmp(str, prefix, strlen(prefix));\n> }\n>\n> -- \n> 1.5.4.rc2-dirty\n"},{"id":"64189","messageId":"e5bfff550712291214p7554ea52o875667906ce1a22d@mail.gmail.com","threadId":"11422","inReplyTo":"7v63yhb8kf.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Speedup prefixcmp() common case","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-29T20:14:55Z","receivedAt":"2007-12-29T20:14:55Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 29, 2007 8:32 PM, Junio C Hamano wrote:\n>\n> Why isn't it like this?\n>\n> if (!prefix[1])\n>\n\nwell, what about if prefix == NULL ?\n\nActually I didn't checked if strncmp() checks for NULL pointers before\nto proceed, if this is the case I managed to keep the same semantic.\n\nYou could say \"Why, lazy you, didn't you checked if strncmp() checks\nfor NULL pointers? \"...but I hope you are foregiving ;-)\n\nThanks\nMarco\n"},{"id":"64190","messageId":"e5bfff550712291239y5648b923y8d332d9c40a8c97b@mail.gmail.com","threadId":"11422","inReplyTo":"Pine.LNX.4.64.0712292019450.14355@wbgn129.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-29T20:39:47Z","receivedAt":"2007-12-29T20:39:47Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 29, 2007 8:22 PM, Johannes Schindelin wrote:\n>\n> Not only does it avoid the strlen() call also for longer prefixes;\n> it also avoids a C++ comment.\n>\n\nAvoiding a C++ comment is good ;-) sorry, it slipped to me.\n\nWhat your patch does not seem to avoid is a segfault if prefix or str\nare NULL pointers.\n\n\nMarco\n"},{"id":"64191","messageId":"e5bfff550712291243x6f8d7b2k15055ff55379142e@mail.gmail.com","threadId":"11422","inReplyTo":"e5bfff550712291001q5f246ceah6700b98308fb96f1@mail.gmail.com","subject":"Re: [PATCH] Speedup prefixcmp() common case","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-29T20:43:14Z","receivedAt":"2007-12-29T20:43:14Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"In case the prefix string is a single char avoid a\ncostly call to strlen() + strncmp()\n\nWith this patch git log with --pretty=format option\nis 10% faster\n\nWith suggestions by Junio C Hamano\n\nSigned-off-by: Marco Costalba \n---\n\n\n git-compat-util.h | 4 ++++\n 1 files changed, 4 insertions(+), 0 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 79eb10e..e26b684 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -398,6 +398,10 @@ static inline int sane_case\n\n static inline int prefixcmp(const char *str, const char *prefix)\n {\n+ /* shortcut common case of a single char prefix */\n+ if (prefix && !prefix[1] && str)\n+ return *str - *prefix;\n+\n return strncmp(str, prefix, strlen(prefix));\n }\n\n--\n1.5.4.rc2-dirty\n"},{"id":"64192","messageId":"200712292154.44169.andyparkins@gmail.com","threadId":"11422","inReplyTo":"Pine.LNX.4.64.0712292019450.14355@wbgn129.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Andy Parkins","fromEmail":"andyparkins@gmail.com","sentAt":"2007-12-29T21:54:43Z","receivedAt":"2007-12-29T21:54:43Z","isPatch":true,"sender":{"key":"andyparkins@gmail.com","avatar":null},"body":"On Saturday 2007, December 29, Johannes Schindelin wrote:\n\n> \tNot only does it avoid the strlen() call also for longer prefixes;\n> \tit also avoids a C++ comment.\n\nI'm sure it doesn't matter; but they're allowed in C99. So it's not a C++ \ncomment any more :-)\n\n\nAndy\n\n-- \nDr Andy Parkins, M Eng (hons), MIET\nandyparkins@gmail.com\n"},{"id":"64193","messageId":"Pine.LNX.4.64.0712292307210.14355@wbgn129.biozentrum.uni-wuerzburg.de","threadId":"11422","inReplyTo":"e5bfff550712291239y5648b923y8d332d9c40a8c97b@mail.gmail.com","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-12-29T22:15:18Z","receivedAt":"2007-12-29T22:15:18Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 29 Dec 2007, Marco Costalba wrote:\n\n> What your patch does not seem to avoid is a segfault if prefix or str \n> are NULL pointers.\n\nI am quite certain that it is not allowed to pass NULL pointers to strcmp, \nand even if it was, I maintain that it is bad style.\n\nFWIW the test suite seems to agree with me, as it passes with my patch.\n\nHowever, since you already seem to have a profiling setup ready, I would \nbe interested in some numbers, i.e. if this patch is faster for you or \nslower, or shows no effect at all.\n\nCiao,\nDscho\n"},{"id":"64195","messageId":"e5bfff550712291444t7b6b5887g24b477552c76a6d7@mail.gmail.com","threadId":"11422","inReplyTo":"Pine.LNX.4.64.0712292307210.14355@wbgn129.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-29T22:44:08Z","receivedAt":"2007-12-29T22:44:08Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 29, 2007 11:15 PM, Johannes Schindelin\n wrote:\n>\n> However, since you already seem to have a profiling setup ready, I would\n> be interested in some numbers, i.e. if this patch is faster for you or\n> slower, or shows no effect at all.\n>\n\nOk. I will do some tests with your patch and I'll let you know.\n\nMarco\n"},{"id":"64197","messageId":"7v1w95avx6.fsf@gitster.siamese.dyndns.org","threadId":"11422","inReplyTo":"e5bfff550712291214p7554ea52o875667906ce1a22d@mail.gmail.com","subject":"Re: [PATCH] Speedup prefixcmp() common case","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-12-30T00:05:57Z","receivedAt":"2007-12-30T00:05:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" writes:\n\n> On Dec 29, 2007 8:32 PM, Junio C Hamano wrote:\n>>\n>> Why isn't it like this?\n>>\n>> if (!prefix[1])\n>>\n>\n> well, what about if prefix == NULL ?\n\nWhat about it? Do not trim what's relevant when your quote,\nplease.\n\nYour slow path does this:\n\n> \treturn strncmp(str, prefix, strlen(prefix));\n> }\n\nSo it will barf when prefix == NULL anyway due to strlen(). I\nthink passing NULL as prefix to prefixcmp() is a caller-error.\n\nI think my version is also buggy. Passing \"\" as prefix to\nprefixcmp() is nonsense but is supported, and checking prefix[1]\nwithout looking at prefix[0] reads past the end of the string.\n\nSo, in summary, I think the following is what we would want.\n\n static inline int prefixcmp(const char *str, const char *prefix)\n {\n+\t// shortcut common case of a single char prefix\n+\tif (prefix[0] && !prefix[1])\n+\t\treturn *str - *prefix;\n+\n \treturn strncmp(str, prefix, strlen(prefix));\n }\n"},{"id":"64200","messageId":"7vir2h9fkh.fsf@gitster.siamese.dyndns.org","threadId":"11422","inReplyTo":"Pine.LNX.4.64.0712292019450.14355@wbgn129.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-12-30T00:44:30Z","receivedAt":"2007-12-30T00:44:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> Certain codepaths (notably \"git log --pretty=format...\") use\n> prefixcmp() extensively, with very short prefixes. In those cases,\n> calling strlen() is a wasteful operation, so avoid it.\n>\n> Initial patch by Marco Costalba.\n>\n> Signed-off-by: Johannes Schindelin \n> ---\n>\n> \tOn Sat, 29 Dec 2007, Marco Costalba wrote:\n>\n> \t> In case the prefix string is a single char avoid a costly call \n> \t> to strlen() + strncmp()\n>\n> \tCould you test this patch, please?\n>\n> \tNot only does it avoid the strlen() call also for longer prefixes; \n> \tit also avoids a C++ comment.\n>\n> git-compat-util.h | 6 +++++-\n> 1 files changed, 5 insertions(+), 1 deletions(-)\n>\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 79eb10e..7059cbd 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -398,7 +398,11 @@ static inline int sane_case(int x, int high)\n> \n> static inline int prefixcmp(const char *str, const char *prefix)\n> {\n> -\treturn strncmp(str, prefix, strlen(prefix));\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\nLosing the unnecessary check for !str || !prefix is a good\nchange.\n\nWhile I think, for the readability's sake, Marco's original\nwithout the unnecessary check would be the way to go, a profile\nfrom your totally inlined version would also be interesting, as\nit may or may not beat the underlying strncmp(), which could be\nhighly optimized.\n"},{"id":"64218","messageId":"e5bfff550712300502p543680b9jbeb9469a5a970f0@mail.gmail.com","threadId":"11422","inReplyTo":"Pine.LNX.4.64.0712292307210.14355@wbgn129.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-30T13:02:28Z","receivedAt":"2007-12-30T13:02:28Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 29, 2007 11:15 PM, Johannes Schindelin\n wrote:\n>\n> However, since you already seem to have a profiling setup ready, I would\n> be interested in some numbers, i.e. if this patch is faster for you or\n> slower, or shows no effect at all.\n>\n\nYes Johannes, your patch is faster then mine ;-)\n\n\nThese are the results tested on Linux tree:\n\nVanilla\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\n3.61user 0.09system 0:03.70elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+27155minor)pagefaults 0swaps\n\n\nMarco's path\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\n3.21user 0.08system 0:03.30elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+27154minor)pagefaults 0swaps\n\n\nJohannes's patch\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.92user 0.08system 0:03.01elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+27155minor)pagefaults 0swaps\n\n\n\nBut that's not the end of the story....\n\nAfter profiling I have found a better yet patch :-)\n\n-------------------- CUT ABOVE --------------------\n\nSubject: [PATCH] Certain codepaths (notably \"git log --pretty=format...\") use\n\nprefixcmp() extensively, with very short prefixes. In those cases,\ncalling strlen() is a wasteful operation, so avoid it.\n\nInitial patch by Johannes Schindelin.\n\nSigned-off-by: Marco Costalba \n---\n git-compat-util.h | 11 ++++++++++-\n 1 files changed, 10 insertions(+), 1 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 79eb10e..843a8f5 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -398,7 +398,16 @@ static inline int sane_case(int x, int high)\n\n static inline int prefixcmp(const char *str, const char *prefix)\n {\n-\treturn strncmp(str, prefix, strlen(prefix));\n+\tdo {\n+\t\tif (*str != *prefix)\n+\t\t\treturn *(unsigned const char *)prefix - *(unsigned const char *)str;\n+\n+\t\tif (!*(++prefix))\n+\t\t\treturn 0;\n+\n+\t\tstr++;\n+\n+\t} while (1);\n }\n\n static inline int strtoul_ui(char const *s, int base, unsigned int *result)\n-- \n1.5.4.rc2-dirty\n\nBTW the results with this profiled patch are the followings:\n\nMarco's patch TAKE 2 (profiled one)\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.89user 0.07system 0:02.96elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+27154minor)pagefaults 0swaps\n\n\nNot a big improvement, but an improvement in any case because the\ncheck for (*prefix==0) and for (*str != *prefix) are swapped regarding\nyour patch, this means that in the common case of a failing match (as\nhappens where you are looking for a specific prefix in a string\nvector) with this patch you avoid the (*prefix==0) comparison because\nprefixcmp() exsits just after the (*str != *prefix).\n\n\nOf course we need that the *prefix is not \"\", but we have already\nruled out prefix == NULL, so It does not seem a biggie...\n\nThanks...it was very fun!\nMarco\n"},{"id":"64222","messageId":"20071230135557.GA25917@artemis.madism.org","threadId":"11422","inReplyTo":"e5bfff550712300502p543680b9jbeb9469a5a970f0@mail.gmail.com","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-12-30T13:55:57Z","receivedAt":"2007-12-30T13:55:57Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Sun, Dec 30, 2007 at 01:02:28PM +0000, Marco Costalba wrote:\n> Subject: [PATCH] Certain codepaths (notably \"git log --pretty=format...\") use\n> \n> prefixcmp() extensively, with very short prefixes. In those cases,\n> calling strlen() is a wasteful operation, so avoid it.\n> \n> Initial patch by Johannes Schindelin.\n> \n> Signed-off-by: Marco Costalba \n> ---\n> git-compat-util.h | 11 ++++++++++-\n> 1 files changed, 10 insertions(+), 1 deletions(-)\n> \n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 79eb10e..843a8f5 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -398,7 +398,16 @@ static inline int sane_case(int x, int high)\n> \n> static inline int prefixcmp(const char *str, const char *prefix)\n> {\n> -\treturn strncmp(str, prefix, strlen(prefix));\n> +\tdo {\n> +\t\tif (*str != *prefix)\n> +\t\t\treturn *(unsigned const char *)prefix - *(unsigned const char *)str;\n> +\n> +\t\tif (!*(++prefix))\n> +\t\t\treturn 0;\n> +\n> +\t\tstr++;\n> +\n> +\t} while (1);\n\n This code doesn't work if prefix is \"\". You want something like:\n\n for (; *prefix; prefix++, str++) {\n if (*str != *prefix)\n return *(unsigned const char *)prefix - *(unsigned const char *)str;\n }\n return 0;\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"64223","messageId":"20071230135820.GB25917@artemis.madism.org","threadId":"11422","inReplyTo":"20071230135557.GA25917@artemis.madism.org","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2007-12-30T13:58:20Z","receivedAt":"2007-12-30T13:58:20Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Sun, Dec 30, 2007 at 01:55:57PM +0000, Pierre Habouzit wrote:\n> On Sun, Dec 30, 2007 at 01:02:28PM +0000, Marco Costalba wrote:\n> > Subject: [PATCH] Certain codepaths (notably \"git log --pretty=format...\") use\n> > \n> > prefixcmp() extensively, with very short prefixes. In those cases,\n> > calling strlen() is a wasteful operation, so avoid it.\n> > \n> > Initial patch by Johannes Schindelin.\n> > \n> > Signed-off-by: Marco Costalba \n> > ---\n> > git-compat-util.h | 11 ++++++++++-\n> > 1 files changed, 10 insertions(+), 1 deletions(-)\n> > \n> > diff --git a/git-compat-util.h b/git-compat-util.h\n> > index 79eb10e..843a8f5 100644\n> > --- a/git-compat-util.h\n> > +++ b/git-compat-util.h\n> > @@ -398,7 +398,16 @@ static inline int sane_case(int x, int high)\n> > \n> > static inline int prefixcmp(const char *str, const char *prefix)\n> > {\n> > -\treturn strncmp(str, prefix, strlen(prefix));\n> > +\tdo {\n> > +\t\tif (*str != *prefix)\n> > +\t\t\treturn *(unsigned const char *)prefix - *(unsigned const char *)str;\n> > +\n> > +\t\tif (!*(++prefix))\n> > +\t\t\treturn 0;\n> > +\n> > +\t\tstr++;\n> > +\n> > +\t} while (1);\n> \n> This code doesn't work if prefix is \"\". You want something like:\n> \n> for (; *prefix; prefix++, str++) {\n> if (*str != *prefix)\n> return *(unsigned const char *)prefix - *(unsigned const char *)str;\n> }\n> return 0;\n\n Which happens to be basically the same than what Dscho wrote, though I\nsuppose the compiler can compile that more efficiently than his code.\n\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"64224","messageId":"e5bfff550712300650j2ea70032jaca893b734592184@mail.gmail.com","threadId":"11422","inReplyTo":"20071230135820.GB25917@artemis.madism.org","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-30T14:50:07Z","receivedAt":"2007-12-30T14:50:07Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 30, 2007 2:58 PM, Pierre Habouzit wrote:\n> >\n> > This code doesn't work if prefix is \"\". You want something like:\n> >\n> > for (; *prefix; prefix++, str++) {\n> > if (*str != *prefix)\n> > return *(unsigned const char *)prefix - *(unsigned const char *)str;\n> > }\n> > return 0;\n>\n> Which happens to be basically the same than what Dscho wrote, though I\n> suppose the compiler can compile that more efficiently than his code.\n>\n\nYes, your version covers the *prefix == \"\" case too. If this case is\nimportant for us we could use something as\n\nstatic inline int prefixcmp(const char *str, const char *prefix)\n{\n\tdo {\n\t\tif (*str != *prefix)\n\t\t\treturn (!*prefix ? 0 : *(unsigned const char *)prefix - *(unsigned\nconst char *)str);\n\n\t\tif (!*(++prefix))\n\t\t\treturn 0;\n\n\t\tstr++;\n\n\t} while (1);\n}\n\n\nBut your code is *surely* nicer then this one. But, for unknown\nreasons, this code happens to be faster, probably as you say the\ncompiler optimizes away the second check in the return statement so\nthat this version is slightly faster then the 'for' loop one, but\nadmitelly we are going to much in the academic now.\n\nIf *prefix == \"\" case is to be considered I vote for your/Johannes\nversion because it's \"better code\" (tm).\n\n\nMarco\n"},{"id":"64226","messageId":"e5bfff550712300717r4512954rbf2516491fc13adc@mail.gmail.com","threadId":"11422","inReplyTo":"e5bfff550712300650j2ea70032jaca893b734592184@mail.gmail.com","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-30T15:17:52Z","receivedAt":"2007-12-30T15:17:52Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 30, 2007 3:50 PM, Marco Costalba wrote:\n>\n> If *prefix == \"\" case is to be considered I vote for your/Johannes\n> version because it's \"better code\" (tm).\n>\nOk this is fast and correct\n\nstatic inline int prefixcmp(const char *str, const char *prefix)\n{\n\twhile (*str == *prefix && *prefix)\n \t\tstr++, prefix++;\n\n\treturn (*prefix ? *(unsigned const char *)prefix - *(unsigned const\nchar *)str : 0);\n}\n\n\nThis is the last one, I promise ;-)\n\nMarco\n"},{"id":"64229","messageId":"Pine.LNX.4.64.0712301653360.14355@wbgn129.biozentrum.uni-wuerzburg.de","threadId":"11422","inReplyTo":"e5bfff550712300502p543680b9jbeb9469a5a970f0@mail.gmail.com","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-12-30T15:54:00Z","receivedAt":"2007-12-30T15:54:00Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 30 Dec 2007, Marco Costalba wrote:\n\n> Initial patch by Johannes Schindelin.\n\nNot true ;-)\n\nCiao,\nDscho\n"},{"id":"64337","messageId":"477BC2DA.6000105@lsrfire.ath.cx","threadId":"11422","inReplyTo":"Pine.LNX.4.64.0712292019450.14355@wbgn129.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-01-02T16:59:06Z","receivedAt":"2008-01-02T16:59:06Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Johannes Schindelin schrieb:\n> Certain codepaths (notably \"git log --pretty=format...\") use\n> prefixcmp() extensively, with very short prefixes. In those cases,\n> calling strlen() is a wasteful operation, so avoid it.\n\n> static inline int prefixcmp(const char *str, const char *prefix)\n> {\n> -\treturn strncmp(str, prefix, strlen(prefix));\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\nprefixcmp() was already optimized before -- only for a different use\ncase. At a number of callsites the prefix is a string literal, which\nallowed the compiler to perform the strlen() call at compile time.\n\nThe patch increases the text size considerably: the file \"git\" is\n2,620,938 without and 2,640,450 with the patch in my build (there are\n136 callsites in builtin*.c). The new version of prefixcmp() shouldn't\nbe inlined any more, as the benefit of doing so is gone.\n\nIs there a portable way to let the preprocessor decide if\nprefixcmp_literal() or prefixcmp_generic() is to be used, depending on\nthe prefix being a string literal or not?\n\nRené\n"},{"id":"64343","messageId":"7v1w90xdpe.fsf@gitster.siamese.dyndns.org","threadId":"11422","inReplyTo":"477BC2DA.6000105@lsrfire.ath.cx","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-02T18:52:13Z","receivedAt":"2008-01-02T18:52:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> prefixcmp() was already optimized before -- only for a different use\n> case. At a number of callsites the prefix is a string literal, which\n> allowed the compiler to perform the strlen() call at compile time.\n>\n> The patch increases the text size considerably: the file \"git\" is\n> 2,620,938 without and 2,640,450 with the patch in my build (there are\n> 136 callsites in builtin*.c). The new version of prefixcmp() shouldn't\n> be inlined any more, as the benefit of doing so is gone.\n\nYuck, you are absolutely right. The late thread may have been\nwell intentioned but resulted in this regression. Sorry about\nthat.\n\nI presume that all callers with constant prefix are outside\nperformance critical parts? Can we simply uninline the function\nin that case?\n"},{"id":"64362","messageId":"477C301A.9020001@lsrfire.ath.cx","threadId":"11422","inReplyTo":"7v1w90xdpe.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Optimize prefixcmp()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-01-03T00:45:14Z","receivedAt":"2008-01-03T00:45:14Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Junio C Hamano schrieb:\n> René Scharfe writes:\n> \n>> prefixcmp() was already optimized before -- only for a different use\n>> case. At a number of callsites the prefix is a string literal, which\n>> allowed the compiler to perform the strlen() call at compile time.\n>>\n>> The patch increases the text size considerably: the file \"git\" is\n>> 2,620,938 without and 2,640,450 with the patch in my build (there are\n>> 136 callsites in builtin*.c). The new version of prefixcmp() shouldn't\n>> be inlined any more, as the benefit of doing so is gone.\n> \n> Yuck, you are absolutely right. The late thread may have been\n> well intentioned but resulted in this regression. Sorry about\n> that.\n> \n> I presume that all callers with constant prefix are outside\n> performance critical parts? Can we simply uninline the function\n> in that case?\n\nMost of them seem to be non-critical performance-wise. They are part of\ncode to parse parameters or config files. Exceptions are the commit\nmessage parsing code used for --pretty=format (which can't be an issue\ngiven that prefixcmp() was made the way it's now to speed up this code\npath) and half of the callsites in fast-import.c.\n\nRené\n"}]}