threads / patch / 46560

patchcache-tree: remove use of strbuf_addf in update_one

Subject: [PATCH] cache-tree: remove use of strbuf_addf in update_one

## tl;dr

7 messages between Aug 10, 2017 and Aug 14, 2017. Diffs are folded; open one to read it.

replies: 6people: 5as markdown or json

Kevin Willford· Aug 10, 2017, 18:47 UTC · lore

String formatting can be a performance issue when there are hundreds of thousands of trees.

Change to stop using the strbuf_addf and just add the strings or characters individually.

There are a limited number of modes so added a switch for the known ones and a default case if something comes through that are not a known one for git.

Signed-off-by: Kevin Willford <kewillf@microsoft.com>
---
 cache-tree.c | 24 +++++++++++++++++++++++-
 1 file changed, 23 insertions(+), 1 deletion(-)
Show changes to cache-tree.c +23 −1
diff --git a/cache-tree.c b/cache-tree.c
index 2440d1dc89..41744b3db7 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -390,7 +390,29 @@ static int update_one(struct cache_tree *it,
 			continue;
 
 		strbuf_grow(&buffer, entlen + 100);
-		strbuf_addf(&buffer, "%o %.*s%c", mode, entlen, path + baselen, '\0');
+
+		switch (mode) {
+		case 0100644:
+			strbuf_add(&buffer, "100644 ", 7);
+			break;
+		case 0100664:
+			strbuf_add(&buffer, "100664 ", 7);
+			break;
+		case 0100755:
+			strbuf_add(&buffer, "100755 ", 7);
+			break;
+		case 0120000:
+			strbuf_add(&buffer, "120000 ", 7);
+			break;
+		case 0160000:
+			strbuf_add(&buffer, "160000 ", 7);
+			break;
+		default:
+			strbuf_addf(&buffer, "%o ", mode);
+			break;
+		}
+		strbuf_add(&buffer, path + baselen, entlen);
+		strbuf_addch(&buffer, '\0');
 		strbuf_add(&buffer, sha1, 20);
 
 #if DEBUG

-- 
2.14.0.rc0.286.g44127d70e4
Stefan Beller· Aug 10, 2017, 18:58 UTC · re: Kevin Willford · lore

Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one

On Thu, Aug 10, 2017 at 11:47 AM, Kevin Willford <kcwillford@gmail.com> wrote:
> String formatting can be a performance issue when there are
> hundreds of thousands of trees.

When changing this for the sake of performance, could you give an example (which kind of repository you need for this to become a bottleneck? I presume the large Windows repo? Or can I reproduce it with a small repo such as linux.git or even git.git?) and some numbers how this improves the performance?

Show 38 quoted lines
> Change to stop using the strbuf_addf and just add the strings
> or characters individually.
>
> There are a limited number of modes so added a switch for the
> known ones and a default case if something comes through that
> are not a known one for git.
>
> Signed-off-by: Kevin Willford <kewillf@microsoft.com>
> ---
>  cache-tree.c | 24 +++++++++++++++++++++++-
>  1 file changed, 23 insertions(+), 1 deletion(-)
>
> diff --git a/cache-tree.c b/cache-tree.c
> index 2440d1dc89..41744b3db7 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -390,7 +390,29 @@ static int update_one(struct cache_tree *it,
>                         continue;
>
>                 strbuf_grow(&buffer, entlen + 100);
> -               strbuf_addf(&buffer, "%o %.*s%c", mode, entlen, path + baselen, '\0');
> +
> +               switch (mode) {
> +               case 0100644:
> +                       strbuf_add(&buffer, "100644 ", 7);
> +                       break;
> +               case 0100664:
> +                       strbuf_add(&buffer, "100664 ", 7);
> +                       break;
> +               case 0100755:
> +                       strbuf_add(&buffer, "100755 ", 7);
> +                       break;
> +               case 0120000:
> +                       strbuf_add(&buffer, "120000 ", 7);
> +                       break;
> +               case 0160000:
> +                       strbuf_add(&buffer, "160000 ", 7);
> +                       break;

Maybe it is worth spelling out the modes in non-numeric, but e.g. S_IFGITLINK.

> +               default:
> +                       strbuf_addf(&buffer, "%o ", mode);

Given the repository you are measuring, maybe we could get away with fewer entries here and only take the 2 or 3 most used entries and special case them?

Or in case this is assumed to be the exhaustive list, we could issue a warning here?

Thanks, Stefan

Jeff King· Aug 10, 2017, 19:03 UTC · re: Stefan Beller · lore

Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one

On Thu, Aug 10, 2017 at 11:58:34AM -0700, Stefan Beller wrote:
Show 9 quoted lines
> On Thu, Aug 10, 2017 at 11:47 AM, Kevin Willford <kcwillford@gmail.com> wrote:
> > String formatting can be a performance issue when there are
> > hundreds of thousands of trees.
> 
> When changing this for the sake of performance, could you give
> an example (which kind of repository you need for this to become
> a bottleneck? I presume the large Windows repo? Or can I
> reproduce it with a small repo such as linux.git or even git.git?)
> and some numbers how this improves the performance?

I was about to say the same thing. Normally I don't mind a small optimization without numbers if the result is obviously an improvement.

But in this case the result is a lot less readable, and it's not entirely clear to me that it would always be an improvement (we now always run 3 strbuf calls instead of one, and have to check the length for each one).

What I'm wondering specifically is if vsnprintf() on Kevin's platform (which I'll assume is Windows) is slow, and we would do better to replace it with a faster compat/ routine.

-Peff
Kevin Willford· Aug 10, 2017, 19:57 UTC · re: Jeff King · lore

Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one

On 8/10/2017 3:03 PM, Jeff King wrote:
Show 23 quoted lines
> On Thu, Aug 10, 2017 at 11:58:34AM -0700, Stefan Beller wrote:
>
>> On Thu, Aug 10, 2017 at 11:47 AM, Kevin Willford <kcwillford@gmail.com> wrote:
>>> String formatting can be a performance issue when there are
>>> hundreds of thousands of trees.
>> When changing this for the sake of performance, could you give
>> an example (which kind of repository you need for this to become
>> a bottleneck? I presume the large Windows repo? Or can I
>> reproduce it with a small repo such as linux.git or even git.git?)
>> and some numbers how this improves the performance?
> I was about to say the same thing. Normally I don't mind a small
> optimization without numbers if the result is obviously an improvement.
>
> But in this case the result is a lot less readable, and it's not
> entirely clear to me that it would always be an improvement (we now
> always run 3 strbuf calls instead of one, and have to check the length
> for each one).
>
> What I'm wondering specifically is if vsnprintf() on Kevin's platform
> (which I'll assume is Windows) is slow, and we would do better to
> replace it with a faster compat/ routine.
>
> -Peff

The strbuf_add call is essentially only having to do a memcpy whereas the strbuf_addf will have to parse the string, determine the types, convert the data, and then get it in the buffer. That could be made faster with a better compat/ routine but I fear still far from the length check and memcpy.

void strbuf_add(struct strbuf *sb, const void *data, size_t len)
{
	strbuf_grow(sb, len);
	memcpy(sb->buf + sb->len, data, len);
	strbuf_setlen(sb, sb->len + len);
}

Here are some of the performance numbers from the windows repo. I will work on writing a perf test for this change so that we have a better idea on smaller repo what the impact of this change is on them.

              | w/o     | with fix |
-----------------------------------
git checkout | 36.08 s | 33.34 s  |
-----------------------------------
git checkout | 32.54 s | 28.26 s  |
-----------------------------------
git checkout | 44.10 s | 38.13 s  |
-----------------------------------
git merge    | 32.90 s | 30.56 s  |
-----------------------------------
git rebase   | 46.14 s | 42.18 s  |
Stefan Beller· Aug 10, 2017, 20:33 UTC · re: Kevin Willford · lore

Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one

On Thu, Aug 10, 2017 at 12:57 PM, Kevin Willford <kcwillford@gmail.com> wrote:
Show 17 quoted lines
> Here are some of the performance numbers from the windows repo.
> I will work on writing a perf test for this change so that we
> have a better idea on smaller repo what the impact of this change
> is on them.
>
>              | w/o     | with fix |
> -----------------------------------
> git checkout | 36.08 s | 33.34 s  |
> -----------------------------------
> git checkout | 32.54 s | 28.26 s  |
> -----------------------------------
> git checkout | 44.10 s | 38.13 s  |
> -----------------------------------
> git merge    | 32.90 s | 30.56 s  |
> -----------------------------------
> git rebase   | 46.14 s | 42.18 s  |
>

~10-15% is impressive for this patch, I certainly did not expect as much. Thanks for providing the numbers!

Stefan
Junio C Hamano· Aug 14, 2017, 18:51 UTC · re: Jeff King · lore

Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one

Jeff King <peff@peff.net> writes:
Show 23 quoted lines
> On Thu, Aug 10, 2017 at 11:58:34AM -0700, Stefan Beller wrote:
>
>> On Thu, Aug 10, 2017 at 11:47 AM, Kevin Willford <kcwillford@gmail.com> wrote:
>> > String formatting can be a performance issue when there are
>> > hundreds of thousands of trees.
>> 
>> When changing this for the sake of performance, could you give
>> an example (which kind of repository you need for this to become
>> a bottleneck? I presume the large Windows repo? Or can I
>> reproduce it with a small repo such as linux.git or even git.git?)
>> and some numbers how this improves the performance?
>
> I was about to say the same thing. Normally I don't mind a small
> optimization without numbers if the result is obviously an improvement.
>
> But in this case the result is a lot less readable, and it's not
> entirely clear to me that it would always be an improvement (we now
> always run 3 strbuf calls instead of one, and have to check the length
> for each one).
>
> What I'm wondering specifically is if vsnprintf() on Kevin's platform
> (which I'll assume is Windows) is slow, and we would do better to
> replace it with a faster compat/ routine.
Yeah, I had the same reaction.
René Scharfe· Aug 11, 2017, 13:08 UTC · re: Kevin Willford · lore

Re: [PATCH] cache-tree: remove use of strbuf_addf in update_one

Am 10.08.2017 um 20:47 schrieb Kevin Willford:
Show 41 quoted lines
> String formatting can be a performance issue when there are
> hundreds of thousands of trees.
> 
> Change to stop using the strbuf_addf and just add the strings
> or characters individually.
> 
> There are a limited number of modes so added a switch for the
> known ones and a default case if something comes through that
> are not a known one for git.
> 
> Signed-off-by: Kevin Willford <kewillf@microsoft.com>
> ---
>   cache-tree.c | 24 +++++++++++++++++++++++-
>   1 file changed, 23 insertions(+), 1 deletion(-)
> 
> diff --git a/cache-tree.c b/cache-tree.c
> index 2440d1dc89..41744b3db7 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -390,7 +390,29 @@ static int update_one(struct cache_tree *it,
>   			continue;
>   
>   		strbuf_grow(&buffer, entlen + 100);
> -		strbuf_addf(&buffer, "%o %.*s%c", mode, entlen, path + baselen, '\0');
> +
> +		switch (mode) {
> +		case 0100644:
> +			strbuf_add(&buffer, "100644 ", 7);
> +			break;
> +		case 0100664:
> +			strbuf_add(&buffer, "100664 ", 7);
> +			break;
> +		case 0100755:
> +			strbuf_add(&buffer, "100755 ", 7);
> +			break;
> +		case 0120000:
> +			strbuf_add(&buffer, "120000 ", 7);
> +			break;
> +		case 0160000:
> +			strbuf_add(&buffer, "160000 ", 7);
> +			break;

You can avoid specifying the string length by using strbuf_addstr. The compiler can determine that value; the resulting object code should be the same with -O2.

Show 6 quoted lines
> +		default:
> +			strbuf_addf(&buffer, "%o ", mode);
> +			break;
> +		}
> +		strbuf_add(&buffer, path + baselen, entlen);
> +		strbuf_addch(&buffer, '\0');

How much of the performance improvement is due to these two (especially %.*s)? Looking forward to the perf script to find out myself. :)

>   		strbuf_add(&buffer, sha1, 20);
>   
>   #if DEBUG
>

← back to recent threads