{"thread":{"id":"46560","subject":"[PATCH] cache-tree: remove use of strbuf_addf in update_one","startedAt":"2017-08-10T18:47:35Z","lastAt":"2017-08-14T18:51:37Z","messageCount":7,"participants":["Kevin Willford","Stefan Beller","Jeff King","René Scharfe","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"326062","messageId":"20170810184723.12424-1-kewillf@microsoft.com","threadId":"46560","inReplyTo":null,"subject":"[PATCH] cache-tree: remove use of strbuf_addf in update_one","fromName":"Kevin Willford","fromEmail":"kcwillford@gmail.com","sentAt":"2017-08-10T18:47:23Z","receivedAt":"2017-08-10T18:47:35Z","isPatch":true,"sender":{"key":"kcwillford@gmail.com","avatar":null},"body":"String formatting can be a performance issue when there are\nhundreds of thousands of trees.\n\nChange to stop using the strbuf_addf and just add the strings\nor characters individually.\n\nThere are a limited number of modes so added a switch for the\nknown ones and a default case if something comes through that\nare not a known one for git.\n\nSigned-off-by: Kevin Willford <kewillf@microsoft.com>\n---\n cache-tree.c | 24 +++++++++++++++++++++++-\n 1 file changed, 23 insertions(+), 1 deletion(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 2440d1dc89..41744b3db7 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -390,7 +390,29 @@ static int update_one(struct cache_tree *it,\n \t\t\tcontinue;\n \n \t\tstrbuf_grow(&buffer, entlen + 100);\n-\t\tstrbuf_addf(&buffer, \"%o %.*s%c\", mode, entlen, path + baselen, '\\0');\n+\n+\t\tswitch (mode) {\n+\t\tcase 0100644:\n+\t\t\tstrbuf_add(&buffer, \"100644 \", 7);\n+\t\t\tbreak;\n+\t\tcase 0100664:\n+\t\t\tstrbuf_add(&buffer, \"100664 \", 7);\n+\t\t\tbreak;\n+\t\tcase 0100755:\n+\t\t\tstrbuf_add(&buffer, \"100755 \", 7);\n+\t\t\tbreak;\n+\t\tcase 0120000:\n+\t\t\tstrbuf_add(&buffer, \"120000 \", 7);\n+\t\t\tbreak;\n+\t\tcase 0160000:\n+\t\t\tstrbuf_add(&buffer, \"160000 \", 7);\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\tstrbuf_addf(&buffer, \"%o \", mode);\n+\t\t\tbreak;\n+\t\t}\n+\t\tstrbuf_add(&buffer, path + baselen, entlen);\n+\t\tstrbuf_addch(&buffer, '\\0');\n \t\tstrbuf_add(&buffer, sha1, 20);\n \n #if DEBUG\n-- \n2.14.0.rc0.286.g44127d70e4\n\n"},{"id":"326069","messageId":"CAGZ79kaB7w+OD_8LOgqHjBJ8gCtXUGWPj7Cw8bWXEEQweqMaFw@mail.gmail.com","threadId":"46560","inReplyTo":"20170810184723.12424-1-kewillf@microsoft.com","subject":"Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-08-10T18:58:34Z","receivedAt":"2017-08-10T18:58:41Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Aug 10, 2017 at 11:47 AM, Kevin Willford <kcwillford@gmail.com> wrote:\n> String formatting can be a performance issue when there are\n> hundreds of thousands of trees.\n\nWhen changing this for the sake of performance, could you give\nan example (which kind of repository you need for this to become\na bottleneck? I presume the large Windows repo? Or can I\nreproduce it with a small repo such as linux.git or even git.git?)\nand some numbers how this improves the performance?\n\n> Change to stop using the strbuf_addf and just add the strings\n> or characters individually.\n>\n> There are a limited number of modes so added a switch for the\n> known ones and a default case if something comes through that\n> are not a known one for git.\n>\n> Signed-off-by: Kevin Willford <kewillf@microsoft.com>\n> ---\n>  cache-tree.c | 24 +++++++++++++++++++++++-\n>  1 file changed, 23 insertions(+), 1 deletion(-)\n>\n> diff --git a/cache-tree.c b/cache-tree.c\n> index 2440d1dc89..41744b3db7 100644\n> --- a/cache-tree.c\n> +++ b/cache-tree.c\n> @@ -390,7 +390,29 @@ static int update_one(struct cache_tree *it,\n>                         continue;\n>\n>                 strbuf_grow(&buffer, entlen + 100);\n> -               strbuf_addf(&buffer, \"%o %.*s%c\", mode, entlen, path + baselen, '\\0');\n> +\n> +               switch (mode) {\n> +               case 0100644:\n> +                       strbuf_add(&buffer, \"100644 \", 7);\n> +                       break;\n> +               case 0100664:\n> +                       strbuf_add(&buffer, \"100664 \", 7);\n> +                       break;\n> +               case 0100755:\n> +                       strbuf_add(&buffer, \"100755 \", 7);\n> +                       break;\n> +               case 0120000:\n> +                       strbuf_add(&buffer, \"120000 \", 7);\n> +                       break;\n> +               case 0160000:\n> +                       strbuf_add(&buffer, \"160000 \", 7);\n> +                       break;\n\nMaybe it is worth spelling out the modes in non-numeric,\nbut e.g. S_IFGITLINK.\n\n> +               default:\n> +                       strbuf_addf(&buffer, \"%o \", mode);\n\nGiven the repository you are measuring, maybe we could\nget away with fewer entries here and only take the 2 or\n3 most used entries and special case them?\n\nOr in case this is assumed to be the exhaustive list,\nwe could issue a warning here?\n\nThanks,\nStefan\n"},{"id":"326070","messageId":"20170810190349.jxlp6i7c6q5hpari@sigill.intra.peff.net","threadId":"46560","inReplyTo":"CAGZ79kaB7w+OD_8LOgqHjBJ8gCtXUGWPj7Cw8bWXEEQweqMaFw@mail.gmail.com","subject":"Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-10T19:03:49Z","receivedAt":"2017-08-10T19:03:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 10, 2017 at 11:58:34AM -0700, Stefan Beller wrote:\n\n> On Thu, Aug 10, 2017 at 11:47 AM, Kevin Willford <kcwillford@gmail.com> wrote:\n> > String formatting can be a performance issue when there are\n> > hundreds of thousands of trees.\n> \n> When changing this for the sake of performance, could you give\n> an example (which kind of repository you need for this to become\n> a bottleneck? I presume the large Windows repo? Or can I\n> reproduce it with a small repo such as linux.git or even git.git?)\n> and some numbers how this improves the performance?\n\nI was about to say the same thing. Normally I don't mind a small\noptimization without numbers if the result is obviously an improvement.\n\nBut in this case the result is a lot less readable, and it's not\nentirely clear to me that it would always be an improvement (we now\nalways run 3 strbuf calls instead of one, and have to check the length\nfor each one).\n\nWhat I'm wondering specifically is if vsnprintf() on Kevin's platform\n(which I'll assume is Windows) is slow, and we would do better to\nreplace it with a faster compat/ routine.\n\n-Peff\n"},{"id":"326083","messageId":"e71f1aab-d93a-2774-4378-8431bd33e146@gmail.com","threadId":"46560","inReplyTo":"20170810190349.jxlp6i7c6q5hpari@sigill.intra.peff.net","subject":"Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one","fromName":"Kevin Willford","fromEmail":"kcwillford@gmail.com","sentAt":"2017-08-10T19:57:24Z","receivedAt":"2017-08-10T19:57:30Z","isPatch":true,"sender":{"key":"kcwillford@gmail.com","avatar":null},"body":"\n\nOn 8/10/2017 3:03 PM, Jeff King wrote:\n> On Thu, Aug 10, 2017 at 11:58:34AM -0700, Stefan Beller wrote:\n>\n>> On Thu, Aug 10, 2017 at 11:47 AM, Kevin Willford <kcwillford@gmail.com> wrote:\n>>> String formatting can be a performance issue when there are\n>>> hundreds of thousands of trees.\n>> When changing this for the sake of performance, could you give\n>> an example (which kind of repository you need for this to become\n>> a bottleneck? I presume the large Windows repo? Or can I\n>> reproduce it with a small repo such as linux.git or even git.git?)\n>> and some numbers how this improves the performance?\n> I was about to say the same thing. Normally I don't mind a small\n> optimization without numbers if the result is obviously an improvement.\n>\n> But in this case the result is a lot less readable, and it's not\n> entirely clear to me that it would always be an improvement (we now\n> always run 3 strbuf calls instead of one, and have to check the length\n> for each one).\n>\n> What I'm wondering specifically is if vsnprintf() on Kevin's platform\n> (which I'll assume is Windows) is slow, and we would do better to\n> replace it with a faster compat/ routine.\n>\n> -Peff\n\nThe strbuf_add call is essentially only having to do a memcpy whereas\nthe strbuf_addf will have to parse the string, determine the types,\nconvert the data, and then get it in the buffer.  That could be made\nfaster with a better compat/ routine but I fear still far from\nthe length check and memcpy.\n\nvoid strbuf_add(struct strbuf *sb, const void *data, size_t len)\n{\n\tstrbuf_grow(sb, len);\n\tmemcpy(sb->buf + sb->len, data, len);\n\tstrbuf_setlen(sb, sb->len + len);\n}\n\nHere are some of the performance numbers from the windows repo.\nI will work on writing a perf test for this change so that we\nhave a better idea on smaller repo what the impact of this change\nis on them.\n\n              | w/o     | with fix |\n-----------------------------------\ngit checkout | 36.08 s | 33.34 s  |\n-----------------------------------\ngit checkout | 32.54 s | 28.26 s  |\n-----------------------------------\ngit checkout | 44.10 s | 38.13 s  |\n-----------------------------------\ngit merge    | 32.90 s | 30.56 s  |\n-----------------------------------\ngit rebase   | 46.14 s | 42.18 s  |\n\n\n\n"},{"id":"326092","messageId":"CAGZ79kbM6F8SMB4K1d_fY1TEEOvVJfuvot7tv8=KWqOtLUgB2g@mail.gmail.com","threadId":"46560","inReplyTo":"e71f1aab-d93a-2774-4378-8431bd33e146@gmail.com","subject":"Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-08-10T20:33:55Z","receivedAt":"2017-08-10T20:34:01Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Aug 10, 2017 at 12:57 PM, Kevin Willford <kcwillford@gmail.com> wrote:\n> Here are some of the performance numbers from the windows repo.\n> I will work on writing a perf test for this change so that we\n> have a better idea on smaller repo what the impact of this change\n> is on them.\n>\n>              | w/o     | with fix |\n> -----------------------------------\n> git checkout | 36.08 s | 33.34 s  |\n> -----------------------------------\n> git checkout | 32.54 s | 28.26 s  |\n> -----------------------------------\n> git checkout | 44.10 s | 38.13 s  |\n> -----------------------------------\n> git merge    | 32.90 s | 30.56 s  |\n> -----------------------------------\n> git rebase   | 46.14 s | 42.18 s  |\n>\n\n~10-15% is impressive for this patch, I certainly did not\nexpect as much. Thanks for providing the numbers!\n\nStefan\n"},{"id":"326142","messageId":"bc8f198c-3fe2-035a-4408-6369f34023e9@web.de","threadId":"46560","inReplyTo":"20170810184723.12424-1-kewillf@microsoft.com","subject":"Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-11T13:08:21Z","receivedAt":"2017-08-11T13:08:44Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 10.08.2017 um 20:47 schrieb Kevin Willford:\n> String formatting can be a performance issue when there are\n> hundreds of thousands of trees.\n> \n> Change to stop using the strbuf_addf and just add the strings\n> or characters individually.\n> \n> There are a limited number of modes so added a switch for the\n> known ones and a default case if something comes through that\n> are not a known one for git.\n> \n> Signed-off-by: Kevin Willford <kewillf@microsoft.com>\n> ---\n>   cache-tree.c | 24 +++++++++++++++++++++++-\n>   1 file changed, 23 insertions(+), 1 deletion(-)\n> \n> diff --git a/cache-tree.c b/cache-tree.c\n> index 2440d1dc89..41744b3db7 100644\n> --- a/cache-tree.c\n> +++ b/cache-tree.c\n> @@ -390,7 +390,29 @@ static int update_one(struct cache_tree *it,\n>   \t\t\tcontinue;\n>   \n>   \t\tstrbuf_grow(&buffer, entlen + 100);\n> -\t\tstrbuf_addf(&buffer, \"%o %.*s%c\", mode, entlen, path + baselen, '\\0');\n> +\n> +\t\tswitch (mode) {\n> +\t\tcase 0100644:\n> +\t\t\tstrbuf_add(&buffer, \"100644 \", 7);\n> +\t\t\tbreak;\n> +\t\tcase 0100664:\n> +\t\t\tstrbuf_add(&buffer, \"100664 \", 7);\n> +\t\t\tbreak;\n> +\t\tcase 0100755:\n> +\t\t\tstrbuf_add(&buffer, \"100755 \", 7);\n> +\t\t\tbreak;\n> +\t\tcase 0120000:\n> +\t\t\tstrbuf_add(&buffer, \"120000 \", 7);\n> +\t\t\tbreak;\n> +\t\tcase 0160000:\n> +\t\t\tstrbuf_add(&buffer, \"160000 \", 7);\n> +\t\t\tbreak;\n\nYou can avoid specifying the string length by using strbuf_addstr.  The\ncompiler can determine that value; the resulting object code should be\nthe same with -O2.\n\n> +\t\tdefault:\n> +\t\t\tstrbuf_addf(&buffer, \"%o \", mode);\n> +\t\t\tbreak;\n> +\t\t}\n> +\t\tstrbuf_add(&buffer, path + baselen, entlen);\n> +\t\tstrbuf_addch(&buffer, '\\0');\n\nHow much of the performance improvement is due to these two (especially\n%.*s)?  Looking forward to the perf script to find out myself. :)\n\n>   \t\tstrbuf_add(&buffer, sha1, 20);\n>   \n>   #if DEBUG\n> \n"},{"id":"326295","messageId":"xmqqo9riugnh.fsf@gitster.mtv.corp.google.com","threadId":"46560","inReplyTo":"20170810190349.jxlp6i7c6q5hpari@sigill.intra.peff.net","subject":"Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-14T18:51:30Z","receivedAt":"2017-08-14T18:51:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Thu, Aug 10, 2017 at 11:58:34AM -0700, Stefan Beller wrote:\n>\n>> On Thu, Aug 10, 2017 at 11:47 AM, Kevin Willford <kcwillford@gmail.com> wrote:\n>> > String formatting can be a performance issue when there are\n>> > hundreds of thousands of trees.\n>> \n>> When changing this for the sake of performance, could you give\n>> an example (which kind of repository you need for this to become\n>> a bottleneck? I presume the large Windows repo? Or can I\n>> reproduce it with a small repo such as linux.git or even git.git?)\n>> and some numbers how this improves the performance?\n>\n> I was about to say the same thing. Normally I don't mind a small\n> optimization without numbers if the result is obviously an improvement.\n>\n> But in this case the result is a lot less readable, and it's not\n> entirely clear to me that it would always be an improvement (we now\n> always run 3 strbuf calls instead of one, and have to check the length\n> for each one).\n>\n> What I'm wondering specifically is if vsnprintf() on Kevin's platform\n> (which I'll assume is Windows) is slow, and we would do better to\n> replace it with a faster compat/ routine.\n\nYeah, I had the same reaction.\n\n"}]}