{"thread":{"id":"36028","subject":"[PATCH v3] skip_prefix: rewrite so that prefix is scanned once","startedAt":"2014-03-03T03:13:04Z","lastAt":"2014-03-04T09:18:26Z","messageCount":9,"participants":["Siddharth Goel","Junio C Hamano","David Kastrup","Duy Nguyen"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"235824","messageId":"1393816384-3300-1-git-send-email-siddharth98391@gmail.com","threadId":"36028","inReplyTo":null,"subject":"[PATCH v3] skip_prefix: rewrite so that prefix is scanned once","fromName":"Siddharth Goel","fromEmail":"siddharth98391@gmail.com","sentAt":"2014-03-03T03:13:04Z","receivedAt":"2014-03-03T03:13:04Z","isPatch":true,"sender":{"key":"siddharth98391@gmail.com","avatar":"https://gravatar.com/avatar/a951feb4fe81ca0581ee1719eb493b15bf8bb86107ae07510bd669811808ee19?d=mp&s=160"},"body":"Helped-by: Eric Sunshine \nSigned-off-by: Siddharth Goel \n---\nAdded a space after colon in the subject as compared to previous \npatch [PATCH v2].\n\n[PATCH v2]: http://thread.gmane.org/gmane.comp.version-control.git/243150\n\n git-compat-util.h | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 614a5e9..550dce3 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -357,8 +357,11 @@ extern int suffixcmp(const char *str, const char *suffix);\n \n static inline const char *skip_prefix(const char *str, const char *prefix)\n {\n-\tsize_t len = strlen(prefix);\n-\treturn strncmp(str, prefix, len) ? NULL : str + len;\n+\twhile (*prefix != '\\0' && *str == *prefix) {\n+\t\tstr++;\n+\t\tprefix++;\n+\t}\n+\treturn (*prefix == '\\0' ? str : NULL);\n }\n \n #if defined(NO_MMAP) || defined(USE_WIN32_MMAP)\n-- \n1.9.0.138.g2de3478.dirty\n"},{"id":"235905","messageId":"xmqqvbvvp0gj.fsf@gitster.dls.corp.google.com","threadId":"36028","inReplyTo":"1393816384-3300-1-git-send-email-siddharth98391@gmail.com","subject":"Re: [PATCH v3] skip_prefix: rewrite so that prefix is scanned once","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-03-03T19:05:16Z","receivedAt":"2014-03-03T19:05:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Siddharth Goel writes:\n\n> Helped-by: Eric Sunshine \n> Signed-off-by: Siddharth Goel \n> ---\n> Added a space after colon in the subject as compared to previous \n> patch [PATCH v2].\n>\n> [PATCH v2]: http://thread.gmane.org/gmane.comp.version-control.git/243150\n\nWhenever you see \"Change\", \"Rewrite\", etc. in the subject of a patch\nthat touches existing code, think twice. The subject line is a\nscarce real estate to be wasted on a noiseword that carries no real\ninformation, and we already know a patch that touches existing code\nchanges or rewrites things.\n\n Subject: [PATCH v3] skip_prefix: scan prefix only once\n\nperhaps?\n\n> git-compat-util.h | 7 +++++--\n> 1 file changed, 5 insertions(+), 2 deletions(-)\n>\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 614a5e9..550dce3 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -357,8 +357,11 @@ extern int suffixcmp(const char *str, const char *suffix);\n> \n> static inline const char *skip_prefix(const char *str, const char *prefix)\n> {\n> -\tsize_t len = strlen(prefix);\n> -\treturn strncmp(str, prefix, len) ? NULL : str + len;\n> +\twhile (*prefix != '\\0' && *str == *prefix) {\n> +\t\tstr++;\n> +\t\tprefix++;\n> +\t}\n> +\treturn (*prefix == '\\0' ? str : NULL);\n\nUnlike another patch I saw the other day on the same topic, this\nchecks *prefix twice for the last round, even though I think this\none is probably slightly easier to read. I dunno.\n"},{"id":"235945","messageId":"xmqq61nuoqd5.fsf@gitster.dls.corp.google.com","threadId":"36028","inReplyTo":"xmqqvbvvp0gj.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v3] skip_prefix: rewrite so that prefix is scanned once","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-03-03T22:43:18Z","receivedAt":"2014-03-03T22:43:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Siddharth Goel writes:\n>\n>> Helped-by: Eric Sunshine \n>> Signed-off-by: Siddharth Goel \n>> ---\n>> Added a space after colon in the subject as compared to previous \n>> patch [PATCH v2].\n>>\n>> [PATCH v2]: http://thread.gmane.org/gmane.comp.version-control.git/243150\n>\n> Whenever you see \"Change\", \"Rewrite\", etc. in the subject of a patch\n> that touches existing code, think twice. The subject line is a\n> scarce real estate to be wasted on a noiseword that carries no real\n> information, and we already know a patch that touches existing code\n> changes or rewrites things.\n>\n> Subject: [PATCH v3] skip_prefix: scan prefix only once\n>\n> perhaps?\n>\n>> git-compat-util.h | 7 +++++--\n>> 1 file changed, 5 insertions(+), 2 deletions(-)\n>>\n>> diff --git a/git-compat-util.h b/git-compat-util.h\n>> index 614a5e9..550dce3 100644\n>> --- a/git-compat-util.h\n>> +++ b/git-compat-util.h\n>> @@ -357,8 +357,11 @@ extern int suffixcmp(const char *str, const char *suffix);\n>> \n>> static inline const char *skip_prefix(const char *str, const char *prefix)\n>> {\n>> -\tsize_t len = strlen(prefix);\n>> -\treturn strncmp(str, prefix, len) ? NULL : str + len;\n>> +\twhile (*prefix != '\\0' && *str == *prefix) {\n>> +\t\tstr++;\n>> +\t\tprefix++;\n>> +\t}\n>> +\treturn (*prefix == '\\0' ? str : NULL);\n>\n> Unlike another patch I saw the other day on the same topic, this\n> checks *prefix twice for the last round, even though I think this\n> one is probably slightly easier to read. I dunno.\n\nThat is, something like this instead. After looking at it again, I\ndo not think it is less readable than the above.\n\n git-compat-util.h | 10 ++++++++--\n 1 file changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex cbd86c3..68ffaef 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -357,8 +357,14 @@ extern int suffixcmp(const char *str, const char *suffix);\n \n static inline const char *skip_prefix(const char *str, const char *prefix)\n {\n-\tsize_t len = strlen(prefix);\n-\treturn strncmp(str, prefix, len) ? NULL : str + len;\n+\twhile (1) {\n+\t\tif (!*prefix)\n+\t\t\treturn str;\n+\t\tif (*str != *prefix)\n+\t\t\treturn NULL;\n+\t\tprefix++;\n+\t\tstr++;\n+\t}\n }\n \n #if defined(NO_MMAP) || defined(USE_WIN32_MMAP)\n"},{"id":"235957","messageId":"87bnxmkguw.fsf@fencepost.gnu.org","threadId":"36028","inReplyTo":"xmqq61nuoqd5.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v3] skip_prefix: rewrite so that prefix is scanned once","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-03-03T23:22:15Z","receivedAt":"2014-03-03T23:22:15Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -357,8 +357,14 @@ extern int suffixcmp(const char *str, const char *suffix);\n> \n> static inline const char *skip_prefix(const char *str, const char *prefix)\n> {\n> -\tsize_t len = strlen(prefix);\n> -\treturn strncmp(str, prefix, len) ? NULL : str + len;\n> +\twhile (1) {\n> +\t\tif (!*prefix)\n> +\t\t\treturn str;\n> +\t\tif (*str != *prefix)\n> +\t\t\treturn NULL;\n> +\t\tprefix++;\n> +\t\tstr++;\n> +\t}\n> }\n\nHow about a function body of\n\n\tdo {\n \tif (!*prefix)\n \treturn str;\n } while (*str++ == *prefix++);\n return NULL;\n\nI'm not too fond of while (1) and tend to use for (;;) instead, but that\nmay again partly be due to some incredibly non-optimizing compiler back\nin the days of my youth. At any rate, the do-while loop seems a bit\nbrisker.\n\n-- \nDavid Kastrup\n"},{"id":"235960","messageId":"xmqqk3can9dp.fsf@gitster.dls.corp.google.com","threadId":"36028","inReplyTo":"87bnxmkguw.fsf@fencepost.gnu.org","subject":"Re: [PATCH v3] skip_prefix: rewrite so that prefix is scanned once","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-03-03T23:35:30Z","receivedAt":"2014-03-03T23:35:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> How about a function body of\n>\n> \tdo {\n> \tif (!*prefix)\n> \treturn str;\n> } while (*str++ == *prefix++);\n> return NULL;\n>\n> I'm not too fond of while (1) and tend to use for (;;) instead, but that\n> may again partly be due to some incredibly non-optimizing compiler back\n> in the days of my youth. At any rate, the do-while loop seems a bit\n> brisker.\n\nI do not have strong preference between \"while (1)\" and \"for (;;)\",\nbut I tend to agree\n\n\tfor (;; prefix++, str++) {\n\t\tif (!*prefix)\n\t\t\treturn str;\n\t\tif (*str != *prefix)\n\t\t\treturn NULL;\n\t}\n\nmay be easier to read than what I suggested. Your do-while loop is\nconcise and very readable, so let's take that one (I'll forge your\nSign-off ;-)).\n\nI haven't looked at the generated assembly of any of these, though.\n"},{"id":"235961","messageId":"CACsJy8ASBeravdk67pbOJbrFUbwg21JwYcLtSbDDMJOu9-F=yA@mail.gmail.com","threadId":"36028","inReplyTo":"xmqq61nuoqd5.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v3] skip_prefix: rewrite so that prefix is scanned once","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-03-03T23:37:25Z","receivedAt":"2014-03-03T23:37:25Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 4, 2014 at 5:43 AM, Junio C Hamano wrote:\n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index cbd86c3..68ffaef 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -357,8 +357,14 @@ extern int suffixcmp(const char *str, const char *suffix);\n>\n> static inline const char *skip_prefix(const char *str, const char *prefix)\n> {\n> - size_t len = strlen(prefix);\n> - return strncmp(str, prefix, len) ? NULL : str + len;\n\nJust a note. gcc does optimize strlen(\"abcdef\") to 6, and with that\ninformation at compile time built-in strncmp might do better.\n\n> + while (1) {\n> + if (!*prefix)\n> + return str;\n> + if (*str != *prefix)\n> + return NULL;\n> + prefix++;\n> + str++;\n> + }\n> }\n>\n> #if defined(NO_MMAP) || defined(USE_WIN32_MMAP)\n-- \nDuy\n"},{"id":"235968","messageId":"877g8akenw.fsf@fencepost.gnu.org","threadId":"36028","inReplyTo":"CACsJy8ASBeravdk67pbOJbrFUbwg21JwYcLtSbDDMJOu9-F=yA@mail.gmail.com","subject":"Re: [PATCH v3] skip_prefix: rewrite so that prefix is scanned once","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-03-04T00:09:39Z","receivedAt":"2014-03-04T00:09:39Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Duy Nguyen writes:\n\n> On Tue, Mar 4, 2014 at 5:43 AM, Junio C Hamano wrote:\n>> diff --git a/git-compat-util.h b/git-compat-util.h\n>> index cbd86c3..68ffaef 100644\n>> --- a/git-compat-util.h\n>> +++ b/git-compat-util.h\n>> @@ -357,8 +357,14 @@ extern int suffixcmp(const char *str, const char *suffix);\n>>\n>> static inline const char *skip_prefix(const char *str, const char *prefix)\n>> {\n>> - size_t len = strlen(prefix);\n>> - return strncmp(str, prefix, len) ? NULL : str + len;\n>\n> Just a note. gcc does optimize strlen(\"abcdef\") to 6, and with that\n> information at compile time built-in strncmp might do better.\n\nIndeed, most (but not all) of the calls have a constant string as\nprefix. However, strncmp in each iteration checks for both *str as well\nas *prefix to be different from '\\0' independently (and it appears\nunlikely to me that the optimizer will figure out that it's unnecessary\nfor either) _and_ compares them for equality so it's not likely to be\nfaster than the open-coded loop.\n\nOne could, however, use memcmp instead of strncmp. I'm just not sure\nwhether memcmp is guaranteed not to peek beyond the first mismatching\nbyte even if the count would allow for more. It could lead to undefined\nbehavior if the first mismatching byte would be the ending NUL byte of\nstr.\n\n-- \nDavid Kastrup\n"},{"id":"235971","messageId":"20140304015819.GA10643@duynguyen-vnpc.dek-tpc.internal","threadId":"36028","inReplyTo":"877g8akenw.fsf@fencepost.gnu.org","subject":"Re: [PATCH v3] skip_prefix: rewrite so that prefix is scanned once","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-03-04T01:58:19Z","receivedAt":"2014-03-04T01:58:19Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 04, 2014 at 01:09:39AM +0100, David Kastrup wrote:\n> Duy Nguyen writes:\n> \n> > On Tue, Mar 4, 2014 at 5:43 AM, Junio C Hamano wrote:\n> >> diff --git a/git-compat-util.h b/git-compat-util.h\n> >> index cbd86c3..68ffaef 100644\n> >> --- a/git-compat-util.h\n> >> +++ b/git-compat-util.h\n> >> @@ -357,8 +357,14 @@ extern int suffixcmp(const char *str, const char *suffix);\n> >>\n> >> static inline const char *skip_prefix(const char *str, const char *prefix)\n> >> {\n> >> - size_t len = strlen(prefix);\n> >> - return strncmp(str, prefix, len) ? NULL : str + len;\n> >\n> > Just a note. gcc does optimize strlen(\"abcdef\") to 6, and with that\n> > information at compile time built-in strncmp might do better.\n> \n> Indeed, most (but not all) of the calls have a constant string as\n> prefix. However, strncmp in each iteration checks for both *str as well\n> as *prefix to be different from '\\0' independently (and it appears\n> unlikely to me that the optimizer will figure out that it's unnecessary\n> for either) _and_ compares them for equality so it's not likely to be\n> faster than the open-coded loop.\n> \n> One could, however, use memcmp instead of strncmp. I'm just not sure\n> whether memcmp is guaranteed not to peek beyond the first mismatching\n> byte even if the count would allow for more. It could lead to undefined\n> behavior if the first mismatching byte would be the ending NUL byte of\n> str.\n\nIt turns out gcc does not generate a call to strncmp either. It\ninlines repz cmpsb instead. I recall we had a discussion long ago\nabout the inefficiency of repz and and open-coded loop is preferred,\nmaybe that was about hashcmp. Anyway this does not matter much as\nskip_prefix() is unlikely to be in any critical path, so I think\nreadability has higher priority.\n\nFor the curious, this small C program\n\n-- 8< --\n#include \n#include \n\nstatic inline const char *skip(const char *str, const char *prefix)\n{\n int len = strlen(prefix);\n return strncmp(str, prefix, len) ? NULL : str + len;\n}\nint main(int ac, char **av)\n{\n const char *s = skip(av[1], \"foo\");\n printf(\"%s\\n\", s);\n return 0;\n}\n-- 8< --\n\nproduces this assembly with gcc -O2 (on x86, apparently)\n\n-- 8< --\n00000000
:\n 0: 55 push %ebp\n 1: b9 03 00 00 00 mov $0x3,%ecx\n 6: 89 e5 mov %esp,%ebp\n 8: 57 push %edi\n 9: bf 00 00 00 00 mov $0x0,%edi\n e: 56 push %esi\n f: 53 push %ebx\n 10: 83 e4 f0 and $0xfffffff0,%esp\n 13: 83 ec 10 sub $0x10,%esp\n 16: 8b 45 0c mov 0xc(%ebp),%eax\n 19: 8b 40 04 mov 0x4(%eax),%eax\n 1c: 89 c6 mov %eax,%esi\n 1e: f3 a6 repz cmpsb %es:(%edi),%ds:(%esi)\n 20: 0f 97 c3 seta %bl\n 23: 0f 92 c1 setb %cl\n 26: 83 c0 03 add $0x3,%eax\n 29: 31 d2 xor %edx,%edx\n 2b: 38 cb cmp %cl,%bl\n 2d: 0f 44 d0 cmove %eax,%edx\n 30: 89 14 24 mov %edx,(%esp)\n 33: e8 fc ff ff ff call 34 \n 38: 8d 65 f4 lea -0xc(%ebp),%esp\n 3b: 31 c0 xor %eax,%eax\n 3d: 5b pop %ebx\n 3e: 5e pop %esi\n 3f: 5f pop %edi\n 40: 5d pop %ebp\n 41: c3 ret\n-- 8< --\n--\nDuy\n"},{"id":"235982","messageId":"87txbeiaot.fsf@fencepost.gnu.org","threadId":"36028","inReplyTo":"20140304015819.GA10643@duynguyen-vnpc.dek-tpc.internal","subject":"Re: [PATCH v3] skip_prefix: rewrite so that prefix is scanned once","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-03-04T09:18:26Z","receivedAt":"2014-03-04T09:18:26Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Duy Nguyen writes:\n\n> On Tue, Mar 04, 2014 at 01:09:39AM +0100, David Kastrup wrote:\n>> Duy Nguyen writes:\n>> \n>> > On Tue, Mar 4, 2014 at 5:43 AM, Junio C Hamano wrote:\n>> >> diff --git a/git-compat-util.h b/git-compat-util.h\n>> >> index cbd86c3..68ffaef 100644\n>> >> --- a/git-compat-util.h\n>> >> +++ b/git-compat-util.h\n>> >> @@ -357,8 +357,14 @@ extern int suffixcmp(const char *str, const char *suffix);\n>> >>\n>> >> static inline const char *skip_prefix(const char *str, const char *prefix)\n>> >> {\n>> >> - size_t len = strlen(prefix);\n>> >> - return strncmp(str, prefix, len) ? NULL : str + len;\n>> >\n>> > Just a note. gcc does optimize strlen(\"abcdef\") to 6, and with that\n>> > information at compile time built-in strncmp might do better.\n>> \n>> Indeed, most (but not all) of the calls have a constant string as\n>> prefix. However, strncmp in each iteration checks for both *str as well\n>> as *prefix to be different from '\\0' independently (and it appears\n>> unlikely to me that the optimizer will figure out that it's unnecessary\n>> for either) _and_ compares them for equality so it's not likely to be\n>> faster than the open-coded loop.\n>> \n>> One could, however, use memcmp instead of strncmp. I'm just not sure\n>> whether memcmp is guaranteed not to peek beyond the first mismatching\n>> byte even if the count would allow for more. It could lead to undefined\n>> behavior if the first mismatching byte would be the ending NUL byte of\n>> str.\n>\n> It turns out gcc does not generate a call to strncmp either. It\n> inlines repz cmpsb instead.\n\nOh wow. So it _does_ know that it's not necessary to check for a NUL\nbyte when the length of one argument is already known. I am seriously\nimpressed.\n\n> I recall we had a discussion long ago about the inefficiency of repz\n> and and open-coded loop is preferred,\n\nI think that this mostly applies for Pentium I, possibly also the\ndead-ended Pentium Pro architecture (that sort-of translated the x86\nopcodes into RISC instructions). I think that later processor variants\n(and AMD anyway) got those instructions back to usable shape.\n\nOne thing where there was a _lot_ of performance difference between\nopen-coding and builtin was using memcpy (repz movb) for copying\nwell-aligned data bytewise rather than copying, say, integer arrays\nelement-wise.\n\nBut since that was egg-on-face material, the hardware got better at it.\n\nAnd anyway, GCC should know what to pick here. So with GCC being as\nsmart as that (using the equivalent of memcmp on its own initiative\ninstead of the full strncmp), I don't think we have a reasonable chance\nto beat its performance with an open-coded variant.\n\n> produces this assembly with gcc -O2 (on x86, apparently)\n>\n> -- 8< --\n> 00000000
:\n> 0: 55 push %ebp\n> 1: b9 03 00 00 00 mov $0x3,%ecx\n> 6: 89 e5 mov %esp,%ebp\n> 8: 57 push %edi\n> 9: bf 00 00 00 00 mov $0x0,%edi\n> e: 56 push %esi\n> f: 53 push %ebx\n> 10: 83 e4 f0 and $0xfffffff0,%esp\n> 13: 83 ec 10 sub $0x10,%esp\n> 16: 8b 45 0c mov 0xc(%ebp),%eax\n> 19: 8b 40 04 mov 0x4(%eax),%eax\n> 1c: 89 c6 mov %eax,%esi\n> 1e: f3 a6 repz cmpsb %es:(%edi),%ds:(%esi)\n> 20: 0f 97 c3 seta %bl\n> 23: 0f 92 c1 setb %cl\n> 26: 83 c0 03 add $0x3,%eax\n> 29: 31 d2 xor %edx,%edx\n> 2b: 38 cb cmp %cl,%bl\n> 2d: 0f 44 d0 cmove %eax,%edx\n\nMore like i686 than x86 here.\n\n> 30: 89 14 24 mov %edx,(%esp)\n> 33: e8 fc ff ff ff call 34 \n> 38: 8d 65 f4 lea -0xc(%ebp),%esp\n> 3b: 31 c0 xor %eax,%eax\n> 3d: 5b pop %ebx\n> 3e: 5e pop %esi\n> 3f: 5f pop %edi\n> 40: 5d pop %ebp\n> 41: c3 ret\n\nWell, we won't beat this here.\n\n-- \nDavid Kastrup\n"}]}