{"thread":{"id":"52868","subject":"[PATCH] use strpbrk(3) to search for characters from a given set","startedAt":"2020-02-22T18:51:27Z","lastAt":"2020-02-24T19:10:03Z","messageCount":6,"participants":["René Scharfe","Martin Ågren","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"392308","messageId":"4140dade-d999-a74a-1f8e-06eedb84ed20@web.de","threadId":"52868","inReplyTo":null,"subject":"[PATCH] use strpbrk(3) to search for characters from a given set","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-02-22T18:51:19Z","receivedAt":"2020-02-22T18:51:27Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"We can check if certain characters are present in a string by calling\nstrchr(3) on each of them, or we can pass them all to a single\nstrpbrk(3) call. The latter is shorter, less repetitive and slightly\nmore efficient, so let's do that instead.\n\nSigned-off-by: René Scharfe \n---\n builtin/show-branch.c | 2 +-\n compat/mingw.c | 2 +-\n mailinfo.c | 3 +--\n t/helper/test-windows-named-pipe.c | 2 +-\n 4 files changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex 35d7f51c23..8c90cbb18f 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -536,7 +536,7 @@ static void append_one_rev(const char *av)\n \t\tappend_ref(av, &revkey, 0);\n \t\treturn;\n \t}\n-\tif (strchr(av, '*') || strchr(av, '?') || strchr(av, '[')) {\n+\tif (strpbrk(av, \"*?[\")) {\n \t\t/* glob style match */\n \t\tint saved_matches = ref_name_cnt;\n\ndiff --git a/compat/mingw.c b/compat/mingw.c\nindex b5230149db..d14065d60e 100644\n--- a/compat/mingw.c\n+++ b/compat/mingw.c\n@@ -1245,7 +1245,7 @@ static char *path_lookup(const char *cmd, int exe_only)\n \tint len = strlen(cmd);\n \tint isexe = len >= 4 && !strcasecmp(cmd+len-4, \".exe\");\n\n-\tif (strchr(cmd, '/') || strchr(cmd, '\\\\'))\n+\tif (strpbrk(cmd, \"/\\\\\"))\n \t\treturn xstrdup(cmd);\n\n \tpath = mingw_getenv(\"PATH\");\ndiff --git a/mailinfo.c b/mailinfo.c\nindex cf92255515..742fa376ab 100644\n--- a/mailinfo.c\n+++ b/mailinfo.c\n@@ -19,8 +19,7 @@ static void cleanup_space(struct strbuf *sb)\n static void get_sane_name(struct strbuf *out, struct strbuf *name, struct strbuf *email)\n {\n \tstruct strbuf *src = name;\n-\tif (name->len < 3 || 60 < name->len || strchr(name->buf, '@') ||\n-\t\tstrchr(name->buf, '<') || strchr(name->buf, '>'))\n+\tif (name->len < 3 || 60 < name->len || strpbrk(name->buf, \"@<>\"))\n \t\tsrc = email;\n \telse if (name == out)\n \t\treturn;\ndiff --git a/t/helper/test-windows-named-pipe.c b/t/helper/test-windows-named-pipe.c\nindex b4b752b01a..ae52183e63 100644\n--- a/t/helper/test-windows-named-pipe.c\n+++ b/t/helper/test-windows-named-pipe.c\n@@ -19,7 +19,7 @@ int cmd__windows_named_pipe(int argc, const char **argv)\n \tif (argc < 2)\n \t\tgoto print_usage;\n \tfilename = argv[1];\n-\tif (strchr(filename, '/') || strchr(filename, '\\\\'))\n+\tif (strpbrk(filename, \"/\\\\\"))\n \t\tgoto print_usage;\n \tstrbuf_addf(&pathname, \"//./pipe/%s\", filename);\n\n--\n2.25.1\n"},{"id":"392349","messageId":"CAN0heSpwNg0MKN7SCRi9b2CnxwQdCwxpc4LEkeVV4f9mxtYkLA@mail.gmail.com","threadId":"52868","inReplyTo":"4140dade-d999-a74a-1f8e-06eedb84ed20@web.de","subject":"Re: [PATCH] use strpbrk(3) to search for characters from a given set","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2020-02-23T09:01:29Z","receivedAt":"2020-02-23T09:01:43Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"On Sat, 22 Feb 2020 at 19:53, René Scharfe wrote:\n>\n> We can check if certain characters are present in a string by calling\n> strchr(3) on each of them, or we can pass them all to a single\n> strpbrk(3) call. The latter is shorter, less repetitive and slightly\n> more efficient, so let's do that instead.\n>\n> Signed-off-by: René Scharfe \n> ---\n> builtin/show-branch.c | 2 +-\n> compat/mingw.c | 2 +-\n> mailinfo.c | 3 +--\n> t/helper/test-windows-named-pipe.c | 2 +-\n> 4 files changed, 4 insertions(+), 5 deletions(-)\n\nI failed to identify any other spots, except for some hits in test data\n(in t/t4256/1/) which are probably better left alone.\n\n> - if (strchr(av, '*') || strchr(av, '?') || strchr(av, '[')) {\n> + if (strpbrk(av, \"*?[\")) {\n\nIndeed, the `strchr()` calls use the same haystack `av`, as opposed to\n`av`/`aw` or `av++`/`av++` or so. All conversions in this patch look\ngood to me.\n\nMartin\n"},{"id":"392392","messageId":"20200224063802.GB1015967@coredump.intra.peff.net","threadId":"52868","inReplyTo":"4140dade-d999-a74a-1f8e-06eedb84ed20@web.de","subject":"Re: [PATCH] use strpbrk(3) to search for characters from a given set","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-24T06:38:02Z","receivedAt":"2020-02-24T06:38:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Feb 22, 2020 at 07:51:19PM +0100, René Scharfe wrote:\n\n> We can check if certain characters are present in a string by calling\n> strchr(3) on each of them, or we can pass them all to a single\n> strpbrk(3) call. The latter is shorter, less repetitive and slightly\n> more efficient, so let's do that instead.\n\nI think the resulting code is more readable, and this is worth doing on\nthose grounds alone.\n\nI was curious whether it's always more efficient (tldr, it is; read on\nonly if you're also curious). The default glibc implementation of\nstrpbrk() is built on strcspn(). That in turn creates a 256-byte table\nwith a boolean flag set for each char in the accept string, and then\nwalks the haystack string doing O(1) lookups in the table for a hit. So\nwe have to memset() the table to zeroes at the start. Depending on the\nlength of the input string, that could be more expensive than just\nwalking the haystack string three times (one for each char in the accept\nstring).\n\nBut of course in practice there's all kinds of weird SSE assembly going\non behind the scenes. So in most of my tests, strpbrk() beats strchr()\nhandily. The one exception is when the first strchr() matches early in\nthe string and can short-circuit the rest of them.\n\nThe test I used was:\n\n $ cat foo.c\n #include \n \n int check(const char *s)\n {\n #if USE_STRCHR\n \treturn strchr(s, '<') || strchr(s, '>') || strchr(s, '@');\n #else\n \treturn !!strpbrk(s, \"@<>\");\n #endif\n }\n\n $ cat bar.c \n int check(const char *s);\n \n int main(int argc, const char **argv)\n {\n \tint ret;\n \tint i;\n \n \tfor (i = 0; i < 100000000; i++)\n \t\tret += check(argv[1]);\n \treturn ret & 0x7f;\n }\n \n\nI put it into two separate files to avoid check() being hoisted out of\nthe loop. There's something a bit interesting, though. If you combine\nthose two files, gcc _does_ hoist the strpbrk() version, generating\nthis as the complete code:\n\n\t subq $8, %rsp\n .cfi_def_cfa_offset 16\n movq 8(%rsi), %rdi\n leaq .LC0(%rip), %rsi\n call strpbrk@PLT\n testq %rax, %rax\n setne %al\n addq $8, %rsp\n .cfi_def_cfa_offset 8\n movzbl %al, %eax\n movl %eax, %edx\n imull $99999999, %eax, %eax\n addl %edx, %eax\n andl $127, %eax\n ret\n\nSo it calls strpbrk() exactly once, then recognizes that the loop is\njust adding up the same variable over and over and turns it into a\nmultiply. No loop at all; very cool (though I am puzzled why it doesn't\nmultiply by the full loop count; instead if multiplies by one less and\nthen adds back in one iteration).\n\nBut with strchr() it was less willing to do that (curiously, it will if\nthe function _isn't_ static, but won't if it is).\n\nAnyway, that's all compiler arcana subject to change between versions,\nand it's a dumb toy example anyway. But it does seem like the single\ncall is more likely to get inlined or hoisted by the compiler, which is\na point in its favor.\n\n-Peff\n"},{"id":"392413","messageId":"xmqqy2srrjx1.fsf@gitster-ct.c.googlers.com","threadId":"52868","inReplyTo":"4140dade-d999-a74a-1f8e-06eedb84ed20@web.de","subject":"Re: [PATCH] use strpbrk(3) to search for characters from a given set","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-24T17:10:02Z","receivedAt":"2020-02-24T17:10:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> We can check if certain characters are present in a string by calling\n> strchr(3) on each of them, or we can pass them all to a single\n> strpbrk(3) call. The latter is shorter, less repetitive and slightly\n> more efficient, so let's do that instead.\n>\n> Signed-off-by: René Scharfe \n> ---\n> builtin/show-branch.c | 2 +-\n> compat/mingw.c | 2 +-\n> mailinfo.c | 3 +--\n> t/helper/test-windows-named-pipe.c | 2 +-\n> 4 files changed, 4 insertions(+), 5 deletions(-)\n>\n> diff --git a/builtin/show-branch.c b/builtin/show-branch.c\n> index 35d7f51c23..8c90cbb18f 100644\n> --- a/builtin/show-branch.c\n> +++ b/builtin/show-branch.c\n> @@ -536,7 +536,7 @@ static void append_one_rev(const char *av)\n> \t\tappend_ref(av, &revkey, 0);\n> \t\treturn;\n> \t}\n> -\tif (strchr(av, '*') || strchr(av, '?') || strchr(av, '[')) {\n> +\tif (strpbrk(av, \"*?[\")) {\n\n\nThe changes in the patch obviously look all correct.\n\nI wonder how we can exploit Coccinelle to do this kind of\ntransformations, though. Would it be possible to say\n\n * if we see \"strchr(S, C1) || strchr(S, C2)\", transform it to\n \"strpbrk(S, concat(stringify(C1),stringify(C2)))\"; and\n * if we see \"strpbrk(S, N) || strchr(S, C)\", transform it to\n \"strpbrk(S, concat(N, stringify(C))\";\n\nand let the tool apply these two rules repeatedly, to catch the\npattern to find any number of needle character in the same haystack?\n"},{"id":"392428","messageId":"21e6eaac-318b-3cb3-bb63-4f65abfae670@web.de","threadId":"52868","inReplyTo":"xmqqy2srrjx1.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] use strpbrk(3) to search for characters from a given set","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-02-24T19:01:36Z","receivedAt":"2020-02-24T19:02:09Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.02.20 um 18:10 schrieb Junio C Hamano:\n> René Scharfe writes:\n>\n>> We can check if certain characters are present in a string by calling\n>> strchr(3) on each of them, or we can pass them all to a single\n>> strpbrk(3) call. The latter is shorter, less repetitive and slightly\n>> more efficient, so let's do that instead.\n>>\n>> Signed-off-by: René Scharfe \n>> ---\n>> builtin/show-branch.c | 2 +-\n>> compat/mingw.c | 2 +-\n>> mailinfo.c | 3 +--\n>> t/helper/test-windows-named-pipe.c | 2 +-\n>> 4 files changed, 4 insertions(+), 5 deletions(-)\n>>\n>> diff --git a/builtin/show-branch.c b/builtin/show-branch.c\n>> index 35d7f51c23..8c90cbb18f 100644\n>> --- a/builtin/show-branch.c\n>> +++ b/builtin/show-branch.c\n>> @@ -536,7 +536,7 @@ static void append_one_rev(const char *av)\n>> \t\tappend_ref(av, &revkey, 0);\n>> \t\treturn;\n>> \t}\n>> -\tif (strchr(av, '*') || strchr(av, '?') || strchr(av, '[')) {\n>> +\tif (strpbrk(av, \"*?[\")) {\n>\n>\n> The changes in the patch obviously look all correct.\n>\n> I wonder how we can exploit Coccinelle to do this kind of\n> transformations, though. Would it be possible to say\n>\n> * if we see \"strchr(S, C1) || strchr(S, C2)\", transform it to\n> \"strpbrk(S, concat(stringify(C1),stringify(C2)))\"; and\n> * if we see \"strpbrk(S, N) || strchr(S, C)\", transform it to\n> \"strpbrk(S, concat(N, stringify(C))\";\n>\n> and let the tool apply these two rules repeatedly, to catch the\n> pattern to find any number of needle character in the same haystack?\n\nThat would be nice. I briefly considered it, but I only can think of a\nsilly way to convert char literals to strings (by using one rule for\neach possible character value), I don't know how to concatenate strings\nin Coccinelle (simply putting them next to each other as in C doesn't\nseem to work), and I don't know how to apply a rule recursively to allow\ntransforming an arbitrarily long chain of strchr() calls. :-/\n\nRené\n"},{"id":"392429","messageId":"20200224191001.GA2739722@coredump.intra.peff.net","threadId":"52868","inReplyTo":"21e6eaac-318b-3cb3-bb63-4f65abfae670@web.de","subject":"Re: [PATCH] use strpbrk(3) to search for characters from a given set","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-24T19:10:01Z","receivedAt":"2020-02-24T19:10:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Feb 24, 2020 at 08:01:36PM +0100, René Scharfe wrote:\n\n> > The changes in the patch obviously look all correct.\n> >\n> > I wonder how we can exploit Coccinelle to do this kind of\n> > transformations, though. Would it be possible to say\n> >\n> > * if we see \"strchr(S, C1) || strchr(S, C2)\", transform it to\n> > \"strpbrk(S, concat(stringify(C1),stringify(C2)))\"; and\n> > * if we see \"strpbrk(S, N) || strchr(S, C)\", transform it to\n> > \"strpbrk(S, concat(N, stringify(C))\";\n> >\n> > and let the tool apply these two rules repeatedly, to catch the\n> > pattern to find any number of needle character in the same haystack?\n> \n> That would be nice. I briefly considered it, but I only can think of a\n> silly way to convert char literals to strings (by using one rule for\n> each possible character value), I don't know how to concatenate strings\n> in Coccinelle (simply putting them next to each other as in C doesn't\n> seem to work), and I don't know how to apply a rule recursively to allow\n> transforming an arbitrarily long chain of strchr() calls. :-/\n\nI suspect you could do it with the python scripting interface of\ncoccinelle. We haven't relied on that so far (since it's technically\noptional), but I think it would be worth doing if it makes impossible\nthings possible (it also would make some existing very slow things much\nfaster).\n\nAs far as the recursive rules, I thought coccinelle would always\nre-apply rules to the result. So the two that Junio gave above would\nwork (each application of the second one would suck up another strchr).\nBut I also won't be surprised if I'm totally wrong; it wouldn't be the\nfirst time I've been puzzled by coccinelle. :)\n\nAll that said, I don't plan to spend time on this. And I wouldn't really\nask you or anyone to unless they find it fun or interesting. It seems\nlike a lot of poking around for probably not that much benefit.\n\n-Peff\n"}]}