# [PATCH v3 1/6] revision: move bloom keyvec precondition into function

22 messages from 2026-08-31 to 2026-09-10. Participants: Toon Claes, Junio C Hamano, Patrick Steinhardt.
Thread: https://gitlist.dev/t/66240

## Toon Claes, 2026-08-31 15:18

Subject: [PATCH v3 1/6] revision: move bloom keyvec precondition into function
Message-ID: <20260831-toon-speed-up-last-modified-v3-1-2bbb864acf93@iotcl.com>
In-Reply-To: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>

```
There are currently two callsites calling
check_maybe_different_in_bloom_filter(). They both check if
revs->bloom_keyvecs_nr is not zero before they call that function.

Move bloom_keyvecs_nr precondition into
check_maybe_different_in_bloom_filter() to simplify the code.

Note that this changes `bloom_ret` to become -1 when there are no Bloom
key vectors, which results in `count_bloom_filter_false_positive` not
being incremented. This is unobservable, as the Bloom statistics are
only reported when key vectors were set up.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 revision.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/revision.c b/revision.c
index 50dc8b1991..6a6a1b6fa0 100644
--- a/revision.c
+++ b/revision.c
@@ -752,6 +752,9 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 	struct bloom_filter *filter;
 	int result = 0;
 
+	if (!revs->bloom_keyvecs_nr)
+		return -1;
+
 	if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
 		return -1;
 
@@ -806,7 +809,7 @@ static int rev_compare_tree(struct rev_info *revs,
 			return REV_TREE_SAME;
 	}
 
-	if (revs->bloom_keyvecs_nr && !nth_parent) {
+	if (!nth_parent) {
 		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
 
 		if (bloom_ret == 0)
@@ -833,7 +836,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,
 	if (!t1)
 		return 0;
 
-	if (!nth_parent && revs->bloom_keyvecs_nr) {
+	if (!nth_parent) {
 		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
 		if (!bloom_ret)
 			return 1;

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-08-31 15:18

Subject: [PATCH v3 2/6] revision: expose check for paths maybe changed in Bloom filter
Message-ID: <20260831-toon-speed-up-last-modified-v3-2-2bbb864acf93@iotcl.com>
In-Reply-To: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>

```
check_maybe_different_in_bloom_filter() looks up a commit's changed-path
Bloom filter and consults it to see whether the commit might have
modified any of the paths in the pathspec that `revs` was set up with.
In a follow-up commit we want to reuse this logic from another builtin.

That caller, however, has already looked up the commit's Bloom filter
for its own purposes, so having the function look it up again would mean
a redundant lookup.

Extract the filter-consulting part into a new public function,
revs_maybe_changed_in_bloom(). This function takes an already looked-up
`struct bloom_filter` instead of a commit.
The existing check_maybe_different_in_bloom_filter() becomes a thin
wrapper that looks up the filter and delegates.

Expose the new function via revision.h so other builtins can reuse the
exact same filtering that `git log <pathspec>` performs.

The existing function check_maybe_different_in_bloom_filter() returns a
tristate value. This returns either:

 * `-1` : No Bloom filter was used.
 *  `0` : The commit definitely did not change any of the paths.
 *  `1` : The commit maybe changed one of the paths.

These return values are used to keep count of false-positives. But
because the new function revs_maybe_changed_in_bloom() is not involved
in counting statistics, it returns a boolean value telling whether the
commit definitely did not change any of the paths, or maybe changed some
of them.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 revision.c | 30 ++++++++++++++++++++----------
 revision.h | 12 ++++++++++++
 2 files changed, 32 insertions(+), 10 deletions(-)

diff --git a/revision.c b/revision.c
index 6a6a1b6fa0..ed46b90b00 100644
--- a/revision.c
+++ b/revision.c
@@ -750,7 +750,6 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 						 struct commit *commit)
 {
 	struct bloom_filter *filter;
-	int result = 0;
 
 	if (!revs->bloom_keyvecs_nr)
 		return -1;
@@ -765,18 +764,29 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 		return -1;
 	}
 
-	for (size_t nr = 0; !result && nr < revs->bloom_keyvecs_nr; nr++) {
-		result = bloom_filter_contains_vec(filter,
-						   revs->bloom_keyvecs[nr],
-						   revs->bloom_filter_settings);
+	if (revs_maybe_changed_in_bloom(revs, filter)) {
+		count_bloom_filter_maybe++;
+		return 1;
 	}
 
-	if (result)
-		count_bloom_filter_maybe++;
-	else
-		count_bloom_filter_definitely_not++;
+	count_bloom_filter_definitely_not++;
+
+	return 0;
+}
+
+bool revs_maybe_changed_in_bloom(struct rev_info *revs,
+				 struct bloom_filter *filter)
+{
+	if (!revs->bloom_keyvecs_nr || !filter)
+		return true;
+
+	for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
+		if (bloom_filter_contains_vec(filter,
+					      revs->bloom_keyvecs[nr],
+					      revs->bloom_filter_settings))
+			return true;
 
-	return result;
+	return false;
 }
 
 static int rev_compare_tree(struct rev_info *revs,
diff --git a/revision.h b/revision.h
index acf6d06b24..67778558e1 100644
--- a/revision.h
+++ b/revision.h
@@ -68,6 +68,7 @@ struct string_list;
 struct saved_parents;
 struct follow_pathspec_slab;
 struct bloom_keyvec;
+struct bloom_filter;
 struct bloom_filter_settings;
 struct option;
 struct parse_opt_ctx_t;
@@ -495,6 +496,17 @@ void reset_revision_walk(void);
  */
 int prepare_revision_walk(struct rev_info *revs);
 
+/**
+ * Consult a changed-path Bloom filter to determine if the commit to which the
+ * filter belongs might have changed any of the paths in the `revs`.
+ * prepare_revision_walk() needs to be called in advance to ensure
+ * pathspec key vectors are set up.
+ *
+ * Returns false iff the commit definitely did not change any of the paths.
+ */
+bool revs_maybe_changed_in_bloom(struct rev_info *revs,
+				 struct bloom_filter *filter);
+
 /* Drain the commits linked list into the priority queue. */
 void rev_info_commit_list_to_queue(struct rev_info *revs);
 /**

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-08-31 15:18

Subject: [PATCH v3 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits
Message-ID: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>
In-Reply-To: <20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com>

```
We have received a report[1] git-last-modified(1) is slow compared to
git-log(1) if you want to find the last commit for all entries in a
directory. For example running the following command on ziglang/zig[2]:

   $ git last-modified -t --max-depth=0 $OID -- doc/langref/

Turns out to find results about 2.5 times slower than:

   $ git log --name-status -c --format=commit%x00%H %P%x00" \
       --parents --no-renames -t -z $OID -- :(literal)doc/langref

Now the latter needs some post-processing to come to the same results,
the total solution still is faster than integrating
git-last-modified(1).

After some research we've discovered the Bloom filters aren't used
optimally. But it turns out the code powering git-log(1) can fairly easy
be reused. We do this in a few steps:

 - Patch 1 & 2 prepare revision.[ch] to expose the helper to check if
   revs maybe changes in Bloom filter.
 - Patch 3 & 4 prepare a similar helper, but this one is needed when
   git-last-modified(1) is called with `--show-trees`.
 - Patch 5 uses these helpers in git-last-modified(1).
 - Patch 6 is a bonus change, which optimizes when working with wildcard
   pathspecs.

Below are benchmarks on the ziglang/zig repository for the
`doc/langref/` directory (with commit-graphs written using
`--changed-paths`):

    Benchmark 1: master: last-modified -z -t
      Time (mean ± σ):      61.9 ms ±   1.8 ms    [User: 57.1 ms, System: 4.0 ms]
      Range (min … max):    58.5 ms …  68.9 ms    150 runs

    Benchmark 2: HEAD: last-modified -z -t
      Time (mean ± σ):      31.8 ms ±   1.3 ms    [User: 27.1 ms, System: 4.2 ms]
      Range (min … max):    29.7 ms …  35.6 ms    150 runs

    Benchmark 3: git log -t
      Time (mean ± σ):      22.1 ms ±   1.2 ms    [User: 16.7 ms, System: 5.0 ms]
      Range (min … max):    20.1 ms …  26.6 ms    150 runs

    Summary
      git log -t ran
        1.44 ± 0.10 times faster than HEAD: last-modified -z -t
        2.80 ± 0.18 times faster than master: last-modified -z -t

Comparing HEAD to master, there is about 1.95x speedup on running `git
last-modified -z -t. `git log -t` is still slightly faster though.

But without `-t` the speedup is even bigger:

    Benchmark 1: master: last-modified -z
      Time (mean ± σ):      60.7 ms ±   4.5 ms    [User: 56.5 ms, System: 3.8 ms]
      Range (min … max):    57.5 ms …  96.2 ms    150 runs

    Benchmark 2: HEAD: last-modified -z
      Time (mean ± σ):      16.2 ms ±   1.4 ms    [User: 13.3 ms, System: 2.7 ms]
      Range (min … max):    13.9 ms …  20.4 ms    212 runs

    Benchmark 3: git log (no -t)
      Time (mean ± σ):      22.0 ms ±   3.7 ms    [User: 16.8 ms, System: 4.9 ms]
      Range (min … max):    18.7 ms …  37.6 ms    150 runs

    Summary
      HEAD: last-modified -z ran
        1.35 ± 0.25 times faster than git log (no -t)
        3.74 ± 0.42 times faster than master: last-modified -z

This makes sense because without `-t` we can use the Bloom filter more
optimally.

Similar timings are seen across a few other repositories (like GitLab's
monolith gitlab-org/gitlab).

[1]: https://lore.kernel.org/git/17f356ff-7bfb-47f5-b714-62a95cc8b821@codeberg.org/
[2]: https://codeberg.org/ziglang/zig

---
Changes in v3:
- Add trace2 "bloom_queries" and use it in test to verify top-level
  wildcard behavior.
- Link to v2: https://patch.msgid.link/20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com

Changes in v2:
- Make the public helper revs_maybe_changed_in_bloom() return a bool
  instead of a tristate.
- Keep the bloom_keyvecs_nr precondition before get_bloom_filter() and
  return early from the key vector loop.
- Add commits 3 & 4 to add helper used with `--show-trees`.
- Use Bloom filter correctly with `--show-trees` and add test to prove.
- Rerun benchmarks to compare results with and without `--show-trees`.
- Link to v1: https://patch.msgid.link/20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com

---
Toon Claes (6):
      revision: move bloom keyvec precondition into function
      revision: expose check for paths maybe changed in Bloom filter
      bloom: add helper to check if any key in a vector is present
      revision: add Bloom check that includes parent directories
      last-modified: check pathspec against Bloom filter first
      last-modified: keep per-path Bloom filters for wildcard pathspecs

 bloom.c                  | 12 +++++++++++
 bloom.h                  | 11 ++++++++++
 builtin/last-modified.c  | 28 ++++++++++++++++++++++++++
 revision.c               | 52 +++++++++++++++++++++++++++++++++++++-----------
 revision.h               | 20 +++++++++++++++++++
 t/t8020-last-modified.sh | 47 +++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 158 insertions(+), 12 deletions(-)

Range-diff versus v2:

1:  a98bbaad50 = 1:  ac58e4a3cd revision: move bloom keyvec precondition into function
2:  ebf4f65fab = 2:  43375b505e revision: expose check for paths maybe changed in Bloom filter
3:  7a3c14fe87 = 3:  41e3a19fde bloom: add helper to check if any key in a vector is present
4:  145c95a2fa = 4:  a648612927 revision: add Bloom check that includes parent directories
5:  9dc5a0be79 = 5:  0e8721fe75 last-modified: check pathspec against Bloom filter first
6:  83036c2fe4 ! 6:  e7997e0a9b last-modified: keep per-path Bloom filters for wildcard pathspecs
    @@ Commit message
         Restore `bloom_filter_settings` after prepare_revision_walk() so the
         per-path check keeps working for wildcard pathspecs.
     
    +    This change isn't having any effect on the output, but only has an
    +    impact on performance. Add a "bloom_queries" trace2 counter that records
    +    how often the per-path Bloom check runs, and a test that asserts the
    +    count increments as appropriate for a top-level wildcard pathspec.
    +
         Signed-off-by: Toon Claes <toon@iotcl.com>
     
      ## builtin/last-modified.c ##
    +@@
    + #include "quote.h"
    + #include "repository.h"
    + #include "revision.h"
    ++#include "trace2.h"
    + 
    + /* Remember to update object flag allocation in object.h */
    + #define PARENT1 (1u<<16) /* used instead of SEEN */
    +@@ builtin/last-modified.c: struct last_modified {
    + 
    + 	/* 'scratch' to avoid allocating a bitmap every process_parent() */
    + 	struct bitmap *scratch;
    ++
    ++	unsigned int count_bloom_filter_queries;
    + };
    + 
    + static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)
    +@@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm,
    + 	if (!filter)
    + 		return true;
    + 
    ++	lm->count_bloom_filter_queries++;
    ++
    + 	/*
    + 	 * With --show-trees we also track the tree entries containing the
    + 	 * paths, so a change to any of those parent directories matters too.
     @@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)
      
      	prepare_revision_walk(&lm->rev);
    @@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)
      	max_count = lm->rev.max_count;
      
      	init_active_paths_for_commit(&lm->active_paths);
    +@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)
    + 	if (hashmap_get_size(&lm->paths))
    + 		BUG("paths remaining beyond boundary in last-modified");
    + 
    ++	trace2_data_intmax("last-modified", lm->rev.repo, "bloom_queries",
    ++			   lm->count_bloom_filter_queries);
    ++
    + 	clear_prio_queue(&not_queue);
    + 	clear_prio_queue(&queue);
    + 	clear_active_paths_for_commit(&lm->active_paths);
    +
    + ## t/t8020-last-modified.sh ##
    +@@ t/t8020-last-modified.sh: test_expect_success 'last-modified with Bloom filters and --show-trees' '
    + 	)
    + '
    + 
    ++test_expect_success 'last-modified with Bloom filters and top-level wildcard' '
    ++	test_when_finished rm -rf wildcard &&
    ++	git init wildcard &&
    ++	(
    ++		cd wildcard &&
    ++		test_commit base-c a.c &&
    ++		test_commit base-h a.h &&
    ++		test_commit touch-c a.c &&
    ++		mkdir d &&
    ++		test_commit sub-c d/b.c &&
    ++
    ++		git commit-graph write --reachable --changed-paths &&
    ++		GIT_TRACE2_PERF="$(pwd)/off.perf" \
    ++			git -c core.commitGraph=false last-modified -r HEAD \
    ++			-- "*.c" >expect &&
    ++		test_grep "data .* bloom_queries:0$" off.perf &&
    ++
    ++		GIT_TRACE2_PERF="$(pwd)/on.perf" \
    ++			git -c core.commitGraph=true last-modified -r HEAD \
    ++			-- "*.c" >actual &&
    ++		test_grep "data .* bloom_queries:2$" on.perf &&
    ++
    ++		test_cmp expect actual
    ++	)
    ++'
    ++
    + test_expect_success 'cannot run last-modified on two commits' '
    + 	test_must_fail git last-modified HEAD HEAD~1 2>err &&
    + 	test_grep "last-modified can only operate on one commit at a time" err


---
base-commit: c73e85354c275c9d409b26445089bc16940fc527
change-id: 20260716-toon-speed-up-last-modified-b04ea1f21831


```

## Toon Claes, 2026-08-31 15:18

Subject: [PATCH v3 3/6] bloom: add helper to check if any key in a vector is present
Message-ID: <20260831-toon-speed-up-last-modified-v3-3-2bbb864acf93@iotcl.com>
In-Reply-To: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>

```
The changed-path Bloom filter of a commit stores a key for every changed
path together with each of its leading directories. To query if a path
was changed, bloom_keyvec_new() fills a key vector the same way: a key
for the given path and one for each of its leading directories. For
example, for "a/b/c" the vector holds keys for "a/b/c", "a/b" and "a".

A Bloom filter can only ever prove absence. When a key is not in the
filter, the path it was made for definitely did not change. When it is
in the filter, the path may have changed, as the key can be a false
positive.

bloom_filter_contains_vec() looks up all keys of a vector and reports
whether all of them are present. That answers: Is this path maybe
changed by this commit?

A caller that also cares about the directories containing the path asks
a different question: Is this path, or any directory leading up to it,
maybe changed by this commit?

Consider the Bloom filter of a commit that changed "a/b/d". It holds
keys for "a/b/d", "a/b" and "a", so looking up the vector of "a/b/c"
with bloom_filter_contains_vec() reports that nothing changed, even
though "a/b" and "a" did.

Add bloom_filter_contains_any_vec(), which reports whether any key in
the vector is present. It returns 0 only when none of the keys are in
the filter, which means the path and all directories leading up to it
definitely did not change.

There are no callers yet, one is added in a subsequent commit.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 bloom.c | 12 ++++++++++++
 bloom.h | 11 +++++++++++
 2 files changed, 23 insertions(+)

diff --git a/bloom.c b/bloom.c
index caf22f9831..b96534e6e3 100644
--- a/bloom.c
+++ b/bloom.c
@@ -607,6 +607,18 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,
 	return ret;
 }
 
+int bloom_filter_contains_any_vec(const struct bloom_filter *filter,
+				  const struct bloom_keyvec *vec,
+				  const struct bloom_filter_settings *settings)
+{
+	int ret = 0;
+
+	for (size_t nr = 0; !ret && nr < vec->count; nr++)
+		ret = bloom_filter_contains(filter, &vec->key[nr], settings);
+
+	return ret;
+}
+
 uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,
 				   int version)
 {
diff --git a/bloom.h b/bloom.h
index 92ab2100d3..f508db23ad 100644
--- a/bloom.h
+++ b/bloom.h
@@ -164,6 +164,17 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,
 			      const struct bloom_keyvec *v,
 			      const struct bloom_filter_settings *settings);
 
+/*
+ * bloom_filter_contains_any_vec - Check if any key in a key vector is in the
+ * Bloom filter.
+ *
+ * Returns 1 if **any** key in the vector is present in the filter, 0 if none
+ * of them are.
+ */
+int bloom_filter_contains_any_vec(const struct bloom_filter *filter,
+				  const struct bloom_keyvec *v,
+				  const struct bloom_filter_settings *settings);
+
 uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,
 				   int version);
 

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-08-31 15:18

Subject: [PATCH v3 4/6] revision: add Bloom check that includes parent directories
Message-ID: <20260831-toon-speed-up-last-modified-v3-4-2bbb864acf93@iotcl.com>
In-Reply-To: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>

```
revs_maybe_changed_in_bloom() reports whether a commit may have changed
any of the paths in the pathspec. It uses bloom_filter_contains_vec(),
which requires all keys of a path's key vector to be present, so it only
answers for the paths themselves.

A caller may track more than those paths. git-last-modified(1) with
--show-trees reports the last modifying commit for the tree entries
containing the paths as well, up to the root. For a pathspec "a/b/c/"
that means it reports "a" and "a/b" next to "a/b/c" and its entries, and
those can each resolve to a different commit. A commit that only changed
"a/top" is the answer for "a", even though it touched nothing under
"a/b".

Such a caller needs to know whether the path, or any of the directories
leading up to it, may have changed. Add
revs_maybe_changed_in_bloom_with_parents(), which asks that question by
using bloom_filter_contains_any_vec() instead. A key vector holds a key
for the path and one for each of its leading directories, so looking up
any of them answers it.

There are no callers yet, one is added in a subsequent commit.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 revision.c | 15 +++++++++++++++
 revision.h |  8 ++++++++
 2 files changed, 23 insertions(+)

diff --git a/revision.c b/revision.c
index ed46b90b00..a560146b4d 100644
--- a/revision.c
+++ b/revision.c
@@ -789,6 +789,21 @@ bool revs_maybe_changed_in_bloom(struct rev_info *revs,
 	return false;
 }
 
+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,
+					      struct bloom_filter *filter)
+{
+	if (!revs->bloom_keyvecs_nr || !filter)
+		return true;
+
+	for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
+		if (bloom_filter_contains_any_vec(filter,
+						  revs->bloom_keyvecs[nr],
+						  revs->bloom_filter_settings))
+			return true;
+
+	return false;
+}
+
 static int rev_compare_tree(struct rev_info *revs,
 			    struct commit *parent, struct commit *commit, int nth_parent)
 {
diff --git a/revision.h b/revision.h
index 67778558e1..192001ff79 100644
--- a/revision.h
+++ b/revision.h
@@ -507,6 +507,14 @@ int prepare_revision_walk(struct rev_info *revs);
 bool revs_maybe_changed_in_bloom(struct rev_info *revs,
 				 struct bloom_filter *filter);
 
+/**
+ * Same as revs_maybe_changed_in_bloom(), but a change to any of the directories
+ * leading up to a path counts as well. Callers that track the tree entries
+ * containing the paths, and not just the paths themselves, need this.
+ */
+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,
+					      struct bloom_filter *filter);
+
 /* Drain the commits linked list into the priority queue. */
 void rev_info_commit_list_to_queue(struct rev_info *revs);
 /**

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-08-31 15:18

Subject: [PATCH v3 5/6] last-modified: check pathspec against Bloom filter first
Message-ID: <20260831-toon-speed-up-last-modified-v3-5-2bbb864acf93@iotcl.com>
In-Reply-To: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>

```
When git-last-modified(1) starts, it builds a list of all the paths
matching the pathspec it needs to find the last modifying commit for.
For example, every file and subdirectory listed by:

    $ git last-modified -t --max-depth=0 -- src/

As it resolves a commit for each path during the revision walk, it drops
that path from the list.

To avoid diffing trees for every commit, Bloom filters are used when
available. For each remaining path, the commit's Bloom filter is checked
to see whether the commit changed that path. The Bloom filter says
either "no" or "maybe", and only in the latter case is the diff
calculated.

git-log(1) does this differently. It does not expand the pathspec but
checks the Bloom filter against the pathspec itself. This way, commits
not touching any path matching the pathspec can be discarded as a whole.

Apply this same check to git-last-modified(1). In a previous commit the
function revs_maybe_changed_in_bloom(), used by git-log(1), was made
public. Use this as a pre-filter in git-last-modified(1). After this
pre-filter, paths are still checked one-by-one to only find those which
don't have a "last commit" yet.

With `--show-trees` the list holds more than the paths matching the
pathspec. It also holds each parent tree entry, up to the root. Each of
those can resolve to a different commit. Thus for the pathspec "a/b/c",
the list will also hold "a" and "a/b".

When a commit touches "a/other", that commit could be the last commit
for "a", but revs_maybe_changed_in_bloom() would discard it, because it
doesn't match the full pathspec.

Instead, when `--show-trees` is given, use
revs_maybe_changed_in_bloom_with_parents(), which indicates the commit
maybe changed any of the paths leading up to the path in the pathspec.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 builtin/last-modified.c  | 12 ++++++++++++
 t/t8020-last-modified.sh | 21 +++++++++++++++++++++
 2 files changed, 33 insertions(+)

diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index 3846244dfc..8ab7944314 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -272,6 +272,18 @@ static bool maybe_changed_path(struct last_modified *lm,
 	if (!filter)
 		return true;
 
+	/*
+	 * With --show-trees we also track the tree entries containing the
+	 * paths, so a change to any of those parent directories matters too.
+	 */
+	if (lm->show_trees) {
+		if (!revs_maybe_changed_in_bloom_with_parents(&lm->rev, filter))
+			return false;
+	} else {
+		if (!revs_maybe_changed_in_bloom(&lm->rev, filter))
+			return false;
+	}
+
 	hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
 		if (active && !bitmap_get(active, ent->diff_idx))
 			continue;
diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh
index 9dba4b9d90..df73c7d0d0 100755
--- a/t/t8020-last-modified.sh
+++ b/t/t8020-last-modified.sh
@@ -269,6 +269,27 @@ test_expect_success 'last-modified merge undoes changes' '
 	EOF
 '
 
+test_expect_success 'last-modified with Bloom filters and --show-trees' '
+	test_when_finished rm -rf bloom &&
+	git init bloom &&
+	(
+		cd bloom &&
+		mkdir d &&
+		test_commit base-a d/a &&
+		test_commit base-b d/b &&
+		test_commit touch-a d/a &&
+		test_commit touch-b d/b &&
+
+		git commit-graph write --reachable --changed-paths &&
+		git -c core.commitGraph=false last-modified -t HEAD -- d/a \
+			>expect &&
+		git -c core.commitGraph=true last-modified -t HEAD -- d/a \
+			>actual &&
+
+		test_cmp expect actual
+	)
+'
+
 test_expect_success 'cannot run last-modified on two commits' '
 	test_must_fail git last-modified HEAD HEAD~1 2>err &&
 	test_grep "last-modified can only operate on one commit at a time" err

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-08-31 15:18

Subject: [PATCH v3 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs
Message-ID: <20260831-toon-speed-up-last-modified-v3-6-2bbb864acf93@iotcl.com>
In-Reply-To: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>

```
The last-modified builtin expands the pathspec to a set of literal paths
and builds a Bloom key for each. During the walk it looks those keys up
in the commit's filter to decide whether the commit is worth diffing.
These lookups need `bloom_filter_settings` for the key hashing.

prepare_revision_walk() runs prepare_to_use_bloom_filter() to build the
pathspec key vectors. For a pathspec that cannot be turned into a Bloom
key, such as a top-level wildcard like "*.c", that function gives up and
clears `bloom_filter_settings`.

Restore `bloom_filter_settings` after prepare_revision_walk() so the
per-path check keeps working for wildcard pathspecs.

This change isn't having any effect on the output, but only has an
impact on performance. Add a "bloom_queries" trace2 counter that records
how often the per-path Bloom check runs, and a test that asserts the
count increments as appropriate for a top-level wildcard pathspec.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 builtin/last-modified.c  | 16 ++++++++++++++++
 t/t8020-last-modified.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 42 insertions(+)

diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index 8ab7944314..bedccb3ace 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -18,6 +18,7 @@
 #include "quote.h"
 #include "repository.h"
 #include "revision.h"
+#include "trace2.h"
 
 /* Remember to update object flag allocation in object.h */
 #define PARENT1 (1u<<16) /* used instead of SEEN */
@@ -63,6 +64,8 @@ struct last_modified {
 
 	/* 'scratch' to avoid allocating a bitmap every process_parent() */
 	struct bitmap *scratch;
+
+	unsigned int count_bloom_filter_queries;
 };
 
 static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)
@@ -272,6 +275,8 @@ static bool maybe_changed_path(struct last_modified *lm,
 	if (!filter)
 		return true;
 
+	lm->count_bloom_filter_queries++;
+
 	/*
 	 * With --show-trees we also track the tree entries containing the
 	 * paths, so a change to any of those parent directories matters too.
@@ -370,6 +375,14 @@ static int last_modified_run(struct last_modified *lm)
 
 	prepare_revision_walk(&lm->rev);
 
+	/*
+	 * prepare_revision_walk() clears bloom_filter_settings for pathspecs
+	 * without a Bloom key. Restore it so the per-path check keeps working.
+	 */
+	if (!lm->rev.bloom_filter_settings)
+		lm->rev.bloom_filter_settings =
+			get_bloom_filter_settings(lm->rev.repo);
+
 	max_count = lm->rev.max_count;
 
 	init_active_paths_for_commit(&lm->active_paths);
@@ -479,6 +492,9 @@ static int last_modified_run(struct last_modified *lm)
 	if (hashmap_get_size(&lm->paths))
 		BUG("paths remaining beyond boundary in last-modified");
 
+	trace2_data_intmax("last-modified", lm->rev.repo, "bloom_queries",
+			   lm->count_bloom_filter_queries);
+
 	clear_prio_queue(&not_queue);
 	clear_prio_queue(&queue);
 	clear_active_paths_for_commit(&lm->active_paths);
diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh
index df73c7d0d0..75b18ee83b 100755
--- a/t/t8020-last-modified.sh
+++ b/t/t8020-last-modified.sh
@@ -290,6 +290,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '
 	)
 '
 
+test_expect_success 'last-modified with Bloom filters and top-level wildcard' '
+	test_when_finished rm -rf wildcard &&
+	git init wildcard &&
+	(
+		cd wildcard &&
+		test_commit base-c a.c &&
+		test_commit base-h a.h &&
+		test_commit touch-c a.c &&
+		mkdir d &&
+		test_commit sub-c d/b.c &&
+
+		git commit-graph write --reachable --changed-paths &&
+		GIT_TRACE2_PERF="$(pwd)/off.perf" \
+			git -c core.commitGraph=false last-modified -r HEAD \
+			-- "*.c" >expect &&
+		test_grep "data .* bloom_queries:0$" off.perf &&
+
+		GIT_TRACE2_PERF="$(pwd)/on.perf" \
+			git -c core.commitGraph=true last-modified -r HEAD \
+			-- "*.c" >actual &&
+		test_grep "data .* bloom_queries:2$" on.perf &&
+
+		test_cmp expect actual
+	)
+'
+
 test_expect_success 'cannot run last-modified on two commits' '
 	test_must_fail git last-modified HEAD HEAD~1 2>err &&
 	test_grep "last-modified can only operate on one commit at a time" err

-- 
2.55.0.679.g6767b8d81c


```

## Junio C Hamano, 2026-08-31 21:19

Subject: Re: [PATCH v3 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits
Message-ID: <xmqqmru2ugxn.fsf@gitster.g>
In-Reply-To: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>

```
Toon Claes <toon@iotcl.com> writes:

> Similar timings are seen across a few other repositories (like GitLab's
> monolith gitlab-org/gitlab).
>
> [1]: https://lore.kernel.org/git/17f356ff-7bfb-47f5-b714-62a95cc8b821@codeberg.org/
> [2]: https://codeberg.org/ziglang/zig
>
> ---
> Changes in v3:
> - Add trace2 "bloom_queries" and use it in test to verify top-level
>   wildcard behavior.
> - Link to v2: https://patch.msgid.link/20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com

Merged to 'seen', pushed the result out, and saw this:

  https://github.com/git/git/actions/runs/33429987759/job/99612809093#step:10:1391

It seems that it is reproducible locally with the variable settings
stolen from ci/run-build-and-tests.sh, i.e.,

    $ bash
    sh-5.3$ export OPENSSL_SHA1_UNSAFE=YesPlease
    sh-5.3$ export GIT_TEST_SPLIT_INDEX=yes
    sh-5.3$ export GIT_TEST_FULL_IN_PACK_ARRAY=true
    sh-5.3$ export GIT_TEST_OE_SIZE=10
    sh-5.3$ export GIT_TEST_OE_DELTA_SIZE=5
    sh-5.3$ export GIT_TEST_COMMIT_GRAPH=1
    sh-5.3$ export GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1
    sh-5.3$ export GIT_TEST_MULTI_PACK_INDEX=1
    sh-5.3$ export GIT_TEST_MULTI_PACK_INDEX_WRITE_INCREMENTAL=1
    sh-5.3$ export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master
    sh-5.3$ export GIT_TEST_NO_WRITE_REV_INDEX=1
    sh-5.3$ export GIT_TEST_CHECKOUT_WORKERS=2
    sh-5.3$ export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1
    sh-5.3$ make T='t8020*' test

and it does reproduce when the topic is tested standalone (I've kept
the base that I have used to queue the previous iteration,
41365c2a9b The 4th batch for Git 2.56).

Ejected out of 'seen' for now.

```

## Junio C Hamano, 2026-09-01 04:19

Subject: Re: [PATCH v3 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs
Message-ID: <xmqq8q5lvc1i.fsf@gitster.g>
In-Reply-To: <20260831-toon-speed-up-last-modified-v3-6-2bbb864acf93@iotcl.com>

```
Toon Claes <toon@iotcl.com> writes:

> diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh
> index df73c7d0d0..75b18ee83b 100755
> --- a/t/t8020-last-modified.sh
> +++ b/t/t8020-last-modified.sh
> @@ -290,6 +290,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '
>  	)
>  '
>  
> +test_expect_success 'last-modified with Bloom filters and top-level wildcard' '
> ...
> +		GIT_TRACE2_PERF="$(pwd)/off.perf" \
> +			git -c core.commitGraph=false last-modified -r HEAD \
> +			-- "*.c" >expect &&
> +		test_grep "data .* bloom_queries:0$" off.perf &&

Ah, OK.  With GIT_TEST_COMMIT_GRAPH=1 exported from the test harness
environment, 'git -c core.commitGraph=false' would not be effective
here.  You would need to do something like:

		GIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF="$(pwd)/off.perf" \
			git -c core.commitGraph=false last-modified -r HEAD \
			-- "*.c" >expect &&

> +		GIT_TRACE2_PERF="$(pwd)/on.perf" \
> +			git -c core.commitGraph=true last-modified -r HEAD \
> +			-- "*.c" >actual &&

And in the case where GIT_TEST_COMMIT_GRAPH=0 comes from the
environment, you might want to be explicit about setting the
variable here as well.

```

## Toon Claes, 2026-09-01 09:14

Subject: Re: [PATCH v3 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs
Message-ID: <87mru1wcyi.fsf@emacs.iotcl.com>
In-Reply-To: <xmqq8q5lvc1i.fsf@gitster.g>

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

> Toon Claes <toon@iotcl.com> writes:
>
>> diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh
>> index df73c7d0d0..75b18ee83b 100755
>> --- a/t/t8020-last-modified.sh
>> +++ b/t/t8020-last-modified.sh
>> @@ -290,6 +290,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '
>>  	)
>>  '
>>  
>> +test_expect_success 'last-modified with Bloom filters and top-level wildcard' '
>> ...
>> +		GIT_TRACE2_PERF="$(pwd)/off.perf" \
>> +			git -c core.commitGraph=false last-modified -r HEAD \
>> +			-- "*.c" >expect &&
>> +		test_grep "data .* bloom_queries:0$" off.perf &&
>
> Ah, OK.  With GIT_TEST_COMMIT_GRAPH=1 exported from the test harness
> environment, 'git -c core.commitGraph=false' would not be effective
> here.  You would need to do something like:
>
> 		GIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF="$(pwd)/off.perf" \
> 			git -c core.commitGraph=false last-modified -r HEAD \
> 			-- "*.c" >expect &&
>
>> +		GIT_TRACE2_PERF="$(pwd)/on.perf" \
>> +			git -c core.commitGraph=true last-modified -r HEAD \
>> +			-- "*.c" >actual &&
>
> And in the case where GIT_TEST_COMMIT_GRAPH=0 comes from the
> environment, you might want to be explicit about setting the
> variable here as well.

Thanks for this suggestion. Yeah, I didn't notice it makes CI fail.

But a little bit of a followup question, I noticed I also should be
setting these in [PATCH 5/6], but test don't fail if not set
appropriately.

I just sent out version 4, but to make it really waterproof, test case
'last-modified with Bloom filters and --show-trees' also should use
trace2 counters. Although I wasn't convinced it's worth it?

-- 
Laters,
Toon

```

## Toon Claes, 2026-09-01 09:10

Subject: [PATCH v4 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits
Message-ID: <20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com>
In-Reply-To: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com>

```
We have received a report[1] git-last-modified(1) is slow compared to
git-log(1) if you want to find the last commit for all entries in a
directory. For example running the following command on ziglang/zig[2]:

   $ git last-modified -t --max-depth=0 $OID -- doc/langref/

Turns out to find results about 2.5 times slower than:

   $ git log --name-status -c --format=commit%x00%H %P%x00" \
       --parents --no-renames -t -z $OID -- :(literal)doc/langref

Now the latter needs some post-processing to come to the same results,
the total solution still is faster than integrating
git-last-modified(1).

After some research we've discovered the Bloom filters aren't used
optimally. But it turns out the code powering git-log(1) can fairly easy
be reused. We do this in a few steps:

 - Patch 1 & 2 prepare revision.[ch] to expose the helper to check if
   revs maybe changes in Bloom filter.
 - Patch 3 & 4 prepare a similar helper, but this one is needed when
   git-last-modified(1) is called with `--show-trees`.
 - Patch 5 uses these helpers in git-last-modified(1).
 - Patch 6 is a bonus change, which optimizes when working with wildcard
   pathspecs.

Below are benchmarks on the ziglang/zig repository for the
`doc/langref/` directory (with commit-graphs written using
`--changed-paths`):

    Benchmark 1: master: last-modified -z -t
      Time (mean ± σ):      61.9 ms ±   1.8 ms    [User: 57.1 ms, System: 4.0 ms]
      Range (min … max):    58.5 ms …  68.9 ms    150 runs

    Benchmark 2: HEAD: last-modified -z -t
      Time (mean ± σ):      31.8 ms ±   1.3 ms    [User: 27.1 ms, System: 4.2 ms]
      Range (min … max):    29.7 ms …  35.6 ms    150 runs

    Benchmark 3: git log -t
      Time (mean ± σ):      22.1 ms ±   1.2 ms    [User: 16.7 ms, System: 5.0 ms]
      Range (min … max):    20.1 ms …  26.6 ms    150 runs

    Summary
      git log -t ran
        1.44 ± 0.10 times faster than HEAD: last-modified -z -t
        2.80 ± 0.18 times faster than master: last-modified -z -t

Comparing HEAD to master, there is about 1.95x speedup on running `git
last-modified -z -t. `git log -t` is still slightly faster though.

But without `-t` the speedup is even bigger:

    Benchmark 1: master: last-modified -z
      Time (mean ± σ):      60.7 ms ±   4.5 ms    [User: 56.5 ms, System: 3.8 ms]
      Range (min … max):    57.5 ms …  96.2 ms    150 runs

    Benchmark 2: HEAD: last-modified -z
      Time (mean ± σ):      16.2 ms ±   1.4 ms    [User: 13.3 ms, System: 2.7 ms]
      Range (min … max):    13.9 ms …  20.4 ms    212 runs

    Benchmark 3: git log (no -t)
      Time (mean ± σ):      22.0 ms ±   3.7 ms    [User: 16.8 ms, System: 4.9 ms]
      Range (min … max):    18.7 ms …  37.6 ms    150 runs

    Summary
      HEAD: last-modified -z ran
        1.35 ± 0.25 times faster than git log (no -t)
        3.74 ± 0.42 times faster than master: last-modified -z

This makes sense because without `-t` we can use the Bloom filter more
optimally.

Similar timings are seen across a few other repositories (like GitLab's
monolith gitlab-org/gitlab).

[1]: https://lore.kernel.org/git/17f356ff-7bfb-47f5-b714-62a95cc8b821@codeberg.org/
[2]: https://codeberg.org/ziglang/zig

---
Changes in v4:
- Override GIT_TEST_COMMIT_GRAPH when passing `-c core.commitGraph=` in
  t8020 tests.
- Link to v3: https://patch.msgid.link/20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com

Changes in v3:
- Add trace2 "bloom_queries" and use it in test to verify top-level
  wildcard behavior.
- Link to v2: https://patch.msgid.link/20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com

Changes in v2:
- Make the public helper revs_maybe_changed_in_bloom() return a bool
  instead of a tristate.
- Keep the bloom_keyvecs_nr precondition before get_bloom_filter() and
  return early from the key vector loop.
- Add commits 3 & 4 to add helper used with `--show-trees`.
- Use Bloom filter correctly with `--show-trees` and add test to prove.
- Rerun benchmarks to compare results with and without `--show-trees`.
- Link to v1: https://patch.msgid.link/20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com

---
Toon Claes (6):
      revision: move bloom keyvec precondition into function
      revision: expose check for paths maybe changed in Bloom filter
      bloom: add helper to check if any key in a vector is present
      revision: add Bloom check that includes parent directories
      last-modified: check pathspec against Bloom filter first
      last-modified: keep per-path Bloom filters for wildcard pathspecs

 bloom.c                  | 12 +++++++++++
 bloom.h                  | 11 ++++++++++
 builtin/last-modified.c  | 28 ++++++++++++++++++++++++++
 revision.c               | 52 +++++++++++++++++++++++++++++++++++++-----------
 revision.h               | 20 +++++++++++++++++++
 t/t8020-last-modified.sh | 49 +++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 160 insertions(+), 12 deletions(-)

Range-diff versus v3:

1:  645c5d1ddf = 1:  dbb1ad8e96 revision: move bloom keyvec precondition into function
2:  3fa70e300d = 2:  6f0d62fe6c revision: expose check for paths maybe changed in Bloom filter
3:  d30e3fea71 = 3:  1c09e9ecba bloom: add helper to check if any key in a vector is present
4:  7b5cc70022 = 4:  7c7792e057 revision: add Bloom check that includes parent directories
5:  5cb67a54b1 ! 5:  ac5a6bd427 last-modified: check pathspec against Bloom filter first
    @@ t/t8020-last-modified.sh: test_expect_success 'last-modified merge undoes change
     +		test_commit touch-b d/b &&
     +
     +		git commit-graph write --reachable --changed-paths &&
    -+		git -c core.commitGraph=false last-modified -t HEAD -- d/a \
    -+			>expect &&
    -+		git -c core.commitGraph=true last-modified -t HEAD -- d/a \
    -+			>actual &&
    ++		GIT_TEST_COMMIT_GRAPH=0 \
    ++			git -c core.commitGraph=false last-modified -t HEAD \
    ++			-- d/a >expect &&
    ++		GIT_TEST_COMMIT_GRAPH=1 \
    ++			git -c core.commitGraph=true last-modified -t HEAD \
    ++			-- d/a >actual &&
     +
     +		test_cmp expect actual
     +	)
6:  c94f744a0f ! 6:  3524a202e7 last-modified: keep per-path Bloom filters for wildcard pathspecs
    @@ t/t8020-last-modified.sh: test_expect_success 'last-modified with Bloom filters
     +		test_commit sub-c d/b.c &&
     +
     +		git commit-graph write --reachable --changed-paths &&
    -+		GIT_TRACE2_PERF="$(pwd)/off.perf" \
    ++		GIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF="$(pwd)/off.perf" \
     +			git -c core.commitGraph=false last-modified -r HEAD \
     +			-- "*.c" >expect &&
     +		test_grep "data .* bloom_queries:0$" off.perf &&
     +
    -+		GIT_TRACE2_PERF="$(pwd)/on.perf" \
    ++		GIT_TEST_COMMIT_GRAPH=1 GIT_TRACE2_PERF="$(pwd)/on.perf" \
     +			git -c core.commitGraph=true last-modified -r HEAD \
     +			-- "*.c" >actual &&
     +		test_grep "data .* bloom_queries:2$" on.perf &&


---
base-commit: c73e85354c275c9d409b26445089bc16940fc527
change-id: 20260716-toon-speed-up-last-modified-b04ea1f21831


```

## Toon Claes, 2026-09-01 09:10

Subject: [PATCH v4 1/6] revision: move bloom keyvec precondition into function
Message-ID: <20260901-toon-speed-up-last-modified-v4-1-a09949800404@iotcl.com>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com>

```
There are currently two callsites calling
check_maybe_different_in_bloom_filter(). They both check if
revs->bloom_keyvecs_nr is not zero before they call that function.

Move bloom_keyvecs_nr precondition into
check_maybe_different_in_bloom_filter() to simplify the code.

Note that this changes `bloom_ret` to become -1 when there are no Bloom
key vectors, which results in `count_bloom_filter_false_positive` not
being incremented. This is unobservable, as the Bloom statistics are
only reported when key vectors were set up.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 revision.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/revision.c b/revision.c
index 50dc8b1991..6a6a1b6fa0 100644
--- a/revision.c
+++ b/revision.c
@@ -752,6 +752,9 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 	struct bloom_filter *filter;
 	int result = 0;
 
+	if (!revs->bloom_keyvecs_nr)
+		return -1;
+
 	if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
 		return -1;
 
@@ -806,7 +809,7 @@ static int rev_compare_tree(struct rev_info *revs,
 			return REV_TREE_SAME;
 	}
 
-	if (revs->bloom_keyvecs_nr && !nth_parent) {
+	if (!nth_parent) {
 		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
 
 		if (bloom_ret == 0)
@@ -833,7 +836,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,
 	if (!t1)
 		return 0;
 
-	if (!nth_parent && revs->bloom_keyvecs_nr) {
+	if (!nth_parent) {
 		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
 		if (!bloom_ret)
 			return 1;

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-09-01 09:10

Subject: [PATCH v4 2/6] revision: expose check for paths maybe changed in Bloom filter
Message-ID: <20260901-toon-speed-up-last-modified-v4-2-a09949800404@iotcl.com>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com>

```
check_maybe_different_in_bloom_filter() looks up a commit's changed-path
Bloom filter and consults it to see whether the commit might have
modified any of the paths in the pathspec that `revs` was set up with.
In a follow-up commit we want to reuse this logic from another builtin.

That caller, however, has already looked up the commit's Bloom filter
for its own purposes, so having the function look it up again would mean
a redundant lookup.

Extract the filter-consulting part into a new public function,
revs_maybe_changed_in_bloom(). This function takes an already looked-up
`struct bloom_filter` instead of a commit.
The existing check_maybe_different_in_bloom_filter() becomes a thin
wrapper that looks up the filter and delegates.

Expose the new function via revision.h so other builtins can reuse the
exact same filtering that `git log <pathspec>` performs.

The existing function check_maybe_different_in_bloom_filter() returns a
tristate value. This returns either:

 * `-1` : No Bloom filter was used.
 *  `0` : The commit definitely did not change any of the paths.
 *  `1` : The commit maybe changed one of the paths.

These return values are used to keep count of false-positives. But
because the new function revs_maybe_changed_in_bloom() is not involved
in counting statistics, it returns a boolean value telling whether the
commit definitely did not change any of the paths, or maybe changed some
of them.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 revision.c | 30 ++++++++++++++++++++----------
 revision.h | 12 ++++++++++++
 2 files changed, 32 insertions(+), 10 deletions(-)

diff --git a/revision.c b/revision.c
index 6a6a1b6fa0..ed46b90b00 100644
--- a/revision.c
+++ b/revision.c
@@ -750,7 +750,6 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 						 struct commit *commit)
 {
 	struct bloom_filter *filter;
-	int result = 0;
 
 	if (!revs->bloom_keyvecs_nr)
 		return -1;
@@ -765,18 +764,29 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 		return -1;
 	}
 
-	for (size_t nr = 0; !result && nr < revs->bloom_keyvecs_nr; nr++) {
-		result = bloom_filter_contains_vec(filter,
-						   revs->bloom_keyvecs[nr],
-						   revs->bloom_filter_settings);
+	if (revs_maybe_changed_in_bloom(revs, filter)) {
+		count_bloom_filter_maybe++;
+		return 1;
 	}
 
-	if (result)
-		count_bloom_filter_maybe++;
-	else
-		count_bloom_filter_definitely_not++;
+	count_bloom_filter_definitely_not++;
+
+	return 0;
+}
+
+bool revs_maybe_changed_in_bloom(struct rev_info *revs,
+				 struct bloom_filter *filter)
+{
+	if (!revs->bloom_keyvecs_nr || !filter)
+		return true;
+
+	for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
+		if (bloom_filter_contains_vec(filter,
+					      revs->bloom_keyvecs[nr],
+					      revs->bloom_filter_settings))
+			return true;
 
-	return result;
+	return false;
 }
 
 static int rev_compare_tree(struct rev_info *revs,
diff --git a/revision.h b/revision.h
index acf6d06b24..67778558e1 100644
--- a/revision.h
+++ b/revision.h
@@ -68,6 +68,7 @@ struct string_list;
 struct saved_parents;
 struct follow_pathspec_slab;
 struct bloom_keyvec;
+struct bloom_filter;
 struct bloom_filter_settings;
 struct option;
 struct parse_opt_ctx_t;
@@ -495,6 +496,17 @@ void reset_revision_walk(void);
  */
 int prepare_revision_walk(struct rev_info *revs);
 
+/**
+ * Consult a changed-path Bloom filter to determine if the commit to which the
+ * filter belongs might have changed any of the paths in the `revs`.
+ * prepare_revision_walk() needs to be called in advance to ensure
+ * pathspec key vectors are set up.
+ *
+ * Returns false iff the commit definitely did not change any of the paths.
+ */
+bool revs_maybe_changed_in_bloom(struct rev_info *revs,
+				 struct bloom_filter *filter);
+
 /* Drain the commits linked list into the priority queue. */
 void rev_info_commit_list_to_queue(struct rev_info *revs);
 /**

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-09-01 09:10

Subject: [PATCH v4 3/6] bloom: add helper to check if any key in a vector is present
Message-ID: <20260901-toon-speed-up-last-modified-v4-3-a09949800404@iotcl.com>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com>

```
The changed-path Bloom filter of a commit stores a key for every changed
path together with each of its leading directories. To query if a path
was changed, bloom_keyvec_new() fills a key vector the same way: a key
for the given path and one for each of its leading directories. For
example, for "a/b/c" the vector holds keys for "a/b/c", "a/b" and "a".

A Bloom filter can only ever prove absence. When a key is not in the
filter, the path it was made for definitely did not change. When it is
in the filter, the path may have changed, as the key can be a false
positive.

bloom_filter_contains_vec() looks up all keys of a vector and reports
whether all of them are present. That answers: Is this path maybe
changed by this commit?

A caller that also cares about the directories containing the path asks
a different question: Is this path, or any directory leading up to it,
maybe changed by this commit?

Consider the Bloom filter of a commit that changed "a/b/d". It holds
keys for "a/b/d", "a/b" and "a", so looking up the vector of "a/b/c"
with bloom_filter_contains_vec() reports that nothing changed, even
though "a/b" and "a" did.

Add bloom_filter_contains_any_vec(), which reports whether any key in
the vector is present. It returns 0 only when none of the keys are in
the filter, which means the path and all directories leading up to it
definitely did not change.

There are no callers yet, one is added in a subsequent commit.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 bloom.c | 12 ++++++++++++
 bloom.h | 11 +++++++++++
 2 files changed, 23 insertions(+)

diff --git a/bloom.c b/bloom.c
index caf22f9831..b96534e6e3 100644
--- a/bloom.c
+++ b/bloom.c
@@ -607,6 +607,18 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,
 	return ret;
 }
 
+int bloom_filter_contains_any_vec(const struct bloom_filter *filter,
+				  const struct bloom_keyvec *vec,
+				  const struct bloom_filter_settings *settings)
+{
+	int ret = 0;
+
+	for (size_t nr = 0; !ret && nr < vec->count; nr++)
+		ret = bloom_filter_contains(filter, &vec->key[nr], settings);
+
+	return ret;
+}
+
 uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,
 				   int version)
 {
diff --git a/bloom.h b/bloom.h
index 92ab2100d3..f508db23ad 100644
--- a/bloom.h
+++ b/bloom.h
@@ -164,6 +164,17 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,
 			      const struct bloom_keyvec *v,
 			      const struct bloom_filter_settings *settings);
 
+/*
+ * bloom_filter_contains_any_vec - Check if any key in a key vector is in the
+ * Bloom filter.
+ *
+ * Returns 1 if **any** key in the vector is present in the filter, 0 if none
+ * of them are.
+ */
+int bloom_filter_contains_any_vec(const struct bloom_filter *filter,
+				  const struct bloom_keyvec *v,
+				  const struct bloom_filter_settings *settings);
+
 uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,
 				   int version);
 

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-09-01 09:10

Subject: [PATCH v4 4/6] revision: add Bloom check that includes parent directories
Message-ID: <20260901-toon-speed-up-last-modified-v4-4-a09949800404@iotcl.com>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com>

```
revs_maybe_changed_in_bloom() reports whether a commit may have changed
any of the paths in the pathspec. It uses bloom_filter_contains_vec(),
which requires all keys of a path's key vector to be present, so it only
answers for the paths themselves.

A caller may track more than those paths. git-last-modified(1) with
--show-trees reports the last modifying commit for the tree entries
containing the paths as well, up to the root. For a pathspec "a/b/c/"
that means it reports "a" and "a/b" next to "a/b/c" and its entries, and
those can each resolve to a different commit. A commit that only changed
"a/top" is the answer for "a", even though it touched nothing under
"a/b".

Such a caller needs to know whether the path, or any of the directories
leading up to it, may have changed. Add
revs_maybe_changed_in_bloom_with_parents(), which asks that question by
using bloom_filter_contains_any_vec() instead. A key vector holds a key
for the path and one for each of its leading directories, so looking up
any of them answers it.

There are no callers yet, one is added in a subsequent commit.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 revision.c | 15 +++++++++++++++
 revision.h |  8 ++++++++
 2 files changed, 23 insertions(+)

diff --git a/revision.c b/revision.c
index ed46b90b00..a560146b4d 100644
--- a/revision.c
+++ b/revision.c
@@ -789,6 +789,21 @@ bool revs_maybe_changed_in_bloom(struct rev_info *revs,
 	return false;
 }
 
+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,
+					      struct bloom_filter *filter)
+{
+	if (!revs->bloom_keyvecs_nr || !filter)
+		return true;
+
+	for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
+		if (bloom_filter_contains_any_vec(filter,
+						  revs->bloom_keyvecs[nr],
+						  revs->bloom_filter_settings))
+			return true;
+
+	return false;
+}
+
 static int rev_compare_tree(struct rev_info *revs,
 			    struct commit *parent, struct commit *commit, int nth_parent)
 {
diff --git a/revision.h b/revision.h
index 67778558e1..192001ff79 100644
--- a/revision.h
+++ b/revision.h
@@ -507,6 +507,14 @@ int prepare_revision_walk(struct rev_info *revs);
 bool revs_maybe_changed_in_bloom(struct rev_info *revs,
 				 struct bloom_filter *filter);
 
+/**
+ * Same as revs_maybe_changed_in_bloom(), but a change to any of the directories
+ * leading up to a path counts as well. Callers that track the tree entries
+ * containing the paths, and not just the paths themselves, need this.
+ */
+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,
+					      struct bloom_filter *filter);
+
 /* Drain the commits linked list into the priority queue. */
 void rev_info_commit_list_to_queue(struct rev_info *revs);
 /**

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-09-01 09:10

Subject: [PATCH v4 5/6] last-modified: check pathspec against Bloom filter first
Message-ID: <20260901-toon-speed-up-last-modified-v4-5-a09949800404@iotcl.com>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com>

```
When git-last-modified(1) starts, it builds a list of all the paths
matching the pathspec it needs to find the last modifying commit for.
For example, every file and subdirectory listed by:

    $ git last-modified -t --max-depth=0 -- src/

As it resolves a commit for each path during the revision walk, it drops
that path from the list.

To avoid diffing trees for every commit, Bloom filters are used when
available. For each remaining path, the commit's Bloom filter is checked
to see whether the commit changed that path. The Bloom filter says
either "no" or "maybe", and only in the latter case is the diff
calculated.

git-log(1) does this differently. It does not expand the pathspec but
checks the Bloom filter against the pathspec itself. This way, commits
not touching any path matching the pathspec can be discarded as a whole.

Apply this same check to git-last-modified(1). In a previous commit the
function revs_maybe_changed_in_bloom(), used by git-log(1), was made
public. Use this as a pre-filter in git-last-modified(1). After this
pre-filter, paths are still checked one-by-one to only find those which
don't have a "last commit" yet.

With `--show-trees` the list holds more than the paths matching the
pathspec. It also holds each parent tree entry, up to the root. Each of
those can resolve to a different commit. Thus for the pathspec "a/b/c",
the list will also hold "a" and "a/b".

When a commit touches "a/other", that commit could be the last commit
for "a", but revs_maybe_changed_in_bloom() would discard it, because it
doesn't match the full pathspec.

Instead, when `--show-trees` is given, use
revs_maybe_changed_in_bloom_with_parents(), which indicates the commit
maybe changed any of the paths leading up to the path in the pathspec.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 builtin/last-modified.c  | 12 ++++++++++++
 t/t8020-last-modified.sh | 23 +++++++++++++++++++++++
 2 files changed, 35 insertions(+)

diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index 3846244dfc..8ab7944314 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -272,6 +272,18 @@ static bool maybe_changed_path(struct last_modified *lm,
 	if (!filter)
 		return true;
 
+	/*
+	 * With --show-trees we also track the tree entries containing the
+	 * paths, so a change to any of those parent directories matters too.
+	 */
+	if (lm->show_trees) {
+		if (!revs_maybe_changed_in_bloom_with_parents(&lm->rev, filter))
+			return false;
+	} else {
+		if (!revs_maybe_changed_in_bloom(&lm->rev, filter))
+			return false;
+	}
+
 	hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
 		if (active && !bitmap_get(active, ent->diff_idx))
 			continue;
diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh
index 9dba4b9d90..e75437c18e 100755
--- a/t/t8020-last-modified.sh
+++ b/t/t8020-last-modified.sh
@@ -269,6 +269,29 @@ test_expect_success 'last-modified merge undoes changes' '
 	EOF
 '
 
+test_expect_success 'last-modified with Bloom filters and --show-trees' '
+	test_when_finished rm -rf bloom &&
+	git init bloom &&
+	(
+		cd bloom &&
+		mkdir d &&
+		test_commit base-a d/a &&
+		test_commit base-b d/b &&
+		test_commit touch-a d/a &&
+		test_commit touch-b d/b &&
+
+		git commit-graph write --reachable --changed-paths &&
+		GIT_TEST_COMMIT_GRAPH=0 \
+			git -c core.commitGraph=false last-modified -t HEAD \
+			-- d/a >expect &&
+		GIT_TEST_COMMIT_GRAPH=1 \
+			git -c core.commitGraph=true last-modified -t HEAD \
+			-- d/a >actual &&
+
+		test_cmp expect actual
+	)
+'
+
 test_expect_success 'cannot run last-modified on two commits' '
 	test_must_fail git last-modified HEAD HEAD~1 2>err &&
 	test_grep "last-modified can only operate on one commit at a time" err

-- 
2.55.0.679.g6767b8d81c


```

## Toon Claes, 2026-09-01 09:10

Subject: [PATCH v4 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs
Message-ID: <20260901-toon-speed-up-last-modified-v4-6-a09949800404@iotcl.com>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com>

```
The last-modified builtin expands the pathspec to a set of literal paths
and builds a Bloom key for each. During the walk it looks those keys up
in the commit's filter to decide whether the commit is worth diffing.
These lookups need `bloom_filter_settings` for the key hashing.

prepare_revision_walk() runs prepare_to_use_bloom_filter() to build the
pathspec key vectors. For a pathspec that cannot be turned into a Bloom
key, such as a top-level wildcard like "*.c", that function gives up and
clears `bloom_filter_settings`.

Restore `bloom_filter_settings` after prepare_revision_walk() so the
per-path check keeps working for wildcard pathspecs.

This change isn't having any effect on the output, but only has an
impact on performance. Add a "bloom_queries" trace2 counter that records
how often the per-path Bloom check runs, and a test that asserts the
count increments as appropriate for a top-level wildcard pathspec.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 builtin/last-modified.c  | 16 ++++++++++++++++
 t/t8020-last-modified.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 42 insertions(+)

diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index 8ab7944314..bedccb3ace 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -18,6 +18,7 @@
 #include "quote.h"
 #include "repository.h"
 #include "revision.h"
+#include "trace2.h"
 
 /* Remember to update object flag allocation in object.h */
 #define PARENT1 (1u<<16) /* used instead of SEEN */
@@ -63,6 +64,8 @@ struct last_modified {
 
 	/* 'scratch' to avoid allocating a bitmap every process_parent() */
 	struct bitmap *scratch;
+
+	unsigned int count_bloom_filter_queries;
 };
 
 static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)
@@ -272,6 +275,8 @@ static bool maybe_changed_path(struct last_modified *lm,
 	if (!filter)
 		return true;
 
+	lm->count_bloom_filter_queries++;
+
 	/*
 	 * With --show-trees we also track the tree entries containing the
 	 * paths, so a change to any of those parent directories matters too.
@@ -370,6 +375,14 @@ static int last_modified_run(struct last_modified *lm)
 
 	prepare_revision_walk(&lm->rev);
 
+	/*
+	 * prepare_revision_walk() clears bloom_filter_settings for pathspecs
+	 * without a Bloom key. Restore it so the per-path check keeps working.
+	 */
+	if (!lm->rev.bloom_filter_settings)
+		lm->rev.bloom_filter_settings =
+			get_bloom_filter_settings(lm->rev.repo);
+
 	max_count = lm->rev.max_count;
 
 	init_active_paths_for_commit(&lm->active_paths);
@@ -479,6 +492,9 @@ static int last_modified_run(struct last_modified *lm)
 	if (hashmap_get_size(&lm->paths))
 		BUG("paths remaining beyond boundary in last-modified");
 
+	trace2_data_intmax("last-modified", lm->rev.repo, "bloom_queries",
+			   lm->count_bloom_filter_queries);
+
 	clear_prio_queue(&not_queue);
 	clear_prio_queue(&queue);
 	clear_active_paths_for_commit(&lm->active_paths);
diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh
index e75437c18e..5be1d0f948 100755
--- a/t/t8020-last-modified.sh
+++ b/t/t8020-last-modified.sh
@@ -292,6 +292,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '
 	)
 '
 
+test_expect_success 'last-modified with Bloom filters and top-level wildcard' '
+	test_when_finished rm -rf wildcard &&
+	git init wildcard &&
+	(
+		cd wildcard &&
+		test_commit base-c a.c &&
+		test_commit base-h a.h &&
+		test_commit touch-c a.c &&
+		mkdir d &&
+		test_commit sub-c d/b.c &&
+
+		git commit-graph write --reachable --changed-paths &&
+		GIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF="$(pwd)/off.perf" \
+			git -c core.commitGraph=false last-modified -r HEAD \
+			-- "*.c" >expect &&
+		test_grep "data .* bloom_queries:0$" off.perf &&
+
+		GIT_TEST_COMMIT_GRAPH=1 GIT_TRACE2_PERF="$(pwd)/on.perf" \
+			git -c core.commitGraph=true last-modified -r HEAD \
+			-- "*.c" >actual &&
+		test_grep "data .* bloom_queries:2$" on.perf &&
+
+		test_cmp expect actual
+	)
+'
+
 test_expect_success 'cannot run last-modified on two commits' '
 	test_must_fail git last-modified HEAD HEAD~1 2>err &&
 	test_grep "last-modified can only operate on one commit at a time" err

-- 
2.55.0.679.g6767b8d81c


```

## Junio C Hamano, 2026-09-01 13:47

Subject: Re: [PATCH v3 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs
Message-ID: <xmqqv78pt75k.fsf@gitster.g>
In-Reply-To: <87mru1wcyi.fsf@emacs.iotcl.com>

```
Toon Claes <toon@iotcl.com> writes:

> Junio C Hamano <gitster@pobox.com> writes:
>
>> Toon Claes <toon@iotcl.com> writes:
>>
>>> diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh
>>> index df73c7d0d0..75b18ee83b 100755
>>> --- a/t/t8020-last-modified.sh
>>> +++ b/t/t8020-last-modified.sh
>>> @@ -290,6 +290,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '
>>>  	)
>>>  '
>>>  
>>> +test_expect_success 'last-modified with Bloom filters and top-level wildcard' '
>>> ...
>>> +		GIT_TRACE2_PERF="$(pwd)/off.perf" \
>>> +			git -c core.commitGraph=false last-modified -r HEAD \
>>> +			-- "*.c" >expect &&
>>> +		test_grep "data .* bloom_queries:0$" off.perf &&
>>
>> Ah, OK.  With GIT_TEST_COMMIT_GRAPH=1 exported from the test harness
>> environment, 'git -c core.commitGraph=false' would not be effective
>> here.  You would need to do something like:
>>
>> 		GIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF="$(pwd)/off.perf" \
>> 			git -c core.commitGraph=false last-modified -r HEAD \
>> 			-- "*.c" >expect &&
>>
>>> +		GIT_TRACE2_PERF="$(pwd)/on.perf" \
>>> +			git -c core.commitGraph=true last-modified -r HEAD \
>>> +			-- "*.c" >actual &&
>>
>> And in the case where GIT_TEST_COMMIT_GRAPH=0 comes from the
>> environment, you might want to be explicit about setting the
>> variable here as well.
>
> Thanks for this suggestion. Yeah, I didn't notice it makes CI fail.
>
> But a little bit of a followup question, I noticed I also should be
> setting these in [PATCH 5/6], but test don't fail if not set
> appropriately.

Yeah, I noticed it when I queued the two fixup commits near the tip
of 'seen'.  I wrote it off as the test *not* checking everything.
If the test is about what the command does and not about how the
command exactly does its thing, you may not notice the difference
as long as two code paths both produce the right results.

So some tightening of tests might be needed, if we care.

```

## Patrick Steinhardt, 2026-09-10 07:03

Subject: Re: [PATCH v4 3/6] bloom: add helper to check if any key in a vector is present
Message-ID: <aqJWX0INerT8F687@pks.im>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-3-a09949800404@iotcl.com>

```
On Tue, Sep 01, 2026 at 11:10:23AM +0200, Toon Claes wrote:
> diff --git a/bloom.c b/bloom.c
> index caf22f9831..b96534e6e3 100644
> --- a/bloom.c
> +++ b/bloom.c
> @@ -607,6 +607,18 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,
>  	return ret;
>  }
>  
> +int bloom_filter_contains_any_vec(const struct bloom_filter *filter,
> +				  const struct bloom_keyvec *vec,
> +				  const struct bloom_filter_settings *settings)
> +{
> +	int ret = 0;
> +
> +	for (size_t nr = 0; !ret && nr < vec->count; nr++)
> +		ret = bloom_filter_contains(filter, &vec->key[nr], settings);
> +
> +	return ret;
> +}

`bloom_filter_contains()` may also return -1 in case `filter->len == 0`,
and we'd bubble up that code. But here...

> diff --git a/bloom.h b/bloom.h
> index 92ab2100d3..f508db23ad 100644
> --- a/bloom.h
> +++ b/bloom.h
> @@ -164,6 +164,17 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,
>  			      const struct bloom_keyvec *v,
>  			      const struct bloom_filter_settings *settings);
>  
> +/*
> + * bloom_filter_contains_any_vec - Check if any key in a key vector is in the
> + * Bloom filter.
> + *
> + * Returns 1 if **any** key in the vector is present in the filter, 0 if none
> + * of them are.
> + */
> +int bloom_filter_contains_any_vec(const struct bloom_filter *filter,
> +				  const struct bloom_keyvec *v,
> +				  const struct bloom_filter_settings *settings);

... you only document that it may return 0 or 1. We should either
properly document this or munge the returned value to be 0 or 1, only.
And if so, we could probably adapt this function to have a boolean
return value.

Patrick

```

## Patrick Steinhardt, 2026-09-10 07:04

Subject: Re: [PATCH v4 4/6] revision: add Bloom check that includes parent directories
Message-ID: <aqJWasW9IKXhjfd7@pks.im>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-4-a09949800404@iotcl.com>

```
On Tue, Sep 01, 2026 at 11:10:24AM +0200, Toon Claes wrote:
> diff --git a/revision.c b/revision.c
> index ed46b90b00..a560146b4d 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -789,6 +789,21 @@ bool revs_maybe_changed_in_bloom(struct rev_info *revs,
>  	return false;
>  }
>  
> +bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,
> +					      struct bloom_filter *filter)

In "revision.c", "parents" would immediately read as "commit parent" to
me. Would `revs_maybe_changed_in_bloom_with_leading_dirs()` be a better
name to clarify that this is about directories, only?

> +{
> +	if (!revs->bloom_keyvecs_nr || !filter)
> +		return true;
> +
> +	for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
> +		if (bloom_filter_contains_any_vec(filter,
> +						  revs->bloom_keyvecs[nr],
> +						  revs->bloom_filter_settings))
> +			return true;
> +
> +	return false;
> +}
> +
>  static int rev_compare_tree(struct rev_info *revs,
>  			    struct commit *parent, struct commit *commit, int nth_parent)
>  {
> diff --git a/revision.h b/revision.h
> index 67778558e1..192001ff79 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -507,6 +507,14 @@ int prepare_revision_walk(struct rev_info *revs);
>  bool revs_maybe_changed_in_bloom(struct rev_info *revs,
>  				 struct bloom_filter *filter);
>  
> +/**
> + * Same as revs_maybe_changed_in_bloom(), but a change to any of the directories
> + * leading up to a path counts as well. Callers that track the tree entries
> + * containing the paths, and not just the paths themselves, need this.
> + */

This comment also talks about leading directories, not parent
directories.

> +bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,
> +					      struct bloom_filter *filter);
> +

Patrick

```

## Patrick Steinhardt, 2026-09-10 07:04

Subject: Re: [PATCH v4 5/6] last-modified: check pathspec against Bloom filter first
Message-ID: <aqJWb1kq81A8AJWI@pks.im>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-5-a09949800404@iotcl.com>

```
On Tue, Sep 01, 2026 at 11:10:25AM +0200, Toon Claes wrote:
> When git-last-modified(1) starts, it builds a list of all the paths
> matching the pathspec it needs to find the last modifying commit for.
> For example, every file and subdirectory listed by:
> 
>     $ git last-modified -t --max-depth=0 -- src/
> 
> As it resolves a commit for each path during the revision walk, it drops
> that path from the list.
> 
> To avoid diffing trees for every commit, Bloom filters are used when
> available. For each remaining path, the commit's Bloom filter is checked
> to see whether the commit changed that path. The Bloom filter says
> either "no" or "maybe", and only in the latter case is the diff
> calculated.
> 
> git-log(1) does this differently. It does not expand the pathspec but
> checks the Bloom filter against the pathspec itself. This way, commits
> not touching any path matching the pathspec can be discarded as a whole.
> 
> Apply this same check to git-last-modified(1). In a previous commit the
> function revs_maybe_changed_in_bloom(), used by git-log(1), was made
> public. Use this as a pre-filter in git-last-modified(1). After this
> pre-filter, paths are still checked one-by-one to only find those which
> don't have a "last commit" yet.

So in theory, we _might_ now do some of the checks multiple times. But
the expectation is that the number of pathspecs is typically much lower
than the number of expanded paths to check against, so in most cases it
should be faster to do this pre-filtering?

It'll probably be possible to craft edge cases where the new logic is
slower because we now do more work in the matching case. But overall I
think this is a sensible tradeoff. After all, we use the same tradeoff
in git-log(1).

> With `--show-trees` the list holds more than the paths matching the
> pathspec. It also holds each parent tree entry, up to the root. Each of
> those can resolve to a different commit. Thus for the pathspec "a/b/c",
> the list will also hold "a" and "a/b".
> 
> When a commit touches "a/other", that commit could be the last commit
> for "a", but revs_maybe_changed_in_bloom() would discard it, because it
> doesn't match the full pathspec.
> 
> Instead, when `--show-trees` is given, use
> revs_maybe_changed_in_bloom_with_parents(), which indicates the commit
> maybe changed any of the paths leading up to the path in the pathspec.

You explain what we do and why it's safe, which is good. But what's
missing is the "why". As far as I understand the reason is performance,
but if so I'd have expected a benchmark demonstrating the benefit.

Patrick

```

## Patrick Steinhardt, 2026-09-10 07:04

Subject: Re: [PATCH v4 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs
Message-ID: <aqJWihcFmX7tPio5@pks.im>
In-Reply-To: <20260901-toon-speed-up-last-modified-v4-6-a09949800404@iotcl.com>

```
On Tue, Sep 01, 2026 at 11:10:26AM +0200, Toon Claes wrote:
> diff --git a/builtin/last-modified.c b/builtin/last-modified.c
> index 8ab7944314..bedccb3ace 100644
> --- a/builtin/last-modified.c
> +++ b/builtin/last-modified.c
> @@ -370,6 +375,14 @@ static int last_modified_run(struct last_modified *lm)
>  
>  	prepare_revision_walk(&lm->rev);
>  
> +	/*
> +	 * prepare_revision_walk() clears bloom_filter_settings for pathspecs
> +	 * without a Bloom key. Restore it so the per-path check keeps working.
> +	 */
> +	if (!lm->rev.bloom_filter_settings)
> +		lm->rev.bloom_filter_settings =
> +			get_bloom_filter_settings(lm->rev.repo);
> +
>  	max_count = lm->rev.max_count;
>  
>  	init_active_paths_for_commit(&lm->active_paths);

So the revision subsystem is unhappy, but we basically force the bloom
filter settings in there anyway? That feels a bit fragile to me. Is
there a reason why the revision machinery itself specifically needs to
have the bloom filters populated, or do we basically just have to set up
the bloom filters so that we can access them ourselves?

If the latter, can't we instead store the bloom filter settings in
`struct last_modified` instead of forcing them into the revision
machinery? Something like the below patch on top of tihs, which still
passes all of our tests.

There might be good reasons though why we can't do it this way.

Patrick

diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index bedccb3ace..dabd0b7c34 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -58,6 +58,8 @@ struct last_modified {
 	bool nul_termination;
 	int max_depth;
 
+	struct bloom_filter_settings *bloom_filter_settings;
+
 	const char **all_paths;
 	size_t all_paths_nr;
 	struct active_paths_for_commit active_paths;
@@ -117,9 +119,9 @@ static void add_path_from_diff(struct diff_queue_struct *q,
 
 		FLEX_ALLOC_STR(ent, path, path);
 		oidcpy(&ent->oid, &p->two->oid);
-		if (lm->rev.bloom_filter_settings)
+		if (lm->bloom_filter_settings)
 			bloom_key_fill(&ent->key, path, strlen(path),
-				       lm->rev.bloom_filter_settings);
+				       lm->bloom_filter_settings);
 		hashmap_entry_init(&ent->hashent, strhash(ent->path));
 		hashmap_add(&lm->paths, &ent->hashent);
 	}
@@ -265,7 +267,7 @@ static bool maybe_changed_path(struct last_modified *lm,
 	struct last_modified_entry *ent;
 	struct hashmap_iter iter;
 
-	if (!lm->rev.bloom_filter_settings)
+	if (!lm->bloom_filter_settings)
 		return true;
 
 	if (commit_graph_generation(origin) == GENERATION_NUMBER_INFINITY)
@@ -294,7 +296,7 @@ static bool maybe_changed_path(struct last_modified *lm,
 			continue;
 
 		if (bloom_filter_contains(filter, &ent->key,
-					  lm->rev.bloom_filter_settings))
+					  lm->bloom_filter_settings))
 			return true;
 	}
 	return false;
@@ -375,14 +377,6 @@ static int last_modified_run(struct last_modified *lm)
 
 	prepare_revision_walk(&lm->rev);
 
-	/*
-	 * prepare_revision_walk() clears bloom_filter_settings for pathspecs
-	 * without a Bloom key. Restore it so the per-path check keeps working.
-	 */
-	if (!lm->rev.bloom_filter_settings)
-		lm->rev.bloom_filter_settings =
-			get_bloom_filter_settings(lm->rev.repo);
-
 	max_count = lm->rev.max_count;
 
 	init_active_paths_for_commit(&lm->active_paths);
@@ -530,7 +524,7 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,
 		return argc;
 	}
 
-	lm->rev.bloom_filter_settings = get_bloom_filter_settings(lm->rev.repo);
+	lm->bloom_filter_settings = get_bloom_filter_settings(lm->rev.repo);
 
 	if (populate_paths_from_revs(lm) < 0)
 		return -1;

```