Re: [PATCH v3 00/11] builtin/cat-file: allow filtering objects in batch mode

[Karthik Nayak <karthik.188@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 20066 bytes --]

Patrick Steinhardt <ps@pks.im> writes:

> Hi,
>
> at GitLab, we sometimes have the need to list all objects regardless of
> their reachability. We use git-cat-file(1) with `--batch-all-objects` to
> do this, and typically this is quite a good fit. In some cases though,
> we only want to list objects of a specific type, where we then basically
> have the following pipeline:
>
>     git cat-file --batch-all-objects --batch-check='%(objecttype) %(objectname)' |
>     grep '^commit ' |
>     cut -d' ' -f2 |
>     git cat-file --batch
>
> This works okayish in medium-sized repositories, but once you reach a
> certain size this isn't really an option anymore. In the Chromium
> repository for example [1] simply listing all objects in the first
> invocation of git-cat-file(1) takes around 80 to 100 seconds. The
> workload is completely I/O-bottlenecked: my machine reads at ~500MB/s,
> and the packfile is 50GB in size, which matches the 100 seconds that I
> observe.
>
> This series addresses the issue by introducing object filters into
> git-cat-file(1). These object filters use the exact same syntax as the
> filters we have in git-rev-list(1), but only a subset of them is
> supported because not all filters can be computed by git-cat-file(1).
> Supported are "blob:none", "blob:limit=" as well as "object:type=".
>
> The filters alone don't really help though: we still have to scan
> through the whole packfile in order to compute the packfiles. While we
> are able to shed a bit of CPU time because we can stop emitting some of
> the objects, we're still I/O-bottlenecked.
>
> The second part of the series thus expands the filters so that they can
> make use of bitmap indices for some of the filters, if available. This
> allows us to efficiently answer the question where to find all objects
> of a specific type, and thus we can avoid scanning through the packfile
> and instead directly look up relevant objects, leading to a significant
> speedup:
>
>     Benchmark 1: cat-file with filter=object:type=commit (revision = HEAD~)
>       Time (mean ± σ):     86.444 s ±  4.081 s    [User: 36.830 s, System: 11.312 s]
>       Range (min … max):   80.305 s … 93.104 s    10 runs
>
>     Benchmark 2: cat-file with filter=object:type=commit (revision = HEAD)
>       Time (mean ± σ):      2.089 s ±  0.015 s    [User: 1.872 s, System: 0.207 s]
>       Range (min … max):    2.073 s …  2.119 s    10 runs
>
>     Summary
>       cat-file with filter=object:type=commit (revision = HEAD) ran
>        41.38 ± 1.98 times faster than cat-file with filter=object:type=commit (revision = HEAD~)
>
> We now directly scale with the number of objects of a specific type
> contained in the packfile instead of scaling with the overall number of
> objects. It's quite fun to see how the math plays out: if you sum up the
> times for each of the types you arrive at the time for the unfiltered
> case.
>
> Changes in v2:
>   - The series is now built on top of "master" at 683c54c999c (Git 2.49,
>     2025-03-14) with "tb/incremental-midx-part-2" at 27afc272c49 (midx:
>     implement writing incremental MIDX bitmaps, 2025-03-20) merged into
>     it.
>   - Rename the filter options to "--filter=" to match
>     git-pack-objects(1).
>   - The bitmap-filtering is now reusing existing mechanisms that we
>     already have in "pack-bitmap.c", as proposed by Taylor.
>   - Link to v1: https://lore.kernel.org/r/20250221-pks-cat-file-object-type-filter-v1-0-0852530888e2@pks.im
>
> Changes in v3:
>   - Wrap some overly long lines.
>   - Better describe how filters interact with the different batch modes.
>   - Adapt the format with `--batch` and `--batch-check` so that we tell
>     the user that the object has been excluded.
>   - Add a test for "--no-filter".
>   - Use `OPT_PARSE_LIST_OBJECTS_FILTER()`.
>   - Link to v2: https://lore.kernel.org/r/20250327-pks-cat-file-object-type-filter-v2-0-4bbc7085d7c5@pks.im
>
> Thanks!
>
> Patrick
>
> [1]: https://github.com/chromium/chromium.git
>
> ---
> Patrick Steinhardt (11):
>       builtin/cat-file: rename variable that tracks usage
>       builtin/cat-file: introduce function to report object status
>       builtin/cat-file: wire up an option to filter objects
>       builtin/cat-file: support "blob:none" objects filter
>       builtin/cat-file: support "blob:limit=" objects filter
>       builtin/cat-file: support "object:type=" objects filter
>       pack-bitmap: allow passing payloads to `show_reachable_fn()`
>       pack-bitmap: add function to iterate over filtered bitmapped objects
>       pack-bitmap: introduce function to check whether a pack is bitmapped
>       builtin/cat-file: deduplicate logic to iterate over all objects
>       builtin/cat-file: use bitmaps to efficiently filter by object type
>
>  Documentation/git-cat-file.adoc |  26 ++++
>  builtin/cat-file.c              | 256 +++++++++++++++++++++++++++++-----------
>  builtin/pack-objects.c          |   3 +-
>  builtin/rev-list.c              |   3 +-
>  pack-bitmap.c                   |  81 +++++++++++--
>  pack-bitmap.h                   |  22 +++-
>  reachable.c                     |   3 +-
>  t/t1006-cat-file.sh             |  99 ++++++++++++++++
>  8 files changed, 411 insertions(+), 82 deletions(-)
>
> Range-diff versus v2:
>
>  1:  a75888e0bf4 !  1:  b0642b6c495 builtin/cat-file: rename variable that tracks usage
>     @@ builtin/cat-file.c: int cmd_cat_file(int argc,
>       		;
>       	else if (batch.follow_symlinks)
>      -		usage_msg_optf(_("'%s' requires a batch mode"), usage, options,
>     -+		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage, options,
>     - 			       "--follow-symlinks");
>     +-			       "--follow-symlinks");
>     ++		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage,
>     ++			       options, "--follow-symlinks");
>       	else if (batch.buffer_output >= 0)
>      -		usage_msg_optf(_("'%s' requires a batch mode"), usage, options,
>     -+		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage, options,
>     - 			       "--buffer");
>     +-			       "--buffer");
>     ++		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage,
>     ++			       options, "--buffer");
>       	else if (batch.all_objects)
>      -		usage_msg_optf(_("'%s' requires a batch mode"), usage, options,
>     -+		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage, options,
>     - 			       "--batch-all-objects");
>     +-			       "--batch-all-objects");
>     ++		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage,
>     ++			       options, "--batch-all-objects");
>       	else if (input_nul_terminated)
>      -		usage_msg_optf(_("'%s' requires a batch mode"), usage, options,
>     -+		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage, options,
>     - 			       "-z");
>     +-			       "-z");
>     ++		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage,
>     ++			       options, "-z");
>       	else if (nul_terminated)
>      -		usage_msg_optf(_("'%s' requires a batch mode"), usage, options,
>     -+		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage, options,
>     - 			       "-Z");
>     +-			       "-Z");
>     ++		usage_msg_optf(_("'%s' requires a batch mode"), builtin_catfile_usage,
>     ++			       options, "-Z");
>
>       	batch.input_delim = batch.output_delim = '\n';
>     + 	if (input_nul_terminated)
>      @@ builtin/cat-file.c: int cmd_cat_file(int argc,
>       			batch.transform_mode = opt;
>       		else if (opt && opt != 'b')
>     @@ builtin/cat-file.c: int cmd_cat_file(int argc,
>      +				       builtin_catfile_usage, options, opt);
>       		else if (argc)
>      -			usage_msg_opt(_("batch modes take no arguments"), usage,
>     -+			usage_msg_opt(_("batch modes take no arguments"), builtin_catfile_usage,
>     - 				      options);
>     +-				      options);
>     ++			usage_msg_opt(_("batch modes take no arguments"),
>     ++				      builtin_catfile_usage, options);
>
>       		return batch_objects(&batch);
>     + 	}
>      @@ builtin/cat-file.c: int cmd_cat_file(int argc,
>       	if (opt) {
>       		if (!argc && opt == 'c')
>       			usage_msg_optf(_("<rev> required with '%s'"),
>      -				       usage, options, "--textconv");
>     -+				       builtin_catfile_usage, options, "--textconv");
>     ++				       builtin_catfile_usage, options,
>     ++				       "--textconv");
>       		else if (!argc && opt == 'w')
>       			usage_msg_optf(_("<rev> required with '%s'"),
>      -				       usage, options, "--filters");
>     -+				       builtin_catfile_usage, options, "--filters");
>     ++				       builtin_catfile_usage, options,
>     ++				       "--filters");
>       		else if (!argc && opt_epts)
>       			usage_msg_optf(_("<object> required with '-%c'"),
>      -				       usage, options, opt);
>     @@ builtin/cat-file.c: int cmd_cat_file(int argc,
>       			obj_name = argv[0];
>       		else
>      -			usage_msg_opt(_("too many arguments"), usage, options);
>     -+			usage_msg_opt(_("too many arguments"), builtin_catfile_usage, options);
>     ++			usage_msg_opt(_("too many arguments"), builtin_catfile_usage,
>     ++				      options);
>       	} else if (!argc) {
>      -		usage_with_options(usage, options);
>      +		usage_with_options(builtin_catfile_usage, options);
>  -:  ----------- >  2:  18353ba706d builtin/cat-file: introduce function to report object status
>  2:  bee9407c1a9 !  3:  1e46af5d07b builtin/cat-file: wire up an option to filter objects
>     @@ Documentation/git-cat-file.adoc: OPTIONS
>      +--filter=<filter-spec>::
>      +--no-filter::
>      +	Omit objects from the list of printed objects. This can only be used in
>     -+	combination with one of the batched modes. The '<filter-spec>' may be
>     -+	one of the following:
>     ++	combination with one of the batched modes. Excluded objects that have
>     ++	been explicitly requested via any of the batch modes that read objects
>     ++	via standard input (`--batch`, `--batch-check`) will be reported as
>     ++	"filtered". Excluded objects in `--batch-all-objects` mode will not be
>     ++	printed at all. No filters are supported yet.
>      +
>       --path=<path>::
>       	For use with `--textconv` or `--filters`, to allow specifying an object
>       	name and a path separately, e.g. when it is difficult to figure out
>     +@@ Documentation/git-cat-file.adoc: the repository, then `cat-file` will ignore any custom format and print:
>     + <object> SP missing LF
>     + ------------
>     +
>     ++If a name is specified on stdin that is filtered out via `--filter=`,
>     ++then `cat-file` will ignore any custom format and print:
>     ++
>     ++------------
>     ++<object> SP excluded LF
>     ++------------
>     ++
>     + If a name is specified that might refer to more than one object (an ambiguous short sha), then `cat-file` will ignore any custom format and print:
>     +
>     + ------------
>
>       ## builtin/cat-file.c ##
>      @@
>     @@ builtin/cat-file.c: int cmd_cat_file(int argc,
>       			    N_("run filters on object's content"), 'w'),
>       		OPT_STRING(0, "path", &force_path, N_("blob|tree"),
>       			   N_("use a <path> for (--textconv | --filters); Not with 'batch'")),
>     -+		OPT_CALLBACK(0, "filter", &batch.objects_filter, N_("args"),
>     -+			     N_("object filtering"), opt_parse_list_objects_filter),
>     ++		OPT_PARSE_LIST_OBJECTS_FILTER(&batch.objects_filter),
>       		OPT_END()
>       	};
>
>     @@ builtin/cat-file.c: int cmd_cat_file(int argc,
>       	if (opt == 'b')
>       		batch.all_objects = 1;
>      @@ builtin/cat-file.c: int cmd_cat_file(int argc,
>     - 			usage_msg_opt(_("batch modes take no arguments"), builtin_catfile_usage,
>     - 				      options);
>     + 			usage_msg_opt(_("batch modes take no arguments"),
>     + 				      builtin_catfile_usage, options);
>
>      -		return batch_objects(&batch);
>      +		ret = batch_objects(&batch);
>     @@ t/t1006-cat-file.sh: test_expect_success PERL '--batch-command info is unbuffere
>      +		test_cmp expect err
>      +	'
>      +done
>     ++
>     ++test_expect_success 'objects filter: disabled' '
>     ++	git -C repo cat-file --batch-check="%(objectname)" --batch-all-objects --no-filter >actual &&
>     ++	sort actual >actual.sorted &&
>     ++	git -C repo rev-list --objects --no-object-names --all >expect &&
>     ++	sort expect >expect.sorted &&
>     ++	test_cmp expect.sorted actual.sorted
>     ++'
>      +
>       test_done
>  3:  ec1d0c63de6 !  4:  878ae8e2a76 builtin/cat-file: support "blob:none" objects filter
>     @@ Commit message
>          Implement support for the "blob:none" filter in git-cat-file(1), which
>          causes us to omit all blobs.
>
>     +    Note that this new filter requires us to read the object type via
>     +    `oid_object_info_extended()` in `batch_object_write()`. But as we try to
>     +    optimize away reading objects from the database the `data->info.typep`
>     +    pointer may not be set. We thus have to adapt the logic to conditionally
>     +    set the pointer in cases where the filter is given.
>     +
>          Signed-off-by: Patrick Steinhardt <ps@pks.im>
>
>       ## Documentation/git-cat-file.adoc ##
>      @@ Documentation/git-cat-file.adoc: OPTIONS
>     - 	Omit objects from the list of printed objects. This can only be used in
>     - 	combination with one of the batched modes. The '<filter-spec>' may be
>     - 	one of the following:
>     + 	been explicitly requested via any of the batch modes that read objects
>     + 	via standard input (`--batch`, `--batch-check`) will be reported as
>     + 	"filtered". Excluded objects in `--batch-all-objects` mode will not be
>     +-	printed at all. No filters are supported yet.
>     ++	printed at all. The '<filter-spec>' may be one of the following:
>      ++
>      +The form '--filter=blob:none' omits all blobs.
>
>     @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
>       		case LOFC_DISABLED:
>       			break;
>      +		case LOFC_BLOB_NONE:
>     -+			if (data->type == OBJ_BLOB)
>     ++			if (data->type == OBJ_BLOB) {
>     ++				if (!opt->all_objects)
>     ++					report_object_status(opt, obj_name,
>     ++							     &data->oid, "excluded");
>      +				return;
>     ++			}
>      +			break;
>       		default:
>       			BUG("unsupported objects filter");
>     @@ t/t1006-cat-file.sh: test_expect_success 'objects filter with unknown option' '
>       do
>       	test_expect_success "objects filter with unsupported option $option" '
>       		case "$option" in
>     -@@ t/t1006-cat-file.sh: do
>     - 	'
>     - done
>     +@@ t/t1006-cat-file.sh: test_expect_success 'objects filter: disabled' '
>     + 	test_cmp expect.sorted actual.sorted
>     + '
>
>      +test_objects_filter () {
>      +	filter="$1"
>     @@ t/t1006-cat-file.sh: do
>      +		sort expect >expect.sorted &&
>      +		test_cmp expect.sorted actual.sorted
>      +	'
>     ++
>     ++	test_expect_success "objects filter prints excluded objects: $filter" '
>     ++		# Find all objects that would be excluded by the current filter.
>     ++		git -C repo rev-list --objects --no-object-names --all >all &&
>     ++		git -C repo rev-list --objects --no-object-names --all --filter="$filter" --filter-provided-objects >filtered &&
>     ++		sort all >all.sorted &&
>     ++		sort filtered >filtered.sorted &&
>     ++		comm -23 all.sorted filtered.sorted >expected.excluded &&
>     ++		test_line_count -gt 0 expected.excluded &&
>     ++
>     ++		git -C repo cat-file --batch-check="%(objectname)" --filter="$filter" <expected.excluded >actual &&
>     ++		awk "/excluded/{ print \$1 }" actual | sort >actual.excluded &&
>     ++		test_cmp expected.excluded actual.excluded
>     ++	'
>      +}
>      +
>      +test_objects_filter "blob:none"
>  4:  a3ed054994d !  5:  a88d5d4b60a builtin/cat-file: support "blob:limit=" objects filter
>     @@ Commit message
>
>       ## Documentation/git-cat-file.adoc ##
>      @@ Documentation/git-cat-file.adoc: OPTIONS
>     - 	one of the following:
>     + 	printed at all. The '<filter-spec>' may be one of the following:
>       +
>       The form '--filter=blob:none' omits all blobs.
>      ++
>     @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
>       		if (pack)
>       			ret = packed_object_info(the_repository, pack, offset,
>      @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
>     - 			if (data->type == OBJ_BLOB)
>       				return;
>     + 			}
>       			break;
>      +		case LOFC_BLOB_LIMIT:
>      +			if (data->type == OBJ_BLOB &&
>     -+			    data->size >= opt->objects_filter.blob_limit_value)
>     ++			    data->size >= opt->objects_filter.blob_limit_value) {
>     ++				if (!opt->all_objects)
>     ++					report_object_status(opt, obj_name,
>     ++							     &data->oid, "excluded");
>      +				return;
>     ++			}
>      +			break;
>       		default:
>       			BUG("unsupported objects filter");
>     @@ t/t1006-cat-file.sh: test_objects_filter () {
>      +test_objects_filter "blob:limit=1"
>      +test_objects_filter "blob:limit=500"
>      +test_objects_filter "blob:limit=1000"
>     -+test_objects_filter "blob:limit=1g"
>     ++test_objects_filter "blob:limit=1k"
>
>       test_done
>  5:  8e39cd218c2 !  6:  13be54300c9 builtin/cat-file: support "object:type=" objects filter
>     @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
>       		if (opt->objects_filter.choice == LOFC_BLOB_LIMIT)
>       			data->info.sizep = &data->size;
>      @@ builtin/cat-file.c: static void batch_object_write(const char *obj_name,
>     - 			    data->size >= opt->objects_filter.blob_limit_value)
>       				return;
>     + 			}
>       			break;
>      +		case LOFC_OBJECT_TYPE:
>     -+			if (data->type != opt->objects_filter.object_type)
>     ++			if (data->type != opt->objects_filter.object_type) {
>     ++				if (!opt->all_objects)
>     ++					report_object_status(opt, obj_name,
>     ++							     &data->oid, "excluded");
>      +				return;
>     ++			}
>      +			break;
>       		default:
>       			BUG("unsupported objects filter");
>     @@ t/t1006-cat-file.sh: test_expect_success 'objects filter with unknown option' '
>      @@ t/t1006-cat-file.sh: test_objects_filter "blob:limit=1"
>       test_objects_filter "blob:limit=500"
>       test_objects_filter "blob:limit=1000"
>     - test_objects_filter "blob:limit=1g"
>     + test_objects_filter "blob:limit=1k"
>      +test_objects_filter "object:type=blob"
>      +test_objects_filter "object:type=commit"
>      +test_objects_filter "object:type=tag"
>  6:  a0655de3ace =  7:  d525a5bc2ef pack-bitmap: allow passing payloads to `show_reachable_fn()`
>  7:  e1e44303dac =  8:  e3cc1ae3a87 pack-bitmap: add function to iterate over filtered bitmapped objects
>  8:  23bc040bb15 =  9:  c0fc0e4ce0c pack-bitmap: introduce function to check whether a pack is bitmapped
>  9:  4eba2a70619 = 10:  28ef93dceec builtin/cat-file: deduplicate logic to iterate over all objects
> 10:  d40f1924ef5 = 11:  842a6002c50 builtin/cat-file: use bitmaps to efficiently filter by object type
>

Thanks for the new version, the range-diff looks good. Good that you
also added a test for "excluded" message too.

> ---
> base-commit: 003c5f45b8447877015b2a23ceab2297638fe1f1
> change-id: 20250220-pks-cat-file-object-type-filter-9140c0ed5ee1

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 690 bytes --]