Re: [PATCH v2 7/8] pack-bitmap: implement combined filter

From: Jeff King <peff@peff.net>
Date: Apr 6, 2021, 17:54 UTC
Message-ID: <YGygV1mesbJzdPr5@coredump.intra.peff.net>
In-Reply-To: <fac3477d979058da0430b974a34f7c7f866bf456.1615813673.git.ps@pks.im>

On Mon, Mar 15, 2021 at 02:14:59PM +0100, Patrick Steinhardt wrote:

Show 8 quoted lines

> When the user has multiple objects filters specified, then this is
> internally represented by having a "combined" filter. These combined
> filters aren't yet supported by bitmap indices and can thus not be
> accelerated.
> 
> Fix this by implementing support for these combined filters. The
> implementation is quite trivial: when there's a combined filter, we
> simply recurse into `filter_bitmap()` for all of the sub-filters.

The goal makes sense.

Before this patch, I think your test:

Show 6 quoted lines

> +test_expect_success 'combine filter' '
> +	git rev-list --objects --filter=blob:limit=1000 --filter=object:type=blob tag >expect &&
> +	git rev-list --use-bitmap-index \
> +		     --objects --filter=blob:limit=1000 --filter=object:type=blob tag >actual &&
> +	test_bitmap_traversal expect actual
> +'

would pass anyway, because we'd just skip using bitmaps. Is there a way we can tell that the bitmap code actually kicked in? Maybe a perf test would make it clear (those aren't always run, but hopefully we'd eventually notice a regression there).

Show 22 quoted lines

> +static int filter_supported(struct list_objects_filter_options *filter)
> +{
> +	int i;
> +
> +	switch (filter->choice) {
> +	case LOFC_BLOB_NONE:
> +	case LOFC_BLOB_LIMIT:
> +	case LOFC_OBJECT_TYPE:
> +		return 1;
> +	case LOFC_TREE_DEPTH:
> +		if (filter->tree_exclude_depth == 0)
> +			return 1;
> +		return 0;
> +	case LOFC_COMBINE:
> +		for (i = 0; i < filter->sub_nr; i++)
> +			if (!filter_supported(&filter->sub[i]))
> +				return 0;
> +		return 1;
> +	default:
> +		return 0;
> +	}
> +}

Hmm. This is essentially reproducing the list in filter_bitmap() of what's OK for bitmaps. So when adding a new filter, it would have to be added in both places.

Can we preserve that property of the original code? I'd think that just adding LOFC_COMBINE to filter_bitmap() would be sufficient. I.e., this hunk:

Show 8 quoted lines

> +	if (filter->choice == LOFC_COMBINE) {
> +		int i;
> +		for (i = 0; i < filter->sub_nr; i++) {
> +			filter_bitmap(bitmap_git, tip_objects, to_filter,
> +				      &filter->sub[i]);
> +		}
> +		return 0;
> +	}

...except that we need to see if filter_bitmap() returns "-1" for any of the recursive calls. Which we probably should be doing anyway to propagate any errors (though I think the only "errors" we'd return are "not supported", at least for now).

-Peff