From: Patrick Steinhardt <ps@pks•im>
To: Lidong Yan <yldhome2d2@gmail•com>
Cc: git@vger•kernel.org, stolee@gmail•com, gitster@pobox•com,
ttaylorr@github•com
Subject: Re: [PATCH] bloom: enable bloom filter with wildcard pathspec in revision traversal
Date: Thu, 7 Aug 2025 08:49:13 +0200 [thread overview]
Message-ID: <aJRMaYfMd3PlRtoz@pks.im> (raw)
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.
> 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".
> 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.
> + 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?
> 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.
next prev parent reply other threads:[~2025-08-07 6:49 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-08-07 5:12 [PATCH] bloom: enable bloom filter with wildcard pathspec in revision traversal Lidong Yan
2025-08-07 6:49 ` Patrick Steinhardt [this message]
2025-08-07 8:59 ` Lidong Yan
2025-08-07 16:15 ` Junio C Hamano
2025-08-08 6:40 ` Lidong Yan
2025-08-08 6:58 ` [PATCH v2] " Lidong Yan
2025-08-08 15:50 ` Junio C Hamano
2025-08-09 2:06 ` Lidong Yan
2025-08-09 2:16 ` [PATCH v3] " Lidong Yan
2025-08-09 4:22 ` [PATCH v4] " Lidong Yan
2025-08-09 7:40 ` Lidong Yan
2025-08-11 6:01 ` [PATCH v5] " Lidong Yan
2025-08-11 15:56 ` Junio C Hamano
2025-08-11 16:08 ` Lidong Yan
2025-08-09 23:51 ` [PATCH v3] " Junio C Hamano
2025-08-10 1:57 ` Lidong Yan
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=aJRMaYfMd3PlRtoz@pks.im \
--to=ps@pks$(echo .)im \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=stolee@gmail$(echo .)com \
--cc=ttaylorr@github$(echo .)com \
--cc=yldhome2d2@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox