[PATCH RFC 3/5] blame-tree: use Bloom filters when available

[Toon Claes <toon@xxxxxxxxx>]

From: Taylor Blau <me@xxxxxxxxxxxx>

Our 'git blame-tree' 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 blame-tree'. 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

Signed-off-by: Toon Claes <toon@xxxxxxxxx>
---
 blame-tree.c | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)

diff --git a/blame-tree.c b/blame-tree.c
index ce57db2cfc..47354557a7 100644
--- a/blame-tree.c
+++ b/blame-tree.c
@@ -7,11 +7,15 @@
 #include "revision.h"
 #include "repository.h"
 #include "log-tree.h"
+#include "dir.h"
+#include "commit-graph.h"
+#include "bloom.h"
 
 struct blame_tree_entry {
 	struct hashmap_entry hashent;
 	struct object_id oid;
 	struct commit *commit;
+	struct bloom_key key;
 	const char path[FLEX_ARRAY];
 };
 
@@ -28,6 +32,9 @@ static void add_from_diff(struct diff_queue_struct *q,
 
 		FLEX_ALLOC_STR(ent, path, path);
 		oidcpy(&ent->oid, &p->two->oid);
+		if (bt->rev.bloom_filter_settings)
+			fill_bloom_key(path, strlen(path), &ent->key,
+				       bt->rev.bloom_filter_settings);
 		hashmap_entry_init(&ent->hashent, strhash(ent->path));
 		hashmap_add(&bt->paths, &ent->hashent);
 	}
@@ -92,12 +99,21 @@ void blame_tree_init(struct blame_tree *bt,
 	if (setup_revisions(argc, argv, &bt->rev, NULL) > 1)
 		die(_("unknown blame-tree argument: %s"), argv[1]);
 
+	(void)generation_numbers_enabled(bt->rev.repo);
+	bt->rev.bloom_filter_settings = get_bloom_filter_settings(bt->rev.repo);
+
 	if (add_from_revs(bt) < 0)
 		die(_("unable to setup blame-tree"));
 }
 
 void blame_tree_release(struct blame_tree *bt)
 {
+	struct hashmap_iter iter;
+	struct blame_tree_entry *ent;
+
+	hashmap_for_each_entry(&bt->paths, &iter, ent, hashent) {
+		clear_bloom_key(&ent->key);
+	}
 	hashmap_clear_and_free(&bt->paths, struct blame_tree_entry, hashent);
 	release_revisions(&bt->rev);
 }
@@ -137,6 +153,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);
 	free(ent);
 }
 
@@ -180,6 +197,30 @@ static void blame_diff(struct diff_queue_struct *q,
 	}
 }
 
+static int maybe_changed_path(struct blame_tree *bt, struct commit *origin)
+{
+	struct bloom_filter *filter;
+	struct blame_tree_entry *e;
+	struct hashmap_iter iter;
+
+	if (!bt->rev.bloom_filter_settings)
+		return 1;
+
+	if (commit_graph_generation(origin) == GENERATION_NUMBER_INFINITY)
+		return 1;
+
+	filter = get_bloom_filter(bt->rev.repo, origin);
+	if (!filter)
+		return 1;
+
+	hashmap_for_each_entry(&bt->paths, &iter, e, hashent) {
+		if (bloom_filter_contains(filter, &e->key,
+					  bt->rev.bloom_filter_settings))
+			return 1;
+	}
+	return 0;
+}
+
 int blame_tree_run(struct blame_tree *bt, blame_tree_callback cb, void *cbdata)
 {
 	struct blame_tree_callback_data data;
@@ -199,6 +240,9 @@ int blame_tree_run(struct blame_tree *bt, blame_tree_callback cb, void *cbdata)
 		if (!data.commit)
 			break;
 
+		if (!maybe_changed_path(bt, data.commit))
+			continue;
+
 		if (data.commit->object.flags & BOUNDARY) {
 			diff_tree_oid(bt->rev.repo->hash_algo->empty_tree,
 				       &data.commit->object.oid,

-- 
2.49.0.rc2