Re: [PATCH v5 3/6] last-modified: use Bloom filters when available
From: Taylor Blau <hidden>
Date: 2025-07-18 00:16:29
On Wed, Jul 16, 2025 at 03:35:15PM +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.
Comparing the perf test results on git.git:
Test HEAD~ HEAD
------------------------------------------------------------------------------------
8020.1: top-level last-modified 4.49(4.34+0.11) 2.22(2.05+0.09) -50.6%
8020.2: top-level recursive last-modified 5.64(5.45+0.11) 5.62(5.30+0.11) -0.4%
8020.3: subdir last-modified 0.11(0.06+0.04) 0.07(0.03+0.04) -36.4%As an aside on 8020.3 (that I probably should have mentioned in the last commit), I think that our "| head -n1" heuristic for picking a sub-tree is skewing these results down. In git.git, the lexicographically earliest sub-tree is ".github", which is awfully tiny. I wonder if we should be grabbing the *last* sub-tree, or maybe the largest one by count of entries?
quoted hunk ↗ jump to hunk
@@ -40,6 +43,12 @@ struct last_modified { static 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); +
I did a double-take to make sure that ent->key would always be initialized here, but it is thanks to the FLEX_ALLOC_STR() call below.
quoted hunk ↗ jump to hunk
hashmap_clear_and_free(&lm->paths, struct last_modified_entry, hashent); release_revisions(&lm->rev); }@@ -67,6 +76,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) + fill_bloom_key(path, strlen(path), &ent->key, + lm->rev.bloom_filter_settings); hashmap_entry_init(&ent->hashent, strhash(ent->path)); hashmap_add(&lm->paths, &ent->hashent); }@@ -126,6 +138,7 @@ static void mark_path(const char *path, const struct object_id *oid, data->callback(path, data->commit, data->callback_data); hashmap_remove(data->paths, &ent->hashent, path); + clear_bloom_key(&ent->key);
OK, we're calling clear_bloom_key() here, too, but it uses FREE_AND_NULL(), so calling it again in last_modified_release() may be a noop, but won't ever be a double-free.
quoted hunk ↗ jump to hunk
@@ -238,6 +276,13 @@ static int last_modified_init(struct last_modified *lm, struct repository *r, return argc; } + /* + * We're not interested in generation numbers here, + * but calling this function to prepare the commit-graph. + */ + (void)generation_numbers_enabled(lm->rev.repo); + lm->rev.bloom_filter_settings = get_bloom_filter_settings(lm->rev.repo);
Hmmph. I think when I originally wrote this I was using the side-effect of calling generation_numbers_enabled() as a hack. But I think that it may be worth making "prepare_commit_graph()" a non-static function and calling that instead. Thanks, Taylor