Re: [PATCH] bloom: enable bloom filter with wildcard pathspec in revision traversal
- From
Patrick Steinhardt <ps@pks.im>
- Date
- Aug 7, 2025, 06:49 UTC
- Message-ID
- <aJRMaYfMd3PlRtoz@pks.im>
- In-Reply-To
- <20250807051243.96884-1-yldhome2d2@gmail.com>
On Thu, Aug 07, 2025 at 01:12:43PM +0800, Lidong Yan wrote:
In the subject it should be s/enable bloom/enable Bloom.
Show 7 quoted lines
> When traversing commits, a pathspec item can be used to limit the > traversal to commits that modify the specified paths. And the > commit-graph includes a Bloom filter to exclude commits that definitely > did not modify a given pathspec item. During commit traversal, the > Bloom filter can significantly improve performance. However, it is > disabled if the specified pathspec item contains wildcard characters > or magic signatures.
Let's add a paragraph here, as we now switch into the "what is being done mode".
> Enable Bloom filter even if a pathspec item contains wildcard > characters by filter only the non-wildcard part of the pathspec item.
s/by filter/by filtering/
> Also Enable Bloom filter if magic signature is not "exclude" or > "icase".
This explains what is done, but not why this is safe to do.
> With this optimization, we get some improvements for pathspec with > wildcard and magic signature. First, in the Git repository we see these
"for pathspecs with wildcards or magic signatures".
Show 12 quoted lines
> diff --git a/revision.c b/revision.c
> index 18f300d455..ef8c0b6eca 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -671,12 +671,13 @@ static void trace2_bloom_filter_statistics_atexit(void)
>
> static int forbid_bloom_filters(struct pathspec *spec)
> {
> - if (spec->has_wildcard)
> - return 1;
> - if (spec->magic & ~PATHSPEC_LITERAL)
> + int forbid_mask =The mask should be `unsigned`.
> + PATHSPEC_EXCLUDE | PATHSPEC_ICASE;
I think instead of a forbid-mask we should use an allow-mask. Otherwise it can happen quite easily that we add new magic that isn't compatible with Bloom filters but forget to update this part here. I'd rather be slow but correct than fast but incorrect.
Show 33 quoted lines
> + if (spec->magic & forbid_mask)
> return 1;
> for (size_t nr = 0; nr < spec->nr; nr++)
> - if (spec->items[nr].magic & ~PATHSPEC_LITERAL)
> + if (spec->items[nr].magic & forbid_mask)
> return 1;
>
> return 0;
> @@ -693,9 +694,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,
> size_t len;
> int res = 0;
>
> + len = pi->nowildcard_len;
> /* remove single trailing slash from path, if needed */
> - if (pi->len > 0 && pi->match[pi->len - 1] == '/') {
> - path_alloc = xmemdupz(pi->match, pi->len - 1);
> + if (len > 0 && pi->match[len - 1] == '/')
> + len--;
> + else if (len != pi->len) {
> + /*
> + * for path like "/dir/file*", nowildcard part would be
> + * "/dir/file", but only "/dir" should be used for the
> + * bloom filter
> + */
> + while (len > 0 && pi->match[len - 1] != '/')
> + len--;
> + }
> +
> + if (len != pi->len) {
> + path_alloc = xmemdupz(pi->match, len);
> path = path_alloc;
> } else
> path = pi->match;Okay, this matches what I've expected: if we have a wildcard we cannot match on the component that contains the wildcard itself. But what we _can_ do is to match on all the components leading to that wildcard component.
One thing I did wonder though: what happens if the first component contains the wildcard? We cannot really make any use of the Bloom filter in that case as the path we match against becomes empty. I expect that we'll handle this just fine. But is it still more performant than not even trying Bloom filters in the first place?
Show 37 quoted lines
> diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh > index 639868ac56..d8200e4dcb 100755 > --- a/t/t4216-log-bloom.sh > +++ b/t/t4216-log-bloom.sh > @@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' ' > test_bloom_filters_used "-- file*" > ' > > -test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' > +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' ' > + test_bloom_filters_used "-- A/\* file4" && > + test_bloom_filters_used "-- file4 A/\*" && > + test_bloom_filters_used "-- * A/\*" > +' > + > +test_expect_success 'git log with path only contains wildcard part does not use Bloom filter' ' > test_bloom_filters_not_used "-- file\*" && > - test_bloom_filters_not_used "-- A/\* file4" && > - test_bloom_filters_not_used "-- file4 A/\*" && > - test_bloom_filters_not_used "-- * A/\*" > + test_bloom_filters_not_used "-- file\* A/\*" && > + test_bloom_filters_not_used "-- file\* *" && > + test_bloom_filters_not_used "-- \*" > +' > + > +test_expect_success 'git log with path contains various magic signatures' ' > + cd A && > + test_bloom_filters_used "-- \:\(top\)B" && > + cd .. && > + > + test_bloom_filters_used "-- \:\(glob\)A/\*\*/C" && > + test_bloom_filters_not_used "-- \:\(icase\)FILE4" && > + test_bloom_filters_not_used "-- \:\(exclude\)A/B/C" && > + > + cat >.gitattributes <<-EOF && > + A/file1 text > + A/B/file2 -text
We typically indent the heredoc text to the same level as the command.
> + EOF > + test_bloom_filters_used "-- \:\(attr\:text\)A" && > + rm .gitattributes
You can use `test_when_finished" instead to clean up after yourself even in case the test fails.