cat-file: skip expanding default format

Commit Message

John Cai March 4, 2022, 9:37 p.m. UTC

From: John Cai <[e-mail]>

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 <[e-mail]>
Signed-off-by: John Cai <[e-mail]>

See https://lore.kernel.org/git/[e-mail]/
---
    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/[e-mail]/

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


base-commit: 715d08a9e51251ad8290b181b6ac3b9e1f9719d7

Comments

Junio C Hamano March 7, 2022, 5:56 a.m. UTC | #1

"John Cai via GitGitGadget" <[e-mail]> writes:

> From: John Cai <[e-mail]>
>
> 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?

Junio C Hamano March 7, 2022, 6:11 a.m. UTC | #2

Junio C Hamano <[e-mail]> writes:

> "John Cai via GitGitGadget" <[e-mail]> writes:
>
>> From: John Cai <[e-mail]>
>>
>> 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?

Ævar Arnfjörð Bjarmason March 7, 2022, 12:15 p.m. UTC | #3

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

> From: John Cai <[e-mail]>
>
> 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 <[e-mail]>

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 <[e-mail]>
> [...]
> +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!

John Cai March 7, 2022, 5:41 p.m. UTC | #4

Hi Junio,

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

> Junio C Hamano <[e-mail]> writes:
>
>> "John Cai via GitGitGadget" <[e-mail]> writes:
>>
>>> From: John Cai <[e-mail]>
>>>
>>> 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.

Patch

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