Re: [PATCH RFC v2 3/5] last-modified: use Bloom filters when available

[Patrick Steinhardt <ps@pks.im>]

On Fri, May 23, 2025 at 11:33:50AM +0200, Toon Claes wrote:
> Our 'git last-modified' performs a revision walk, and computes a diff at
> each point in the walk to figure out whether a given revision changed
> any of the paths it considers interesting.
> 
> When changed-path Bloom filters are available, we can avoid computing
> many such diffs. Before computing a diff, we first check if any of the
> remaining paths of interest were possibly changed at a given commit by
> consulting its Bloom filter. If any of them are, we are resigned to
> compute the diff.
> 
> If none of those queries returned "maybe", we know that the given commit
> doesn't contain any changed paths which are interesting to us. So, we
> can avoid computing it in this case.
> 
> This results in a substantial performance speed-up in common cases of
> 'git last-modified'. In the kernel, here is the before and after (all
> times computed with best-of-five):
> 
> With commit-graphs (but no Bloom filters):
> 
>     real	0m5.133s
>     user	0m4.942s
>     sys	0m0.180s
> 
> ...and with Bloom filters:
> 
>     real	0m0.936s
>     user	0m0.842s
>     sys	0m0.092s
> 
> These times are with my development-version of Git, so it's compiled
> without optimizations. Compiling instead with `-O3`, the results look
> even better:
> 
>     real	0m0.754s
>     user	0m0.661s
>     sys	0m0.092s

I'm sure that the old state without bloom filters will also improve a
bit?

> Signed-off-by: Toon Claes <toon@iotcl.com>
> ---
>  last-modified.c | 44 ++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 44 insertions(+)
> 
> diff --git a/last-modified.c b/last-modified.c
> index 9283f8fcae..f628434929 100644
> --- a/last-modified.c
> +++ b/last-modified.c
> @@ -92,12 +99,21 @@ void last_modified_init(struct last_modified *lm,
>  	if (setup_revisions(argc, argv, &lm->rev, NULL) > 1)
>  		die(_("unknown last-modified argument: %s"), argv[1]);
>  
> +	(void)generation_numbers_enabled(lm->rev.repo);

Why the `(void)` cast? And why even call this in the first place? This
definitely needs a comment and smells like funky design in our commit
graph subsystem where we rely on side effects of one function to leak
into a different function.

> +	lm->rev.bloom_filter_settings = get_bloom_filter_settings(lm->rev.repo);
> +
>  	if (add_from_revs(lm) < 0)
>  		die(_("unable to setup last-modified"));
>  }
>  
>  void last_modified_release(struct last_modified *lm)
>  {
> +	struct hashmap_iter iter;
> +	struct last_modified_entry *ent;
> +
> +	hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
> +		clear_bloom_key(&ent->key);
> +	}

The curly braces shouldn't be needed.

> @@ -180,6 +197,30 @@ static void last_modified_diff(struct diff_queue_struct *q,
>  	}
>  }
>  
> +static int maybe_changed_path(struct last_modified *lm, struct commit *origin)
> +{
> +	struct bloom_filter *filter;
> +	struct last_modified_entry *ent;
> +	struct hashmap_iter iter;
> +
> +	if (!lm->rev.bloom_filter_settings)
> +		return 1;
> +
> +	if (commit_graph_generation(origin) == GENERATION_NUMBER_INFINITY)
> +		return 1;

Hm, okay, so here we require generation numbers to exist. Why is that
though? Shouldn't we only care about bloom filters? I don't quite get
that part yet.

> +	filter = get_bloom_filter(lm->rev.repo, origin);
> +	if (!filter)
> +		return 1;
> +
> +	hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
> +		if (bloom_filter_contains(filter, &ent->key,
> +					  lm->rev.bloom_filter_settings))
> +			return 1;
> +	}
> +	return 0;
> +}
> +

Okay, and here we check whether any of our desired paths may be
contained in the bloom filter.

>  int last_modified_run(struct last_modified *lm, last_modified_callback cb, void *cbdata)
>  {
>  	struct last_modified_callback_data data;
> @@ -199,6 +240,9 @@ int last_modified_run(struct last_modified *lm, last_modified_callback cb, void
>  		if (!data.commit)
>  			break;
>  
> +		if (!maybe_changed_path(lm, data.commit))
> +			continue;

If there either are no bloom filters or in case none of them contain our
commit we can safely skip over the commit indeed. Otherwise we'll have
to check whether the commit really is interesting.

Makes sense.

Patrick