cat-file: skip expanding default format

From: John Cai <[email protected]>

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.

Quoted 11 lines · John Cai via GitGitGadget

From: John Cai <[email protected]>

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 ...

builtin/cat-file.c static void batch_object_write(const char *obj_name, · line 407

Quoted 9 lines

builtin/cat-file.c +9 -0

+	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

builtin/cat-file.c static int batch_objects(struct batch_options *opt) · line 520

Quoted 7 lines

builtin/cat-file.c +0 -3

@@ -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?

Quoted 55 lines · Junio C Hamano

Quoted 11 lines · John Cai via GitGitGadget

From: John Cai <[email protected]>

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 ...

builtin/cat-file.c static void batch_object_write(const char *obj_name, · line 407

Quoted 9 lines

builtin/cat-file.c +9 -0

+	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

builtin/cat-file.c static int batch_objects(struct batch_options *opt) · line 520

Quoted 7 lines

builtin/cat-file.c +0 -3

@@ -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;

Quoted 6 lines

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?

From: John Cai <[email protected]>

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 <[email protected]>

Signed-off-by John Cai <[email protected]>

[...]

builtin/cat-file.c +14 -0

+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);

builtin/cat-file.c +0 -0

index 7b3f42950ec..ab9a49e13a4 100644

Quoted 5 lines · John Cai via GitGitGadget

builtin/cat-file.c +0 -0

index 7b3f42950ec..ab9a49e13a4 100644

builtin/cat-file.c static void print_object_or_die(struct batch_options *opt, struct expand_data *d · line 360

Quoted 10 lines

builtin/cat-file.c +7 -0

@@ -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.

builtin/cat-file.c static void batch_object_write(const char *obj_name, · line 377

Quoted 11 lines

builtin/cat-file.c +4 -0

 /*
  * 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)) {

(quoted diff) +0 -2

-		if (data->mark_query)
-			data->info.typep = &data->type;

	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.

Review static void batch_object_write(const char *obj_name, · line 377

Quoted 11 lines · John Cai via GitGitGadget

/*
* 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

(quoted diff) +4 -0

@@ -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 ---

builtin/cat-file.c +2 -11

index ab9a49e13a..9f55afa75b 100644
@@ -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

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

Quoted 2 lines · Taylor Blau

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< ---

builtin/cat-file.c +20 -15

index ab9a49e13a..4b3cfb9e68 100644
@@ -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

builtin/cat-file.c +0 -0

index 7b3f42950ec..e2edba70b41 100644

builtin/cat-file.c +1 -0

+
 /*
  * 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,
 		}

Quoted 8 lines · John Cai via GitGitGadget

builtin/cat-file.c +0 -0

index 7b3f42950ec..e2edba70b41 100644
@@ -351,6 +351,13 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
 	}
 }
 

builtin/cat-file.c static void print_object_or_die(struct batch_options *opt, struct expand_data *d · line 359

Quoted 6 lines

builtin/cat-file.c +6 -0

+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.

Quoted 7 lines

builtin/cat-file.c +1 -0

+
 /*
  * 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,
 		}

builtin/cat-file.c static void batch_object_write(const char *obj_name, · line 394

Quoted 10 lines

builtin/cat-file.c +4 -4

 	}
 
-	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.

t/perf/p1006-cat-file.sh line 3

Quoted 9 lines

t/perf/p1006-cat-file.sh new file +3 -0

new file mode 100755
index 00000000000..e463623f5a3
@@ -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.

t/perf/p1006-cat-file.sh line 14

Quoted 7 lines

t/perf/p1006-cat-file.sh new file +7 -0

+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

Hi Taylor,

Quoted 9 lines · Taylor Blau

Quoted 8 lines · John Cai via GitGitGadget

builtin/cat-file.c +0 -0

index 7b3f42950ec..e2edba70b41 100644
@@ -351,6 +351,13 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d
 	}
 }
 

Quoted 10 lines

builtin/cat-file.c static void print_object_or_die(struct batch_options *opt, struct expand_data *d · line 359

Quoted 6 lines

builtin/cat-file.c +6 -0

+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.

Quoted 6 lines

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.

Quoted 22 lines

Quoted 7 lines

builtin/cat-file.c +1 -0

+
 /*
  * 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,
 		}

builtin/cat-file.c static void batch_object_write(const char *obj_name, · line 394

Quoted 10 lines

builtin/cat-file.c +4 -4

 	}
 
-	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?

Quoted 3 lines

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?

Quoted 17 lines

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

t/perf/p1006-cat-file.sh line 3

Quoted 9 lines

t/perf/p1006-cat-file.sh new file +3 -0

new file mode 100755
index 00000000000..e463623f5a3
@@ -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.

Quoted 13 lines

t/perf/p1006-cat-file.sh line 10

Quoted 7 lines

t/perf/p1006-cat-file.sh new file +7 -0

+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!

Quoted 3 lines

Thanks,
Taylor