[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

[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

[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

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

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