patchbloom: enable bloom filter with wildcard pathspec in revision traversal

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. Enable Bloom filter even if a pathspec item contains wildcard characters by filter only the non-wildcard part of the pathspec item. Also Enable Bloom filter if magic signature is not "exclude" or "icase".

With this optimization, we get some improvements for pathspec with wildcard and magic signature. First, in the Git repository we see these modest results:

git log -100 -- "t/*"

Benchmark 1: new
  Time (mean ± σ):      20.7 ms ±   0.5 ms
  Range (min … max):    19.8 ms …  21.8 ms

Benchmark 2: old
  Time (mean ± σ):      25.4 ms ±   0.6 ms
  Range (min … max):    24.1 ms …  26.8 ms

git log -100 -- ":(top)t"

Benchmark 1: new
  Time (mean ± σ):      15.3 ms ±   0.3 ms
  Range (min … max):    14.5 ms …  16.1 ms

Benchmark 2: old
  Time (mean ± σ):      19.5 ms ±   0.5 ms
  Range (min … max):    18.7 ms …  20.7 ms

But in a larger repo, such as the LLVM project repo below, we get even better results:

git log -100 -- "libc/*"

Benchmark 1: new
  Time (mean ± σ):      10.1 ms ±   0.7 ms
  Range (min … max):     8.7 ms …  11.5 ms

Benchmark 2: old
  Time (mean ± σ):      26.1 ms ±   0.7 ms
  Range (min … max):    24.6 ms …  27.4 ms

git log -100 -- ":(top)libc"

Benchmark 1: new
  Time (mean ± σ):      11.0 ms ±   0.8 ms
  Range (min … max):     9.6 ms …  13.9 ms

Benchmark 2: old
  Time (mean ± σ):      20.7 ms ±   0.8 ms
  Range (min … max):    18.8 ms …  21.8 ms

Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>
---
 revision.c           | 26 ++++++++++++++++++++------
 t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----
 2 files changed, 47 insertions(+), 10 deletions(-)

On Thu, Aug 07, 2025 at 01:12:43PM +0800, Lidong Yan wrote:

In the subject it should be s/enable bloom/enable Bloom.

Let's add a paragraph here, as we now switch into the "what is being done mode".

s/by filter/by filtering/

This explains what is done, but not why this is safe to do.

"for pathspecs with wildcards or magic signatures".

The mask should be `unsigned`.

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.

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?

We typically indent the heredoc text to the same level as the command.

You can use `test_when_finished" instead to clean up after yourself even in case the test fails.

Patrick Steinhardt <ps@pks.im> wrote:

Will fix all the grammatical errors in next version.

I forgot to mention this — I’ll make sure to include it in the next commit message. 

Interesting and reasonable point — will fix.

If the first component contains the wildcard, convert_pathspec_to_bloom_keyvec() failed and returns -1, which lead to prepare_to_use_bloom_filter() cleanup (free and NULLing) all bloom filter related field. So the performant would be as same as bloom filter is not even tried.

I actually find a bug in my code and I will add test and fix it, the code should be

	if (len != pi->len)
		while (len > 0 && pi->match[len - 1])
			len—;
	if (len > 0 && pi->match[len - 1] == ‘/‘)
		len—;

Got it, will fix.

I see — I never knew how to deal with the issue where one failing test case causes all subsequent tests to fail.

Thanks, Lidong

Patrick Steinhardt <ps@pks.im> writes:

I agree, a paragraph break is very welcome here. I was confused when I read this first that you are suggesting to add a new paragraph with unspecified contents.

And for that, the enumeration needs to be done inclusively, e.g. "we know :(literal) is OK because we can do X; we know :(glob) is OK because we can do Y".

The numbers are impressive ;-)

Good suggestion. From the use of &-, it is obvious it is a mask, but "allow-mask" is not clear among what kind of things some are allowed, so how about calling it:

    unsigned allowed_magic;

Thanks.

Junio C Hamano <gitster@pobox.com> writes:

The bad news is that the Git versions I tested are 2.39 and 2.51, and I used git commit-graph write --split to build the commit graph, which resulted in a large value for filter_not_present in trace.perf.

The good news is that after rebuilding the commit-graph, I repeated the experiment on HEAD and HEAD~1, and the results on HEAD were still better. Anyway, I will update the experimental results in the next patch.

Thanks, Lidong

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.

For performance reason, enable Bloom filter even if a pathspec item contains wildcard characters by filtering only the non-wildcard part of the pathspec item.

The function of pathspec magic signature is generally to narrow down the path specified by the pathspecs. So, enable Bloom filter when the magic signature is "top", "glob", "attr", "--depth" or "literal". "exclude" is used to select paths other than the specified path, rather than serving as a filtering function, so it cannot be used together with the Bloom filter. Since Bloom filter is not case insensitive even in case insensitive system (e.g. MacOS), it cannot be used together with "icase" magic.

With this optimization, we get some improvements for pathspecs with wildcards or magic signatures. First, in the Git repository we see these modest results:

git log -100 -- "t/*"

Benchmark 1: new
  Time (mean ± σ):      20.4 ms ±   0.6 ms
  Range (min … max):    19.3 ms …  24.4 ms

Benchmark 2: old
  Time (mean ± σ):      23.4 ms ±   0.5 ms
  Range (min … max):    22.5 ms …  24.7 ms

git log -100 -- ":(top)t"

Benchmark 1: new
  Time (mean ± σ):      16.2 ms ±   0.4 ms
  Range (min … max):    15.3 ms …  17.2 ms

Benchmark 2: old
  Time (mean ± σ):      18.6 ms ±   0.5 ms
  Range (min … max):    17.6 ms …  20.4 ms

But in a larger repo, such as the LLVM project repo below, we get even better results:

git log -100 -- "libc/*"

Benchmark 1: new
  Time (mean ± σ):      16.0 ms ±   0.6 ms
  Range (min … max):    14.7 ms …  17.8 ms

Benchmark 2: old
  Time (mean ± σ):      26.7 ms ±   0.5 ms
  Range (min … max):    25.4 ms …  27.8 ms

git log -100 -- ":(top)libc"

Benchmark 1: new
  Time (mean ± σ):      15.6 ms ±   0.6 ms
  Range (min … max):    14.4 ms …  17.7 ms

Benchmark 2: old
  Time (mean ± σ):      19.6 ms ±   0.5 ms
  Range (min … max):    18.6 ms …  20.6 ms

Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>
---
 revision.c           | 30 ++++++++++++++++++++++++------
 t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----
 2 files changed, 51 insertions(+), 10 deletions(-)

Lidong Yan <yldhome2d2@gmail.com> writes:

Quite straight-forward and easy to see that this is a simple enhancement of the existing code. Good.

Leading "/" makes it look as if the pathspec element can begin with a slash, but it can not, can it?

In a tree that has both "builtin/" directory and "builtin.h" file, what pathspec_element do we get here when we run

	$ git log "builtin*"

We need to be able to catch commits that touch anything in "builtin/" and also anything at the top-level that begins with "builtin", like "builtin.h" and other things that might have existed ever in the history. I think len goes down to 0 and that is the correct behaviour.

The code does deal with the case where len is reduced down to zero, but a bit poorly. It would allocate a zero-length string, then realize it frees it, and returns -1. As it must know how long the resulting path is before it allocated, and by definition len is pi->len if it did not have to allocate, it should be able to take the "goto cleanup" code path before it even attempts to allocate, and it should not have to do strlen(). But the current code is not incorrect.

We'd ask the Bloom filter: skip commits that you know that can never be touching either "A/(anything)" or "file4".

We'd ask the Bloom filter: skip commits that you know that can never be touching either "A/".

What do we ask? The second one says that a commit that might touch "A/(something)" is worth investigating, but what about the first one?

Ahhh, that one is not quoted, so the shell expands to existing files (which presumably do not have any wildcard characters). OK. If the lone * were quoted, we shouldn't be using the Bloom filter.

OK, this is exactly the case I wondered about in the above wrt "builtin*" and I agree with the expectation of this test.

This one I understand. The first one reduces len down to 0 in the wildcard stripping loop, and makes us say "a commit that might touch any path is worth investigating", which amounts to the same thing as not using the Bloom filter at all.

Ditto. Even if the unquoted * may expand to many concrete paths, "file\*" that can match any path that begins with "file" that ever have existed in the history would not help skipping any commit.

Ditto.

OK. Good to see negative test cases here, which we sometimes forget to test when showing off our shiny new toy.

Taking what I suggested above, here is a possible improvement.

 revision.c | 18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)

Junio C Hamano <gitster@pobox.com> writes:

Yes, seems like if we pass a absolute path "/path/to/repository/dir/file”, git will automatically move "/path/to/repository” (in setup.c abspath_part_inside_repo()) So I should remove leading slash in my comment.

Thanks, I will apply this and add your signed-off. Lidong

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.

For performance reason, enable Bloom filter even if a pathspec item contains wildcard characters by filtering only the non-wildcard part of the pathspec item.

The function of pathspec magic signature is generally to narrow down the path specified by the pathspecs. So, enable Bloom filter when the magic signature is "top", "glob", "attr", "--depth" or "literal". "exclude" is used to select paths other than the specified path, rather than serving as a filtering function, so it cannot be used together with the Bloom filter. Since Bloom filter is not case insensitive even in case insensitive system (e.g. MacOS), it cannot be used together with "icase" magic.

With this optimization, we get some improvements for pathspecs with wildcards or magic signatures. First, in the Git repository we see these modest results:

git log -100 -- "t/*"

Benchmark 1: new
  Time (mean ± σ):      20.4 ms ±   0.6 ms
  Range (min … max):    19.3 ms …  24.4 ms

Benchmark 2: old
  Time (mean ± σ):      23.4 ms ±   0.5 ms
  Range (min … max):    22.5 ms …  24.7 ms

git log -100 -- ":(top)t"

Benchmark 1: new
  Time (mean ± σ):      16.2 ms ±   0.4 ms
  Range (min … max):    15.3 ms …  17.2 ms

Benchmark 2: old
  Time (mean ± σ):      18.6 ms ±   0.5 ms
  Range (min … max):    17.6 ms …  20.4 ms

But in a larger repo, such as the LLVM project repo below, we get even better results:

git log -100 -- "libc/*"

Benchmark 1: new
  Time (mean ± σ):      16.0 ms ±   0.6 ms
  Range (min … max):    14.7 ms …  17.8 ms

Benchmark 2: old
  Time (mean ± σ):      26.7 ms ±   0.5 ms
  Range (min … max):    25.4 ms …  27.8 ms

git log -100 -- ":(top)libc"

Benchmark 1: new
  Time (mean ± σ):      15.6 ms ±   0.6 ms
  Range (min … max):    14.4 ms …  17.7 ms

Benchmark 2: old
  Time (mean ± σ):      19.6 ms ±   0.5 ms
  Range (min … max):    18.6 ms …  20.6 ms

Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>
[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 revision.c           | 37 +++++++++++++++++++++++++++----------
 t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----
 2 files changed, 54 insertions(+), 14 deletions(-)

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.

For performance reason, enable Bloom filter even if a pathspec item contains wildcard characters by filtering only the non-wildcard part of the pathspec item.

The function of pathspec magic signature is generally to narrow down the path specified by the pathspecs. So, enable Bloom filter when the magic signature is "top", "glob", "attr", "--depth" or "literal". "exclude" is used to select paths other than the specified path, rather than serving as a filtering function, so it cannot be used together with the Bloom filter. Since Bloom filter is not case insensitive even in case insensitive system (e.g. MacOS), it cannot be used together with "icase" magic.

With this optimization, we get some improvements for pathspecs with wildcards or magic signatures. First, in the Git repository we see these modest results:

git log -100 -- "t/*"

Benchmark 1: new
  Time (mean ± σ):      20.4 ms ±   0.6 ms
  Range (min … max):    19.3 ms …  24.4 ms

Benchmark 2: old
  Time (mean ± σ):      23.4 ms ±   0.5 ms
  Range (min … max):    22.5 ms …  24.7 ms

git log -100 -- ":(top)t"

Benchmark 1: new
  Time (mean ± σ):      16.2 ms ±   0.4 ms
  Range (min … max):    15.3 ms …  17.2 ms

Benchmark 2: old
  Time (mean ± σ):      18.6 ms ±   0.5 ms
  Range (min … max):    17.6 ms …  20.4 ms

But in a larger repo, such as the LLVM project repo below, we get even better results:

git log -100 -- "libc/*"

Benchmark 1: new
  Time (mean ± σ):      16.0 ms ±   0.6 ms
  Range (min … max):    14.7 ms …  17.8 ms

Benchmark 2: old
  Time (mean ± σ):      26.7 ms ±   0.5 ms
  Range (min … max):    25.4 ms …  27.8 ms

git log -100 -- ":(top)libc"

Benchmark 1: new
  Time (mean ± σ):      15.6 ms ±   0.6 ms
  Range (min … max):    14.4 ms …  17.7 ms

Benchmark 2: old
  Time (mean ± σ):      19.6 ms ±   0.5 ms
  Range (min … max):    18.6 ms …  20.6 ms

Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>
[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 revision.c           | 45 +++++++++++++++++++++++++++-----------------
 t/t4216-log-bloom.sh | 31 ++++++++++++++++++++++++++----
 2 files changed, 55 insertions(+), 21 deletions(-)

Lidong Yan <yldhome2d2@gmail.com> writes:

I realized that I shouldn’t delete free(path_alloc) part in the patch. I wonder if Junio could help remove that part from the patch.

Thanks, Lidong

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.

For performance reason, enable Bloom filter even if a pathspec item contains wildcard characters by filtering only the non-wildcard part of the pathspec item.

The function of pathspec magic signature is generally to narrow down the path specified by the pathspecs. So, enable Bloom filter when the magic signature is "top", "glob", "attr", "--depth" or "literal". "exclude" is used to select paths other than the specified path, rather than serving as a filtering function, so it cannot be used together with the Bloom filter. Since Bloom filter is not case insensitive even in case insensitive system (e.g. MacOS), it cannot be used together with "icase" magic.

With this optimization, we get some improvements for pathspecs with wildcards or magic signatures. First, in the Git repository we see these modest results:

git log -100 -- "t/*"

Benchmark 1: new
  Time (mean ± σ):      20.4 ms ±   0.6 ms
  Range (min … max):    19.3 ms …  24.4 ms

Benchmark 2: old
  Time (mean ± σ):      23.4 ms ±   0.5 ms
  Range (min … max):    22.5 ms …  24.7 ms

git log -100 -- ":(top)t"

Benchmark 1: new
  Time (mean ± σ):      16.2 ms ±   0.4 ms
  Range (min … max):    15.3 ms …  17.2 ms

Benchmark 2: old
  Time (mean ± σ):      18.6 ms ±   0.5 ms
  Range (min … max):    17.6 ms …  20.4 ms

But in a larger repo, such as the LLVM project repo below, we get even better results:

git log -100 -- "libc/*"

Benchmark 1: new
  Time (mean ± σ):      16.0 ms ±   0.6 ms
  Range (min … max):    14.7 ms …  17.8 ms

Benchmark 2: old
  Time (mean ± σ):      26.7 ms ±   0.5 ms
  Range (min … max):    25.4 ms …  27.8 ms

git log -100 -- ":(top)libc"

Benchmark 1: new
  Time (mean ± σ):      15.6 ms ±   0.6 ms
  Range (min … max):    14.4 ms …  17.7 ms

Benchmark 2: old
  Time (mean ± σ):      19.6 ms ±   0.5 ms
  Range (min … max):    18.6 ms …  20.6 ms

Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>
[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 revision.c           | 42 +++++++++++++++++++++++++++++-------------
 t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----
 2 files changed, 56 insertions(+), 17 deletions(-)

Lidong Yan <yldhome2d2@gmail.com> writes:

Instead just do

        Helped-by: Junio C Hamano <gitster@pobox.com>
        Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>

here. [who: comment] followed by a sign-off from that person is done by the person who is signing off the tweak, not by the original author.

No need to resend; I'll fix it up locally.

Thanks.

Junio C Hamano <gitster@pobox.com> writes:

I see — when someone makes additions to another person’s commit, they’ll also modify the log message in the process.

Thanks, Lidong

Lidong Yan <yldhome2d2@gmail.com> writes:

This is different from what I did, though.

A missing full-stop.

Two comments.

 * For a function that finds an error condition in the middle and
   jumps to the "cleanup:" label at the end, it is more future-proof
   to start pessimistic (i.e. initialize 'res' to error(-1)) and
   flip 'res' to success(0) at the very end when everything went
   well.  It would simplify the change necessary when we need to add
   _more_ early error return code paths to the function in the
   future.

   But this flip from "assume success" to "assume failure" is
   something that should be not be done as part of this patch;
   perhaps doing it a separate preliminary clean-up patch is a
   better way to do so.

 * I think the change from v3 (this one) to v4 makes the function
   worse; we found that it is a good practice to have a single place
   to release any resources we temporarily acquired and arrange
   exception handling code to just jump there during the course of
   this project.

   The current implementation may happen to have only one such early
   return (i.e. "len has become 0; we realize that we cannot use the
   Bloom filter"), but adding a new early return in the future would
   be easier if you kept the original arrangement.  The new early
   return condition may have to be computed after we have acquired
   resources we need to release, so it may need more than a simple
   "return -1".

Junio C Hamano <gitster@pobox.com> writes:

Sorry, I don’t fully understand what you mean — should I remove this line or rewrite it?

Will fix.

Ah, I’ve always thought that `ret = -1; goto cleanup;` was a kind of the everybody-should-use pattern. So when I saw you write `int ret = -1;` first, I was a bit puzzled. Now I understand what you mean, and I’ll add a cleanup patch.

Understand. I was thinking about less code is better. I will add the cleanup part back.

Thanks, Lidong