git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH] cat-file: skip expanding default format
@ 2022-03-04 21:37 John Cai via GitGitGadget
  2022-03-07  5:56 ` Junio C Hamano
                   ` (2 more replies)
  0 siblings, 3 replies; 17+ messages in thread
From: John Cai via GitGitGadget @ 2022-03-04 21:37 UTC (permalink / raw)
  To: git; +Cc: John Cai, John Cai

From: John Cai <johncai86@gmail.com>

When format is passed into --batch, --batch-check, --batch-command,
the format gets expanded. When nothing is passed in, the default format
is set and the expand_format() gets called.

We can save on these cycles by hardcoding how to print the
information when nothing is passed as the format, or when the default
format is passed. There is no need for the fully expanded format with
the default. Since batch_object_write() happens on every object provided
in batch mode, we get a nice performance improvement.

git rev-list --all > /tmp/all-obj.txt

git cat-file --batch-check </tmp/all-obj.txt

with HEAD^:

Time (mean ± σ): 57.6 ms ± 1.7 ms [User: 51.5 ms, System: 6.2 ms]
Range (min … max): 54.6 ms … 64.7 ms 50 runs

with HEAD:

Time (mean ± σ): 49.8 ms ± 1.7 ms [User: 42.6 ms, System: 7.3 ms]
Range (min … max): 46.9 ms … 55.9 ms 56 runs

If nothing is provided as a format argument, or if the default format is
passed, skip expanding of the format and print the object info with a
default format.

Based-on-patch-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: John Cai <johncai86@gmail.com>

See https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/
---
    optimize cat file batch info writing
    
    When cat-file --batch or --batch-check is used, we can skip having to
    expand the format if no format is specified or if the default format is
    specified. In this case we know exactly how to print the objects without
    the full expanded format.
    
    This was first discussed in [1].
    
    We get a little performance boost from this optimization because this
    happens for each objects provided to --batch, --batch-check, or
    --batch-command. Because batch_object_write() is called on every oid
    provided in batch mode, this optimization adds up when a large number of
    oid info is printed.
    
    git rev-list --all >/tmp/all-objs.txt
    
    git cat-file --batch-check </tmp/all-obj.txt (with hyperfine)
    
    run on origin/master:
    
    Time (mean ± σ): 57.6 ms ± 1.7 ms [User: 51.5 ms, System: 6.2 ms] Range
    (min … max): 54.6 ms … 64.7 ms 50 runs
    
    run on jc/optimize-cat-file-batch-default-format:
    
    Time (mean ± σ): 49.8 ms ± 1.7 ms [User: 42.6 ms, System: 7.3 ms] Range
    (min … max): 46.9 ms … 55.9 ms 56 runs
    
     1. https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1221%2Fjohn-cai%2Fjc%2Foptimize-cat-file-batch-default-format-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1221/john-cai/jc/optimize-cat-file-batch-default-format-v1
Pull-Request: https://github.com/git/git/pull/1221

 builtin/cat-file.c       | 39 +++++++++++++++++++++++++++++++++------
 t/perf/p1006-cat-file.sh | 16 ++++++++++++++++
 2 files changed, 49 insertions(+), 6 deletions(-)
 create mode 100755 t/perf/p1006-cat-file.sh

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index 7b3f42950ec..6a337941638 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -17,6 +17,7 @@
 #include "object-store.h"
 #include "promisor-remote.h"
 
+static const char *default_format = "%(objectname) %(objecttype) %(objectsize)";
 struct batch_options {
 	int enabled;
 	int follow_symlinks;
@@ -351,6 +352,14 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
 	}
 }
 
+static void print_default_format(char *buf, int len, struct expand_data *data)
+{
+	snprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
+		 data->info.type_name->buf,
+		 (uintmax_t)*data->info.sizep);
+
+}
+
 /*
  * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
  * which the object may be accessed (though note that we may also rely on
@@ -363,6 +372,12 @@ static void batch_object_write(const char *obj_name,
 			       struct packed_git *pack,
 			       off_t offset)
 {
+	const char *fmt;
+
+	struct strbuf type_name = STRBUF_INIT;
+	if (!opt->format)
+		data->info.type_name = &type_name;
+
 	if (!data->skip_object_info) {
 		int ret;
 
@@ -377,12 +392,21 @@ static void batch_object_write(const char *obj_name,
 			printf("%s missing\n",
 			       obj_name ? obj_name : oid_to_hex(&data->oid));
 			fflush(stdout);
-			return;
+			goto cleanup;
 		}
 	}
 
+	if (!opt->format && !opt->print_contents) {
+		char buf[1024];
+
+		print_default_format(buf, 1024, data);
+		batch_write(opt, buf, strlen(buf));
+		goto cleanup;
+	}
+
+	fmt = opt->format ? opt->format : default_format;
 	strbuf_reset(scratch);
-	strbuf_expand(scratch, opt->format, expand_format, data);
+	strbuf_expand(scratch, fmt, expand_format, data);
 	strbuf_addch(scratch, '\n');
 	batch_write(opt, scratch->buf, scratch->len);
 
@@ -390,8 +414,12 @@ static void batch_object_write(const char *obj_name,
 		print_object_or_die(opt, data);
 		batch_write(opt, "\n", 1);
 	}
+
+cleanup:
+	strbuf_release(&type_name);
 }
 
+
 static void batch_one_object(const char *obj_name,
 			     struct strbuf *scratch,
 			     struct batch_options *opt,
@@ -515,9 +543,7 @@ static int batch_objects(struct batch_options *opt)
 	struct expand_data data;
 	int save_warning;
 	int retval = 0;
-
-	if (!opt->format)
-		opt->format = "%(objectname) %(objecttype) %(objectsize)";
+	const char *fmt;
 
 	/*
 	 * Expand once with our special mark_query flag, which will prime the
@@ -526,7 +552,8 @@ static int batch_objects(struct batch_options *opt)
 	 */
 	memset(&data, 0, sizeof(data));
 	data.mark_query = 1;
-	strbuf_expand(&output, opt->format, expand_format, &data);
+	fmt = opt->format ? opt->format : default_format;
+	strbuf_expand(&output, fmt, expand_format, &data);
 	data.mark_query = 0;
 	strbuf_release(&output);
 	if (opt->cmdmode)
diff --git a/t/perf/p1006-cat-file.sh b/t/perf/p1006-cat-file.sh
new file mode 100755
index 00000000000..e463623f5a3
--- /dev/null
+++ b/t/perf/p1006-cat-file.sh
@@ -0,0 +1,16 @@
+#!/bin/sh
+
+test_description='Basic sort performance tests'
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+test_expect_success 'setup' '
+	git rev-list --all >rla
+'
+
+test_perf 'cat-file --batch-check' '
+	git cat-file --batch-check <rla
+'
+
+test_done

base-commit: 715d08a9e51251ad8290b181b6ac3b9e1f9719d7
-- 
gitgitgadget

^ permalink raw reply related	[flat|nested] 17+ messages in thread

* Re: [PATCH] cat-file: skip expanding default format
  2022-03-04 21:37 [PATCH] cat-file: skip expanding default format John Cai via GitGitGadget
@ 2022-03-07  5:56 ` Junio C Hamano
  2022-03-07  6:11   ` Junio C Hamano
  2022-03-07 12:15 ` Ævar Arnfjörð Bjarmason
  2022-03-08  2:54 ` [PATCH v2] " John Cai via GitGitGadget
  2 siblings, 1 reply; 17+ messages in thread
From: Junio C Hamano @ 2022-03-07  5:56 UTC (permalink / raw)
  To: John Cai via GitGitGadget; +Cc: git, John Cai

"John Cai via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: John Cai <johncai86@gmail.com>
>
> When format is passed into --batch, --batch-check, --batch-command,
> the format gets expanded. When nothing is passed in, the default format
> is set and the expand_format() gets called.
>
> We can save on these cycles by hardcoding how to print the
> information when nothing is passed as the format, or when the default
> format is passed. There is no need for the fully expanded format with
> the default. Since batch_object_write() happens on every object provided
> in batch mode, we get a nice performance improvement.

That is OK in principle, but ...

> +	if (!opt->format && !opt->print_contents) {
> +		char buf[1024];
> +
> +		print_default_format(buf, 1024, data);
> +		batch_write(opt, buf, strlen(buf));
> +		goto cleanup;
> +	}
> +
> +	fmt = opt->format ? opt->format : default_format;

... instead of doing this, wouldn't it be nicer to base the decision
to call print_default_format() on purely the contents of the format,
i.e.

	fmt = opt->format ? opt->format : default_format;
	if (!strcmp(fmt, DEFAULT_FORMAT) && !opt->print_contents) {
		... the above print_default_format() call block here ...
		goto cleanup;
	}

where DEFAULT_FORMAT is 

#define DEFAULT_FORMAT = "%(objectname) %(objecttype) %(objectsize)"

and

> @@ -515,9 +543,7 @@ static int batch_objects(struct batch_options *opt)
>  	struct expand_data data;
>  	int save_warning;
>  	int retval = 0;
> -
> -	if (!opt->format)
> -		opt->format = "%(objectname) %(objecttype) %(objectsize)";

retain the defaulting with

	if (!opt->format)
		opt->format = DEFAULT_FORMAT;

instead of making opt->format == NULL to mean something special?

That way, even if the user-input happens to name the format that is
identical to DEFAULT_FORMAT, because we only care what the format
is, and not where the format comes from, we will get the same
optimization.  Wouldn't it make more sense?


^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] cat-file: skip expanding default format
  2022-03-07  5:56 ` Junio C Hamano
@ 2022-03-07  6:11   ` Junio C Hamano
  2022-03-07 17:41     ` John Cai
  0 siblings, 1 reply; 17+ messages in thread
From: Junio C Hamano @ 2022-03-07  6:11 UTC (permalink / raw)
  To: John Cai via GitGitGadget; +Cc: git, John Cai

Junio C Hamano <gitster@pobox.com> writes:

> "John Cai via GitGitGadget" <gitgitgadget@gmail.com> writes:
>
>> From: John Cai <johncai86@gmail.com>
>>
>> When format is passed into --batch, --batch-check, --batch-command,
>> the format gets expanded. When nothing is passed in, the default format
>> is set and the expand_format() gets called.
>>
>> We can save on these cycles by hardcoding how to print the
>> information when nothing is passed as the format, or when the default
>> format is passed. There is no need for the fully expanded format with
>> the default. Since batch_object_write() happens on every object provided
>> in batch mode, we get a nice performance improvement.
>
> That is OK in principle, but ...
>
>> +	if (!opt->format && !opt->print_contents) {
>> +		char buf[1024];
>> +
>> +		print_default_format(buf, 1024, data);
>> +		batch_write(opt, buf, strlen(buf));
>> +		goto cleanup;
>> +	}
>> +
>> +	fmt = opt->format ? opt->format : default_format;
>
> ... instead of doing this, wouldn't it be nicer to base the decision
> to call print_default_format() on purely the contents of the format,
> i.e.
>
> 	fmt = opt->format ? opt->format : default_format;
> 	if (!strcmp(fmt, DEFAULT_FORMAT) && !opt->print_contents) {
> 		... the above print_default_format() call block here ...
> 		goto cleanup;
> 	}
>
> where DEFAULT_FORMAT is 
>
> #define DEFAULT_FORMAT = "%(objectname) %(objecttype) %(objectsize)"
>
> and
>
>> @@ -515,9 +543,7 @@ static int batch_objects(struct batch_options *opt)
>>  	struct expand_data data;
>>  	int save_warning;
>>  	int retval = 0;
>> -
>> -	if (!opt->format)
>> -		opt->format = "%(objectname) %(objecttype) %(objectsize)";
>
> retain the defaulting with
>
> 	if (!opt->format)
> 		opt->format = DEFAULT_FORMAT;
>
> instead of making opt->format == NULL to mean something special?
>
> That way, even if the user-input happens to name the format that is
> identical to DEFAULT_FORMAT, because we only care what the format
> is, and not where the format comes from, we will get the same
> optimization.  Wouldn't it make more sense?

Actually, doing that literally and naively would not be a good idea,
as the special case code is inside batch_object_write() that is
called once per each object, and because the format used will not
change for each call, doing strcmp() every time is wasteful.  The
same is true for

	fmt = opt->format ? opt->format : default_format;

as opt->format will not change across calls to this function.

So, if we were to do this optimization:

 * we key on the fact that opt->format is NULL to trigger the
   optimization inside batch_object_write(), so that we do not have
   to strcmp(DEFAULT_FORMAT, fmt) for each and every object.

 * a while loop in batch_objects() or for_each_*_object() calls is
   what calls batch_object_write() for each object.  So somewhere
   early in that function (or before we enter the function), we can
   check opt->format and

    - if it is NULL, we can leave it NULL.
    - if it is the same as DEFAULT_FORMAT, clear it to NULL.

   so that the optimization in batch_object_write() can cheaply kick
   in.

would be a good way to go, perhaps?

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] cat-file: skip expanding default format
  2022-03-04 21:37 [PATCH] cat-file: skip expanding default format John Cai via GitGitGadget
  2022-03-07  5:56 ` Junio C Hamano
@ 2022-03-07 12:15 ` Ævar Arnfjörð Bjarmason
  2022-03-08  2:54 ` [PATCH v2] " John Cai via GitGitGadget
  2 siblings, 0 replies; 17+ messages in thread
From: Ævar Arnfjörð Bjarmason @ 2022-03-07 12:15 UTC (permalink / raw)
  To: John Cai via GitGitGadget; +Cc: git, John Cai


On Fri, Mar 04 2022, John Cai via GitGitGadget wrote:

> From: John Cai <johncai86@gmail.com>
>
> When format is passed into --batch, --batch-check, --batch-command,
> the format gets expanded. When nothing is passed in, the default format
> is set and the expand_format() gets called.
>
> We can save on these cycles by hardcoding how to print the
> information when nothing is passed as the format, or when the default
> format is passed. There is no need for the fully expanded format with
> the default. Since batch_object_write() happens on every object provided
> in batch mode, we get a nice performance improvement.
>
> git rev-list --all > /tmp/all-obj.txt
>
> git cat-file --batch-check </tmp/all-obj.txt
>
> with HEAD^:
>
> Time (mean ± σ): 57.6 ms ± 1.7 ms [User: 51.5 ms, System: 6.2 ms]
> Range (min … max): 54.6 ms … 64.7 ms 50 runs
>
> with HEAD:
>
> Time (mean ± σ): 49.8 ms ± 1.7 ms [User: 42.6 ms, System: 7.3 ms]
> Range (min … max): 46.9 ms … 55.9 ms 56 runs
>
> If nothing is provided as a format argument, or if the default format is
> passed, skip expanding of the format and print the object info with a
> default format.
>
> Based-on-patch-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>

Nit: I think it's probably better to just add a Signed-off-by here for
me instead to indicate that it's originally based on my crappy WIP code
(but most of what you've got here is thoroughly yours & better).

> Signed-off-by: John Cai <johncai86@gmail.com>
> [...]
> +static void print_default_format(char *buf, int len, struct expand_data *data)
> +{
> +	snprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
> +		 data->info.type_name->buf,
> +		 (uintmax_t)*data->info.sizep);
> +
> +}
> +
>  /*
>   * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
>   * which the object may be accessed (though note that we may also rely on
> @@ -363,6 +372,12 @@ static void batch_object_write(const char *obj_name,
>  			       struct packed_git *pack,
>  			       off_t offset)
>  {
> +	const char *fmt;
> +
> +	struct strbuf type_name = STRBUF_INIT;
> +	if (!opt->format)
> +		data->info.type_name = &type_name;
> +
>  	if (!data->skip_object_info) {
>  		int ret;
>  
> @@ -377,12 +392,21 @@ static void batch_object_write(const char *obj_name,
>  			printf("%s missing\n",
>  			       obj_name ? obj_name : oid_to_hex(&data->oid));
>  			fflush(stdout);
> -			return;
> +			goto cleanup;
>  		}
>  	}
>  
> +	if (!opt->format && !opt->print_contents) {
> +		char buf[1024];
> +
> +		print_default_format(buf, 1024, data);
> +		batch_write(opt, buf, strlen(buf));

Just a nit (Junio comment on most of the rest), for something that's an
optimization patch we shouldn't ever need to do strlen() here, since we
just called snprintf(), let's just use its return value instead.

I also think that in this case you'll want xsnprintf(), and if not this
code is buggy & needs to check the return value (but let's just use x*()
...).

FWIW snprintf() relly should be in a mostly-banned.h, but we only have
the blanket banned.h, and there's a few legitimate uses of it :)

(And yes, this is all probably commentary on my own bugs in some WIP
code, but at this point I honestly can't remember & didn't look it up)

Thanks for hacking on this & carrying it forward!

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH] cat-file: skip expanding default format
  2022-03-07  6:11   ` Junio C Hamano
@ 2022-03-07 17:41     ` John Cai
  0 siblings, 0 replies; 17+ messages in thread
From: John Cai @ 2022-03-07 17:41 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: John Cai via GitGitGadget, git

Hi Junio,

On 7 Mar 2022, at 1:11, Junio C Hamano wrote:

> Junio C Hamano <gitster@pobox.com> writes:
>
>> "John Cai via GitGitGadget" <gitgitgadget@gmail.com> writes:
>>
>>> From: John Cai <johncai86@gmail.com>
>>>
>>> When format is passed into --batch, --batch-check, --batch-command,
>>> the format gets expanded. When nothing is passed in, the default format
>>> is set and the expand_format() gets called.
>>>
>>> We can save on these cycles by hardcoding how to print the
>>> information when nothing is passed as the format, or when the default
>>> format is passed. There is no need for the fully expanded format with
>>> the default. Since batch_object_write() happens on every object provided
>>> in batch mode, we get a nice performance improvement.
>>
>> That is OK in principle, but ...
>>
>>> +	if (!opt->format && !opt->print_contents) {
>>> +		char buf[1024];
>>> +
>>> +		print_default_format(buf, 1024, data);
>>> +		batch_write(opt, buf, strlen(buf));
>>> +		goto cleanup;
>>> +	}
>>> +
>>> +	fmt = opt->format ? opt->format : default_format;
>>
>> ... instead of doing this, wouldn't it be nicer to base the decision
>> to call print_default_format() on purely the contents of the format,
>> i.e.
>>
>> 	fmt = opt->format ? opt->format : default_format;
>> 	if (!strcmp(fmt, DEFAULT_FORMAT) && !opt->print_contents) {
>> 		... the above print_default_format() call block here ...
>> 		goto cleanup;
>> 	}
>>
>> where DEFAULT_FORMAT is
>>
>> #define DEFAULT_FORMAT = "%(objectname) %(objecttype) %(objectsize)"
>>
>> and
>>
>>> @@ -515,9 +543,7 @@ static int batch_objects(struct batch_options *opt)
>>>  	struct expand_data data;
>>>  	int save_warning;
>>>  	int retval = 0;
>>> -
>>> -	if (!opt->format)
>>> -		opt->format = "%(objectname) %(objecttype) %(objectsize)";
>>
>> retain the defaulting with
>>
>> 	if (!opt->format)
>> 		opt->format = DEFAULT_FORMAT;
>>
>> instead of making opt->format == NULL to mean something special?
>>
>> That way, even if the user-input happens to name the format that is
>> identical to DEFAULT_FORMAT, because we only care what the format
>> is, and not where the format comes from, we will get the same
>> optimization.  Wouldn't it make more sense?
>
> Actually, doing that literally and naively would not be a good idea,
> as the special case code is inside batch_object_write() that is
> called once per each object, and because the format used will not
> change for each call, doing strcmp() every time is wasteful.  The
> same is true for
>
> 	fmt = opt->format ? opt->format : default_format;
>
> as opt->format will not change across calls to this function.
>
> So, if we were to do this optimization:
>
>  * we key on the fact that opt->format is NULL to trigger the
>    optimization inside batch_object_write(), so that we do not have
>    to strcmp(DEFAULT_FORMAT, fmt) for each and every object.
>
>  * a while loop in batch_objects() or for_each_*_object() calls is
>    what calls batch_object_write() for each object.  So somewhere
>    early in that function (or before we enter the function), we can
>    check opt->format and
>
>     - if it is NULL, we can leave it NULL.
>     - if it is the same as DEFAULT_FORMAT, clear it to NULL.
>
>    so that the optimization in batch_object_write() can cheaply kick
>    in.
>
> would be a good way to go, perhaps?

thanks for looking into this. Yeah, I think the approach you outlined makes
sense for the reasons given.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* [PATCH v2] cat-file: skip expanding default format
  2022-03-04 21:37 [PATCH] cat-file: skip expanding default format John Cai via GitGitGadget
  2022-03-07  5:56 ` Junio C Hamano
  2022-03-07 12:15 ` Ævar Arnfjörð Bjarmason
@ 2022-03-08  2:54 ` John Cai via GitGitGadget
  2022-03-08 16:59   ` Junio C Hamano
                     ` (2 more replies)
  2 siblings, 3 replies; 17+ messages in thread
From: John Cai via GitGitGadget @ 2022-03-08  2:54 UTC (permalink / raw)
  To: git; +Cc: Ævar Arnfjörð Bjarmason, John Cai, John Cai

From: John Cai <johncai86@gmail.com>

When format is passed into --batch, --batch-check, --batch-command,
the format gets expanded. When nothing is passed in, the default format
is set and the expand_format() gets called.

We can save on these cycles by hardcoding how to print the
information when nothing is passed as the format, or when the default
format is passed. There is no need for the fully expanded format with
the default. Since batch_object_write() happens on every object provided
in batch mode, we get a nice performance improvement.

git rev-list --all > /tmp/all-obj.txt

git cat-file --batch-check </tmp/all-obj.txt

with HEAD^:

Time (mean ± σ): 57.6 ms ± 1.7 ms [User: 51.5 ms, System: 6.2 ms]
Range (min … max): 54.6 ms … 64.7 ms 50 runs

with HEAD:

Time (mean ± σ): 49.8 ms ± 1.7 ms [User: 42.6 ms, System: 7.3 ms]
Range (min … max): 46.9 ms … 55.9 ms 56 runs

If nothing is provided as a format argument, or if the default format is
passed, skip expanding of the format and print the object info with a
default format.

See https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: John Cai <johncai86@gmail.com>
---
    optimize cat file batch info writing
    
    When cat-file --batch or --batch-check is used, we can skip having to
    expand the format if no format is specified or if the default format is
    specified. In this case we know exactly how to print the objects without
    the full expanded format.
    
    This was first discussed in [1].
    
    We get a little performance boost from this optimization because this
    happens for each objects provided to --batch, --batch-check, or
    --batch-command. Because batch_object_write() is called on every oid
    provided in batch mode, this optimization adds up when a large number of
    oid info is printed.
    
    git rev-list --all >/tmp/all-objs.txt
    
    git cat-file --batch-check </tmp/all-obj.txt (with hyperfine)
    
    run on origin/master:
    
    Time (mean ± σ): 57.6 ms ± 1.7 ms [User: 51.5 ms, System: 6.2 ms] Range
    (min … max): 54.6 ms … 64.7 ms 50 runs
    
    run on jc/optimize-cat-file-batch-default-format:
    
    Time (mean ± σ): 49.8 ms ± 1.7 ms [User: 42.6 ms, System: 7.3 ms] Range
    (min … max): 46.9 ms … 55.9 ms 56 runs
    
    Changes since v1:
    
     * set opt->format in batch_objects so that the loop that prints objects
       only has to check if the format is null to know to print the object
       info in the default format
     * fixed up commit trailer to include Ævar as Signed-off-by
    
     1. https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1221%2Fjohn-cai%2Fjc%2Foptimize-cat-file-batch-default-format-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1221/john-cai/jc/optimize-cat-file-batch-default-format-v2
Pull-Request: https://github.com/git/git/pull/1221

Range-diff vs v1:

 1:  9f659b36c8f ! 1:  f5d578d14a9 cat-file: skip expanding default format
     @@ Commit message
          passed, skip expanding of the format and print the object info with a
          default format.
      
     -    Based-on-patch-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
     -    Signed-off-by: John Cai <johncai86@gmail.com>
     -
          See https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/
      
     +    Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
     +    Signed-off-by: John Cai <johncai86@gmail.com>
     +
       ## builtin/cat-file.c ##
     -@@
     - #include "object-store.h"
     - #include "promisor-remote.h"
     - 
     -+static const char *default_format = "%(objectname) %(objecttype) %(objectsize)";
     - struct batch_options {
     - 	int enabled;
     - 	int follow_symlinks;
      @@ builtin/cat-file.c: static void print_object_or_die(struct batch_options *opt, struct expand_data *d
       	}
       }
       
     -+static void print_default_format(char *buf, int len, struct expand_data *data)
     ++static int print_default_format(char *buf, int len, struct expand_data *data)
      +{
     -+	snprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
     ++	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
      +		 data->info.type_name->buf,
      +		 (uintmax_t)*data->info.sizep);
      +
     @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
       			       struct packed_git *pack,
       			       off_t offset)
       {
     -+	const char *fmt;
     -+
      +	struct strbuf type_name = STRBUF_INIT;
     ++
      +	if (!opt->format)
      +		data->info.type_name = &type_name;
      +
     @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
       		}
       	}
       
     -+	if (!opt->format && !opt->print_contents) {
     +-	strbuf_reset(scratch);
     +-	strbuf_expand(scratch, opt->format, expand_format, data);
     +-	strbuf_addch(scratch, '\n');
     +-	batch_write(opt, scratch->buf, scratch->len);
     ++	if (!opt->format) {
      +		char buf[1024];
     -+
     -+		print_default_format(buf, 1024, data);
     -+		batch_write(opt, buf, strlen(buf));
     -+		goto cleanup;
     ++		int len = print_default_format(buf, 1024, data);
     ++		batch_write(opt, buf, len);
     ++	} else {
     ++		strbuf_reset(scratch);
     ++		strbuf_expand(scratch, opt->format, expand_format, data);
     ++		strbuf_addch(scratch, '\n');
     ++		batch_write(opt, scratch->buf, scratch->len);
      +	}
     -+
     -+	fmt = opt->format ? opt->format : default_format;
     - 	strbuf_reset(scratch);
     --	strbuf_expand(scratch, opt->format, expand_format, data);
     -+	strbuf_expand(scratch, fmt, expand_format, data);
     - 	strbuf_addch(scratch, '\n');
     - 	batch_write(opt, scratch->buf, scratch->len);
       
     -@@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
     + 	if (opt->print_contents) {
       		print_object_or_die(opt, data);
       		batch_write(opt, "\n", 1);
       	}
     @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
       static void batch_one_object(const char *obj_name,
       			     struct strbuf *scratch,
       			     struct batch_options *opt,
     +@@ builtin/cat-file.c: static int batch_unordered_packed(const struct object_id *oid,
     + 				      data);
     + }
     + 
     ++
     ++#define DEFAULT_FORMAT "%(objectname) %(objecttype) %(objectsize)"
     ++
     + static int batch_objects(struct batch_options *opt)
     + {
     + 	struct strbuf input = STRBUF_INIT;
      @@ builtin/cat-file.c: static int batch_objects(struct batch_options *opt)
     - 	struct expand_data data;
       	int save_warning;
       	int retval = 0;
     --
     + 
      -	if (!opt->format)
      -		opt->format = "%(objectname) %(objecttype) %(objectsize)";
     -+	const char *fmt;
     - 
     +-
       	/*
       	 * Expand once with our special mark_query flag, which will prime the
     + 	 * object_info to be handed to oid_object_info_extended for each
      @@ builtin/cat-file.c: static int batch_objects(struct batch_options *opt)
       	 */
       	memset(&data, 0, sizeof(data));
       	data.mark_query = 1;
      -	strbuf_expand(&output, opt->format, expand_format, &data);
     -+	fmt = opt->format ? opt->format : default_format;
     -+	strbuf_expand(&output, fmt, expand_format, &data);
     ++	strbuf_expand(&output,
     ++		      opt->format ? opt->format : DEFAULT_FORMAT,
     ++		      expand_format,
     ++		      &data);
       	data.mark_query = 0;
       	strbuf_release(&output);
       	if (opt->cmdmode)
     + 		data.split_on_whitespace = 1;
     + 
     ++	if (opt->format && !strcmp(opt->format, DEFAULT_FORMAT))
     ++		opt->format = NULL;
     + 	/*
     + 	 * If we are printing out the object, then always fill in the type,
     + 	 * since we will want to decide whether or not to stream.
      
       ## t/perf/p1006-cat-file.sh (new) ##
      @@


 builtin/cat-file.c       | 46 ++++++++++++++++++++++++++++++++--------
 t/perf/p1006-cat-file.sh | 16 ++++++++++++++
 2 files changed, 53 insertions(+), 9 deletions(-)
 create mode 100755 t/perf/p1006-cat-file.sh

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index 7b3f42950ec..ab9a49e13a4 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -351,6 +351,14 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
 	}
 }
 
+static int print_default_format(char *buf, int len, struct expand_data *data)
+{
+	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
+		 data->info.type_name->buf,
+		 (uintmax_t)*data->info.sizep);
+
+}
+
 /*
  * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
  * which the object may be accessed (though note that we may also rely on
@@ -363,6 +371,11 @@ static void batch_object_write(const char *obj_name,
 			       struct packed_git *pack,
 			       off_t offset)
 {
+	struct strbuf type_name = STRBUF_INIT;
+
+	if (!opt->format)
+		data->info.type_name = &type_name;
+
 	if (!data->skip_object_info) {
 		int ret;
 
@@ -377,21 +390,31 @@ static void batch_object_write(const char *obj_name,
 			printf("%s missing\n",
 			       obj_name ? obj_name : oid_to_hex(&data->oid));
 			fflush(stdout);
-			return;
+			goto cleanup;
 		}
 	}
 
-	strbuf_reset(scratch);
-	strbuf_expand(scratch, opt->format, expand_format, data);
-	strbuf_addch(scratch, '\n');
-	batch_write(opt, scratch->buf, scratch->len);
+	if (!opt->format) {
+		char buf[1024];
+		int len = print_default_format(buf, 1024, data);
+		batch_write(opt, buf, len);
+	} else {
+		strbuf_reset(scratch);
+		strbuf_expand(scratch, opt->format, expand_format, data);
+		strbuf_addch(scratch, '\n');
+		batch_write(opt, scratch->buf, scratch->len);
+	}
 
 	if (opt->print_contents) {
 		print_object_or_die(opt, data);
 		batch_write(opt, "\n", 1);
 	}
+
+cleanup:
+	strbuf_release(&type_name);
 }
 
+
 static void batch_one_object(const char *obj_name,
 			     struct strbuf *scratch,
 			     struct batch_options *opt,
@@ -508,6 +531,9 @@ static int batch_unordered_packed(const struct object_id *oid,
 				      data);
 }
 
+
+#define DEFAULT_FORMAT "%(objectname) %(objecttype) %(objectsize)"
+
 static int batch_objects(struct batch_options *opt)
 {
 	struct strbuf input = STRBUF_INIT;
@@ -516,9 +542,6 @@ static int batch_objects(struct batch_options *opt)
 	int save_warning;
 	int retval = 0;
 
-	if (!opt->format)
-		opt->format = "%(objectname) %(objecttype) %(objectsize)";
-
 	/*
 	 * Expand once with our special mark_query flag, which will prime the
 	 * object_info to be handed to oid_object_info_extended for each
@@ -526,12 +549,17 @@ static int batch_objects(struct batch_options *opt)
 	 */
 	memset(&data, 0, sizeof(data));
 	data.mark_query = 1;
-	strbuf_expand(&output, opt->format, expand_format, &data);
+	strbuf_expand(&output,
+		      opt->format ? opt->format : DEFAULT_FORMAT,
+		      expand_format,
+		      &data);
 	data.mark_query = 0;
 	strbuf_release(&output);
 	if (opt->cmdmode)
 		data.split_on_whitespace = 1;
 
+	if (opt->format && !strcmp(opt->format, DEFAULT_FORMAT))
+		opt->format = NULL;
 	/*
 	 * If we are printing out the object, then always fill in the type,
 	 * since we will want to decide whether or not to stream.
diff --git a/t/perf/p1006-cat-file.sh b/t/perf/p1006-cat-file.sh
new file mode 100755
index 00000000000..e463623f5a3
--- /dev/null
+++ b/t/perf/p1006-cat-file.sh
@@ -0,0 +1,16 @@
+#!/bin/sh
+
+test_description='Basic sort performance tests'
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+test_expect_success 'setup' '
+	git rev-list --all >rla
+'
+
+test_perf 'cat-file --batch-check' '
+	git cat-file --batch-check <rla
+'
+
+test_done

base-commit: 715d08a9e51251ad8290b181b6ac3b9e1f9719d7
-- 
gitgitgadget

^ permalink raw reply related	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] cat-file: skip expanding default format
  2022-03-08  2:54 ` [PATCH v2] " John Cai via GitGitGadget
@ 2022-03-08 16:59   ` Junio C Hamano
  2022-03-08 19:01     ` John Cai
  2022-03-08 22:00   ` Taylor Blau
  2022-03-08 22:08   ` [PATCH v3] " John Cai via GitGitGadget
  2 siblings, 1 reply; 17+ messages in thread
From: Junio C Hamano @ 2022-03-08 16:59 UTC (permalink / raw)
  To: John Cai via GitGitGadget
  Cc: git, Ævar Arnfjörð Bjarmason, John Cai

"John Cai via GitGitGadget" <gitgitgadget@gmail.com> writes:

> diff --git a/builtin/cat-file.c b/builtin/cat-file.c
> index 7b3f42950ec..ab9a49e13a4 100644
> --- a/builtin/cat-file.c
> +++ b/builtin/cat-file.c
> @@ -351,6 +351,14 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
>  	}
>  }
>  
> +static int print_default_format(char *buf, int len, struct expand_data *data)
> +{
> +	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
> +		 data->info.type_name->buf,
> +		 (uintmax_t)*data->info.sizep);
> +
> +}

OK.  We want size and type if we were to show the default output out
of the object-info API.

>  /*
>   * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
>   * which the object may be accessed (though note that we may also rely on
> @@ -363,6 +371,11 @@ static void batch_object_write(const char *obj_name,
>  			       struct packed_git *pack,
>  			       off_t offset)
>  {
> +	struct strbuf type_name = STRBUF_INIT;
> +
> +	if (!opt->format)
> +		data->info.type_name = &type_name;

And at this point, !opt->format means we would use the default
format, so we cannot leave .type_name member NULL.  That is OK
but puzzling.  Why didn't we need this before?

If the caller is batch_objects(), there is the "mark_query" call to
strbuf_expand() to learn which field in data->info are needed, so
it seems that this new code should NOT be necessary.

    Side note.  I briefly wondered if this expand is something you
    would want to optimize when the default format is used, but this
    is just "probe just once to ensure various members of data->info
    are populated, to prepare for showing hundreds of objects in the
    batch request", so it probably is not worth it.

I am guessing that this is for callers that do not come via
batch_objects() where the "mark_query" strbuf_expand() is not made?
If so,

 * why is it sufficient to fill .type_name and not .sizep for the
   default format (i.e. when opt->format is NULL)?

 * why is it OK not to do anything for non-default format?  If no
   "mark_query" call has been made, we wouldn't be preparing the
   .type_name field even if the user-supplied format calls for
   %(objecttype), would we?

Looking at the call graph:

 - batch_object_write() is called by
   - batch_one_object()
   - batch_object_cb()
   - batch_unordered_object()

 - batch_one_object() is called only by batch_objects()
 - batch_object_cb() is used only by batch_objects()

 - batch_unordered_object() is called by
   - batch_unordered_loose()
   - batch_unordered_packed()
   and these two are called only by batch_objects()

And the "mark_query" strbuf_expand() to probe which members in
expand_data are are necessary is done very early, before any of the
calls batch_objects() makes that reach batch_object_write().

OK, so my initial guess that the new "we need .type_name member to
point at a strbuf" is because there are some code that bypasses the
"mark_query" strbuf_expand() in batch_objects() is totally wrong.
Everybody uses the "mark_query" thing.  Then why do we need to ask
type_name?

Going back to the new special case print_default_format() gives us
the answer to the question.  It expects that data->info already
knows the stringified typename in the type_name member.  The
original slow code path in expand_atom() uses this, instead:

	} else if (is_atom("objecttype", atom, len)) {
		if (data->mark_query)
			data->info.typep = &data->type;
		else
			strbuf_addstr(sb, type_name(data->type));

Which makes me wonder:

 * Is calling type_name(data->type) for many objects a lot less
   efficient than asking the stringified type_name from the
   object-info layer?  If that is the case, would you gain
   performance for all cases if you did this instead

	} else if (is_atom("objecttype", atom, len)) {
-		if (data->mark_query)
-			data->info.typep = &data->type;
-		else
-			strbuf_addstr(sb, type_name(data->type));
+		if (data->mark_query) {
+			data->info.typep = &data->type;
+			data->info.type_name = &data->type_name;
+		} else {
+			strbuf_addstr(sb, data->type_name);
+		}

   in expand_atom()?

	Side note: I am keeping data->info.typep because a lot of
	existing code switches on data->type, which is an enum.

   We may have to keep the strbuf_release() at the end of this
   function this patch added, to release data->info.type_name, if we
   go that route, but we wouldn't be dealing with an on-stack
   type_name in this function.

 * If it does not make any difference between calling type_name() on
   our side in expand_atom() or asking object-info API to do so,
   then would it make more sense to lose the local type_name strbuf
   and print type_name(data->type) in print_default_format() instead?

Other than that, this looks good to me.

Thanks.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] cat-file: skip expanding default format
  2022-03-08 16:59   ` Junio C Hamano
@ 2022-03-08 19:01     ` John Cai
  0 siblings, 0 replies; 17+ messages in thread
From: John Cai @ 2022-03-08 19:01 UTC (permalink / raw)
  To: Junio C Hamano
  Cc: John Cai via GitGitGadget, git, Ævar Arnfjörð Bjarmason

Hi Junio,

On 8 Mar 2022, at 11:59, Junio C Hamano wrote:

> "John Cai via GitGitGadget" <gitgitgadget@gmail.com> writes:
>
>> diff --git a/builtin/cat-file.c b/builtin/cat-file.c
>> index 7b3f42950ec..ab9a49e13a4 100644
>> --- a/builtin/cat-file.c
>> +++ b/builtin/cat-file.c
>> @@ -351,6 +351,14 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
>>  	}
>>  }
>>
>> +static int print_default_format(char *buf, int len, struct expand_data *data)
>> +{
>> +	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
>> +		 data->info.type_name->buf,
>> +		 (uintmax_t)*data->info.sizep);
>> +
>> +}
>
> OK.  We want size and type if we were to show the default output out
> of the object-info API.
>
>>  /*
>>   * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
>>   * which the object may be accessed (though note that we may also rely on
>> @@ -363,6 +371,11 @@ static void batch_object_write(const char *obj_name,
>>  			       struct packed_git *pack,
>>  			       off_t offset)
>>  {
>> +	struct strbuf type_name = STRBUF_INIT;
>> +
>> +	if (!opt->format)
>> +		data->info.type_name = &type_name;
>
> And at this point, !opt->format means we would use the default
> format, so we cannot leave .type_name member NULL.  That is OK
> but puzzling.  Why didn't we need this before?
>
> If the caller is batch_objects(), there is the "mark_query" call to
> strbuf_expand() to learn which field in data->info are needed, so
> it seems that this new code should NOT be necessary.
>
>     Side note.  I briefly wondered if this expand is something you
>     would want to optimize when the default format is used, but this
>     is just "probe just once to ensure various members of data->info
>     are populated, to prepare for showing hundreds of objects in the
>     batch request", so it probably is not worth it.
>
> I am guessing that this is for callers that do not come via
> batch_objects() where the "mark_query" strbuf_expand() is not made?
> If so,
>
>  * why is it sufficient to fill .type_name and not .sizep for the
>    default format (i.e. when opt->format is NULL)?
>
>  * why is it OK not to do anything for non-default format?  If no
>    "mark_query" call has been made, we wouldn't be preparing the
>    .type_name field even if the user-supplied format calls for
>    %(objecttype), would we?
>
> Looking at the call graph:
>
>  - batch_object_write() is called by
>    - batch_one_object()
>    - batch_object_cb()
>    - batch_unordered_object()
>
>  - batch_one_object() is called only by batch_objects()
>  - batch_object_cb() is used only by batch_objects()
>
>  - batch_unordered_object() is called by
>    - batch_unordered_loose()
>    - batch_unordered_packed()
>    and these two are called only by batch_objects()
>
> And the "mark_query" strbuf_expand() to probe which members in
> expand_data are are necessary is done very early, before any of the
> calls batch_objects() makes that reach batch_object_write().
>
> OK, so my initial guess that the new "we need .type_name member to
> point at a strbuf" is because there are some code that bypasses the
> "mark_query" strbuf_expand() in batch_objects() is totally wrong.
> Everybody uses the "mark_query" thing.  Then why do we need to ask
> type_name?
>
> Going back to the new special case print_default_format() gives us
> the answer to the question.  It expects that data->info already
> knows the stringified typename in the type_name member.  The
> original slow code path in expand_atom() uses this, instead:
>
> 	} else if (is_atom("objecttype", atom, len)) {
> 		if (data->mark_query)
> 			data->info.typep = &data->type;
> 		else
> 			strbuf_addstr(sb, type_name(data->type));

Thanks for going through this analysis! so looks like I am relying on
oid_object_info_extended() which calls do_oid_object_info_extended(), which calls
type_name(co->type) if oi->type_name is not NULL.

This is a bit roundabout, so I like what you suggest below of just calling
type_name() in print_default_format() directly.

>
> Which makes me wonder:
>
>  * Is calling type_name(data->type) for many objects a lot less
>    efficient than asking the stringified type_name from the
>    object-info layer?
I'm not sure, but I imagine that if the # of calls to type_name remain the same,
eg: once per object that it wouldn't really matter much where in the stack it
happens. Also, I took a look at type_name() in object.c and it's just a lookup
in a constant array so that should be pretty fast.

>    If that is the case, would you gain
>    performance for all cases if you did this instead
>
> 	} else if (is_atom("objecttype", atom, len)) {
> -		if (data->mark_query)
> -			data->info.typep = &data->type;
> -		else
> -			strbuf_addstr(sb, type_name(data->type));
> +		if (data->mark_query) {
> +			data->info.typep = &data->type;
> +			data->info.type_name = &data->type_name;
> +		} else {
> +			strbuf_addstr(sb, data->type_name);
> +		}
>
>    in expand_atom()?

I don't quite follow here. Would we add a member type_name to
expand_data? Also where would the call to type_name() be to get the stringified
type_name?

Also I'm thinking this approach may not work well with the default format
optimization as we would be skipping the strbuf_expand() call altogether when
default format is used.

>
> 	Side note: I am keeping data->info.typep because a lot of
> 	existing code switches on data->type, which is an enum.
>
>    We may have to keep the strbuf_release() at the end of this
>    function this patch added, to release data->info.type_name, if we
>    go that route, but we wouldn't be dealing with an on-stack
>    type_name in this function.
>
>  * If it does not make any difference between calling type_name() on
>    our side in expand_atom() or asking object-info API to do so,
>    then would it make more sense to lose the local type_name strbuf
>    and print type_name(data->type) in print_default_format() instead?

I think this is the most intuitive solution.

>
> Other than that, this looks good to me.
>
> Thanks.

thanks!
John

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] cat-file: skip expanding default format
  2022-03-08  2:54 ` [PATCH v2] " John Cai via GitGitGadget
  2022-03-08 16:59   ` Junio C Hamano
@ 2022-03-08 22:00   ` Taylor Blau
  2022-03-08 22:06     ` John Cai
  2022-03-08 22:24     ` Taylor Blau
  2022-03-08 22:08   ` [PATCH v3] " John Cai via GitGitGadget
  2 siblings, 2 replies; 17+ messages in thread
From: Taylor Blau @ 2022-03-08 22:00 UTC (permalink / raw)
  To: John Cai via GitGitGadget
  Cc: git, Ævar Arnfjörð Bjarmason, John Cai

On Tue, Mar 08, 2022 at 02:54:23AM +0000, John Cai via GitGitGadget wrote:
>  /*
>   * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
>   * which the object may be accessed (though note that we may also rely on
> @@ -363,6 +371,11 @@ static void batch_object_write(const char *obj_name,
>  			       struct packed_git *pack,
>  			       off_t offset)
>  {
> +	struct strbuf type_name = STRBUF_INIT;
> +
> +	if (!opt->format)
> +		data->info.type_name = &type_name;

Hmmm, I'm not quite sure I understand why the extra string buffer is
necessary here. When we do the first expansion with the DEFAULT_FORMAT,
we set data->info.typep to point at data->type.

So by the time we do our actual query (either with
`packed_object_info()` or just `oid_object_info_extended()`), we will
get the type filled into data->type.

And we should be able to use that in print_default_format(), which saves
us in a couple of ways:

  - We don't have to (stack) allocate a string buffer, which then needs
    to be cleaned up after printing each object.

  - (More importantly) we can avoid the extra string copy through the
    intermediate buffer by using type_name() directly.

Here's a small patch on top that you could apply, if you're interested:

--- >8 ---


diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index ab9a49e13a..9f55afa75b 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -355,5 +355,5 @@ static int print_default_format(char *buf, int len, struct expand_data *data)
 {
 	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
-		 data->info.type_name->buf,
+			 type_name(data->type),
 		 (uintmax_t)*data->info.sizep);

@@ -372,9 +372,4 @@ static void batch_object_write(const char *obj_name,
 			       off_t offset)
 {
-	struct strbuf type_name = STRBUF_INIT;
-
-	if (!opt->format)
-		data->info.type_name = &type_name;
-
 	if (!data->skip_object_info) {
 		int ret;
@@ -391,5 +386,5 @@ static void batch_object_write(const char *obj_name,
 			       obj_name ? obj_name : oid_to_hex(&data->oid));
 			fflush(stdout);
-			goto cleanup;
+			return;
 		}
 	}
@@ -410,7 +405,4 @@ static void batch_object_write(const char *obj_name,
 		batch_write(opt, "\n", 1);
 	}
-
-cleanup:
-	strbuf_release(&type_name);
 }

--- 8< ---

On my copy of git.git., it shaves off around ~7ms that we're spending
just copying type names back and forth.

    (without the above)
    Benchmark 1: git.compile cat-file --batch-check --batch-all-objects
      Time (mean ± σ):     578.7 ms ±  12.7 ms    [User: 553.4 ms, System: 25.2 ms]
      Range (min … max):   568.1 ms … 600.1 ms    10 runs

    (with the above)
    Benchmark 1: git.compile cat-file --batch-check --batch-all-objects
      Time (mean ± σ):     571.5 ms ±   7.9 ms    [User: 544.0 ms, System: 27.3 ms]
      Range (min … max):   558.8 ms … 583.2 ms    10 runs

Thanks,
Taylor

^ permalink raw reply related	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] cat-file: skip expanding default format
  2022-03-08 22:00   ` Taylor Blau
@ 2022-03-08 22:06     ` John Cai
  2022-03-08 22:24     ` Taylor Blau
  1 sibling, 0 replies; 17+ messages in thread
From: John Cai @ 2022-03-08 22:06 UTC (permalink / raw)
  To: Taylor Blau
  Cc: John Cai via GitGitGadget, git, Ævar Arnfjörð Bjarmason

Hi Taylor

On 8 Mar 2022, at 17:00, Taylor Blau wrote:

> On Tue, Mar 08, 2022 at 02:54:23AM +0000, John Cai via GitGitGadget wrote:
>>  /*
>>   * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
>>   * which the object may be accessed (though note that we may also rely on
>> @@ -363,6 +371,11 @@ static void batch_object_write(const char *obj_name,
>>  			       struct packed_git *pack,
>>  			       off_t offset)
>>  {
>> +	struct strbuf type_name = STRBUF_INIT;
>> +
>> +	if (!opt->format)
>> +		data->info.type_name = &type_name;
>
> Hmmm, I'm not quite sure I understand why the extra string buffer is
> necessary here. When we do the first expansion with the DEFAULT_FORMAT,
> we set data->info.typep to point at data->type.
>
> So by the time we do our actual query (either with
> `packed_object_info()` or just `oid_object_info_extended()`), we will
> get the type filled into data->type.
>
> And we should be able to use that in print_default_format(), which saves
> us in a couple of ways:
>
>   - We don't have to (stack) allocate a string buffer, which then needs
>     to be cleaned up after printing each object.
>
>   - (More importantly) we can avoid the extra string copy through the
>     intermediate buffer by using type_name() directly.

Agree with your reasoning here.

>
> Here's a small patch on top that you could apply, if you're interested:
>
> --- >8 ---
>
>
> diff --git a/builtin/cat-file.c b/builtin/cat-file.c
> index ab9a49e13a..9f55afa75b 100644
> --- a/builtin/cat-file.c
> +++ b/builtin/cat-file.c
> @@ -355,5 +355,5 @@ static int print_default_format(char *buf, int len, struct expand_data *data)
>  {
>  	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
> -		 data->info.type_name->buf,
> +			 type_name(data->type),
>  		 (uintmax_t)*data->info.sizep);
>
> @@ -372,9 +372,4 @@ static void batch_object_write(const char *obj_name,
>  			       off_t offset)
>  {
> -	struct strbuf type_name = STRBUF_INIT;
> -
> -	if (!opt->format)
> -		data->info.type_name = &type_name;
> -
>  	if (!data->skip_object_info) {
>  		int ret;
> @@ -391,5 +386,5 @@ static void batch_object_write(const char *obj_name,
>  			       obj_name ? obj_name : oid_to_hex(&data->oid));
>  			fflush(stdout);
> -			goto cleanup;
> +			return;
>  		}
>  	}
> @@ -410,7 +405,4 @@ static void batch_object_write(const char *obj_name,
>  		batch_write(opt, "\n", 1);
>  	}
> -
> -cleanup:
> -	strbuf_release(&type_name);
>  }
>
> --- 8< ---
>
> On my copy of git.git., it shaves off around ~7ms that we're spending
> just copying type names back and forth.
>
>     (without the above)
>     Benchmark 1: git.compile cat-file --batch-check --batch-all-objects
>       Time (mean ± σ):     578.7 ms ±  12.7 ms    [User: 553.4 ms, System: 25.2 ms]
>       Range (min … max):   568.1 ms … 600.1 ms    10 runs
>
>     (with the above)
>     Benchmark 1: git.compile cat-file --batch-check --batch-all-objects
>       Time (mean ± σ):     571.5 ms ±   7.9 ms    [User: 544.0 ms, System: 27.3 ms]
>       Range (min … max):   558.8 ms … 583.2 ms    10 runs

Thanks for this suggestion and the benchmark! This is similar to what Junio suggested, and
I do think this is the right thing to do here.

>
> Thanks,
> Taylor

Thanks,
John

^ permalink raw reply	[flat|nested] 17+ messages in thread

* [PATCH v3] cat-file: skip expanding default format
  2022-03-08  2:54 ` [PATCH v2] " John Cai via GitGitGadget
  2022-03-08 16:59   ` Junio C Hamano
  2022-03-08 22:00   ` Taylor Blau
@ 2022-03-08 22:08   ` John Cai via GitGitGadget
  2022-03-08 22:30     ` Taylor Blau
  2022-03-15  2:40     ` [PATCH v4] " John Cai via GitGitGadget
  2 siblings, 2 replies; 17+ messages in thread
From: John Cai via GitGitGadget @ 2022-03-08 22:08 UTC (permalink / raw)
  To: git
  Cc: Ævar Arnfjörð Bjarmason, Taylor Blau, John Cai, John Cai

From: John Cai <johncai86@gmail.com>

When format is passed into --batch, --batch-check, --batch-command,
the format gets expanded. When nothing is passed in, the default format
is set and the expand_format() gets called.

We can save on these cycles by hardcoding how to print the
information when nothing is passed as the format, or when the default
format is passed. There is no need for the fully expanded format with
the default. Since batch_object_write() happens on every object provided
in batch mode, we get a nice performance improvement.

git rev-list --all > /tmp/all-obj.txt

git cat-file --batch-check </tmp/all-obj.txt

with HEAD^:

Time (mean ± σ): 57.6 ms ± 1.7 ms [User: 51.5 ms, System: 6.2 ms]
Range (min … max): 54.6 ms … 64.7 ms 50 runs

with HEAD:

Time (mean ± σ): 49.8 ms ± 1.7 ms [User: 42.6 ms, System: 7.3 ms]
Range (min … max): 46.9 ms … 55.9 ms 56 runs

If nothing is provided as a format argument, or if the default format is
passed, skip expanding of the format and print the object info with a
default format.

See https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: John Cai <johncai86@gmail.com>
---
    optimize cat file batch info writing
    
    When cat-file --batch or --batch-check is used, we can skip having to
    expand the format if no format is specified or if the default format is
    specified. In this case we know exactly how to print the objects without
    the full expanded format.
    
    This was first discussed in [1].
    
    We get a little performance boost from this optimization because this
    happens for each objects provided to --batch, --batch-check, or
    --batch-command. Because batch_object_write() is called on every oid
    provided in batch mode, this optimization adds up when a large number of
    oid info is printed.
    
    git rev-list --all >/tmp/all-objs.txt
    
    git cat-file --batch-check </tmp/all-obj.txt (with hyperfine)
    
    run on origin/master:
    
    Time (mean ± σ): 57.6 ms ± 1.7 ms [User: 51.5 ms, System: 6.2 ms] Range
    (min … max): 54.6 ms … 64.7 ms 50 runs
    
    run on jc/optimize-cat-file-batch-default-format:
    
    Time (mean ± σ): 49.8 ms ± 1.7 ms [User: 42.6 ms, System: 7.3 ms] Range
    (min … max): 46.9 ms … 55.9 ms 56 runs
    
    Changes since v1:
    
     * set opt->format in batch_objects so that the loop that prints objects
       only has to check if the format is null to know to print the object
       info in the default format
     * fixed up commit trailer to include Ævar as Signed-off-by
    
     1. https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1221%2Fjohn-cai%2Fjc%2Foptimize-cat-file-batch-default-format-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1221/john-cai/jc/optimize-cat-file-batch-default-format-v3
Pull-Request: https://github.com/git/git/pull/1221

Range-diff vs v2:

 1:  f5d578d14a9 ! 1:  56d13da5141 cat-file: skip expanding default format
     @@ builtin/cat-file.c: static void print_object_or_die(struct batch_options *opt, s
      +static int print_default_format(char *buf, int len, struct expand_data *data)
      +{
      +	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
     -+		 data->info.type_name->buf,
     -+		 (uintmax_t)*data->info.sizep);
     -+
     ++			 type_name(data->type),
     ++			 (uintmax_t)*data->info.sizep);
      +}
      +
       /*
        * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
        * which the object may be accessed (though note that we may also rely on
      @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
     - 			       struct packed_git *pack,
     - 			       off_t offset)
     - {
     -+	struct strbuf type_name = STRBUF_INIT;
     -+
     -+	if (!opt->format)
     -+		data->info.type_name = &type_name;
     -+
     - 	if (!data->skip_object_info) {
     - 		int ret;
     - 
     -@@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
     - 			printf("%s missing\n",
     - 			       obj_name ? obj_name : oid_to_hex(&data->oid));
     - 			fflush(stdout);
     --			return;
     -+			goto cleanup;
       		}
       	}
       
     @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
       
       	if (opt->print_contents) {
       		print_object_or_die(opt, data);
     - 		batch_write(opt, "\n", 1);
     - 	}
     -+
     -+cleanup:
     -+	strbuf_release(&type_name);
     - }
     - 
     -+
     - static void batch_one_object(const char *obj_name,
     - 			     struct strbuf *scratch,
     - 			     struct batch_options *opt,
      @@ builtin/cat-file.c: static int batch_unordered_packed(const struct object_id *oid,
       				      data);
       }


 builtin/cat-file.c       | 34 ++++++++++++++++++++++++++--------
 t/perf/p1006-cat-file.sh | 16 ++++++++++++++++
 2 files changed, 42 insertions(+), 8 deletions(-)
 create mode 100755 t/perf/p1006-cat-file.sh

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index 7b3f42950ec..e2edba70b41 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -351,6 +351,13 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
 	}
 }
 
+static int print_default_format(char *buf, int len, struct expand_data *data)
+{
+	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
+			 type_name(data->type),
+			 (uintmax_t)*data->info.sizep);
+}
+
 /*
  * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
  * which the object may be accessed (though note that we may also rely on
@@ -381,10 +388,16 @@ static void batch_object_write(const char *obj_name,
 		}
 	}
 
-	strbuf_reset(scratch);
-	strbuf_expand(scratch, opt->format, expand_format, data);
-	strbuf_addch(scratch, '\n');
-	batch_write(opt, scratch->buf, scratch->len);
+	if (!opt->format) {
+		char buf[1024];
+		int len = print_default_format(buf, 1024, data);
+		batch_write(opt, buf, len);
+	} else {
+		strbuf_reset(scratch);
+		strbuf_expand(scratch, opt->format, expand_format, data);
+		strbuf_addch(scratch, '\n');
+		batch_write(opt, scratch->buf, scratch->len);
+	}
 
 	if (opt->print_contents) {
 		print_object_or_die(opt, data);
@@ -508,6 +521,9 @@ static int batch_unordered_packed(const struct object_id *oid,
 				      data);
 }
 
+
+#define DEFAULT_FORMAT "%(objectname) %(objecttype) %(objectsize)"
+
 static int batch_objects(struct batch_options *opt)
 {
 	struct strbuf input = STRBUF_INIT;
@@ -516,9 +532,6 @@ static int batch_objects(struct batch_options *opt)
 	int save_warning;
 	int retval = 0;
 
-	if (!opt->format)
-		opt->format = "%(objectname) %(objecttype) %(objectsize)";
-
 	/*
 	 * Expand once with our special mark_query flag, which will prime the
 	 * object_info to be handed to oid_object_info_extended for each
@@ -526,12 +539,17 @@ static int batch_objects(struct batch_options *opt)
 	 */
 	memset(&data, 0, sizeof(data));
 	data.mark_query = 1;
-	strbuf_expand(&output, opt->format, expand_format, &data);
+	strbuf_expand(&output,
+		      opt->format ? opt->format : DEFAULT_FORMAT,
+		      expand_format,
+		      &data);
 	data.mark_query = 0;
 	strbuf_release(&output);
 	if (opt->cmdmode)
 		data.split_on_whitespace = 1;
 
+	if (opt->format && !strcmp(opt->format, DEFAULT_FORMAT))
+		opt->format = NULL;
 	/*
 	 * If we are printing out the object, then always fill in the type,
 	 * since we will want to decide whether or not to stream.
diff --git a/t/perf/p1006-cat-file.sh b/t/perf/p1006-cat-file.sh
new file mode 100755
index 00000000000..e463623f5a3
--- /dev/null
+++ b/t/perf/p1006-cat-file.sh
@@ -0,0 +1,16 @@
+#!/bin/sh
+
+test_description='Basic sort performance tests'
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+test_expect_success 'setup' '
+	git rev-list --all >rla
+'
+
+test_perf 'cat-file --batch-check' '
+	git cat-file --batch-check <rla
+'
+
+test_done

base-commit: 715d08a9e51251ad8290b181b6ac3b9e1f9719d7
-- 
gitgitgadget

^ permalink raw reply related	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] cat-file: skip expanding default format
  2022-03-08 22:00   ` Taylor Blau
  2022-03-08 22:06     ` John Cai
@ 2022-03-08 22:24     ` Taylor Blau
  2022-03-08 22:45       ` John Cai
  1 sibling, 1 reply; 17+ messages in thread
From: Taylor Blau @ 2022-03-08 22:24 UTC (permalink / raw)
  To: John Cai via GitGitGadget
  Cc: git, Ævar Arnfjörð Bjarmason, John Cai

On Tue, Mar 08, 2022 at 05:00:53PM -0500, Taylor Blau wrote:
> On my copy of git.git., it shaves off around ~7ms that we're spending
> just copying type names back and forth.

...while we're at it, I think we could go a little further and avoid
doing the mark_query phase altogether, by doing something like:

--- 8< ---

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index ab9a49e13a..4b3cfb9e68 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -542,24 +542,30 @@ static int batch_objects(struct batch_options *opt)
 	int save_warning;
 	int retval = 0;

-	/*
-	 * Expand once with our special mark_query flag, which will prime the
-	 * object_info to be handed to oid_object_info_extended for each
-	 * object.
-	 */
-	memset(&data, 0, sizeof(data));
-	data.mark_query = 1;
-	strbuf_expand(&output,
-		      opt->format ? opt->format : DEFAULT_FORMAT,
-		      expand_format,
-		      &data);
-	data.mark_query = 0;
-	strbuf_release(&output);
 	if (opt->cmdmode)
 		data.split_on_whitespace = 1;

-	if (opt->format && !strcmp(opt->format, DEFAULT_FORMAT))
+	memset(&data, 0, sizeof(data));
+	if (!opt->format || !strcmp(opt->format, DEFAULT_FORMAT)) {
+		data.info.sizep = &data.size;
+		data.info.typep = &data.type;
+
 		opt->format = NULL;
+	} else {
+		/*
+		 * Expand once with our special mark_query flag, which will prime the
+		 * object_info to be handed to oid_object_info_extended for each
+		 * object.
+		 */
+		data.mark_query = 1;
+		strbuf_expand(&output,
+			      opt->format ? opt->format : DEFAULT_FORMAT,
+			      expand_format,
+			      &data);
+		data.mark_query = 0;
+		strbuf_release(&output);
+	}
+
 	/*
 	 * If we are printing out the object, then always fill in the type,
 	 * since we will want to decide whether or not to stream.

--- >8 ---

...but in my experiments it doesn't seem to help much. Or, at least, it
doesn't obviously help, there's too much noise from run to run for me to
see a worthwhile speed-up here.

Thanks,
Taylor

^ permalink raw reply related	[flat|nested] 17+ messages in thread

* Re: [PATCH v3] cat-file: skip expanding default format
  2022-03-08 22:08   ` [PATCH v3] " John Cai via GitGitGadget
@ 2022-03-08 22:30     ` Taylor Blau
  2022-03-08 23:09       ` John Cai
  2022-03-15  2:40     ` [PATCH v4] " John Cai via GitGitGadget
  1 sibling, 1 reply; 17+ messages in thread
From: Taylor Blau @ 2022-03-08 22:30 UTC (permalink / raw)
  To: John Cai via GitGitGadget
  Cc: git, Ævar Arnfjörð Bjarmason, John Cai

On Tue, Mar 08, 2022 at 10:08:46PM +0000, John Cai via GitGitGadget wrote:
> diff --git a/builtin/cat-file.c b/builtin/cat-file.c
> index 7b3f42950ec..e2edba70b41 100644
> --- a/builtin/cat-file.c
> +++ b/builtin/cat-file.c
> @@ -351,6 +351,13 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
>  	}
>  }
>
> +static int print_default_format(char *buf, int len, struct expand_data *data)
> +{
> +	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
> +			 type_name(data->type),
> +			 (uintmax_t)*data->info.sizep);
> +}

Two small nits here. It looks like the indentation on the second and
third lines is off a little bit, since we'd typically expect those to be
indented to the same margin as the first argument to xsnprintf().

The other is that you're reading data->info.sizep by dereferencing it,
but we know that it points to data->size. So I think there it makes
sense to just read the value directly out of data->size, though note
that you'll still need the cast to uintmax_t since you're formatting it
with PRIuMAX.

> +
>  /*
>   * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
>   * which the object may be accessed (though note that we may also rely on
> @@ -381,10 +388,16 @@ static void batch_object_write(const char *obj_name,
>  		}
>  	}
>
> -	strbuf_reset(scratch);
> -	strbuf_expand(scratch, opt->format, expand_format, data);
> -	strbuf_addch(scratch, '\n');
> -	batch_write(opt, scratch->buf, scratch->len);
> +	if (!opt->format) {
> +		char buf[1024];
> +		int len = print_default_format(buf, 1024, data);
> +		batch_write(opt, buf, len);

Just curious (and apologies if this was discussed earlier and I missed
it), but: is there a reason that we have to use a scratch buffer here
that is separate from the strbuf we already have allocated?

That would avoid a large-ish stack variable, but it means that the two
paths are a little more similar, and can share the batch_write call
outside of the if/else statement.

The rest of the changes in this file all look good to me.

> diff --git a/t/perf/p1006-cat-file.sh b/t/perf/p1006-cat-file.sh
> new file mode 100755
> index 00000000000..e463623f5a3
> --- /dev/null
> +++ b/t/perf/p1006-cat-file.sh
> @@ -0,0 +1,16 @@
> +#!/bin/sh
> +
> +test_description='Basic sort performance tests'

Is this description a hold-over from p0071? If so, it may be worth
updating here.

> +test_expect_success 'setup' '
> +	git rev-list --all >rla
> +'
> +
> +test_perf 'cat-file --batch-check' '
> +	git cat-file --batch-check <rla
> +'

We could probably get away with dropping the setup test and using
`--batch-all-objects` here. Note that right now you're only printing
commit objects, so there would be a slight behavior change from the way
the patch is currently written, but it should demonstrate the same
performance improvement.

Thanks,
Taylor

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v2] cat-file: skip expanding default format
  2022-03-08 22:24     ` Taylor Blau
@ 2022-03-08 22:45       ` John Cai
  0 siblings, 0 replies; 17+ messages in thread
From: John Cai @ 2022-03-08 22:45 UTC (permalink / raw)
  To: Taylor Blau
  Cc: John Cai via GitGitGadget, git, Ævar Arnfjörð Bjarmason

Hi Taylor,

On 8 Mar 2022, at 17:24, Taylor Blau wrote:

> On Tue, Mar 08, 2022 at 05:00:53PM -0500, Taylor Blau wrote:
>> On my copy of git.git., it shaves off around ~7ms that we're spending
>> just copying type names back and forth.
>
> ...while we're at it, I think we could go a little further and avoid
> doing the mark_query phase altogether, by doing something like:
>
> --- 8< ---
>
> diff --git a/builtin/cat-file.c b/builtin/cat-file.c
> index ab9a49e13a..4b3cfb9e68 100644
> --- a/builtin/cat-file.c
> +++ b/builtin/cat-file.c
> @@ -542,24 +542,30 @@ static int batch_objects(struct batch_options *opt)
>  	int save_warning;
>  	int retval = 0;
>
> -	/*
> -	 * Expand once with our special mark_query flag, which will prime the
> -	 * object_info to be handed to oid_object_info_extended for each
> -	 * object.
> -	 */
> -	memset(&data, 0, sizeof(data));
> -	data.mark_query = 1;
> -	strbuf_expand(&output,
> -		      opt->format ? opt->format : DEFAULT_FORMAT,
> -		      expand_format,
> -		      &data);
> -	data.mark_query = 0;
> -	strbuf_release(&output);
>  	if (opt->cmdmode)
>  		data.split_on_whitespace = 1;
>
> -	if (opt->format && !strcmp(opt->format, DEFAULT_FORMAT))
> +	memset(&data, 0, sizeof(data));
> +	if (!opt->format || !strcmp(opt->format, DEFAULT_FORMAT)) {
> +		data.info.sizep = &data.size;
> +		data.info.typep = &data.type;
> +
>  		opt->format = NULL;
> +	} else {
> +		/*
> +		 * Expand once with our special mark_query flag, which will prime the
> +		 * object_info to be handed to oid_object_info_extended for each
> +		 * object.
> +		 */
> +		data.mark_query = 1;
> +		strbuf_expand(&output,
> +			      opt->format ? opt->format : DEFAULT_FORMAT,
> +			      expand_format,
> +			      &data);
> +		data.mark_query = 0;
> +		strbuf_release(&output);
> +	}
> +
>  	/*
>  	 * If we are printing out the object, then always fill in the type,
>  	 * since we will want to decide whether or not to stream.
>
> --- >8 ---
>
> ...but in my experiments it doesn't seem to help much. Or, at least, it
> doesn't obviously help, there's too much noise from run to run for me to
> see a worthwhile speed-up here.

Yeah I had the same thought. I also didn't see a noticeable difference so I'm on the fence
regarding whether or not it's worth it. I'm kind of leaning towards no, since it adds some
one-off logic without a clear performance gain.

>
> Thanks,
> Taylor

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v3] cat-file: skip expanding default format
  2022-03-08 22:30     ` Taylor Blau
@ 2022-03-08 23:09       ` John Cai
  2022-03-08 23:34         ` John Cai
  0 siblings, 1 reply; 17+ messages in thread
From: John Cai @ 2022-03-08 23:09 UTC (permalink / raw)
  To: Taylor Blau
  Cc: John Cai via GitGitGadget, git, Ævar Arnfjörð Bjarmason

Hi Taylor,

On 8 Mar 2022, at 17:30, Taylor Blau wrote:

> On Tue, Mar 08, 2022 at 10:08:46PM +0000, John Cai via GitGitGadget wrote:
>> diff --git a/builtin/cat-file.c b/builtin/cat-file.c
>> index 7b3f42950ec..e2edba70b41 100644
>> --- a/builtin/cat-file.c
>> +++ b/builtin/cat-file.c
>> @@ -351,6 +351,13 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
>>  	}
>>  }
>>
>> +static int print_default_format(char *buf, int len, struct expand_data *data)
>> +{
>> +	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
>> +			 type_name(data->type),
>> +			 (uintmax_t)*data->info.sizep);
>> +}
>
> Two small nits here. It looks like the indentation on the second and
> third lines is off a little bit, since we'd typically expect those to be
> indented to the same margin as the first argument to xsnprintf().

Thanks for bringing this up. I did have a question about indentation in this
case. for the second line, I did try to indent it to align with buf. I attempted
to do the same with the third line, but it's the ( that lines up with buf so
optically it looks a little off.

>
> The other is that you're reading data->info.sizep by dereferencing it,
> but we know that it points to data->size. So I think there it makes
> sense to just read the value directly out of data->size, though note
> that you'll still need the cast to uintmax_t since you're formatting it
> with PRIuMAX.

good point, I'll adjust this in the next version.

>
>> +
>>  /*
>>   * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
>>   * which the object may be accessed (though note that we may also rely on
>> @@ -381,10 +388,16 @@ static void batch_object_write(const char *obj_name,
>>  		}
>>  	}
>>
>> -	strbuf_reset(scratch);
>> -	strbuf_expand(scratch, opt->format, expand_format, data);
>> -	strbuf_addch(scratch, '\n');
>> -	batch_write(opt, scratch->buf, scratch->len);
>> +	if (!opt->format) {
>> +		char buf[1024];
>> +		int len = print_default_format(buf, 1024, data);
>> +		batch_write(opt, buf, len);
>
> Just curious (and apologies if this was discussed earlier and I missed
> it), but: is there a reason that we have to use a scratch buffer here
> that is separate from the strbuf we already have allocated?
>
> That would avoid a large-ish stack variable, but it means that the two
> paths are a little more similar, and can share the batch_write call
> outside of the if/else statement.

This was holdover code from before. Looks like the scratch buffer gets passed
in. Do you mean we don't need to allocate char buf[1024] and instead we can just
use scratch and pass it into print_default_format?

>
> The rest of the changes in this file all look good to me.
>
>> diff --git a/t/perf/p1006-cat-file.sh b/t/perf/p1006-cat-file.sh
>> new file mode 100755
>> index 00000000000..e463623f5a3
>> --- /dev/null
>> +++ b/t/perf/p1006-cat-file.sh
>> @@ -0,0 +1,16 @@
>> +#!/bin/sh
>> +
>> +test_description='Basic sort performance tests'
>
> Is this description a hold-over from p0071? If so, it may be worth
> updating here.
>
>> +test_expect_success 'setup' '
>> +	git rev-list --all >rla
>> +'
>> +
>> +test_perf 'cat-file --batch-check' '
>> +	git cat-file --batch-check <rla
>> +'
>
> We could probably get away with dropping the setup test and using
> `--batch-all-objects` here. Note that right now you're only printing
> commit objects, so there would be a slight behavior change from the way
> the patch is currently written, but it should demonstrate the same
> performance improvement.

This sounds good to me!

>
> Thanks,
> Taylor

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v3] cat-file: skip expanding default format
  2022-03-08 23:09       ` John Cai
@ 2022-03-08 23:34         ` John Cai
  0 siblings, 0 replies; 17+ messages in thread
From: John Cai @ 2022-03-08 23:34 UTC (permalink / raw)
  To: Taylor Blau
  Cc: John Cai via GitGitGadget, git, Ævar Arnfjörð Bjarmason



On 8 Mar 2022, at 18:09, John Cai wrote:

> Hi Taylor,
>
> On 8 Mar 2022, at 17:30, Taylor Blau wrote:
>
>> On Tue, Mar 08, 2022 at 10:08:46PM +0000, John Cai via GitGitGadget wrote:
>>> diff --git a/builtin/cat-file.c b/builtin/cat-file.c
>>> index 7b3f42950ec..e2edba70b41 100644
>>> --- a/builtin/cat-file.c
>>> +++ b/builtin/cat-file.c
>>> @@ -351,6 +351,13 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
>>>  	}
>>>  }
>>>
>>> +static int print_default_format(char *buf, int len, struct expand_data *data)
>>> +{
>>> +	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
>>> +			 type_name(data->type),
>>> +			 (uintmax_t)*data->info.sizep);
>>> +}
>>
>> Two small nits here. It looks like the indentation on the second and
>> third lines is off a little bit, since we'd typically expect those to be
>> indented to the same margin as the first argument to xsnprintf().
>
> Thanks for bringing this up. I did have a question about indentation in this
> case. for the second line, I did try to indent it to align with buf. I attempted
> to do the same with the third line, but it's the ( that lines up with buf so
> optically it looks a little off.
>
>>
>> The other is that you're reading data->info.sizep by dereferencing it,
>> but we know that it points to data->size. So I think there it makes
>> sense to just read the value directly out of data->size, though note
>> that you'll still need the cast to uintmax_t since you're formatting it
>> with PRIuMAX.
>
> good point, I'll adjust this in the next version.
>
>>
>>> +
>>>  /*
>>>   * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
>>>   * which the object may be accessed (though note that we may also rely on
>>> @@ -381,10 +388,16 @@ static void batch_object_write(const char *obj_name,
>>>  		}
>>>  	}
>>>
>>> -	strbuf_reset(scratch);
>>> -	strbuf_expand(scratch, opt->format, expand_format, data);
>>> -	strbuf_addch(scratch, '\n');
>>> -	batch_write(opt, scratch->buf, scratch->len);
>>> +	if (!opt->format) {
>>> +		char buf[1024];
>>> +		int len = print_default_format(buf, 1024, data);
>>> +		batch_write(opt, buf, len);
>>
>> Just curious (and apologies if this was discussed earlier and I missed
>> it), but: is there a reason that we have to use a scratch buffer here
>> that is separate from the strbuf we already have allocated?
>>
>> That would avoid a large-ish stack variable, but it means that the two
>> paths are a little more similar, and can share the batch_write call
>> outside of the if/else statement.
>
> This was holdover code from before. Looks like the scratch buffer gets passed
> in. Do you mean we don't need to allocate char buf[1024] and instead we can just
> use scratch and pass it into print_default_format?

something like this?

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index e2edba70b418..2336bcc80850 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -351,11 +351,11 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
        }
 }

-static int print_default_format(char *buf, int len, struct expand_data *data)
+static void print_default_format(struct strbuf *scratch, struct expand_data *data)
 {
-       return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
-                        type_name(data->type),
-                        (uintmax_t)*data->info.sizep);
+       strbuf_addf(scratch, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
+                   type_name(data->type),
+                   (uintmax_t)data->size);
 }

 /*
@@ -388,17 +388,17 @@ static void batch_object_write(const char *obj_name,
                }
        }

+       strbuf_reset(scratch);
+
        if (!opt->format) {
-               char buf[1024];
-               int len = print_default_format(buf, 1024, data);
-               batch_write(opt, buf, len);
+               print_default_format(scratch, data);
        } else {
-               strbuf_reset(scratch);
                strbuf_expand(scratch, opt->format, expand_format, data);
                strbuf_addch(scratch, '\n');
-               batch_write(opt, scratch->buf, scratch->len);
        }

+       batch_write(opt, scratch->buf, scratch->len);
+
        if (opt->print_contents) {
                print_object_or_die(opt, data);
                batch_write(opt, "\n", 1);
>
>>
>> The rest of the changes in this file all look good to me.
>>
>>> diff --git a/t/perf/p1006-cat-file.sh b/t/perf/p1006-cat-file.sh
>>> new file mode 100755
>>> index 00000000000..e463623f5a3
>>> --- /dev/null
>>> +++ b/t/perf/p1006-cat-file.sh
>>> @@ -0,0 +1,16 @@
>>> +#!/bin/sh
>>> +
>>> +test_description='Basic sort performance tests'
>>
>> Is this description a hold-over from p0071? If so, it may be worth
>> updating here.
>>
>>> +test_expect_success 'setup' '
>>> +	git rev-list --all >rla
>>> +'
>>> +
>>> +test_perf 'cat-file --batch-check' '
>>> +	git cat-file --batch-check <rla
>>> +'
>>
>> We could probably get away with dropping the setup test and using
>> `--batch-all-objects` here. Note that right now you're only printing
>> commit objects, so there would be a slight behavior change from the way
>> the patch is currently written, but it should demonstrate the same
>> performance improvement.
>
> This sounds good to me!
>
>>
>> Thanks,
>> Taylor

^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH v4] cat-file: skip expanding default format
  2022-03-08 22:08   ` [PATCH v3] " John Cai via GitGitGadget
  2022-03-08 22:30     ` Taylor Blau
@ 2022-03-15  2:40     ` John Cai via GitGitGadget
  1 sibling, 0 replies; 17+ messages in thread
From: John Cai via GitGitGadget @ 2022-03-15  2:40 UTC (permalink / raw)
  To: git
  Cc: Ævar Arnfjörð Bjarmason, Taylor Blau, John Cai, John Cai

From: John Cai <johncai86@gmail.com>

When format is passed into --batch, --batch-check, --batch-command,
the format gets expanded. When nothing is passed in, the default format
is set and the expand_format() gets called.

We can save on these cycles by hardcoding how to print the
information when nothing is passed as the format, or when the default
format is passed. There is no need for the fully expanded format with
the default. Since batch_object_write() happens on every object provided
in batch mode, we get a nice performance improvement.

git rev-list --all > /tmp/all-obj.txt

git cat-file --batch-check </tmp/all-obj.txt

with HEAD^:

Time (mean ± σ): 57.6 ms ± 1.7 ms [User: 51.5 ms, System: 6.2 ms]
Range (min … max): 54.6 ms … 64.7 ms 50 runs

with HEAD:

Time (mean ± σ): 49.8 ms ± 1.7 ms [User: 42.6 ms, System: 7.3 ms]
Range (min … max): 46.9 ms … 55.9 ms 56 runs

If nothing is provided as a format argument, or if the default format is
passed, skip expanding of the format and print the object info with a
default format.

See https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: John Cai <johncai86@gmail.com>
---
    optimize cat file batch info writing
    
    When cat-file --batch or --batch-check is used, we can skip having to
    expand the format if no format is specified or if the default format is
    specified. In this case we know exactly how to print the objects without
    the full expanded format.
    
    This was first discussed in [1].
    
    We get a little performance boost from this optimization because this
    happens for each objects provided to --batch, --batch-check, or
    --batch-command. Because batch_object_write() is called on every oid
    provided in batch mode, this optimization adds up when a large number of
    oid info is printed.
    
    git rev-list --all >/tmp/all-objs.txt
    
    git cat-file --batch-check </tmp/all-obj.txt (with hyperfine)
    
    run on origin/master:
    
    Time (mean ± σ): 57.6 ms ± 1.7 ms [User: 51.5 ms, System: 6.2 ms] Range
    (min … max): 54.6 ms … 64.7 ms 50 runs
    
    run on jc/optimize-cat-file-batch-default-format:
    
    Time (mean ± σ): 49.8 ms ± 1.7 ms [User: 42.6 ms, System: 7.3 ms] Range
    (min … max): 46.9 ms … 55.9 ms 56 runs
    
    Changes since v3:
    
     * reuse scratch string buffer
     * use --batch-all-objects in test
    
    Changes since v2:
    
     * get rid of type_name string buffer, and call type_name() for each
       object in print_default_format()
    
    Changes since v1:
    
     * set opt->format in batch_objects so that the loop that prints objects
       only has to check if the format is null to know to print the object
       info in the default format
     * fixed up commit trailer to include Ævar as Signed-off-by
    
     1. https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1221%2Fjohn-cai%2Fjc%2Foptimize-cat-file-batch-default-format-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1221/john-cai/jc/optimize-cat-file-batch-default-format-v4
Pull-Request: https://github.com/git/git/pull/1221

Range-diff vs v3:

 1:  56d13da5141 ! 1:  b0c6a18b7ad cat-file: skip expanding default format
     @@ builtin/cat-file.c: static void print_object_or_die(struct batch_options *opt, s
       	}
       }
       
     -+static int print_default_format(char *buf, int len, struct expand_data *data)
     ++static void print_default_format(struct strbuf *scratch, struct expand_data *data)
      +{
     -+	return xsnprintf(buf, len, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
     -+			 type_name(data->type),
     -+			 (uintmax_t)*data->info.sizep);
     ++	strbuf_addf(scratch, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
     ++		    type_name(data->type),
     ++		    (uintmax_t)data->size);
      +}
      +
       /*
        * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
        * which the object may be accessed (though note that we may also rely on
      @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
     - 		}
       	}
       
     --	strbuf_reset(scratch);
     + 	strbuf_reset(scratch);
      -	strbuf_expand(scratch, opt->format, expand_format, data);
      -	strbuf_addch(scratch, '\n');
     --	batch_write(opt, scratch->buf, scratch->len);
     ++
      +	if (!opt->format) {
     -+		char buf[1024];
     -+		int len = print_default_format(buf, 1024, data);
     -+		batch_write(opt, buf, len);
     ++		print_default_format(scratch, data);
      +	} else {
     -+		strbuf_reset(scratch);
      +		strbuf_expand(scratch, opt->format, expand_format, data);
      +		strbuf_addch(scratch, '\n');
     -+		batch_write(opt, scratch->buf, scratch->len);
      +	}
     ++
     + 	batch_write(opt, scratch->buf, scratch->len);
       
     - 	if (opt->print_contents) {
     - 		print_object_or_die(opt, data);
     -@@ builtin/cat-file.c: static int batch_unordered_packed(const struct object_id *oid,
     - 				      data);
     + 	if (opt->batch_mode == BATCH_MODE_CONTENTS) {
     +@@ builtin/cat-file.c: static void batch_objects_command(struct batch_options *opt,
     + 	strbuf_release(&input);
       }
       
     -+
      +#define DEFAULT_FORMAT "%(objectname) %(objecttype) %(objectsize)"
      +
       static int batch_objects(struct batch_options *opt)
     @@ builtin/cat-file.c: static int batch_objects(struct batch_options *opt)
      +		      &data);
       	data.mark_query = 0;
       	strbuf_release(&output);
     - 	if (opt->cmdmode)
     + 	if (opt->transform_mode)
       		data.split_on_whitespace = 1;
       
      +	if (opt->format && !strcmp(opt->format, DEFAULT_FORMAT))
     @@ t/perf/p1006-cat-file.sh (new)
      @@
      +#!/bin/sh
      +
     -+test_description='Basic sort performance tests'
     ++test_description='Tests listing object info performance'
      +. ./perf-lib.sh
      +
      +test_perf_large_repo
      +
     -+test_expect_success 'setup' '
     -+	git rev-list --all >rla
     -+'
     -+
      +test_perf 'cat-file --batch-check' '
     -+	git cat-file --batch-check <rla
     ++	git cat-file --batch-all-objects --batch-check
      +'
      +
      +test_done


 builtin/cat-file.c       | 29 +++++++++++++++++++++++------
 t/perf/p1006-cat-file.sh | 12 ++++++++++++
 2 files changed, 35 insertions(+), 6 deletions(-)
 create mode 100755 t/perf/p1006-cat-file.sh

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index e75e110302e..94d5901e9a7 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -357,6 +357,13 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
 	}
 }
 
+static void print_default_format(struct strbuf *scratch, struct expand_data *data)
+{
+	strbuf_addf(scratch, "%s %s %"PRIuMAX"\n", oid_to_hex(&data->oid),
+		    type_name(data->type),
+		    (uintmax_t)data->size);
+}
+
 /*
  * If "pack" is non-NULL, then "offset" is the byte offset within the pack from
  * which the object may be accessed (though note that we may also rely on
@@ -388,8 +395,14 @@ static void batch_object_write(const char *obj_name,
 	}
 
 	strbuf_reset(scratch);
-	strbuf_expand(scratch, opt->format, expand_format, data);
-	strbuf_addch(scratch, '\n');
+
+	if (!opt->format) {
+		print_default_format(scratch, data);
+	} else {
+		strbuf_expand(scratch, opt->format, expand_format, data);
+		strbuf_addch(scratch, '\n');
+	}
+
 	batch_write(opt, scratch->buf, scratch->len);
 
 	if (opt->batch_mode == BATCH_MODE_CONTENTS) {
@@ -643,6 +656,8 @@ static void batch_objects_command(struct batch_options *opt,
 	strbuf_release(&input);
 }
 
+#define DEFAULT_FORMAT "%(objectname) %(objecttype) %(objectsize)"
+
 static int batch_objects(struct batch_options *opt)
 {
 	struct strbuf input = STRBUF_INIT;
@@ -651,9 +666,6 @@ static int batch_objects(struct batch_options *opt)
 	int save_warning;
 	int retval = 0;
 
-	if (!opt->format)
-		opt->format = "%(objectname) %(objecttype) %(objectsize)";
-
 	/*
 	 * Expand once with our special mark_query flag, which will prime the
 	 * object_info to be handed to oid_object_info_extended for each
@@ -661,12 +673,17 @@ static int batch_objects(struct batch_options *opt)
 	 */
 	memset(&data, 0, sizeof(data));
 	data.mark_query = 1;
-	strbuf_expand(&output, opt->format, expand_format, &data);
+	strbuf_expand(&output,
+		      opt->format ? opt->format : DEFAULT_FORMAT,
+		      expand_format,
+		      &data);
 	data.mark_query = 0;
 	strbuf_release(&output);
 	if (opt->transform_mode)
 		data.split_on_whitespace = 1;
 
+	if (opt->format && !strcmp(opt->format, DEFAULT_FORMAT))
+		opt->format = NULL;
 	/*
 	 * If we are printing out the object, then always fill in the type,
 	 * since we will want to decide whether or not to stream.
diff --git a/t/perf/p1006-cat-file.sh b/t/perf/p1006-cat-file.sh
new file mode 100755
index 00000000000..dcd80153796
--- /dev/null
+++ b/t/perf/p1006-cat-file.sh
@@ -0,0 +1,12 @@
+#!/bin/sh
+
+test_description='Tests listing object info performance'
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+test_perf 'cat-file --batch-check' '
+	git cat-file --batch-all-objects --batch-check
+'
+
+test_done

base-commit: b896f729e240d250cf56899e6a0073f6aa469f5d
-- 
gitgitgadget

^ permalink raw reply related	[flat|nested] 17+ messages in thread

end of thread, other threads:[~2022-03-15  2:40 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-03-04 21:37 [PATCH] cat-file: skip expanding default format John Cai via GitGitGadget
2022-03-07  5:56 ` Junio C Hamano
2022-03-07  6:11   ` Junio C Hamano
2022-03-07 17:41     ` John Cai
2022-03-07 12:15 ` Ævar Arnfjörð Bjarmason
2022-03-08  2:54 ` [PATCH v2] " John Cai via GitGitGadget
2022-03-08 16:59   ` Junio C Hamano
2022-03-08 19:01     ` John Cai
2022-03-08 22:00   ` Taylor Blau
2022-03-08 22:06     ` John Cai
2022-03-08 22:24     ` Taylor Blau
2022-03-08 22:45       ` John Cai
2022-03-08 22:08   ` [PATCH v3] " John Cai via GitGitGadget
2022-03-08 22:30     ` Taylor Blau
2022-03-08 23:09       ` John Cai
2022-03-08 23:34         ` John Cai
2022-03-15  2:40     ` [PATCH v4] " John Cai via GitGitGadget

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).