[PATCH 0/4] last-modified: use the pathspec's Bloom key to pre-filter commits

[PATCH 0/4] last-modified: use the pathspec's Bloom key to pre-filter commits

[Toon Claes]

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 moves a condition around so it becomes deduplicated and
   eventually can be reused by git-last-modified(1).
 - Patch 2 exposes a helper from revision.c publicly. The function is
   split out so the Bloom filter wouldn't be looked up twice from
   git-last-modified(1).
 - Patch 3 uses this new helper in git-last-modified(1).
 - Patch 4 is bonus change, which optimizes when working with wildcard
   pathspecs.

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

    Benchmark 1: master last-modified
      Time (mean ± σ):      52.6 ms ±   4.0 ms    [User: 49.2 ms, System: 3.0 ms]
      Range (min … max):    48.2 ms …  73.8 ms    62 runs

    Benchmark 2: HEAD last-modified
      Time (mean ± σ):      14.3 ms ±   1.8 ms    [User: 12.0 ms, System: 2.1 ms]
      Range (min … max):    10.5 ms …  18.9 ms    182 runs

    Benchmark 3: git log
      Time (mean ± σ):      17.4 ms ±   1.4 ms    [User: 13.5 ms, System: 3.7 ms]
      Range (min … max):    15.0 ms …  26.1 ms    185 runs

    Summary
      HEAD last-modified ran
        1.22 ± 0.18 times faster than git log
        3.66 ± 0.55 times faster than master last-modified

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

---
Toon Claes (4):
      revision: move bloom keyvec precondition into function
      revision: expose check for paths maybe changed in Bloom filter
      last-modified: check pathspec against Bloom filter first
      last-modified: keep per-path Bloom filters for wildcard pathspecs

 builtin/last-modified.c | 11 +++++++++++
 revision.c              | 32 +++++++++++++++++++++++---------
 revision.h              | 17 +++++++++++++++++
 3 files changed, 51 insertions(+), 9 deletions(-)



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

[PATCH 1/4] revision: move bloom keyvec precondition into function

[Toon Claes]

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 137a86d33b..f3c9407a66 100644
--- a/revision.c
+++ b/revision.c
@@ -750,6 +750,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;
 
@@ -804,7 +807,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)
@@ -831,7 +834,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.53.0.1323.g189a785ab5

Re: [PATCH 1/4] revision: move bloom keyvec precondition into function

[Jeff King]

On Fri, Jul 17, 2026 at 05:46:59PM +0200, Toon Claes wrote:

> 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.

Makes sense, but...

> 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.

This "-1" return is kind of subtle. The function is really a tristate
returning one of:

  0: no, it's definitely not in the filter
  1: yes, it's (probably) in the filter
  -1: we could not even check the filter

But nobody ever cares about the difference between "1" and "-1", because
the probabilistic data structure means "we could not check" must err on
the side of "it might be in the filter". But that leads to code like:

  if (!bloom_ret)

that _looks_ wrong at first glance (as in "oops, we are not catching -1
and accidentally treating it the same as 1"). But it's is actually
correct for the reason above.

The "return -1" you are adding here is not the first (we'd do a similar
thing if the commit was not found in the graph file). So it is not
really adding to the confusion.

But as we prepare to make this function public, should we consider
changing that tristate to a boolean, like:

  false: no, the path is definitely not touched by this commit
  true: the path could be touched by this commit

It's a minor point, but I think this makes the interface much more
obvious.

-Peff

[PATCH 2/4] revision: expose check for paths maybe changed in Bloom filter

[Toon Claes]

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.

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

diff --git a/revision.c b/revision.c
index f3c9407a66..040b30b5ee 100644
--- a/revision.c
+++ b/revision.c
@@ -748,26 +748,20 @@ 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;
+	int result;
 
 	if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
 		return -1;
 
 	filter = get_bloom_filter(revs->repo, commit);
-
 	if (!filter) {
 		count_bloom_filter_not_present++;
 		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);
-	}
+	result = revs_maybe_changed_in_bloom(revs, filter);
+	if (result < 0)
+		return result;
 
 	if (result)
 		count_bloom_filter_maybe++;
@@ -777,6 +771,23 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 	return result;
 }
 
+int revs_maybe_changed_in_bloom(struct rev_info *revs,
+				struct bloom_filter *filter)
+{
+	int result = 0;
+
+	if (!revs->bloom_keyvecs_nr)
+		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);
+	}
+
+	return result;
+}
+
 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 569b3fa1cb..7569c210cc 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;
@@ -493,6 +494,22 @@ void reset_revision_walk(void);
  */
 int prepare_revision_walk(struct rev_info *revs);
 
+/**
+ * Take in a changed-path Bloom filter that belongs to a commit, and consult it
+ * to see if it might have modified any of the paths in the `revs`.
+ * The caller should look up `filter`, probably with get_bloom_filter().
+ * prepare_revision_walk() needs to be called in advance to ensure
+ * pathspec key vectors are set up.
+ *
+ * Returns -1 if no sensible answer could be given because of missing
+ * preconditions (no pathspec key vectors).
+ * Returns 0 if the commit definitely did not change any of the paths and 1 if
+ * the commit maybe has changed one of them, although that might be a
+ * false-positive.
+ */
+int 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.53.0.1323.g189a785ab5

Re: [PATCH 2/4] revision: expose check for paths maybe changed in Bloom filter

[Junio C Hamano]

Toon Claes <toon@iotcl.com> writes:

> @@ -748,26 +748,20 @@ 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;
> +	int result;
>  
>  	if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
>  		return -1;
>  
>  	filter = get_bloom_filter(revs->repo, commit);
> -
>  	if (!filter) {
>  		count_bloom_filter_not_present++;
>  		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);
> -	}
> +	result = revs_maybe_changed_in_bloom(revs, filter);
> +	if (result < 0)
> +		return result;
>  
>  	if (result)
>  		count_bloom_filter_maybe++;

Doesn't this change skew the stats?

In today's code, revs->bloom_keyvecs_nr == 0 results in an early
return, without touching count_bloom_filter_not_present.  In the
updated code, we would not notice revs->bloom_keyvecs_nr being zero
and call get_bloom_filter() first.  If that yields NULL, we increment
_not_present variable.

Also an error return -1 from bloom_filter_contains_vec() breaks the
loop in today's code, increments count_bloom_filter_maybe (even
though the result is -1, not positive) and returns.  In updated
code, an error return would return from this function but neither
_maybe nor _definitely_not is incremented.

It could be that these two are intended "while at it we fix it too"
improvements, but then they deserve to be mentioned in the proposed
log message.  Personally, I think the first one that increments the
_not_present statistics when keyvecs is empty a bug, though.

> @@ -777,6 +771,23 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
>  	return result;
>  }
>  
> +int revs_maybe_changed_in_bloom(struct rev_info *revs,
> +				struct bloom_filter *filter)
> +{
> +	int result = 0;
> +
> +	if (!revs->bloom_keyvecs_nr)
> +		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);
> +	}
> +
> +	return result;
> +}

This is inherited from the original, but I think it would be easier
to follow if it were written like this:

	for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++) {
		if ((result = bloom_filter_contains_vec(filter,
					revs->bloom_keyvecs[nr],
					revs->bloom_filter_settings)))
			return result;
	}
	return 0;

Re: [PATCH 2/4] revision: expose check for paths maybe changed in Bloom filter

[Taylor Blau]

On Fri, Jul 17, 2026 at 01:47:03PM -0700, Junio C Hamano wrote:
> >  	if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
> >  		return -1;
> >
> >  	filter = get_bloom_filter(revs->repo, commit);
> > -

(This is an extreme nit-pick, but can we please try and avoid stray
changes like this? This one is not a huge deal, but it does make the
patch more difficult to read than necessary.)

> >  	if (!filter) {
> >  		count_bloom_filter_not_present++;
> >  		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);
> > -	}
> > +	result = revs_maybe_changed_in_bloom(revs, filter);
> > +	if (result < 0)
> > +		return result;
> >
> >  	if (result)
> >  		count_bloom_filter_maybe++;
>
> Doesn't this change skew the stats?

I believe so.

I had the same thinking, which is that without any key vectors, there is
no Bloom query to perform or account for, so that guard should stay
ahead of the generation and filter lookups.

> It could be that these two are intended "while at it we fix it too"
> improvements, but then they deserve to be mentioned in the proposed
> log message.  Personally, I think the first one that increments the
> _not_present statistics when keyvecs is empty a bug, though.

It seems separable. It may be worth fixing, but I would mention it
explicitly in the commit message.

Thanks,
Taylor

[PATCH 3/4] last-modified: check pathspec against Bloom filter first

[Toon Claes]

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.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 builtin/last-modified.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index 5478182f2e..e8ee610404 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -272,6 +272,9 @@ static bool maybe_changed_path(struct last_modified *lm,
 	if (!filter)
 		return true;
 
+	if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)
+		return false;
+
 	hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
 		if (active && !bitmap_get(active, ent->diff_idx))
 			continue;

-- 
2.53.0.1323.g189a785ab5

Re: [PATCH 3/4] last-modified: check pathspec against Bloom filter first

[Taylor Blau]

On Fri, Jul 17, 2026 at 05:47:01PM +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.
>
> Signed-off-by: Toon Claes <toon@iotcl.com>

> ---
>  builtin/last-modified.c | 3 +++
>  1 file changed, 3 insertions(+)
>
> diff --git a/builtin/last-modified.c b/builtin/last-modified.c
> index 5478182f2e..e8ee610404 100644
> --- a/builtin/last-modified.c
> +++ b/builtin/last-modified.c
> @@ -272,6 +272,9 @@ static bool maybe_changed_path(struct last_modified *lm,
>  	if (!filter)
>  		return true;
>
> +	if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)

Nit: please prefer 'if (!foo())' over 'if (foo() == 0)'.

> +		return false;
> +

I don't think this is safe with '--show-trees'. The original pathspec
does not cover every entry in 'lm->paths', since the function
'populate_paths_from_revs()' also adds ancestor tree entries.

This can be reproduced by adding the following to t8020:

    test_expect_success 'Bloom filter with --show-trees' '
        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
    '

Without the graph, 'd' is attributed to 'touch-b' and 'd/a' to 'touch-a'.
With the graph, both are attributed to 'touch-a'. The filter for
'touch-b' lacks 'd/a', so the new prefilter skips its diff even though 'd'
changed.

I think that the conditional is otherwise correct, if guarded when we
know that 'lm->show_trees' is false, like so:

    if (!lm->show_trees &&
        !revs_maybe_changed_in_bloom(&lm->rev, filter))
            return false;

The cover benchmark uses the same --show-trees plus narrow-pathspec
shape, so I think its output should be checked before interpreting the
speedup.

Thanks,
Taylor

Re: [PATCH 3/4] last-modified: check pathspec against Bloom filter first

[Jeff King]

On Fri, Jul 17, 2026 at 06:05:39PM -0500, Taylor Blau wrote:

> > diff --git a/builtin/last-modified.c b/builtin/last-modified.c
> > index 5478182f2e..e8ee610404 100644
> > --- a/builtin/last-modified.c
> > +++ b/builtin/last-modified.c
> > @@ -272,6 +272,9 @@ static bool maybe_changed_path(struct last_modified *lm,
> >  	if (!filter)
> >  		return true;
> >
> > +	if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)
> 
> Nit: please prefer 'if (!foo())' over 'if (foo() == 0)'.

Yeah, though there is some subtlety here because of the tristate return
I described elsewhere in the thread. I think if we switch to a boolean
return then a straight "!" becomes even more desirable.

> I don't think this is safe with '--show-trees'. The original pathspec
> does not cover every entry in 'lm->paths', since the function
> 'populate_paths_from_revs()' also adds ancestor tree entries.

Hmm, interesting. I am surprised to learn that "-t" includes "d" when
the pathspec asked for "d/a". I thought it was mostly about showing
"d/a" when we recurse to find "d/a/b". But I guess it does not make a
distinction between the two (probably because it is just telling the
diff code to show trees, and it does not further apply the pathspec to
the output).

Does this mean there is also a bug in "git log"? I guess not, because it
is purely pruning based on the pathspec, and only shows "d/" for those
commits.

>         git -c core.commitGraph=false last-modified -t HEAD -- d/a \
>             >expect &&
>         git -c core.commitGraph=true last-modified -t HEAD -- d/a \
>             >actual &&

A minor side note: the documentation claims "-t" has no effect without
"-r", but it clearly is not true (it tells us to show "d", even when we
are not recursing).

> I think that the conditional is otherwise correct, if guarded when we
> know that 'lm->show_trees' is false, like so:
> 
>     if (!lm->show_trees &&
>         !revs_maybe_changed_in_bloom(&lm->rev, filter))
>             return false;

Hmph. That makes this optimization all but useless, because the intended
use case of last-modified is almost always going to use "-t" to be able
to mark the interior trees. And most callers are not going to care about
seeing "d" here; their purpose was to find out about the things _inside_
"d".

Would we consider removing "d" from the output for this case? Presumably
by double-checking the pathspecs again in add_path_from_diff(). That
gives less surprising output (to me, anyway) and would enable this
optimization. And the command is still marked as experimental, and I
think this is exactly the kind of corner case that is meant to cover.

-Peff

[PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs

[Toon Claes]

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.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
 builtin/last-modified.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index e8ee610404..adc7cd8c74 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -360,6 +360,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);

-- 
2.53.0.1323.g189a785ab5

Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs

[Toon Claes]

Toon Claes <toon@iotcl.com> writes:

> 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.
>
> Signed-off-by: Toon Claes <toon@iotcl.com>
> ---
>  builtin/last-modified.c | 8 ++++++++
>  1 file changed, 8 insertions(+)
>
> diff --git a/builtin/last-modified.c b/builtin/last-modified.c
> index e8ee610404..adc7cd8c74 100644
> --- a/builtin/last-modified.c
> +++ b/builtin/last-modified.c
> @@ -360,6 +360,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);
> +

@Peff, as far I could tell:

* This change was not needed to be able to use the Bloom filters with
  the pathspec.

* Only restoring bloom_filter_settings was needed. In your patch you're
  calling prepare_to_use_bloom_filter(), but that is being called by
  prepare_revision_walk(). Thus the restoring of the filter settings
  I've added after that function.

>  	max_count = lm->rev.max_count;
>  
>  	init_active_paths_for_commit(&lm->active_paths);
>
> -- 
> 2.53.0.1323.g189a785ab5
>

-- 
Cheers,
Toon

Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs

[Jeff King]

On Fri, Jul 17, 2026 at 09:16:34PM +0200, Toon Claes wrote:

> > +	/*
> > +	 * 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);
> > +
> 
> @Peff, as far I could tell:
> 
> * This change was not needed to be able to use the Bloom filters with
>   the pathspec.

Ah, right. In my earlier attempt I came at it from the bottom up: I
found the bloom_keyvec, saw how it was populated, and then worked my way
back to prepare_to_use_bloom_filter() without going further.

But it is much nicer if we can rely on prepare_revision_walk() here, as
we don't need to make an additional function public.

> * Only restoring bloom_filter_settings was needed. In your patch you're
>   calling prepare_to_use_bloom_filter(), but that is being called by
>   prepare_revision_walk(). Thus the restoring of the filter settings
>   I've added after that function.

Hmm, OK. The "clearing" done by prepare_revision_walk() is kind of
weird. The bloom settings are a const pointer, not a resource we own, so
there is really no need to clear them.

But accepting for a moment that we do clear them, is this maybe an
indication that we are abusing rev_info.bloom_filter_settings? It is
really an internal implementation detail that revision.c uses for its
own bloom filters. Wouldn't it be cleaner for last-modified to keep its
own, like this:

diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index fe012b0c2e..5e176bbeed 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -61,6 +61,8 @@ struct last_modified {
 	size_t all_paths_nr;
 	struct active_paths_for_commit active_paths;
 
+	struct bloom_filter_settings *bloom_filter_settings;
+
 	/* 'scratch' to avoid allocating a bitmap every process_parent() */
 	struct bitmap *scratch;
 };
@@ -114,9 +116,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);
 	}
@@ -262,7 +264,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)
@@ -277,7 +279,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;
@@ -502,7 +504,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;

It's mostly academic, as both of the pointers (if not NULL) would always
point to the same setting that ultimately come from the repository
object. But it feels cleaner for them to keep their own pointers,
because that pointer may also signal "do we have usable bloom filters".
We are a little lucky in dodging a bug here: last-modified uses the
pointer for that purpose, but if revision.c did so also, they'd
conflict.

  Side note: this is really a repository property, so it would be nice
  if we could just do:

    repo_bloom_filter_contains(filter, &ent->key);

  without managing the settings pointer ourselves at all. But the cost
  to fetch it from the graph linked list is not totally trivial, so we'd
  probably end up having to cache it somewhere. I don't know if that's
  worth it (plus last-modified would still have to keep a boolean
  somewhere to decide whether it is using bloom filters or not).

-Peff

Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs

[Taylor Blau]

On Fri, Jul 17, 2026 at 05:47:02PM +0200, Toon Claes wrote:
> Restore `bloom_filter_settings` after prepare_revision_walk() so the
> per-path check keeps working for wildcard pathspecs.

Could we add a test which actually exercises this?

t8020 never writes a commit-graph with --changed-paths, so these new
Bloom paths remain dormant. The existing "last-modified subdir with
wildcard non-recursive" case passes a/* unquoted, so the shell expands
it into literal pathspecs before last-modified sees it.

Writing a changed-path commit-graph and using a genuinely quoted
top-level wildcard, e.g.:

    check_last_modified -r "*"

, would cover the zero-prefix wildcard case here. -r is necessary
since the default max-depth rejects a true wildcard pathspec.

(To be clear, I don't think that there is a correctness issue here,
but I do think we have a gap in test coverage in this patch.)

Thanks,
Taylor

Re: [PATCH 0/4] last-modified: use the pathspec's Bloom key to pre-filter commits

[Toon Claes]

Toon Claes <toon@iotcl.com> writes:

>  - Patch 3 uses this new helper in git-last-modified(1).
>  - Patch 4 is bonus change, which optimizes when working with wildcard
>    pathspecs.

I just realize I forgot to add Helped-by or Based-on-patches-by trailers
for Peff. I'm happy to add them on reroll.

-- 
Cheers,
Toon