Changed Paths Bloom Filters

From: Garima Singh <[email protected]>

Revision walk will now use Bloom filters for commits to speed up revision walks for a particular path (for computing history for that path), if they are present in the commit-graph file.

We load the Bloom filters during the prepare_revision_walk step, but only when dealing with a single pathspec. While comparing trees in rev_compare_trees(), if the Bloom filter says that the file is not different between the two trees, we don't need to compute the expensive diff. This is where we get our performance gains. The other response of the Bloom filter is maybe, in which case we fall back to the full diff calculation to determine if the path was changed in the commit.

Performance Gains:
We tested the performance of git log -- <path> on the git repo, the linux and some internal large repos, with a variety of paths of varying depths.

On the git and linux repos:
- we observed a 2x to 5x speed up.

On a large internal repo with files seated 6-10 levels deep in the tree:
- we observed 10x to 20x speed ups, with some paths going up to 28 times faster.

---
 revision.c                 | 124 +++++++++++++++++++++++++++++++-
 revision.h                 |  11 +++
 t/helper/test-read-graph.c |   4 ++
 t/t4216-log-bloom.sh       | 140 +++++++++++++++++++++++++++++++++++++
 4 files changed, 277 insertions(+), 2 deletions(-)
 create mode 100755 t/t4216-log-bloom.sh

index 8136929e23..d1622afa17 100644
@@ -29,6 +29,8 @@
 #include "prio-queue.h"
 #include "hashmap.h"
 #include "utf8.h"
+#include "bloom.h"
+#include "json-writer.h"
 
 volatile show_early_output_fn_t show_early_output;
 

@@ -624,11 +626,114 @@ static void file_change(struct diff_options *options,
 	options->flags.has_changes = 1;
 }
 
+static int bloom_filter_atexit_registered;
+static unsigned int count_bloom_filter_maybe;
+static unsigned int count_bloom_filter_definitely_not;
+static unsigned int count_bloom_filter_false_positive;
+static unsigned int count_bloom_filter_not_present;
+static unsigned int count_bloom_filter_length_zero;
+
+static void trace2_bloom_filter_statistics_atexit(void)
+{
+	struct json_writer jw = JSON_WRITER_INIT;
+
+	jw_object_begin(&jw, 0);
+	jw_object_intmax(&jw, "filter_not_present", count_bloom_filter_not_present);
+	jw_object_intmax(&jw, "zero_length_filter", count_bloom_filter_length_zero);
+	jw_object_intmax(&jw, "maybe", count_bloom_filter_maybe);
+	jw_object_intmax(&jw, "definitely_not", count_bloom_filter_definitely_not);
+	jw_end(&jw);
+
+	trace2_data_json("bloom", the_repository, "statistics", &jw);
+
+	jw_release(&jw);
+}
+
+static void prepare_to_use_bloom_filter(struct rev_info *revs)
+{
+	struct pathspec_item *pi;
+	char *path_alloc = NULL;
+	const char *path;
+	int last_index;
+	int len;
+
+	if (!revs->commits)
+	    return;
+
+	repo_parse_commit(revs->repo, revs->commits->item);
+
+	if (!revs->repo->objects->commit_graph)
+		return;
+
+	revs->bloom_filter_settings = revs->repo->objects->commit_graph->bloom_filter_settings;
+	if (!revs->bloom_filter_settings)
+		return;
+
+	pi = &revs->pruning.pathspec.items[0];
+	last_index = pi->len - 1;
+
+	if (pi->match[last_index] == '/') {
+	    path_alloc = xstrdup(pi->match);
+	    path_alloc[last_index] = '\0';
+	    path = path_alloc;
+	} else
+	    path = pi->match;
+
+	len = strlen(path);
+
+	revs->bloom_key = xmalloc(sizeof(struct bloom_key));
+	fill_bloom_key(path, len, revs->bloom_key, revs->bloom_filter_settings);
+
+	if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
+		atexit(trace2_bloom_filter_statistics_atexit);
+		bloom_filter_atexit_registered = 1;
+	}
+
+	free(path_alloc);
+}
+
+static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
+						 struct commit *commit)
+{
+	struct bloom_filter *filter;
+	int result;
+
+	if (!revs->repo->objects->commit_graph)
+		return -1;
+
+	if (commit->generation == GENERATION_NUMBER_INFINITY)
+		return -1;
+
+	filter = get_bloom_filter(revs->repo, commit, 0);
+
+	if (!filter) {
+		count_bloom_filter_not_present++;
+		return -1;
+	}
+
+	if (!filter->len) {
+		count_bloom_filter_length_zero++;
+		return -1;
+	}
+
+	result = bloom_filter_contains(filter,
+				       revs->bloom_key,
+				       revs->bloom_filter_settings);
+
+	if (result)
+		count_bloom_filter_maybe++;
+	else
+		count_bloom_filter_definitely_not++;
+
+	return result;
+}
+
 static int rev_compare_tree(struct rev_info *revs,
-			    struct commit *parent, struct commit *commit)
+			    struct commit *parent, struct commit *commit, int nth_parent)
 {
 	struct tree *t1 = get_commit_tree(parent);
 	struct tree *t2 = get_commit_tree(commit);
+	int bloom_ret = 1;
 
 	if (!t1)
 		return REV_TREE_NEW;

@@ -653,11 +758,23 @@ static int rev_compare_tree(struct rev_info *revs,
 			return REV_TREE_SAME;
 	}
 
+	if (revs->pruning.pathspec.nr == 1 && !revs->reflog_info && !nth_parent) {
+		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
+
+		if (bloom_ret == 0)
+			return REV_TREE_SAME;
+	}
+
 	tree_difference = REV_TREE_SAME;
 	revs->pruning.flags.has_changes = 0;
 	if (diff_tree_oid(&t1->object.oid, &t2->object.oid, "",
 			   &revs->pruning) < 0)
 		return REV_TREE_DIFFERENT;
+
+	if (!nth_parent)
+		if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
+			count_bloom_filter_false_positive++;
+
 	return tree_difference;
 }
 

@@ -855,7 +972,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 			die("cannot simplify commit %s (because of %s)",
 			    oid_to_hex(&commit->object.oid),
 			    oid_to_hex(&p->object.oid));
-		switch (rev_compare_tree(revs, p, commit)) {
+		switch (rev_compare_tree(revs, p, commit, nth_parent)) {
 		case REV_TREE_SAME:
 			if (!revs->simplify_history || !relevant_commit(p)) {
 				/* Even if a merge with an uninteresting

@@ -3362,6 +3479,8 @@ int prepare_revision_walk(struct rev_info *revs)
 				       FOR_EACH_OBJECT_PROMISOR_ONLY);
 	}
 
+	if (revs->pruning.pathspec.nr == 1 && !revs->reflog_info)
+		prepare_to_use_bloom_filter(revs);
 	if (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED)
 		commit_list_sort_by_date(&revs->commits);
 	if (revs->no_walk)

@@ -3379,6 +3498,7 @@ int prepare_revision_walk(struct rev_info *revs)
 		simplify_merges(revs);
 	if (revs->children.name)
 		set_children(revs);
+
 	return 0;
 }
 

index 475f048fb6..7c026fe41f 100644
@@ -56,6 +56,8 @@ struct repository;
 struct rev_info;
 struct string_list;
 struct saved_parents;
+struct bloom_key;
+struct bloom_filter_settings;
 define_shared_commit_slab(revision_sources, char *);
 
 struct rev_cmdline_info {

@@ -291,6 +293,15 @@ struct rev_info {
 	struct revision_sources *sources;
 
 	struct topo_walk_info *topo_walk_info;
+
+	/* Commit graph bloom filter fields */
+	/* The bloom filter key for the pathspec */
+	struct bloom_key *bloom_key;
+	/*
+	 * The bloom filter settings used to generate the key.
+	 * This is loaded from the commit-graph being used.
+	 */
+	struct bloom_filter_settings *bloom_filter_settings;
 };
 
 int ref_excluded(struct string_list *, const char *path);

index d2884efe0a..aff597c7a3 100644
@@ -45,6 +45,10 @@ int cmd__read_graph(int argc, const char **argv)
 		printf(" commit_metadata");
 	if (graph->chunk_extra_edges)
 		printf(" extra_edges");
+	if (graph->chunk_bloom_indexes)
+		printf(" bloom_indexes");
+	if (graph->chunk_bloom_data)
+		printf(" bloom_data");
 	printf("\n");
 
 	UNLEAK(graph);

gitgitgadget

Why do we need to turn this feature off for --walk-reflog?

Anyway, in my opinion this restriction should be stated explicitly in the commit message, if kept.

I would add the qualifier "currently" here, i.e. s/only/currently only/ to make it clear that it is the limitation of current implementation, and not the inherent implementation of the technique.

All right, looks good.

Very minor nitpick: s/maybe/'maybe'/ (in my opinion).

Another repository that we could test Bloom filters feature would be, as I have written before, Android AOSP frameworks core repository
https://android.googlesource.com/platform/frameworks/base/
because being written in Java it has deep path hierarchy, and it also has large number of commits.

It would be nice to have at least one specific and repeatable example:
in given repository, starting from given commit or tag, following the history of given path, what are timing results for doing some specific command with and without Bloom filters computed and enabled.

One might also want to know the cost of this speedup: how much disk space does it take (i.e. how large is the commit-graph file with and without Bloom filters chunks), and how long does it take to compute (i.e. how much time writing commit-graph takes with and without using --changed-paths options).

This is good to know.

In the future we might want to have procedurally generated synthetic repository, where we would be able to control number of files, depth of filesystem hierarchy, average number of changes per commit, etc. to be used for performance testing. (Just wishful thinking)

Jakub Narębski

"Garima Singh via GitGitGadget" <[email protected]> writes:

This is a second part of my response, focusing solely on tests of the Bloom filters feature.

[...]

  +graph_read_expect () {

	(incorrect)
	my_function(){
		...

	(correct)
	my_function () {
		...

  +setup () {
  +	rm "$TRASH_DIRECTORY/trace.perf" &&
  +	git -c core.commitGraph=false log --format="%s" $1 >log_wo_bloom &&
  +	GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" \
  +	git -c core.commitGraph=true log --format="%s" $1 >log_w_bloom
  +}

Jakub Narębski

From: Garima Singh <[email protected]>

Add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag to the test setup suite in order to toggle writing Bloom filters when running any of the git tests. If set to true, we will compute and write Bloom filters every time a test calls git commit-graph write, as if the --changed-paths option was passed in.

The test suite passes when GIT_TEST_COMMIT_GRAPH and GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS are enabled.

---
 builtin/commit-graph.c        | 3 ++-
 ci/run-build-and-tests.sh     | 1 +
 commit-graph.h                | 1 +
 t/README                      | 5 +++++
 t/t4216-log-bloom.sh          | 3 +++
 t/t5318-commit-graph.sh       | 2 ++
 t/t5324-split-commit-graph.sh | 1 +
 7 files changed, 15 insertions(+), 1 deletion(-)

index 261dcce091..fc9b234ab0 100644
@@ -146,7 +146,8 @@ static int graph_write(int argc, const char **argv)
 		flags |= COMMIT_GRAPH_WRITE_SPLIT;
 	if (opts.progress)
 		flags |= COMMIT_GRAPH_WRITE_PROGRESS;
-	if (opts.enable_changed_paths)
+	if (opts.enable_changed_paths ||
+	    git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))
 		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;
 
 	read_replace_refs = 0;

index ff0ef7f08e..7b4857651d 100755
@@ -19,6 +19,7 @@ linux-gcc)
 	export GIT_TEST_OE_SIZE=10
 	export GIT_TEST_OE_DELTA_SIZE=5
 	export GIT_TEST_COMMIT_GRAPH=1
+	export GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1
 	export GIT_TEST_MULTI_PACK_INDEX=1
 	make test
 	;;

index 25fefefb3e..4c202ff3d7 100644
@@ -8,6 +8,7 @@
 
 #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH"
 #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD"
+#define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS "GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS"
 
 struct commit;
 struct bloom_filter_settings;

index caa125ba9a..be2f7d7fd2 100644
@@ -378,6 +378,11 @@ GIT_TEST_COMMIT_GRAPH=<boolean>, when true, forces the commit-graph to
 be written after every 'git commit' command, and overrides the
 'core.commitGraph' setting to true.
 
+GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=<boolean>, when true, forces
+commit-graph write to compute and write changed path Bloom filters for
+every 'git commit-graph write', as if the `--changed-paths` option was
+passed in.
+
 GIT_TEST_FSMONITOR=$PWD/t7519/fsmonitor-all exercises the fsmonitor
 code path for utilizing a file system monitor to speed up detecting
 new or changed files.

index 19eca1864b..7acebb3962 100755
@@ -3,6 +3,9 @@
 test_description='git log for a path with bloom filters'
 . ./test-lib.sh
 
+GIT_TEST_COMMIT_GRAPH=0
+GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0
+
 test_expect_success 'setup test - repo, commits, commit graph, log outputs' '
 	git init &&
 	mkdir A A/B A/B/C &&

index 3f03de6018..973020be2d 100755
@@ -3,6 +3,8 @@
 test_description='commit graph'
 . ./test-lib.sh
 
+GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0
+
 test_expect_success 'setup full repo' '
 	mkdir full &&
 	cd "$TRASH_DIRECTORY/full" &&

index c24823431f..9235db4561 100755
@@ -4,6 +4,7 @@ test_description='split commit graph'
 . ./test-lib.sh
 
 GIT_TEST_COMMIT_GRAPH=0
+GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0
 
 test_expect_success 'setup repo' '
 	git init &&

gitgitgadget

All right. Nice.

Jakub Narębski

Don't know when I'll find enough time to properly review the series. maybe someday...

This fails on big endian, e.g. in Travis CI's s390x build:

https://travis-ci.org/szeder/git-cooking-topics-for-travis-ci/jobs/647253022#L2210

(The link highlights the failure, but I'm afraid your browser won't jump there right away; you'll have to click on the print-test-failures fold at the bottom, and scroll down a bit...)

Thank you so much for running this pipeline and pointing out the error!

We will carefully review our interactions with the binary data and hopefully solve this in the next version.

Cheers!
Garima Singh

Szeder,

Thanks so much for running this test. We don't have access to a big endian machine right now, so could you please apply this patch and re-run your tests?

The issue is described in the message below, and Garima is working to ensure the handling of the filter data is clarified in the next version.

This is an issue from WAY back in the original prototype, and it highlights that we've never been writing the data in network-byte order. This is completely my fault.

Thanks,
-Stolee

-->8--

From c1067db5d618b2dae430dfe373a11c771517da9e Mon Sep 17 00:00:00 2001
From: Derrick Stolee <[email protected]>
Date: Fri, 7 Feb 2020 10:24:05 -0500
Subject: [PATCH] fixup! bloom: core Bloom filter implementation for changed
paths

The 'data' field of 'struct bloom_filter' can point to a memory location (when computing one before writing to the commit-graph) or a memmap()'d file location (when reading from the Bloom data chunk of the commit-graph file). This means that the memory representation may be backwards in Little Endian or Big Endian machines.

Always write and read bits from 'filter->data' using network order. This allows us to avoid loading the data streams from the file into memory buffers.

---
 bloom.c               | 6 ++++--
 t/helper/test-bloom.c | 2 +-
 2 files changed, 5 insertions(+), 3 deletions(-)

index 90d84dc713..aa6896584b 100644
@@ -124,8 +124,9 @@ void add_key_to_filter(struct bloom_key *key,
 	for (i = 0; i < settings->num_hashes; i++) {
 		uint64_t hash_mod = key->hashes[i] % mod;
 		uint64_t block_pos = hash_mod / BITS_PER_WORD;
+		uint64_t bit = get_bitmask(hash_mod);
 
-		filter->data[block_pos] |= get_bitmask(hash_mod);
+		filter->data[block_pos] |= htonll(bit);
 	}
 }
 

@@ -269,7 +270,8 @@ int bloom_filter_contains(struct bloom_filter *filter,
 	for (i = 0; i < settings->num_hashes; i++) {
 		uint64_t hash_mod = key->hashes[i] % mod;
 		uint64_t block_pos = hash_mod / BITS_PER_WORD;
-		if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
+		uint64_t bit = get_bitmask(hash_mod);
+		if (!(filter->data[block_pos] & htonll(bit)))
 			return 0;
 	}
 

index 9b4be97f75..09b2bb0a00 100644
@@ -23,7 +23,7 @@ static void print_bloom_filter(struct bloom_filter *filter) {
 	printf("Filter_Length:%d\n", filter->len);
 	printf("Filter_Data:");
 	for (i = 0; i < filter->len; i++){
-		printf("%"PRIx64"|", filter->data[i]);
+		printf("%"PRIx64"|", ntohll(filter->data[i]));
 	}
 	printf("\n");
 }

2.25.0.vfs.1.1.1.g9906319d24.dirty

Unfortunately, it still failed:

https://travis-ci.org/szeder/git-cooking-topics-for-travis-ci/jobs/647395554#L2204

Thanks! Both fail on test 2 of t0095-bloom.sh, which includes this expected output line:

	Filter_Data:508928809087080a|8a7648210804001|4089824400951000|841ab310098051a8|

We may not be properly adjusting the output in the test-helper.

I still think the fixup patch I included is a good idea, but Garima continues to dig into the problem from all angles to understand this failure and the full fix.

-Stolee

Hey!

The patch below carries the fix for the failure on Big-endian architectures. We now treat bloom filter data as a simple binary stream of 1 byte words instead of 8 byte words. This avoids the Big-endian vs Little-endian confusion on different CPU architectures.

Here is the successful run of SZEDER's Travis CI s390x build.

https://travis-ci.org/szeder/git/jobs/649044879

I will be squashing this patch into the appropriate commits in the series in v3, which I will send out after people have had a chance to complete their review of v2.

A special thanks to SZEDER for helping us test our patches on his CI pipeline and saving us the overhead of setting up a Big-endian machine!

Cheers!
Garima Singh

-->8--

From ee72310dd8c3ad2b810914edb651008f637e7c2a Mon Sep 17 00:00:00 2001
From: Garima Singh <[email protected]>
Date: Tue, 11 Feb 2020 13:55:03 -0500
Subject: [PATCH] Process bloom filter data as 1 byte words

Process bloom filter data as 1 byte words instead of 8 byte words to avoid the Big-endian vs Little-endian confusion on different CPU architectures

---
 bloom.c               |  24 ++++-----
 bloom.h               |   4 +-
 commit-graph.c        |   4 +-
 t/helper/test-bloom.c |   4 +-
 t/t0095-bloom.sh      | 118 +++++++++++++++++++++---------------------
 5 files changed, 77 insertions(+), 77 deletions(-)

index 90d84dc713..6d5d6bb2ef 100644
@@ -45,12 +45,13 @@ static uint32_t seed_murmur3(uint32_t seed, const char *data, int len)
 
 	int len4 = len / sizeof(uint32_t);
 
-	const uint32_t *blocks = (const uint32_t*)data;
-
 	uint32_t k;
-	for (i = 0; i < len4; i++)
-	{
-		k = blocks[i];
+	for (i = 0; i < len4; i++) {	
+		uint32_t byte1 = (uint32_t)data[4*i];
+		uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8;
+		uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16;
+		uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24;
+		k = byte1 | byte2 | byte3 | byte4;
 		k *= c1;
 		k = rotate_right(k, r1);
 		k *= c2;

@@ -61,8 +62,7 @@ static uint32_t seed_murmur3(uint32_t seed, const char *data, int len)
 
 	tail = (data + len4 * sizeof(uint32_t));
 
-	switch (len & (sizeof(uint32_t) - 1))
-	{
+	switch (len & (sizeof(uint32_t) - 1)) {
 	case 3:
 		k1 ^= ((uint32_t)tail[2]) << 16;
 		/*-fallthrough*/

@@ -88,9 +88,9 @@ static uint32_t seed_murmur3(uint32_t seed, const char *data, int len)
 	return seed;
 }
 
-static inline uint64_t get_bitmask(uint32_t pos)
+static inline unsigned char get_bitmask(uint32_t pos)
 {
-	return ((uint64_t)1) << (pos & (BITS_PER_WORD - 1));
+	return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
 }
 
 void load_bloom_filters(void)

@@ -152,8 +152,8 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,
 		start_index = 0;
 
 	filter->len = end_index - start_index;
-	filter->data = (uint64_t *)(g->chunk_bloom_data +
-					sizeof(uint64_t) * start_index +
+	filter->data = (unsigned char *)(g->chunk_bloom_data +
+					sizeof(unsigned char) * start_index +
 					BLOOMDATA_CHUNK_HEADER_SIZE);
 
 	return 1;

@@ -234,7 +234,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 		}
 
 		filter->len = (hashmap_get_size(&pathmap) * settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
-		filter->data = xcalloc(filter->len, sizeof(uint64_t));
+		filter->data = xcalloc(filter->len, sizeof(unsigned char));
 
 		hashmap_for_each_entry(&pathmap, &iter, e, entry) {
 			struct bloom_key key;

index 76f8a9ad0c..9604723ce0 100644
@@ -12,7 +12,7 @@ struct bloom_filter_settings {
 };
 
 #define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10 }
-#define BITS_PER_WORD 64
+#define BITS_PER_WORD 8
 #define BLOOMDATA_CHUNK_HEADER_SIZE 3*sizeof(uint32_t)
 
 /*

@@ -22,7 +22,7 @@ struct bloom_filter_settings {
  * 'data'.
  */
 struct bloom_filter {
-	uint64_t *data;
+	unsigned char *data;
 	int len;
 };
 

index c0e9834bf2..f5f9a23c9a 100644
@@ -1125,7 +1125,7 @@ static void write_graph_chunk_bloom_data(struct hashfile *f,
 	while (list < last) {
 		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
 		display_progress(progress, ++i);
-		hashwrite(f, filter->data, filter->len * sizeof(uint64_t));
+		hashwrite(f, filter->data, filter->len * sizeof(unsigned char));
 		list++;
 	}
 

@@ -1305,7 +1305,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = sorted_by_pos[i];
 		struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1);
-		ctx->total_bloom_filter_data_size += sizeof(uint64_t) * filter->len;
+		ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
 		display_progress(progress, i + 1);
 	}
 

index 9b4be97f75..8fa2d8fc25 100644
@@ -23,7 +23,7 @@ static void print_bloom_filter(struct bloom_filter *filter) {
 	printf("Filter_Length:%d\n", filter->len);
 	printf("Filter_Data:");
 	for (i = 0; i < filter->len; i++){
-		printf("%"PRIx64"|", filter->data[i]);
+		printf("%02x|", filter->data[i]);
 	}
 	printf("\n");
 }

@@ -57,7 +57,7 @@ int cmd__bloom(int argc, const char **argv)
 		struct bloom_filter filter;
 		int i = 2;
 		filter.len =  (settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
-		filter.data = xcalloc(filter.len, sizeof(uint64_t));
+		filter.data = xcalloc(filter.len, sizeof(unsigned char));
 
 		if (!argv[2]){
 			die("at least one input string expected");

2.22.0.windows.1

Sidenote: I wondered why it did use MurmurHash3 (64-bit version), which requires adding its implementation, instead of reusing FNV-1 hash (Fowler–Noll–Vo hash function) used by Git hashmap implementation, see
https://github.com/git/git/blob/228f53135a4a41a37b6be8e4d6e2b6153db4a8ed/hashmap.h#L109
Beside the fact that everyone is using MurmurHash for Bloom filters ;-)

It turns out that in various benchmark MurmurHash is faster and also slightly better as a hash than FNV-1 or FNV-1b.

I wonder then if it would be a good idea (in the future) to make it easy to use hashmap with MurmurHash3 instead of FNV-1, or maybe to even make it the default for hashing strings.

As I wrote in reply to previous version of this series, a good public repository (and thus being able to use by anyone) to test the Bloom filter performance improvements could be AOSP (Android) base:

https://android.googlesource.com/platform/frameworks/base/

which is a large repository with long path depths (due to Java file naming conventions).

Very nice! Good work!

What is the cost of this feature, that is how long it takes to generate Bloom filters, and how much larger commit-graph file gets? It would be nice to know.

Shouldn't then tests that were added in v2 mark use of Bloom filters with multiple paths revision walking as _not working *yet*_ (test_expect_failure), and not expected to not work (test_expect_success with test_bloom_filters_not_used)?

The shortlog summary is a fine tool to show contributors to the patch series, but is not as useful to show patch series as a whole: splitting of patches and their ordering.

I will review each of patches individually, but now I would like to say a few things about the series as a whole.

- [PATCH v2 01/11] commit-graph: use MAX_NUM_CHUNKS

Simple and non-controversial patch, improvement to existing code with the goal of helping future development (including further patches).

- [PATCH v2 02/11] bloom: core Bloom filter implementation for changed paths

In my opinion this patch could be split into three individual pieces, though one might think it is not worth it.

a. Add implementation of MurmurHash v3 (64-bit)

Include tests based on test-tool (creating file similar to the t/helper/test-hash.c, or enhancing to that file) that the implementation is correct, for example that 'The quick brown fox jumps over the lazy dog' with given seed (for example the default feed of 0) hashes to the same value as other implementations.

b. Add implementation of Bloom filter

Include generic Bloom filter tests i.e. that it correctly answers "yes" and "maybe" (create filter, save it or print it, then use stored filter), and tests specific to our implementation, namely that the size of the filter behaves as it should.

c. Bloom filter implementation for changed paths

Here include tests that use 'test-tool bloom get_filter_for_commit', that filter for commit with no changes and for commit with more than 512 fies changed works correctly, that directories are added along the paths, etc.

- [PATCH v2 03/11] diff: halt tree-diff early after max_changes

I think keeping this patch as a separate step makes individual commits easier to understand and review.

- [PATCH v2 04/11] commit-graph: compute Bloom filters for changed paths

Here we compute Bloom filters for changed paths for each commit in the commit-graph file, without writing it to file; as a side-effect we calculate total Bloom filters data size.

This doesn't make much sense as a standalone patch, but it is nice, easy to understand incremental step in building the feature.

- [PATCH v2 05/11] commit-graph: examine changed-path objects in pack order
- [PATCH v2 06/11] commit-graph: examine commits by generation number

Those two are performance improvements of previous step. It is good to keep them as separate commits, makes it easier to understand (and easier to catch error via git-bisect, if there would be any)

- [PATCH v2 07/11] commit-graph: write Bloom filters to commit graph file

This commit includes the documentation of the two new chunks of commit-graph file format.

I wonder if the 9th patch in this series, namely
commit-graph: add --changed-paths option to write subcommand should not precede this commit. Otherwise we have this new code but no way of testing it. On the other hand it makes it easier to review. On the gripping hand, you can't really test that writing works without the ability to parse Bloom filter data out of commit-graph file... which is the next commit.

- [PATCH v2 08/11] commit-graph: reuse existing Bloom filters during write

This implements reading Bloom filters data from commit-graph file. Is it a good split? I think it makes it easier to review the single patch, but itt also makes them less standalone.

- [PATCH v2 09/11] commit-graph: add --changed-paths option to write subcommand

One thing we could test there is that we are writing two new chunks to the commit-graph file (and perhaps checking that they are correctly formatted, and have correct shape).

- [PATCH v2 10/11] revision.c: use Bloom filters to speed up path based revision walks

This is quite a big and involved patch, which in my opinion could be split in two or three parts:

a. Add a bare bones implementation, like in v2

This limits amount of testing we can do; the only thing we can really test is that we get the same results with and without Bloom filters.

b.1. Add trace2 Bloom filter statistics
b.2. Use said trace2 statistics to test use of Bloom filters

- [PATCH v2 11/11] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag

This one is for (optional) exhaustive testing of the feature.

Feel free to disagree with those ideas.

Best,

Jakub Narębski

Making Murmur3 hash the default for hashing strings is definitely outside the scope of this series. Also, if the method signatures for the murmur3 hash matched the existing hash method signatures in hashmap.c, then it would be appropriate to place them adjacently, even if no hashmap consumer uses it for hashmaps. However, we need the option to start at a custom seed to do our double hashing. A change in the future that involves adopting murmur3 in the hashmap code would involve a simple code move before creating the new methods that avoid a custom seed. So for now, it makes sense that these methods leave in bloom.c where they are being used for a very specific purpose.

Thank you! I will incorporate these results into the commit messages as appropriate in v3.

The cost of writing is much better now with Peff and Dr. Stolee's improvements. I will include these numbers as well in the commit messages as appropriate in v3.

My intent is to ensure that bloom filters are not being used in any of the unsupported code paths. I don't have a strong preference about the test semantics as long as I get that coverage :) So I will look into switching it to test_expect_failure as you have suggested.

This is a GitGitGadget specific thing, and it is probably by design. I have opened an issue in that repo for any follow up discussions:
https://github.com/gitgitgadget/gitgitgadget/issues/203

I have gone back and forth on doing this. I like most of the core Bloom filter computations being isolated in one patch/commit. But based on the rest of your review, it seems like you are leaning heavily on having this split out. So, I will take a proper stab at doing it for v3.

Getting complete test coverage within a single patch would require 2 or 3 of these patches to be combined. This would lead to a large patch that would be much more difficult to review.

My tests in the patches following this one run git commands. Hence the tests get introduced when the command line is ready to use all the new code.

The current ordering of patches works better than adding the --changed-paths option before the logic that computes and writes. Otherwise the option will not be doing what it is supposed to do in the patch it was introduced in.

All the logic upto this point works just fine without the ability to read and parse precomputed bloom filters. This patch is an enhancement and it also separates out the reading and writing logic. Reusing existing bloom filters during write is the simplest interatcion that involves reading from the commit graph file, and builds the foundation to make the git log improvements. Hence, it warrants its own patch and review.

Sure. I will look into doing this split as well for v3.

Thanks for taking the time for reviewing this series so thoroughly! It is greatly appreciated!

Cheers,
Garima Singh

Thanks for a great discussion. Just a friendly ping to the thread, so that something from the discussion thread will stay on the first page of mailing list archive's threaded view ;-)

Hey!

The commit graph feature brought in a lot of performance improvements across multiple commands. However, file based history continues to be a performance pain point, especially in large repositories.

Adopting changed path Bloom filters has been discussed on the list before, and a prototype version was worked on by SZEDER Gábor, Jonathan Tan and Dr. Derrick Stolee [1]. This series is based on Dr. Stolee's proof of concept in
[2]

With the changes in this series, git users will be able to choose to write Bloom filters to the commit-graph using the following command:

'git commit-graph write --changed-paths'

Subsequent 'git log -- path' commands will use these computed Bloom filters to decided which commits are worth exploring further to produce the history of the provided path.

Cost of computing and writing Bloom filters
===========================================

Computing and writing Bloom filters to the commit graph for the first time implies computing the diffs and the resulting Bloom filters for all the commits in the repository. This adds a non trivial amount of time to run time. Every subsequent run is incremental i.e. we reuse the previously computed Bloom filters. So this is a one time cost.

Time taken by 'git commit-graph write' with and w/o --changed-paths, speed up in 'git log -- path' with computed Bloom filters (see a):-

-------------------------------------------------------------------------
| Repo | w/o --changed-paths | with --changed-paths | Speed up |
-------------------------------------------------------------------------

| git [3]     | 0.9 seconds         | 7 seconds            | 2x to 6x   |
| linux [4]   | 16 seconds          | 1 minute 8 seconds   | 2x to 6x   | 
| android [5] | 9 seconds           | 48 seconds           | 2x to 6x   |
| AzDo(see b) | 1 minute            | 5 minutes 2 seconds  | 10x to 30x |

-------------------------------------------------------------------------

a) We tested the performance of git log -- path with randomly chosen paths of varying depths in each repo. The speed up depends on how deep the files are in the hierarchy and how often a file has been touched in the commit history.

b) This internal repository has about 420k commits, 183k files distributed across 34k folders, the size on disk is about 17 GiB. The most massive gains on this repository were for files 6-12 levels deep in the tree.

c) These numbers were collected on a Windows machine, except for the linux repo which was tested on a Linux machine.

Future Work (not included in the scope of this series)
======================================================

1. Supporting multiple path based revision walk
2. Adopting it in git blame logic.
3. Interactions with line log git log -L

Cheers! Garima Singh

[1] https://lore.kernel.org/git/[email protected]/

[2]
https://lore.kernel.org/git/[email protected]/

[3] https://github.com/git/git

[4] https://github.com/torvalds/linux

[5] https://android.googlesource.com/platform/frameworks/base/

[email protected], [email protected], [email protected], [email protected],[email protected], [email protected], [email protected],[email protected]

Derrick Stolee (1):
diff: halt tree-diff early after max_changes

Garima Singh (14):
commit-graph: define and use MAX_NUM_CHUNKS
bloom.c: add the murmur3 hash implementation
bloom.c: introduce core Bloom filter constructs
bloom.c: core Bloom filter implementation for changed paths.
commit-graph: compute Bloom filters for changed paths
commit-graph: examine commits by generation number
diff: skip batch object download when possible
commit-graph: write Bloom filters to commit graph file
commit-graph: reuse existing Bloom filters during write
commit-graph: add --changed-paths option to write subcommand revision.c: use Bloom filters to speed up path based revision walks revision.c: add trace2 stats around Bloom filter usage
t4216: add end to end tests for git log with Bloom filters
commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag

Jeff King (1):
commit-graph: examine changed-path objects in pack order

 Documentation/git-commit-graph.txt            |   5 +
 .../technical/commit-graph-format.txt         |  30 ++
 Makefile                                      |   2 +
 bloom.c                                       | 276 ++++++++++++++++++
 bloom.h                                       |  90 ++++++
 builtin/commit-graph.c                        |  10 +-
 ci/run-build-and-tests.sh                     |   1 +
 commit-graph.c                                | 213 +++++++++++++-
 commit-graph.h                                |   9 +-
 diff.c                                        |   8 +-
 diff.h                                        |   6 +
 revision.c                                    | 126 +++++++-
 revision.h                                    |  11 +
 t/README                                      |   5 +
 t/helper/test-bloom.c                         |  81 +++++
 t/helper/test-read-graph.c                    |   4 +
 t/helper/test-tool.c                          |   1 +
 t/helper/test-tool.h                          |   1 +
 t/t0095-bloom.sh                              | 117 ++++++++
 t/t4216-log-bloom.sh                          | 155 ++++++++++
 t/t5318-commit-graph.sh                       |   2 +
 t/t5324-split-commit-graph.sh                 |   1 +
 tree-diff.c                                   |   6 +
 23 files changed, 1148 insertions(+), 12 deletions(-)
 create mode 100644 bloom.c
 create mode 100644 bloom.h
 create mode 100644 t/helper/test-bloom.c
 create mode 100755 t/t0095-bloom.sh
 create mode 100755 t/t4216-log-bloom.sh

base-commit: 3bab5d56259722843359702bc27111475437ad2a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-497%2Fgarimasi514%2FcoreGit-bloomFilters-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-497/garimasi514/coreGit-bloomFilters-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/497

Range-diff vs v2:

1: bf6b93878af ! 1: c3ffd9820d5 commit-graph: use MAX_NUM_CHUNKS
@@ -1,10 +1,12 @@
Author: Garima Singh <[email protected]>

- commit-graph: use MAX_NUM_CHUNKS
+ commit-graph: define and use MAX_NUM_CHUNKS

- This is a minor cleanup to make it easier to change the
- number of chunks being written to the commit-graph in the future.
+ This is a minor cleanup to make it easier to change
+ the number of chunks being written to the commit
+ graph.

+ Reviewed-by: Jakub Narębski <[email protected]>

diff --git a/commit-graph.c b/commit-graph.c

  -:  ----------- >  2:  a5aa3415c05 bloom.c: add the murmur3 hash implementation
  -:  ----------- >  3:  a7702c1afde bloom.c: introduce core Bloom filter constructs
  2:  02b16d94227 !  4:  8304c297520 bloom: core Bloom filter implementation for changed paths
     @@ -1,89 +1,33 @@
      Author: Garima Singh <[email protected]>
      
     -    bloom: core Bloom filter implementation for changed paths
     +    bloom.c: core Bloom filter implementation for changed paths.
      
     -    Add the core Bloom filter logic for computing the paths changed between a
     -    commit and its first parent. For details on what Bloom filters are and how they
     -    work, please refer to Dr. Derrick Stolee's blog post [1]. It provides a concise
     -    explaination of the adoption of Bloom filters as described in [2] and [3]
     +    Add the core implementation for computing Bloom filters for
     +    the paths changed between a commit and it's first parent.
      
     -    1. We currently use 7 and 10 for the number of hashes and the size of each
     -       entry respectively. They served as great starting values, the mathematical
     -       details behind this choice are described in [1] and [4]. The implementation
     -       while not completely open to it at the moment, is flexible enough to allow
     -       for tweaking these settings in the future.
     +    We fill the Bloom filters as (const char *data, int len) pairs
     +    as `struct bloom_filters" within a commit slab.
      
     -       Note: The performance gains we have observed with these values are
     -       significant enough that we did not need to tweak these settings.
     -       The performance numbers are included in the cover letter of this series
     -       and in the message of a subsequent commit where we use Bloom filters in
     -       to speed up `git log -- <path>`.
     -
     -    2. As described in the blog and in [3], we do not need 7 independent hashing
     -       functions. We use the Murmur3 hashing scheme. Seed it twice and then
     -       combine those to procure an arbitrary number of hash values.
     -
     -    3. The filters are sized according to the number of changes in the each commit,
     -       with minimum size of one 64 bit word.
     -
     -    4. We fill the Bloom filters as (const char *data, int len) pairs as
     -       "struct bloom_filter"s in a commit slab.
     -
     -    5. The seed_murmur3 method is implemented as described in [5]. It hashes the
     -       given data using a given seed and produces a uniformly distributed hash
     -       value.
     -
     -    [1] https://devblogs.microsoft.com/devops/super-charging-the-git-commit-graph-iv-Bloom-filters/
     -
     -    [2] Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese
     -        "An Improved Construction for Counting Bloom Filters"
     -        http://theory.stanford.edu/~rinap/papers/esa2006b.pdf
     -        https://doi.org/10.1007/11841036_61
     -
     -    [3] Peter C. Dillinger and Panagiotis Manolios
     -        "Bloom Filters in Probabilistic Verification"
     -        http://www.ccs.neu.edu/home/pete/pub/Bloom-filters-verification.pdf
     -        https://doi.org/10.1007/978-3-540-30494-4_26
     -
     -    [4] Thomas Mueller Graf, Daniel Lemire
     -        "Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters"
     -        https://arxiv.org/abs/1912.08258
     -
     -    [5] https://en.wikipedia.org/wiki/MurmurHash#Algorithm
     +    Filters for commits with no changes and more than 512 changes,
     +    is represented with a filter of length zero. There is no gain
     +    in distinguishing between a computed filter of length zero for
     +    a commit with no changes, and an uncomputed filter for new commits
     +    or for commits with more than 512 changes. The effect on
     +    `git log -- path` is the same in both cases. We will fall back to
     +    the normal diffing algorithm when we can't benefit from the
     +    existence of Bloom filters.
      
          Helped-by: Jeff King <[email protected]>
          Helped-by: Derrick Stolee <[email protected]>
     +    Reviewed-by: Jakub Narębski <[email protected]>
          Signed-off-by: Garima Singh <[email protected]>
      
     - diff --git a/Makefile b/Makefile
     - --- a/Makefile
     - +++ b/Makefile
     -@@
     - 
     - PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))
     - 
     -+TEST_BUILTINS_OBJS += test-bloom.o
     - TEST_BUILTINS_OBJS += test-chmtime.o
     - TEST_BUILTINS_OBJS += test-config.o
     - TEST_BUILTINS_OBJS += test-ctype.o
     -@@
     - LIB_OBJS += bisect.o
     - LIB_OBJS += blame.o
     - LIB_OBJS += blob.o
     -+LIB_OBJS += bloom.o
     - LIB_OBJS += branch.o
     - LIB_OBJS += bulk-checkin.o
     - LIB_OBJS += bundle.o
     -
       diff --git a/bloom.c b/bloom.c
     - new file mode 100644
     - --- /dev/null
     + --- a/bloom.c
       +++ b/bloom.c
      @@
     -+#include "git-compat-util.h"
     -+#include "bloom.h"
     -+#include "commit-graph.h"
     -+#include "object-store.h"
     + #include "git-compat-util.h"
     + #include "bloom.h"
      +#include "diff.h"
      +#include "diffcore.h"
      +#include "revision.h"
     @@ -97,118 +41,19 @@
      +    struct hashmap_entry entry;
      +    const char path[FLEX_ARRAY];
      +};
     + 
     + static uint32_t rotate_left(uint32_t value, int32_t count)
     + {
     +@@
     + 		filter->data[block_pos] |= get_bitmask(hash_mod);
     + 	}
     + }
      +
     -+static uint32_t rotate_right(uint32_t value, int32_t count)
     -+{
     -+	uint32_t mask = 8 * sizeof(uint32_t) - 1;
     -+	count &= mask;
     -+	return ((value >> count) | (value << ((-count) & mask)));
     -+}
     -+
     -+/*
     -+ * Calculate a hash value for the given data using the given seed.
     -+ * Produces a uniformly distributed hash value.
     -+ * Not considered to be cryptographically secure.
     -+ * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
     -+ **/
     -+static uint32_t seed_murmur3(uint32_t seed, const char *data, int len)
     -+{
     -+	const uint32_t c1 = 0xcc9e2d51;
     -+	const uint32_t c2 = 0x1b873593;
     -+	const uint32_t r1 = 15;
     -+	const uint32_t r2 = 13;
     -+	const uint32_t m = 5;
     -+	const uint32_t n = 0xe6546b64;
     -+	int i;
     -+	uint32_t k1 = 0;
     -+	const char *tail;
     -+
     -+	int len4 = len / sizeof(uint32_t);
     -+
     -+	const uint32_t *blocks = (const uint32_t*)data;
     -+
     -+	uint32_t k;
     -+	for (i = 0; i < len4; i++)
     -+	{
     -+		k = blocks[i];
     -+		k *= c1;
     -+		k = rotate_right(k, r1);
     -+		k *= c2;
     -+
     -+		seed ^= k;
     -+		seed = rotate_right(seed, r2) * m + n;
     -+	}
     -+
     -+	tail = (data + len4 * sizeof(uint32_t));
     -+
     -+	switch (len & (sizeof(uint32_t) - 1))
     -+	{
     -+	case 3:
     -+		k1 ^= ((uint32_t)tail[2]) << 16;
     -+		/*-fallthrough*/
     -+	case 2:
     -+		k1 ^= ((uint32_t)tail[1]) << 8;
     -+		/*-fallthrough*/
     -+	case 1:
     -+		k1 ^= ((uint32_t)tail[0]) << 0;
     -+		k1 *= c1;
     -+		k1 = rotate_right(k1, r1);
     -+		k1 *= c2;
     -+		seed ^= k1;
     -+		break;
     -+	}
     -+
     -+	seed ^= (uint32_t)len;
     -+	seed ^= (seed >> 16);
     -+	seed *= 0x85ebca6b;
     -+	seed ^= (seed >> 13);
     -+	seed *= 0xc2b2ae35;
     -+	seed ^= (seed >> 16);
     -+
     -+	return seed;
     -+}
     -+
     -+static inline uint64_t get_bitmask(uint32_t pos)
     -+{
     -+	return ((uint64_t)1) << (pos & (BITS_PER_WORD - 1));
     -+}
     -+
     -+void load_bloom_filters(void)
     ++void init_bloom_filters(void)
      +{
      +	init_bloom_filter_slab(&bloom_filters);
      +}
      +
     -+void fill_bloom_key(const char *data,
     -+					int len,
     -+					struct bloom_key *key,
     -+					struct bloom_filter_settings *settings)
     -+{
     -+	int i;
     -+	const uint32_t seed0 = 0x293ae76f;
     -+	const uint32_t seed1 = 0x7e646e2c;
     -+	const uint32_t hash0 = seed_murmur3(seed0, data, len);
     -+	const uint32_t hash1 = seed_murmur3(seed1, data, len);
     -+
     -+	key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
     -+	for (i = 0; i < settings->num_hashes; i++)
     -+		key->hashes[i] = hash0 + i * hash1;
     -+}
     -+
     -+void add_key_to_filter(struct bloom_key *key,
     -+					   struct bloom_filter *filter,
     -+					   struct bloom_filter_settings *settings)
     -+{
     -+	int i;
     -+	uint64_t mod = filter->len * BITS_PER_WORD;
     -+
     -+	for (i = 0; i < settings->num_hashes; i++) {
     -+		uint64_t hash_mod = key->hashes[i] % mod;
     -+		uint64_t block_pos = hash_mod / BITS_PER_WORD;
     -+
     -+		filter->data[block_pos] |= get_bitmask(hash_mod);
     -+	}
     -+}
     -+
      +struct bloom_filter *get_bloom_filter(struct repository *r,
      +				      struct commit *c)
      +{
     @@ -217,7 +62,7 @@
      +	int i;
      +	struct diff_options diffopt;
      +
     -+	if (!bloom_filters.slab_size)
     ++	if (bloom_filters.slab_size == 0)
      +		return NULL;
      +
      +	filter = bloom_filter_slab_at(&bloom_filters, c);
     @@ -234,13 +79,12 @@
      +
      +	if (diff_queued_diff.nr <= 512) {
      +		struct hashmap pathmap;
     -+		struct pathmap_hash_entry* e;
     ++		struct pathmap_hash_entry *e;
      +		struct hashmap_iter iter;
      +		hashmap_init(&pathmap, NULL, NULL, 0);
      +
      +		for (i = 0; i < diff_queued_diff.nr; i++) {
     -+			const char* path = diff_queued_diff.queue[i]->two->path;
     -+			const char* p = path;
     ++			const char *path = diff_queued_diff.queue[i]->two->path;
      +
      +			/*
      +			* Add each leading directory of the changed file, i.e. for
     @@ -251,23 +95,23 @@
      +			* Note that directories are added without the trailing '/'.
      +			*/
      +			do {
     -+				char* last_slash = strrchr(p, '/');
     ++				char *last_slash = strrchr(path, '/');
      +
      +				FLEX_ALLOC_STR(e, path, path);
     -+				hashmap_entry_init(&e->entry, strhash(p));
     ++				hashmap_entry_init(&e->entry, strhash(path));
      +				hashmap_add(&pathmap, &e->entry);
      +
      +				if (!last_slash)
     -+					last_slash = (char*)p;
     ++					last_slash = (char*)path;
      +				*last_slash = '\0';
      +
     -+			} while (*p);
     ++			} while (*path);
      +
      +			diff_free_filepair(diff_queued_diff.queue[i]);
      +		}
      +
      +		filter->len = (hashmap_get_size(&pathmap) * settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
     -+		filter->data = xcalloc(filter->len, sizeof(uint64_t));
     ++		filter->data = xcalloc(filter->len, sizeof(unsigned char));
      +
      +		hashmap_for_each_entry(&pathmap, &iter, e, entry) {
      +			struct bloom_key key;
     @@ -287,138 +131,48 @@
      +	DIFF_QUEUE_CLEAR(&diff_queued_diff);
      +
      +	return filter;
     -+}
     -+
     -+int bloom_filter_contains(struct bloom_filter *filter,
     -+			  struct bloom_key *key,
     -+			  struct bloom_filter_settings *settings)
     -+{
     -+	int i;
     -+	uint64_t mod = filter->len * BITS_PER_WORD;
     -+
     -+	if (!mod)
     -+		return -1;
     -+
     -+	for (i = 0; i < settings->num_hashes; i++) {
     -+		uint64_t hash_mod = key->hashes[i] % mod;
     -+		uint64_t block_pos = hash_mod / BITS_PER_WORD;
     -+		if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
     -+			return 0;
     -+	}
     -+
     -+	return 1;
      +}
      
       diff --git a/bloom.h b/bloom.h
     - new file mode 100644
     - --- /dev/null
     + --- a/bloom.h
       +++ b/bloom.h
      @@
     -+#ifndef BLOOM_H
     -+#define BLOOM_H
     -+
     + #ifndef BLOOM_H
     + #define BLOOM_H
     + 
      +struct commit;
      +struct repository;
     -+struct commit_graph;
     -+
     -+struct bloom_filter_settings {
     -+	uint32_t hash_version;
     -+	uint32_t num_hashes;
     -+	uint32_t bits_per_entry;
     -+};
     -+
     -+#define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10 }
     -+#define BITS_PER_WORD 64
      +
     -+/*
     -+ * A bloom_filter struct represents a data segment to
     -+ * use when testing hash values. The 'len' member
     -+ * dictates how many uint64_t entries are stored in
     -+ * 'data'.
     -+ */
     -+struct bloom_filter {
     -+	uint64_t *data;
     -+	int len;
     -+};
     -+
     -+/*
     -+ * A bloom_key represents the k hash values for a
     -+ * given hash input. These can be precomputed and
     -+ * stored in a bloom_key for re-use when testing
     -+ * against a bloom_filter.
     -+ */
     -+struct bloom_key {
     -+	uint32_t *hashes;
     -+};
     -+
     -+void load_bloom_filters(void);
     -+
     -+void fill_bloom_key(const char *data,
     -+		    int len,
     -+		    struct bloom_key *key,
     -+		    struct bloom_filter_settings *settings);
     -+
     -+void add_key_to_filter(struct bloom_key *key,
     -+					   struct bloom_filter *filter,
     -+					   struct bloom_filter_settings *settings);
     + struct bloom_filter_settings {
     + 	/*
     + 	 * The version of the hashing technique being used.
     +@@
     + 					   struct bloom_filter *filter,
     + 					   const struct bloom_filter_settings *settings);
     + 
     ++void init_bloom_filters(void);
      +
      +struct bloom_filter *get_bloom_filter(struct repository *r,
      +				      struct commit *c);
      +
     -+int bloom_filter_contains(struct bloom_filter *filter,
     -+			  struct bloom_key *key,
     -+			  struct bloom_filter_settings *settings);
     -+
     -+#endif
     + #endif
     + \ No newline at end of file
      
       diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c
     - new file mode 100644
     - --- /dev/null
     + --- a/t/helper/test-bloom.c
       +++ b/t/helper/test-bloom.c
      @@
     -+#include "test-tool.h"
     -+#include "git-compat-util.h"
     -+#include "bloom.h"
     -+#include "test-tool.h"
     -+#include "cache.h"
     -+#include "commit-graph.h"
     + #include "git-compat-util.h"
     + #include "bloom.h"
     + #include "test-tool.h"
      +#include "commit.h"
     -+#include "config.h"
     -+#include "object-store.h"
     -+#include "object.h"
     -+#include "repository.h"
     -+#include "tree.h"
     -+
     -+struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
     -+
     -+static void print_bloom_filter(struct bloom_filter *filter) {
     -+	int i;
     -+
     -+	if (!filter) {
     -+		printf("No filter.\n");
     -+		return;
     -+	}
     -+	printf("Filter_Length:%d\n", filter->len);
     -+	printf("Filter_Data:");
     -+	for (i = 0; i < filter->len; i++){
     -+		printf("%"PRIx64"|", filter->data[i]);
     -+	}
     -+	printf("\n");
     -+}
     -+
     -+static void add_string_to_filter(const char *data, struct bloom_filter *filter) {
     -+		struct bloom_key key;
     -+		int i;
     -+
     -+		fill_bloom_key(data, strlen(data), &key, &settings);
     -+		printf("Hashes:");
     -+		for (i = 0; i < settings.num_hashes; i++){
     -+			printf("%08x|", key.hashes[i]);
     -+		}
     -+		printf("\n");
     -+		add_key_to_filter(&key, filter, &settings);
     -+}
     -+
     + 
     + struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
     + 
     +@@
     + 	printf("\n");
     + }
     + 
      +static void get_bloom_filter_for_commit(const struct object_id *commit_oid)
      +{
      +	struct commit *c;
     @@ -429,72 +183,33 @@
      +	print_bloom_filter(filter);
      +}
      +
     -+int cmd__bloom(int argc, const char **argv)
     -+{
     -+    if (!strcmp(argv[1], "generate_filter")) {
     -+		struct bloom_filter filter;
     -+		int i = 2;
     -+		filter.len =  (settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
     -+		filter.data = xcalloc(filter.len, sizeof(uint64_t));
     -+
     -+		if (!argv[2]){
     -+			die("at least one input string expected");
     -+		}
     -+
     -+		while (argv[i]) {
     -+			add_string_to_filter(argv[i], &filter);
     -+			i++;
     -+		}
     -+
     -+		print_bloom_filter(&filter);
     -+	}
     -+
     -+	if (!strcmp(argv[1], "get_filter_for_commit")) {
     + int cmd__bloom(int argc, const char **argv)
     + {
     + 	if (!strcmp(argv[1], "get_murmur3")) {
     +@@
     + 		print_bloom_filter(&filter);
     + 	}
     + 
     ++    if (!strcmp(argv[1], "get_filter_for_commit")) {
      +		struct object_id oid;
      +		const char *end;
      +		if (parse_oid_hex(argv[2], &oid, &end))
      +			die("cannot parse oid '%s'", argv[2]);
     -+		load_bloom_filters();
     ++		init_bloom_filters();
      +		get_bloom_filter_for_commit(&oid);
      +	}
      +
     -+	return 0;
     -+}
     -
     - diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
     - --- a/t/helper/test-tool.c
     - +++ b/t/helper/test-tool.c
     -@@
     - };
     - 
     - static struct test_cmd cmds[] = {
     -+	{ "bloom", cmd__bloom },
     - 	{ "chmtime", cmd__chmtime },
     - 	{ "config", cmd__config },
     - 	{ "ctype", cmd__ctype },
     -
     - diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
     - --- a/t/helper/test-tool.h
     - +++ b/t/helper/test-tool.h
     -@@
     - #define USE_THE_INDEX_COMPATIBILITY_MACROS
     - #include "git-compat-util.h"
     - 
     -+int cmd__bloom(int argc, const char **argv);
     - int cmd__chmtime(int argc, const char **argv);
     - int cmd__config(int argc, const char **argv);
     - int cmd__ctype(int argc, const char **argv);
     + 	return 0;
     + }
     + \ No newline at end of file
      
       diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh
     - new file mode 100755
     - --- /dev/null
     + --- a/t/t0095-bloom.sh
       +++ b/t/t0095-bloom.sh
      @@
     -+#!/bin/sh
     -+
     -+test_description='test bloom.c'
     -+. ./test-lib.sh
     -+
     + 	test_cmp expect actual
     + '
     + 
      +test_expect_success 'get bloom filters for commit with no changes' '
      +	git init &&
      +	git commit --allow-empty -m "c0" &&
     @@ -517,8 +232,8 @@
      +	git add smallDir &&
      +	git commit -m "commit with 10 changes" &&
      +	cat >expect <<-\EOF &&
     -+	Filter_Length:4
     -+	Filter_Data:508928809087080a|8a7648210804001|4089824400951000|841ab310098051a8|
     ++	Filter_Length:25
     ++	Filter_Data:82|a0|65|47|0c|92|90|c0|a1|40|02|a0|e2|40|e0|04|0a|9a|66|cf|80|19|85|42|23|
      +	EOF
      +	test-tool bloom get_filter_for_commit "$(git rev-parse HEAD)" >actual &&
      +	test_cmp expect actual
     @@ -542,64 +257,5 @@
      +	test_cmp expect actual
      +'
      +
     -+test_expect_success 'compute bloom key for empty string' '
     -+	cat >expect <<-\EOF &&
     -+	Hashes:5615800c|5b966560|61174ab4|66983008|6c19155c|7199fab0|771ae004|
     -+	Filter_Length:1
     -+	Filter_Data:11000110001110|
     -+	EOF
     -+	test-tool bloom generate_filter "" >actual &&
     -+	test_cmp expect actual
     -+'
     -+
     -+test_expect_success 'compute bloom key for whitespace' '
     -+	cat >expect <<-\EOF &&
     -+	Hashes:1bf014e6|8a91b50b|f9335530|67d4f555|d676957a|4518359f|b3b9d5c4|
     -+	Filter_Length:1
     -+	Filter_Data:401004080200810|
     -+	EOF
     -+	test-tool bloom generate_filter " " >actual &&
     -+	test_cmp expect actual
     -+'
     -+
     -+test_expect_success 'compute bloom key for a root level folder' '
     -+	cat >expect <<-\EOF &&
     -+	Hashes:1a21016f|fff1c06d|e5c27f6b|cb933e69|b163fd67|9734bc65|7d057b63|
     -+	Filter_Length:1
     -+	Filter_Data:aaa800000000|
     -+	EOF
     -+	test-tool bloom generate_filter "A" >actual &&
     -+	test_cmp expect actual
     -+'
     -+
     -+test_expect_success 'compute bloom key for a root level file' '
     -+	cat >expect <<-\EOF &&
     -+	Hashes:e2d51107|30970605|7e58fb03|cc1af001|19dce4ff|679ed9fd|b560cefb|
     -+	Filter_Length:1
     -+	Filter_Data:a8000000000000aa|
     -+	EOF
     -+	test-tool bloom generate_filter "file.txt" >actual &&
     -+	test_cmp expect actual
     -+'
     -+
     -+test_expect_success 'compute bloom key for a deep folder' '
     -+	cat >expect <<-\EOF &&
     -+	Hashes:864cf838|27f055cd|c993b362|6b3710f7|0cda6e8c|ae7dcc21|502129b6|
     -+	Filter_Length:1
     -+	Filter_Data:1c0000600003000|
     -+	EOF
     -+	test-tool bloom generate_filter "A/B/C/D/E" >actual &&
     -+	test_cmp expect actual
     -+'
     -+
     -+test_expect_success 'compute bloom key for a deep file' '
     -+	cat >expect <<-\EOF &&
     -+	Hashes:07cdf850|4af629c7|8e1e5b3e|d1468cb5|146ebe2c|5796efa3|9abf211a|
     -+	Filter_Length:1
     -+	Filter_Data:4020100804010080|
     -+	EOF
     -+	test-tool bloom generate_filter "A/B/C/D/E/file.txt" >actual &&
     -+	test_cmp expect actual
     -+'
     -+
     -+test_done
     + test_done
     + \ No newline at end of file
  3:  a698c04a78c !  5:  2d4c0b2da38 diff: halt tree-diff early after max_changes
     @@ -29,7 +29,7 @@
       	struct diff_options diffopt;
      +	int max_changes = 512;
       
     - 	if (!bloom_filters.slab_size)
     + 	if (bloom_filters.slab_size == 0)
       		return NULL;
      @@
       
     @@ -46,7 +46,7 @@
      -	if (diff_queued_diff.nr <= 512) {
      +	if (diff_queued_diff.nr <= max_changes) {
       		struct hashmap pathmap;
     - 		struct pathmap_hash_entry* e;
     + 		struct pathmap_hash_entry *e;
       		struct hashmap_iter iter;
      
       diff --git a/diff.h b/diff.h
  4:  c17bbcbc66e !  6:  c38b9b386ef commit-graph: compute Bloom filters for changed paths
     @@ -2,11 +2,13 @@
      
          commit-graph: compute Bloom filters for changed paths
      
     -    Compute Bloom filters for the paths that changed between a commit and its
     -    first parent using the implementation in bloom.c, when the
     -    COMMIT_GRAPH_WRITE_CHANGED_PATHS flag is set. This computation is done on a
     -    commit-by-commit basis. We will write these Bloom filters to the commit graph
     -    file in the next change.
     +    Add new COMMIT_GRAPH_WRITE_CHANGED_PATHS flag that makes Git compute
     +    Bloom filters for the paths that changed between a commit and it's
     +    first parent, for each commit in the commit-graph.  This computation
     +    is done on a commit-by-commit basis.
     +
     +    We will write these Bloom filters to the commit-graph file, to store
     +    this data on disk, in the next change in this series.
      
          Helped-by: Derrick Stolee <[email protected]>
          Signed-off-by: Garima Singh <[email protected]>
     @@ -31,7 +33,7 @@
      +		 changed_paths:1;
       
       	const struct split_commit_graph_opts *split_opts;
     -+	uint32_t total_bloom_filter_data_size;
     ++	size_t total_bloom_filter_data_size;
       };
       
       static void write_graph_chunk_fanout(struct hashfile *f,
     @@ -44,17 +46,17 @@
      +	int i;
      +	struct progress *progress = NULL;
      +
     -+	load_bloom_filters();
     ++	init_bloom_filters();
      +
      +	if (ctx->report_progress)
     -+		progress = start_progress(
     -+			_("Computing commit diff Bloom filters"),
     ++		progress = start_delayed_progress(
     ++			_("Computing commit changed paths Bloom filters"),
      +			ctx->commits.nr);
      +
      +	for (i = 0; i < ctx->commits.nr; i++) {
      +		struct commit *c = ctx->commits.list[i];
      +		struct bloom_filter *filter = get_bloom_filter(ctx->r, c);
     -+		ctx->total_bloom_filter_data_size += sizeof(uint64_t) * filter->len;
     ++		ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
      +		display_progress(progress, i + 1);
      +	}
      +
     @@ -93,7 +95,7 @@
       	/* Make sure that each OID in the input is a valid commit OID. */
      -	COMMIT_GRAPH_WRITE_CHECK_OIDS = (1 << 3)
      +	COMMIT_GRAPH_WRITE_CHECK_OIDS = (1 << 3),
     -+	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4)
     ++	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4),
       };
       
       struct split_commit_graph_opts {
  5:  78e8e49c3a1 !  7:  d24c85c54ef commit-graph: examine changed-path objects in pack order
     @@ -39,6 +39,7 @@
       /* Remember to update object flag allocation in object.h */
       #define REACHABLE       (1u<<15)
       
     +-char *get_commit_graph_filename(struct object_directory *odb)
      +/* Keep track of the order in which commits are added to our list. */
      +define_commit_slab(commit_pos, int);
      +static struct commit_pos commit_pos = COMMIT_SLAB_INIT(1, commit_pos);
     @@ -55,16 +56,20 @@
      +}
      +
      +static int commit_pos_cmp(const void *va, const void *vb)
     -+{
     + {
     +-	return xstrfmt("%s/info/commit-graph", odb->path);
      +	const struct commit *a = *(const struct commit **)va;
      +	const struct commit *b = *(const struct commit **)vb;
      +	return commit_pos_at(&commit_pos, a) -
      +	       commit_pos_at(&commit_pos, b);
      +}
      +
     - char *get_commit_graph_filename(const char *obj_dir)
     - {
     - 	char *filename = xstrfmt("%s/info/commit-graph", obj_dir);
     ++char *get_commit_graph_filename(struct object_directory *obj_dir)
     ++{
     ++	return xstrfmt("%s/info/commit-graph", obj_dir->path);
     + }
     + 
     + static char *get_split_graph_filename(struct object_directory *odb,
      @@
       	oidcpy(&(ctx->oids.list[ctx->oids.nr]), oid);
       	ctx->oids.nr++;
     @@ -78,27 +83,27 @@
       {
       	int i;
       	struct progress *progress = NULL;
     -+	struct commit **sorted_by_pos;
     ++	struct commit **sorted_commits;
       
     - 	load_bloom_filters();
     + 	init_bloom_filters();
       
      @@
     - 			_("Computing commit diff Bloom filters"),
     + 			_("Computing commit changed paths Bloom filters"),
       			ctx->commits.nr);
       
     -+	ALLOC_ARRAY(sorted_by_pos, ctx->commits.nr);
     -+	COPY_ARRAY(sorted_by_pos, ctx->commits.list, ctx->commits.nr);
     -+	QSORT(sorted_by_pos, ctx->commits.nr, commit_pos_cmp);
     ++	ALLOC_ARRAY(sorted_commits, ctx->commits.nr);
     ++	COPY_ARRAY(sorted_commits, ctx->commits.list, ctx->commits.nr);
     ++	QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
      +
       	for (i = 0; i < ctx->commits.nr; i++) {
      -		struct commit *c = ctx->commits.list[i];
     -+		struct commit *c = sorted_by_pos[i];
     ++		struct commit *c = sorted_commits[i];
       		struct bloom_filter *filter = get_bloom_filter(ctx->r, c);
     - 		ctx->total_bloom_filter_data_size += sizeof(uint64_t) * filter->len;
     + 		ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
       		display_progress(progress, i + 1);
       	}
       
     -+	free(sorted_by_pos);
     ++	free(sorted_commits);
       	stop_progress(&progress);
       }

6: 58704d81b6b ! 8: 5ed16f35fed commit-graph: examine commits by generation number

     @@ -1,11 +1,11 @@
     -Author: Derrick Stolee <[email protected]>
     +Author: Garima Singh <[email protected]>
      
          commit-graph: examine commits by generation number
      
          When running 'git commit-graph write --changed-paths', we sort the
          commits by pack-order to save time when computing the changed-paths
          bloom filters. This does not help when finding the commits via the
     -    --reachable flag.
     +    '--reachable' flag.
      
          If not using pack-order, then sort by generation number before
          examining the diff. Commits with similar generation are more likely
     @@ -45,9 +45,9 @@
      +	return 0;
      +}
      +
     - char *get_commit_graph_filename(const char *obj_dir)
     + char *get_commit_graph_filename(struct object_directory *obj_dir)
       {
     - 	char *filename = xstrfmt("%s/info/commit-graph", obj_dir);
     + 	return xstrfmt("%s/info/commit-graph", obj_dir->path);
      @@
       		 report_progress:1,
       		 split:1,
     @@ -57,20 +57,20 @@
      +		 order_by_pack:1;
       
       	const struct split_commit_graph_opts *split_opts;
     - 	uint32_t total_bloom_filter_data_size;
     + 	size_t total_bloom_filter_data_size;
      @@
       
     - 	ALLOC_ARRAY(sorted_by_pos, ctx->commits.nr);
     - 	COPY_ARRAY(sorted_by_pos, ctx->commits.list, ctx->commits.nr);
     --	QSORT(sorted_by_pos, ctx->commits.nr, commit_pos_cmp);
     + 	ALLOC_ARRAY(sorted_commits, ctx->commits.nr);
     + 	COPY_ARRAY(sorted_commits, ctx->commits.list, ctx->commits.nr);
     +-	QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
      +
      +	if (ctx->order_by_pack)
     -+		QSORT(sorted_by_pos, ctx->commits.nr, commit_pos_cmp);
     ++		QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
      +	else
     -+		QSORT(sorted_by_pos, ctx->commits.nr, commit_gen_cmp);
     ++		QSORT(sorted_commits, ctx->commits.nr, commit_gen_cmp);
       
       	for (i = 0; i < ctx->commits.nr; i++) {
     - 		struct commit *c = sorted_by_pos[i];
     + 		struct commit *c = sorted_commits[i];
      @@
       	}

  -:  ----------- >  9:  55824cda89c diff: skip batch object download when possible
  7:  39ee0610800 ! 10:  1e4663523de commit-graph: write Bloom filters to commit graph file
     @@ -2,9 +2,10 @@
      
          commit-graph: write Bloom filters to commit graph file
      
     -    Update the technical documentation for commit-graph-format with the formats for
     -    the Bloom filter index (BIDX) and Bloom filter data (BDAT) chunks. Write the
     -    computed Bloom filters information to the commit graph file using this format.
     +    Update the technical documentation for commit-graph-format with
     +    the formats for the Bloom filter index (BIDX) and Bloom filter
     +    data (BDAT) chunks. Write the computed Bloom filters information
     +    to the commit graph file using this format.
      
          Helped-by: Derrick Stolee <[email protected]>
          Signed-off-by: Garima Singh <[email protected]>
     @@ -17,7 +18,7 @@
         the graph file.
       
      +- The Bloom filter of the commit carrying the paths that were changed between
     -+  the commit and its first parent.
     ++  the commit and its first parent, if requested.
      +
       These positional references are stored as unsigned 32-bit integers
       corresponding to the array position within the list of commit OIDs. Due
     @@ -36,16 +37,22 @@
      +  Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
      +    * It starts with header consisting of three unsigned 32-bit integers:
      +      - Version of the hash algorithm being used. We currently only support
     -+	value 1 which implies the murmur3 hash implemented exactly as described
     -+	in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
     ++	value 1 which corresponds to the 32-bit version of the murmur3 hash
     ++	implemented exactly as described in
     ++	https://en.wikipedia.org/wiki/MurmurHash#Algorithm and the double
     ++	hashing technique using seed values 0x293ae76f and 0x7e646e2 as
     ++	described in https://doi.org/10.1007/978-3-540-30494-4_26 "Bloom Filters
     ++	in Probabilistic Verification"
      +      - The number of times a path is hashed and hence the number of bit positions
     -+	that cumulatively determine whether a file is present in the commit.
     ++	      that cumulatively determine whether a file is present in the commit.
      +      - The minimum number of bits 'b' per entry in the Bloom filter. If the filter
     -+	contains 'n' entries, then the filter size is the minimum number of 64-bit
     -+	words that contain n*b bits.
     ++	      contains 'n' entries, then the filter size is the minimum number of 64-bit
     ++	      words that contain n*b bits.
      +    * The rest of the chunk is the concatenation of all the computed Bloom
      +      filters for the commits in lexicographic order.
     -+    * The BDAT chunk is present iff BIDX is present.
     ++    * Note: Commits with no changes or more than 512 changes have Bloom filters
     ++      of length zero.
     ++    * The BDAT chunk is present if and only if BIDX is present.
      +
         Base Graphs List (ID: {'B', 'A', 'S', 'E'}) [Optional]
             This list of H-byte hashes describe a set of B commit-graph files that
     @@ -103,16 +110,14 @@
       		last_chunk_offset = chunk_offset;
       	}
       
     -+	/* We need both the bloom chunks to exist together. Else ignore the data */
     -+	if ((graph->chunk_bloom_indexes && !graph->chunk_bloom_data)
     -+		 || (!graph->chunk_bloom_indexes && graph->chunk_bloom_data)) {
     ++	if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
     ++		init_bloom_filters();
     ++	} else {
     ++		/* We need both the bloom chunks to exist together. Else ignore the data */
      +		graph->chunk_bloom_indexes = NULL;
      +		graph->chunk_bloom_data = NULL;
      +		graph->bloom_filter_settings = NULL;
      +	}
     -+
     -+	if (graph->chunk_bloom_indexes && graph->chunk_bloom_data)
     -+		load_bloom_filters();
      +
       	hashcpy(graph->oid.hash, graph->data + graph->data_len - graph->hash_len);
       
     @@ -148,7 +153,7 @@
      +
      +static void write_graph_chunk_bloom_data(struct hashfile *f,
      +					 struct write_commit_graph_context *ctx,
     -+					 struct bloom_filter_settings *settings)
     ++					 const struct bloom_filter_settings *settings)
      +{
      +	struct commit **list = ctx->commits.list;
      +	struct commit **last = ctx->commits.list + ctx->commits.nr;
     @@ -167,7 +172,7 @@
      +	while (list < last) {
      +		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
      +		display_progress(progress, ++i);
     -+		hashwrite(f, filter->data, filter->len * sizeof(uint64_t));
     ++		hashwrite(f, filter->data, filter->len * sizeof(unsigned char));
      +		list++;
      +	}
      +
     @@ -177,22 +182,11 @@
       static int oid_compare(const void *_a, const void *_b)
       {
       	const struct object_id *a = (const struct object_id *)_a;
     -@@
     - 	load_bloom_filters();
     - 
     - 	if (ctx->report_progress)
     --		progress = start_progress(
     --			_("Computing commit diff Bloom filters"),
     -+		progress = start_delayed_progress(
     -+			_("Computing changed paths Bloom filters"),
     - 			ctx->commits.nr);
     - 
     - 	ALLOC_ARRAY(sorted_by_pos, ctx->commits.nr);
      @@
       	struct strbuf progress_title = STRBUF_INIT;
       	int num_chunks = 3;
       	struct object_id file_hash;
     -+	struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;
     ++	const struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;
       
       	if (ctx->split) {
       		struct strbuf tmp_file = STRBUF_INIT;
     @@ -236,6 +230,14 @@
       	if (ctx->num_commit_graphs_after > 1 &&
       	    write_graph_chunk_base(f, ctx)) {
       		return -1;
     +@@
     + 		close(g->graph_fd);
     + 	}
     + 	free(g->filename);
     ++	free(g->bloom_filter_settings);
     + 	free(g);
     + }
     + 
      
       diff --git a/commit-graph.h b/commit-graph.h
       --- a/commit-graph.h
     @@ -246,7 +248,7 @@
       struct commit;
      +struct bloom_filter_settings;
       
     - char *get_commit_graph_filename(const char *obj_dir);
     + char *get_commit_graph_filename(struct object_directory *odb);
       int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
      @@
       	const unsigned char *chunk_commit_data;
     @@ -258,13 +260,4 @@
      +	struct bloom_filter_settings *bloom_filter_settings;
       };
       
     - struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st);
     -@@
     - 	COMMIT_GRAPH_WRITE_SPLIT      = (1 << 2),
     - 	/* Make sure that each OID in the input is a valid commit OID. */
     - 	COMMIT_GRAPH_WRITE_CHECK_OIDS = (1 << 3),
     --	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4)
     -+	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4),
     - };
     - 
     - struct split_commit_graph_opts {
     + struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st,
  8:  b20c8d2b209 ! 11:  68395d4051b commit-graph: reuse existing Bloom filters during write.
     @@ -1,9 +1,10 @@
      Author: Garima Singh <[email protected]>
      
     -    commit-graph: reuse existing Bloom filters during write.
     +    commit-graph: reuse existing Bloom filters during write
      
     -    Read previously computed Bloom filters from the commit-graph file if
     -    possible to avoid recomputing during commit-graph write.
     +    Add logic to
     +    a) parse Bloom filter information from the commit graph file and,
     +    b) re-use existing Bloom filters.
      
          See Documentation/technical/commit-graph-format for the format in which
          the Bloom filter information is written to the commit graph file.
     @@ -25,7 +26,7 @@
             commit's filter.
      
          We toggle whether Bloom filters should be recomputed based on the
     -    compute_if_null flag.
     +    compute_if_not_present flag.
      
          Helped-by: Derrick Stolee <[email protected]>
          Signed-off-by: Garima Singh <[email protected]>
     @@ -34,15 +35,16 @@
       --- a/bloom.c
       +++ b/bloom.c
      @@
     - #include "git-compat-util.h"
     - #include "bloom.h"
     + #include "diffcore.h"
     + #include "revision.h"
     + #include "hashmap.h"
     ++#include "commit-graph.h"
      +#include "commit.h"
     -+#include "commit-slab.h"
     - #include "commit-graph.h"
     - #include "object-store.h"
     - #include "diff.h"
     + 
     + define_commit_slab(bloom_filter_slab, struct bloom_filter);
     + 
      @@
     - 	}
     + 	return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
       }
       
      +static int load_bloom_filter_from_graph(struct commit_graph *g,
     @@ -62,23 +64,29 @@
      +
      +	end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
      +
     -+	if (lex_pos)
     ++	if (lex_pos > 0)
      +		start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1));
      +	else
      +		start_index = 0;
      +
      +	filter->len = end_index - start_index;
     -+	filter->data = (uint64_t *)(g->chunk_bloom_data +
     -+					sizeof(uint64_t) * start_index +
     ++	filter->data = (unsigned char *)(g->chunk_bloom_data +
     ++					sizeof(unsigned char) * start_index +
      +					BLOOMDATA_CHUNK_HEADER_SIZE);
      +
      +	return 1;
      +}
      +
     + /*
     +  * Calculate the murmur3 32-bit hash value for the given data
     +  * using the given seed.
     +@@
     + }
     + 
       struct bloom_filter *get_bloom_filter(struct repository *r,
      -				      struct commit *c)
      +				      struct commit *c,
     -+				      int compute_if_not_present)
     ++					  int compute_if_not_present)
       {
       	struct bloom_filter *filter;
       	struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
     @@ -102,7 +110,7 @@
      +
       	repo_diff_setup(r, &diffopt);
       	diffopt.flags.recursive = 1;
     - 	diffopt.max_changes = max_changes;
     + 	diffopt.detect_rename = 0;
      
       diff --git a/bloom.h b/bloom.h
       --- a/bloom.h
     @@ -110,21 +118,21 @@
      @@
       
       #define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10 }
     - #define BITS_PER_WORD 64
     -+#define BLOOMDATA_CHUNK_HEADER_SIZE 3*sizeof(uint32_t)
     + #define BITS_PER_WORD 8
     ++#define BLOOMDATA_CHUNK_HEADER_SIZE 3 * sizeof(uint32_t)
       
       /*
        * A bloom_filter struct represents a data segment to
      @@
     - 					   struct bloom_filter_settings *settings);
     + void init_bloom_filters(void);
       
       struct bloom_filter *get_bloom_filter(struct repository *r,
      -				      struct commit *c);
      +				      struct commit *c,
      +				      int compute_if_not_present);
       
     - int bloom_filter_contains(struct bloom_filter *filter,
     - 			  struct bloom_key *key,
     + #endif
     + \ No newline at end of file
      
       diff --git a/commit-graph.c b/commit-graph.c
       --- a/commit-graph.c
     @@ -145,25 +153,17 @@
      -		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
      +		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
       		display_progress(progress, ++i);
     - 		hashwrite(f, filter->data, filter->len * sizeof(uint64_t));
     + 		hashwrite(f, filter->data, filter->len * sizeof(unsigned char));
       		list++;
      @@
       
       	for (i = 0; i < ctx->commits.nr; i++) {
     - 		struct commit *c = sorted_by_pos[i];
     + 		struct commit *c = sorted_commits[i];
      -		struct bloom_filter *filter = get_bloom_filter(ctx->r, c);
      +		struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1);
     - 		ctx->total_bloom_filter_data_size += sizeof(uint64_t) * filter->len;
     + 		ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
       		display_progress(progress, i + 1);
       	}
     -@@
     - 		g->data = NULL;
     - 		close(g->graph_fd);
     - 	}
     -+	free(g->bloom_filter_settings);
     - 	free(g->filename);
     - 	free(g);
     - }
      
       diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c
       --- a/t/helper/test-bloom.c
  9:  3d7ee0c9695 ! 12:  7e450e45236 commit-graph: add --changed-paths option to write subcommand
     @@ -56,7 +56,7 @@
      +	int enable_changed_paths;
       } opts;
       
     - static int graph_verify(int argc, const char **argv)
     + static struct object_directory *find_odb(struct repository *r,
      @@
       			N_("start walk at commits listed by stdin")),
       		OPT_BOOL(0, "append", &opts.append,
     @@ -74,4 +74,4 @@
      +		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;
       
       	read_replace_refs = 0;
     - 
     + 	odb = find_odb(the_repository, opts.obj_dir);
 10:  77f1c561e82 ! 13:  b18af58aa3e revision.c: use Bloom filters to speed up path based revision walks
     @@ -2,17 +2,27 @@
      
          revision.c: use Bloom filters to speed up path based revision walks
      
     -    Revision walk will now use Bloom filters for commits to speed up revision
     -    walks for a particular path (for computing history for that path), if they
     -    are present in the commit-graph file.
     +    Revision walk will now use Bloom filters for commits to speed up
     +    revision walks for a particular path (for computing history for
     +    that path), if they are present in the commit-graph file.
      
     -    We load the Bloom filters during the prepare_revision_walk step, but only
     -    when dealing with a single pathspec. While comparing trees in
     -    rev_compare_trees(), if the Bloom filter says that the file is not different
     -    between the two trees, we don't need to compute the expensive diff. This is
     -    where we get our performance gains. The other response of the Bloom filter
     -    is `maybe`, in which case we fall back to the full diff calculation to
     -    determine if the path was changed in the commit.
     +    We load the Bloom filters during the prepare_revision_walk step,
     +    currently only when dealing with a single pathspec. Extending
     +    it to work with multiple pathspecs can be explored and built on
     +    top of this series in the future.
     +
     +    While comparing trees in rev_compare_trees(), if the Bloom filter
     +    says that the file is not different between the two trees, we don't
     +    need to compute the expensive diff. This is where we get our
     +    performance gains. The other response of the Bloom filter is '`:maybe',
     +    in which case we fall back to the full diff calculation to determine
     +    if the path was changed in the commit.
     +
     +    We do not try to use Bloom filters when the '--walk-reflogs' option
     +    is specified. The '--walk-reflogs' option does not walk the commit
     +    ancestry chain like the rest of the options. Incorporating the
     +    performance gains when walking reflog entries would add more
     +    complexity, and can be explored in a later series.
      
          Performance Gains:
          We tested the performance of `git log -- <path>` on the git repo, the linux
     @@ -30,6 +40,49 @@
          Helped-by: Jonathan Tan <[email protected]>
          Signed-off-by: Garima Singh <[email protected]>
      
     + diff --git a/bloom.c b/bloom.c
     + --- a/bloom.c
     + +++ b/bloom.c
     +@@
     + 
     + 	return filter;
     + }
     ++
     ++int bloom_filter_contains(const struct bloom_filter *filter,
     ++			  const struct bloom_key *key,
     ++			  const struct bloom_filter_settings *settings)
     ++{
     ++	int i;
     ++	uint64_t mod = filter->len * BITS_PER_WORD;
     ++
     ++	if (!mod)
     ++		return -1;
     ++
     ++	for (i = 0; i < settings->num_hashes; i++) {
     ++		uint64_t hash_mod = key->hashes[i] % mod;
     ++		uint64_t block_pos = hash_mod / BITS_PER_WORD;
     ++		if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
     ++			return 0;
     ++	}
     ++
     ++	return 1;
     ++}
     + \ No newline at end of file
     +
     + diff --git a/bloom.h b/bloom.h
     + --- a/bloom.h
     + +++ b/bloom.h
     +@@
     + 				      struct commit *c,
     + 				      int compute_if_not_present);
     + 
     ++int bloom_filter_contains(const struct bloom_filter *filter,
     ++			  const struct bloom_key *key,
     ++			  const struct bloom_filter_settings *settings);
     ++
     + #endif
     + \ No newline at end of file
     +
       diff --git a/revision.c b/revision.c
       --- a/revision.c
       +++ b/revision.c
     @@ -38,7 +91,6 @@
       #include "hashmap.h"
       #include "utf8.h"
      +#include "bloom.h"
     -+#include "json-writer.h"
       
       volatile show_early_output_fn_t show_early_output;
       
     @@ -46,29 +98,6 @@
       	options->flags.has_changes = 1;
       }
       
     -+static int bloom_filter_atexit_registered;
     -+static unsigned int count_bloom_filter_maybe;
     -+static unsigned int count_bloom_filter_definitely_not;
     -+static unsigned int count_bloom_filter_false_positive;
     -+static unsigned int count_bloom_filter_not_present;
     -+static unsigned int count_bloom_filter_length_zero;
     -+
     -+static void trace2_bloom_filter_statistics_atexit(void)
     -+{
     -+	struct json_writer jw = JSON_WRITER_INIT;
     -+
     -+	jw_object_begin(&jw, 0);
     -+	jw_object_intmax(&jw, "filter_not_present", count_bloom_filter_not_present);
     -+	jw_object_intmax(&jw, "zero_length_filter", count_bloom_filter_length_zero);
     -+	jw_object_intmax(&jw, "maybe", count_bloom_filter_maybe);
     -+	jw_object_intmax(&jw, "definitely_not", count_bloom_filter_definitely_not);
     -+	jw_end(&jw);
     -+
     -+	trace2_data_json("bloom", the_repository, "statistics", &jw);
     -+
     -+	jw_release(&jw);
     -+}
     -+
      +static void prepare_to_use_bloom_filter(struct rev_info *revs)
      +{
      +	struct pathspec_item *pi;
     @@ -92,6 +121,7 @@
      +	pi = &revs->pruning.pathspec.items[0];
      +	last_index = pi->len - 1;
      +
     ++	/* remove single trailing slash from path, if needed */
      +	if (pi->match[last_index] == '/') {
      +	    path_alloc = xstrdup(pi->match);
      +	    path_alloc[last_index] = '\0';
     @@ -104,11 +134,6 @@
      +	revs->bloom_key = xmalloc(sizeof(struct bloom_key));
      +	fill_bloom_key(path, len, revs->bloom_key, revs->bloom_filter_settings);
      +
     -+	if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
     -+		atexit(trace2_bloom_filter_statistics_atexit);
     -+		bloom_filter_atexit_registered = 1;
     -+	}
     -+
      +	free(path_alloc);
      +}
      +
     @@ -127,12 +152,10 @@
      +	filter = get_bloom_filter(revs->repo, commit, 0);
      +
      +	if (!filter) {
     -+		count_bloom_filter_not_present++;
      +		return -1;
      +	}
      +
      +	if (!filter->len) {
     -+		count_bloom_filter_length_zero++;
      +		return -1;
      +	}
      +
     @@ -140,11 +163,6 @@
      +				       revs->bloom_key,
      +				       revs->bloom_filter_settings);
      +
     -+	if (result)
     -+		count_bloom_filter_maybe++;
     -+	else
     -+		count_bloom_filter_definitely_not++;
     -+
      +	return result;
      +}
      +
     @@ -162,7 +180,7 @@
       			return REV_TREE_SAME;
       	}
       
     -+	if (revs->pruning.pathspec.nr == 1 && !revs->reflog_info && !nth_parent) {
     ++	if (revs->bloom_key && !nth_parent) {
      +		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
      +
      +		if (bloom_ret == 0)
     @@ -174,10 +192,6 @@
       	if (diff_tree_oid(&t1->object.oid, &t2->object.oid, "",
       			   &revs->pruning) < 0)
       		return REV_TREE_DIFFERENT;
     -+
     -+	if (!nth_parent)
     -+		if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
     -+			count_bloom_filter_false_positive++;
      +
       	return tree_difference;
       }
     @@ -237,164 +251,3 @@
       };
       
       int ref_excluded(struct string_list *, const char *path);
     -
     - diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c
     - --- a/t/helper/test-read-graph.c
     - +++ b/t/helper/test-read-graph.c
     -@@
     - 		printf(" commit_metadata");
     - 	if (graph->chunk_extra_edges)
     - 		printf(" extra_edges");
     -+	if (graph->chunk_bloom_indexes)
     -+		printf(" bloom_indexes");
     -+	if (graph->chunk_bloom_data)
     -+		printf(" bloom_data");
     - 	printf("\n");
     - 
     - 	UNLEAK(graph);
     -
     - diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
     - new file mode 100755
     - --- /dev/null
     - +++ b/t/t4216-log-bloom.sh
     -@@
     -+#!/bin/sh
     -+
     -+test_description='git log for a path with bloom filters'
     -+. ./test-lib.sh
     -+
     -+test_expect_success 'setup test - repo, commits, commit graph, log outputs' '
     -+	git init &&
     -+	mkdir A A/B A/B/C &&
     -+	test_commit c1 A/file1 &&
     -+	test_commit c2 A/B/file2 &&
     -+	test_commit c3 A/B/C/file3 &&
     -+	test_commit c4 A/file1 &&
     -+	test_commit c5 A/B/file2 &&
     -+	test_commit c6 A/B/C/file3 &&
     -+	test_commit c7 A/file1 &&
     -+	test_commit c8 A/B/file2 &&
     -+	test_commit c9 A/B/C/file3 &&
     -+	git checkout -b side HEAD~4 &&
     -+	test_commit side-1 file4 &&
     -+	git checkout master &&
     -+	git merge side &&
     -+	test_commit c10 file5 &&
     -+	mv file5 file5_renamed &&
     -+	git add file5_renamed &&
     -+	git commit -m "rename" &&
     -+	git commit-graph write --reachable --changed-paths
     -+'
     -+graph_read_expect() {
     -+	OPTIONAL=""
     -+	NUM_CHUNKS=5
     -+	cat >expect <<- EOF
     -+	header: 43475048 1 1 $NUM_CHUNKS 0
     -+	num_commits: $1
     -+	chunks: oid_fanout oid_lookup commit_metadata bloom_indexes bloom_data
     -+	EOF
     -+	test-tool read-graph >output &&
     -+	test_cmp expect output
     -+}
     -+
     -+test_expect_success 'commit-graph write wrote out the bloom chunks' '
     -+	graph_read_expect 13
     -+'
     -+
     -+setup() {
     -+	rm output
     -+	rm "$TRASH_DIRECTORY/trace.perf"
     -+	git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom
     -+	GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom
     -+}
     -+
     -+test_bloom_filters_used() {
     -+	log_args=$1
     -+	bloom_trace_prefix="statistics:{\"filter_not_present\":0,\"zero_length_filter\":0,\"maybe\""
     -+	setup "$log_args"
     -+	grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" && test_cmp log_wo_bloom log_w_bloom
     -+}
     -+
     -+test_bloom_filters_not_used() {
     -+	log_args=$1
     -+	setup "$log_args"
     -+	!(grep -q "statistics:{\"filter_not_present\":" "$TRASH_DIRECTORY/trace.perf") && test_cmp log_wo_bloom log_w_bloom
     -+}
     -+
     -+for path in A A/B A/B/C A/file1 A/B/file2 A/B/C/file3 file4 file5_renamed
     -+do
     -+	for option in "" \
     -+		      "--full-history" \
     -+		      "--full-history --simplify-merges" \
     -+		      "--simplify-merges" \
     -+		      "--simplify-by-decoration" \
     -+		      "--follow" \
     -+		      "--first-parent" \
     -+		      "--topo-order" \
     -+		      "--date-order" \
     -+		      "--author-date-order" \
     -+		      "--ancestry-path side..master"
     -+	do
     -+		test_expect_success "git log option: $option for path: $path" '
     -+			test_bloom_filters_used "$option -- $path"
     -+		'
     -+	done
     -+done
     -+
     -+test_expect_success 'git log -- folder works with and without the trailing slash' '
     -+	test_bloom_filters_used "-- A" &&
     -+	test_bloom_filters_used "-- A/"
     -+'
     -+
     -+test_expect_success 'git log for path that does not exist. ' '
     -+	test_bloom_filters_used "-- path_does_not_exist"
     -+'
     -+
     -+test_expect_success 'git log with --walk-reflogs does not use bloom filters' '
     -+	test_bloom_filters_not_used "--walk-reflogs -- A"
     -+'
     -+
     -+test_expect_success 'git log -- multiple path specs does not use bloom filters' '
     -+	test_bloom_filters_not_used "-- file4 A/file1"
     -+'
     -+
     -+test_expect_success 'git log with wildcard that resolves to a single path uses bloom filters' '
     -+	test_bloom_filters_used "-- *4" &&
     -+	test_bloom_filters_used "-- *renamed"
     -+'
     -+
     -+test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses bloom filters' '
     -+	test_bloom_filters_not_used "-- *" &&
     -+	test_bloom_filters_not_used "-- file*"
     -+'
     -+
     -+test_expect_success 'setup - add commit-graph to the chain without bloom filters' '
     -+	test_commit c14 A/anotherFile2 &&
     -+	test_commit c15 A/B/anotherFile2 &&
     -+	test_commit c16 A/B/C/anotherFile2 &&
     -+	GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0 git commit-graph write --reachable --split &&
     -+	test_line_count = 2 .git/objects/info/commit-graphs/commit-graph-chain
     -+'
     -+
     -+test_expect_success 'git log does not use bloom filters if the latest graph does not have bloom filters.' '
     -+	test_bloom_filters_not_used "-- A/B"
     -+'
     -+
     -+test_expect_success 'setup - add commit-graph to the chain with bloom filters' '
     -+	test_commit c17 A/anotherFile3 &&
     -+	git commit-graph write --reachable --changed-paths --split &&
     -+	test_line_count = 3 .git/objects/info/commit-graphs/commit-graph-chain
     -+'
     -+
     -+test_bloom_filters_used_when_some_filters_are_missing() {
     -+	log_args=$1
     -+	bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"zero_length_filter\":0,\"maybe\":6,\"definitely_not\":6"
     -+	setup "$log_args"
     -+	grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" && test_cmp log_wo_bloom log_w_bloom
     -+}
     -+
     -+test_expect_success 'git log uses bloom filters if they exist in the latest but not all commit graphs in the chain.' '
     -+	test_bloom_filters_used_when_some_filters_are_missing "-- A/B"
     -+'
     -+
     -+test_done
  -:  ----------- > 14:  b5eb280178f revision.c: add trace2 stats around Bloom filter usage
  -:  ----------- > 15:  3019ef72881 t4216: add end to end tests for git log with Bloom filters
 11:  e1b076a714d ! 16:  213abb5d895 commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag

@@ -37,8 +37,8 @@
export GIT_TEST_COMMIT_GRAPH=1
+ export GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1
export GIT_TEST_MULTI_PACK_INDEX=1
+ export GIT_TEST_ADD_I_USE_BUILTIN=1
make test
- ;;

diff --git a/commit-graph.h b/commit-graph.h
--- a/commit-graph.h
@@ -68,20 +68,6 @@
code path for utilizing a file system monitor to speed up detecting new or changed files.

- diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
- --- a/t/t4216-log-bloom.sh
- +++ b/t/t4216-log-bloom.sh
-@@
- test_description='git log for a path with bloom filters'
- . ./test-lib.sh
-
-+GIT_TEST_COMMIT_GRAPH=0
-+GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0
-+
- test_expect_success 'setup test - repo, commits, commit graph, log outputs' '
- git init &&
- mkdir A A/B A/B/C &&
-
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh --- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh

gitgitgadget

From: Garima Singh <[email protected]>

This is a minor cleanup to make it easier to change the number of chunks being written to the commit graph.

---
 commit-graph.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

index f013a84e294..e4f1a5b2f1a 100644
@@ -23,6 +23,7 @@
 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
+#define MAX_NUM_CHUNKS 5
 
 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
 

@@ -1350,8 +1351,8 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 	int fd;
 	struct hashfile *f;
 	struct lock_file lk = LOCK_INIT;
-	uint32_t chunk_ids[6];
-	uint64_t chunk_offsets[6];
+	uint32_t chunk_ids[MAX_NUM_CHUNKS + 1];
+	uint64_t chunk_offsets[MAX_NUM_CHUNKS + 1];
 	const unsigned hashsz = the_hash_algo->rawsz;
 	struct strbuf progress_title = STRBUF_INIT;
 	int num_chunks = 3;

gitgitgadget

From: Garima Singh <[email protected]>

In preparation for computing changed paths Bloom filters, implement the Murmur3 hash algorithm as described in [1]. It hashes the given data using the given seed and produces a uniformly distributed hash value.

[1] https://en.wikipedia.org/wiki/MurmurHash#Algorithm

---
 Makefile              |  2 ++
 bloom.c               | 73 +++++++++++++++++++++++++++++++++++++++++++
 bloom.h               | 13 ++++++++
 t/helper/test-bloom.c | 13 ++++++++
 t/helper/test-tool.c  |  1 +
 t/helper/test-tool.h  |  1 +
 t/t0095-bloom.sh      | 30 ++++++++++++++++++
 7 files changed, 133 insertions(+)
 create mode 100644 bloom.c
 create mode 100644 bloom.h
 create mode 100644 t/helper/test-bloom.c
 create mode 100755 t/t0095-bloom.sh

index ef1ff2228f0..491f75e68c5 100644
@@ -695,6 +695,7 @@ X =
 PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))
 
 TEST_BUILTINS_OBJS += test-advise.o
+TEST_BUILTINS_OBJS += test-bloom.o
 TEST_BUILTINS_OBJS += test-chmtime.o
 TEST_BUILTINS_OBJS += test-config.o
 TEST_BUILTINS_OBJS += test-ctype.o

@@ -840,6 +841,7 @@ LIB_OBJS += base85.o
 LIB_OBJS += bisect.o
 LIB_OBJS += blame.o
 LIB_OBJS += blob.o
+LIB_OBJS += bloom.o
 LIB_OBJS += branch.o
 LIB_OBJS += bulk-checkin.o
 LIB_OBJS += bundle.o

new file mode 100644
index 00000000000..d0fcc5f0aa6
@@ -0,0 +1,13 @@
+#ifndef BLOOM_H
+#define BLOOM_H
+
+/*
+ * Calculate the murmur3 32-bit hash value for the given data
+ * using the given seed.
+ * Produces a uniformly distributed hash value.
+ * Not considered to be cryptographically secure.
+ * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
+ */
+uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len);
+
+#endif
\ No newline at end of file

new file mode 100644
index 00000000000..60ee2043689
@@ -0,0 +1,13 @@
+#include "git-compat-util.h"
+#include "bloom.h"
+#include "test-tool.h"
+
+int cmd__bloom(int argc, const char **argv)
+{
+	if (!strcmp(argv[1], "get_murmur3")) {
+		uint32_t hashed = murmur3_seeded(0, argv[2], strlen(argv[2]));
+		printf("Murmur3 Hash with seed=0:0x%08x\n", hashed);
+	}
+
+	return 0;
+}
\ No newline at end of file

index 31eedcd241f..6e26bd65c97 100644
@@ -15,6 +15,7 @@ struct test_cmd {
 
 static struct test_cmd cmds[] = {
 	{ "advise", cmd__advise_if_enabled },
+	{ "bloom", cmd__bloom },
 	{ "chmtime", cmd__chmtime },
 	{ "config", cmd__config },
 	{ "ctype", cmd__ctype },

index 4eb5e6609e1..dceeef1d5c2 100644
@@ -5,6 +5,7 @@
 #include "git-compat-util.h"
 
 int cmd__advise_if_enabled(int argc, const char **argv);
+int cmd__bloom(int argc, const char **argv);
 int cmd__chmtime(int argc, const char **argv);
 int cmd__config(int argc, const char **argv);
 int cmd__ctype(int argc, const char **argv);

new file mode 100755
index 00000000000..2dad8c4a94e
@@ -0,0 +1,30 @@
+#!/bin/sh
+
+test_description='Testing the various Bloom filter computations in bloom.c'
+. ./test-lib.sh
+
+test_expect_success 'compute unseeded murmur3 hash for empty string' '
+	cat >expect <<-\EOF &&
+	Murmur3 Hash with seed=0:0x00000000
+	EOF
+	test-tool bloom get_murmur3 "" >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'compute unseeded murmur3 hash for test string 1' '
+	cat >expect <<-\EOF &&
+	Murmur3 Hash with seed=0:0x627b0c2c
+	EOF
+	test-tool bloom get_murmur3 "Hello world!" >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'compute unseeded murmur3 hash for test string 2' '
+	cat >expect <<-\EOF &&
+	Murmur3 Hash with seed=0:0x2e4ff723
+	EOF
+	test-tool bloom get_murmur3 "The quick brown fox jumps over the lazy dog" >actual &&
+	test_cmp expect actual
+'
+
+test_done
\ No newline at end of file

gitgitgadget

From: Garima Singh <[email protected]>

Introduce the constructs for Bloom filters, Bloom filter keys and Bloom filter settings.
For details on what Bloom filters are and how they work, refer to Dr. Derrick Stolee's blog post [1]. It provides a concise explanation of the adoption of Bloom filters as described in
[2] and [3].

Implementation specifics:
1. We currently use 7 and 10 for the number of hashes and the size of each entry respectively. They served as great starting values, the mathematical details behind this choice are described in [1] and [4]. The implementation, while not completely open to it at the moment, is flexible enough to allow for tweaking these settings in the future.

Note: The performance gains we have observed with these values are significant enough that we did not need to tweak these settings. The performance numbers are included in the cover letter of this series and in the commit message of the subsequent commit where we use Bloom filters to speed up git log -- path.

2. As described in [1] and [3], we do not need 7 independent hashing functions. We use the Murmur3 hashing scheme, seed it twice and then combine those to procure an arbitrary number of hash values.

3. The filters will be sized according to the number of changes in each commit, in multiples of 8 bit words.

[1] Derrick Stolee
"Supercharging the Git Commit Graph IV: Bloom Filters"
https://devblogs.microsoft.com/devops/super-charging-the-git-commit-graph-iv-Bloom-filters/

[2] Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese

    "An Improved Construction for Counting Bloom Filters"
    http://theory.stanford.edu/~rinap/papers/esa2006b.pdf
    https://doi.org/10.1007/11841036_61

[3] Peter C. Dillinger and Panagiotis Manolios
"Bloom Filters in Probabilistic Verification"
http://www.ccs.neu.edu/home/pete/pub/Bloom-filters-verification.pdf
https://doi.org/10.1007/978-3-540-30494-4_26

[4] Thomas Mueller Graf, Daniel Lemire
"Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters"
https://arxiv.org/abs/1912.08258

---
 bloom.c               | 38 +++++++++++++++++++++++++-
 bloom.h               | 63 +++++++++++++++++++++++++++++++++++++++++++
 t/helper/test-bloom.c | 48 +++++++++++++++++++++++++++++++++
 t/t0095-bloom.sh      | 40 +++++++++++++++++++++++++++
 4 files changed, 188 insertions(+), 1 deletion(-)

index 40e87632aeb..888b67f1ea6 100644
@@ -8,6 +8,11 @@ static uint32_t rotate_left(uint32_t value, int32_t count)
 	return ((value << count) | (value >> ((-count) & mask)));
 }
 
+static inline unsigned char get_bitmask(uint32_t pos)
+{
+	return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
+}
+
 /*
  * Calculate the murmur3 32-bit hash value for the given data
  * using the given seed.

@@ -70,4 +75,35 @@ uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
 	seed ^= (seed >> 16);
 
 	return seed;
-}
\ No newline at end of file
+}
+
+void fill_bloom_key(const char *data,
+					size_t len,
+					struct bloom_key *key,
+					const struct bloom_filter_settings *settings)
+{
+	int i;
+	const uint32_t seed0 = 0x293ae76f;
+	const uint32_t seed1 = 0x7e646e2c;
+	const uint32_t hash0 = murmur3_seeded(seed0, data, len);
+	const uint32_t hash1 = murmur3_seeded(seed1, data, len);
+
+	key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
+	for (i = 0; i < settings->num_hashes; i++)
+		key->hashes[i] = hash0 + i * hash1;
+}
+
+void add_key_to_filter(const struct bloom_key *key,
+					   struct bloom_filter *filter,
+					   const struct bloom_filter_settings *settings)
+{
+	int i;
+	uint64_t mod = filter->len * BITS_PER_WORD;
+
+	for (i = 0; i < settings->num_hashes; i++) {
+		uint64_t hash_mod = key->hashes[i] % mod;
+		uint64_t block_pos = hash_mod / BITS_PER_WORD;
+
+		filter->data[block_pos] |= get_bitmask(hash_mod);
+	}
+}

index 2dad8c4a94e..36a086c7c60 100755
@@ -27,4 +27,44 @@ test_expect_success 'compute unseeded murmur3 hash for test string 2' '
 	test_cmp expect actual
 '
 
+test_expect_success 'compute bloom key for empty string' '
+	cat >expect <<-\EOF &&
+	Hashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004|
+	Filter_Length:2
+	Filter_Data:11|11|
+	EOF
+	test-tool bloom generate_filter "" >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'compute bloom key for whitespace' '
+	cat >expect <<-\EOF &&
+	Hashes:0xf178874c|0x5f3d6eb6|0xcd025620|0x3ac73d8a|0xa88c24f4|0x16510c5e|0x8415f3c8|
+	Filter_Length:2
+	Filter_Data:51|55|
+	EOF
+	test-tool bloom generate_filter " " >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'compute bloom key for test string 1' '
+	cat >expect <<-\EOF &&
+	Hashes:0xb270de9b|0x1bb6f26e|0x84fd0641|0xee431a14|0x57892de7|0xc0cf41ba|0x2a15558d|
+	Filter_Length:2
+	Filter_Data:92|6c|
+	EOF
+	test-tool bloom generate_filter "Hello world!" >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'compute bloom key for test string 2' '
+	cat >expect <<-\EOF &&
+	Hashes:0x20ab385b|0xf5237fe2|0xc99bc769|0x9e140ef0|0x728c5677|0x47049dfe|0x1b7ce585|
+	Filter_Length:2
+	Filter_Data:a5|4a|
+	EOF
+	test-tool bloom generate_filter "file.txt" >actual &&
+	test_cmp expect actual
+'
+
 test_done
\ No newline at end of file

gitgitgadget

From: Garima Singh <[email protected]>

Add the core implementation for computing Bloom filters for the paths changed between a commit and it's first parent.

We fill the Bloom filters as (const char *data, int len) pairs as `struct bloom_filters" within a commit slab.

Filters for commits with no changes and more than 512 changes, is represented with a filter of length zero. There is no gain in distinguishing between a computed filter of length zero for a commit with no changes, and an uncomputed filter for new commits or for commits with more than 512 changes. The effect on git log -- path is the same in both cases. We will fall back to the normal diffing algorithm when we can't benefit from the existence of Bloom filters.

---
 bloom.c               | 97 +++++++++++++++++++++++++++++++++++++++++++
 bloom.h               |  8 ++++
 t/helper/test-bloom.c | 20 +++++++++
 t/t0095-bloom.sh      | 47 +++++++++++++++++++++
 4 files changed, 172 insertions(+)

index 888b67f1ea6..881a9841ede 100644
@@ -1,5 +1,18 @@
 #include "git-compat-util.h"
 #include "bloom.h"
+#include "diff.h"
+#include "diffcore.h"
+#include "revision.h"
+#include "hashmap.h"
+
+define_commit_slab(bloom_filter_slab, struct bloom_filter);
+
+struct bloom_filter_slab bloom_filters;
+
+struct pathmap_hash_entry {
+    struct hashmap_entry entry;
+    const char path[FLEX_ARRAY];
+};
 
 static uint32_t rotate_left(uint32_t value, int32_t count)
 {

@@ -107,3 +120,87 @@ void add_key_to_filter(const struct bloom_key *key,
 		filter->data[block_pos] |= get_bitmask(hash_mod);
 	}
 }
+
+void init_bloom_filters(void)
+{
+	init_bloom_filter_slab(&bloom_filters);
+}
+
+struct bloom_filter *get_bloom_filter(struct repository *r,
+				      struct commit *c)
+{
+	struct bloom_filter *filter;
+	struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
+	int i;
+	struct diff_options diffopt;
+
+	if (bloom_filters.slab_size == 0)
+		return NULL;
+
+	filter = bloom_filter_slab_at(&bloom_filters, c);
+
+	repo_diff_setup(r, &diffopt);
+	diffopt.flags.recursive = 1;
+	diff_setup_done(&diffopt);
+
+	if (c->parents)
+		diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt);
+	else
+		diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
+	diffcore_std(&diffopt);
+
+	if (diff_queued_diff.nr <= 512) {
+		struct hashmap pathmap;
+		struct pathmap_hash_entry *e;
+		struct hashmap_iter iter;
+		hashmap_init(&pathmap, NULL, NULL, 0);
+
+		for (i = 0; i < diff_queued_diff.nr; i++) {
+			const char *path = diff_queued_diff.queue[i]->two->path;
+
+			/*
+			* Add each leading directory of the changed file, i.e. for
+			* 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
+			* the Bloom filter could be used to speed up commands like
+			* 'git log dir/subdir', too.
+			*
+			* Note that directories are added without the trailing '/'.
+			*/
+			do {
+				char *last_slash = strrchr(path, '/');
+
+				FLEX_ALLOC_STR(e, path, path);
+				hashmap_entry_init(&e->entry, strhash(path));
+				hashmap_add(&pathmap, &e->entry);
+
+				if (!last_slash)
+					last_slash = (char*)path;
+				*last_slash = '\0';
+
+			} while (*path);
+
+			diff_free_filepair(diff_queued_diff.queue[i]);
+		}
+
+		filter->len = (hashmap_get_size(&pathmap) * settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
+		filter->data = xcalloc(filter->len, sizeof(unsigned char));
+
+		hashmap_for_each_entry(&pathmap, &iter, e, entry) {
+			struct bloom_key key;
+			fill_bloom_key(e->path, strlen(e->path), &key, &settings);
+			add_key_to_filter(&key, filter, &settings);
+		}
+
+		hashmap_free_entries(&pathmap, struct pathmap_hash_entry, entry);
+	} else {
+		for (i = 0; i < diff_queued_diff.nr; i++)
+			diff_free_filepair(diff_queued_diff.queue[i]);
+		filter->data = NULL;
+		filter->len = 0;
+	}
+
+	free(diff_queued_diff.queue);
+	DIFF_QUEUE_CLEAR(&diff_queued_diff);
+
+	return filter;
+}

index b9ce422ca2d..85ab8e9423d 100644
@@ -1,6 +1,9 @@
 #ifndef BLOOM_H
 #define BLOOM_H
 
+struct commit;
+struct repository;
+
 struct bloom_filter_settings {
 	/*
 	 * The version of the hashing technique being used.

@@ -73,4 +76,9 @@ void add_key_to_filter(const struct bloom_key *key,
 					   struct bloom_filter *filter,
 					   const struct bloom_filter_settings *settings);
 
+void init_bloom_filters(void);
+
+struct bloom_filter *get_bloom_filter(struct repository *r,
+				      struct commit *c);
+
 #endif
\ No newline at end of file

index 20460cde775..f18d1b722e1 100644
@@ -1,6 +1,7 @@
 #include "git-compat-util.h"
 #include "bloom.h"
 #include "test-tool.h"
+#include "commit.h"
 
 struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
 

@@ -32,6 +33,16 @@ static void print_bloom_filter(struct bloom_filter *filter) {
 	printf("\n");
 }
 
+static void get_bloom_filter_for_commit(const struct object_id *commit_oid)
+{
+	struct commit *c;
+	struct bloom_filter *filter;
+	setup_git_directory();
+	c = lookup_commit(the_repository, commit_oid);
+	filter = get_bloom_filter(the_repository, c);
+	print_bloom_filter(filter);
+}
+
 int cmd__bloom(int argc, const char **argv)
 {
 	if (!strcmp(argv[1], "get_murmur3")) {

@@ -57,5 +68,14 @@ int cmd__bloom(int argc, const char **argv)
 		print_bloom_filter(&filter);
 	}
 
+    if (!strcmp(argv[1], "get_filter_for_commit")) {
+		struct object_id oid;
+		const char *end;
+		if (parse_oid_hex(argv[2], &oid, &end))
+			die("cannot parse oid '%s'", argv[2]);
+		init_bloom_filters();
+		get_bloom_filter_for_commit(&oid);
+	}
+
 	return 0;
 }
\ No newline at end of file

gitgitgadget

From: Derrick Stolee <[email protected]>

When computing the changed-paths bloom filters for the commit-graph, we limit the size of the filter by restricting the number of paths in the diff. Instead of computing a large diff and then ignoring the result, it is better to halt the diff computation early.

Create a new "max_changes" option in struct diff_options. If non-zero, then halt the diff computation after discovering strictly more changed paths. This includes paths corresponding to trees that change.

Use this max_changes option in the bloom filter calculations. This reduces the time taken to compute the filters for the Linux kernel repo from 2m50s to 2m35s. On a large internal repository with ~500 commits that perform tree-wide changes, the time reduced from 6m15s to 3m48s.

---
 bloom.c     | 4 +++-
 diff.h      | 5 +++++
 tree-diff.c | 6 ++++++
 3 files changed, 14 insertions(+), 1 deletion(-)

index 881a9841ede..a16eee92331 100644
@@ -133,6 +133,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 	struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
 	int i;
 	struct diff_options diffopt;
+	int max_changes = 512;
 
 	if (bloom_filters.slab_size == 0)
 		return NULL;

@@ -141,6 +142,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 
 	repo_diff_setup(r, &diffopt);
 	diffopt.flags.recursive = 1;
+	diffopt.max_changes = max_changes;
 	diff_setup_done(&diffopt);
 
 	if (c->parents)

@@ -149,7 +151,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 		diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
 	diffcore_std(&diffopt);
 
-	if (diff_queued_diff.nr <= 512) {
+	if (diff_queued_diff.nr <= max_changes) {
 		struct hashmap pathmap;
 		struct pathmap_hash_entry *e;
 		struct hashmap_iter iter;

index 6febe7e3656..9443dc1b003 100644
@@ -285,6 +285,11 @@ struct diff_options {
 	/* Number of hexdigits to abbreviate raw format output to. */
 	int abbrev;
 
+	/* If non-zero, then stop computing after this many changes. */
+	int max_changes;
+	/* For internal use only. */
+	int num_changes;
+
 	int ita_invisible_in_index;
 /* white-space error highlighting */
 #define WSEH_NEW (1<<12)

index 33ded7f8b3e..f3d303c6e54 100644
@@ -434,6 +434,9 @@ static struct combine_diff_path *ll_diff_tree_paths(
 		if (diff_can_quit_early(opt))
 			break;
 
+		if (opt->max_changes && opt->num_changes > opt->max_changes)
+			break;
+
 		if (opt->pathspec.nr) {
 			skip_uninteresting(&t, base, opt);
 			for (i = 0; i < nparent; i++)

@@ -518,6 +521,7 @@ static struct combine_diff_path *ll_diff_tree_paths(
 
 			/* t↓ */
 			update_tree_entry(&t);
+			opt->num_changes++;
 		}
 
 		/* t > p[imin] */

@@ -535,6 +539,7 @@ static struct combine_diff_path *ll_diff_tree_paths(
 		skip_emit_tp:
 			/* ∀ pi=p[imin]  pi↓ */
 			update_tp_entries(tp, nparent);
+			opt->num_changes++;
 		}
 	}
 

@@ -552,6 +557,7 @@ struct combine_diff_path *diff_tree_paths(
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt)
 {
+	opt->num_changes = 0;
 	p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);
 
 	/*

gitgitgadget

From: Garima Singh <[email protected]>

Add new COMMIT_GRAPH_WRITE_CHANGED_PATHS flag that makes Git compute Bloom filters for the paths that changed between a commit and it's first parent, for each commit in the commit-graph. This computation is done on a commit-by-commit basis.

We will write these Bloom filters to the commit-graph file, to store this data on disk, in the next change in this series.

---
 commit-graph.c | 32 +++++++++++++++++++++++++++++++-
 commit-graph.h |  3 ++-
 2 files changed, 33 insertions(+), 2 deletions(-)

index e4f1a5b2f1a..862a00d67ed 100644
@@ -16,6 +16,7 @@
 #include "hashmap.h"
 #include "replace-object.h"
 #include "progress.h"
+#include "bloom.h"
 
 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */

@@ -789,9 +790,11 @@ struct write_commit_graph_context {
 	unsigned append:1,
 		 report_progress:1,
 		 split:1,
-		 check_oids:1;
+		 check_oids:1,
+		 changed_paths:1;
 
 	const struct split_commit_graph_opts *split_opts;
+	size_t total_bloom_filter_data_size;
 };
 
 static void write_graph_chunk_fanout(struct hashfile *f,

@@ -1134,6 +1137,28 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 	stop_progress(&ctx->progress);
 }
 
+static void compute_bloom_filters(struct write_commit_graph_context *ctx)
+{
+	int i;
+	struct progress *progress = NULL;
+
+	init_bloom_filters();
+
+	if (ctx->report_progress)
+		progress = start_delayed_progress(
+			_("Computing commit changed paths Bloom filters"),
+			ctx->commits.nr);
+
+	for (i = 0; i < ctx->commits.nr; i++) {
+		struct commit *c = ctx->commits.list[i];
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, c);
+		ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
+		display_progress(progress, i + 1);
+	}
+
+	stop_progress(&progress);
+}
+
 static int add_ref_to_list(const char *refname,
 			   const struct object_id *oid,
 			   int flags, void *cb_data)

@@ -1776,6 +1801,8 @@ int write_commit_graph(struct object_directory *odb,
 	ctx->split = flags & COMMIT_GRAPH_WRITE_SPLIT ? 1 : 0;
 	ctx->check_oids = flags & COMMIT_GRAPH_WRITE_CHECK_OIDS ? 1 : 0;
 	ctx->split_opts = split_opts;
+	ctx->changed_paths = flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS ? 1 : 0;
+	ctx->total_bloom_filter_data_size = 0;
 
 	if (ctx->split) {
 		struct commit_graph *g;

@@ -1870,6 +1897,9 @@ int write_commit_graph(struct object_directory *odb,
 
 	compute_generation_numbers(ctx);
 
+	if (ctx->changed_paths)
+		compute_bloom_filters(ctx);
+
 	res = write_commit_graph_file(ctx);
 
 	if (ctx->split)

index e87a6f63600..86be81219da 100644
@@ -79,7 +79,8 @@ enum commit_graph_write_flags {
 	COMMIT_GRAPH_WRITE_PROGRESS   = (1 << 1),
 	COMMIT_GRAPH_WRITE_SPLIT      = (1 << 2),
 	/* Make sure that each OID in the input is a valid commit OID. */
-	COMMIT_GRAPH_WRITE_CHECK_OIDS = (1 << 3)
+	COMMIT_GRAPH_WRITE_CHECK_OIDS = (1 << 3),
+	COMMIT_GRAPH_WRITE_BLOOM_FILTERS = (1 << 4),
 };
 
 struct split_commit_graph_opts {

gitgitgadget

From: Jeff King <[email protected]>

Looking at the diff of commit objects in pack order is much faster than in sha1 order, as it gives locality to the access of tree deltas (whereas sha1 order is effectively random). Unfortunately the commit-graph code sorts the commits (several times, sometimes as an oid and sometimes a pointer-to-commit), and we ultimately traverse in sha1 order.

Instead, let's remember the position at which we see each commit, and traverse in that order when looking at bloom filters. This drops my time for "git commit-graph write --changed-paths" in linux.git from ~4 minutes to ~1.5 minutes.

Probably the "--reachable" code path would want something similar.

Or alternatively, we could use a different data structure (either a hash, or maybe even just a bit in "struct commit") to keep track of which oids we've seen, etc instead of sorting. And then we could keep the original order.

---
 commit-graph.c | 38 +++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)

index 862a00d67ed..31b06f878ce 100644
@@ -17,6 +17,7 @@
 #include "replace-object.h"
 #include "progress.h"
 #include "bloom.h"
+#include "commit-slab.h"
 
 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */

@@ -46,9 +47,32 @@
 /* Remember to update object flag allocation in object.h */
 #define REACHABLE       (1u<<15)
 
-char *get_commit_graph_filename(struct object_directory *odb)
+/* Keep track of the order in which commits are added to our list. */
+define_commit_slab(commit_pos, int);
+static struct commit_pos commit_pos = COMMIT_SLAB_INIT(1, commit_pos);
+
+static void set_commit_pos(struct repository *r, const struct object_id *oid)
+{
+	static int32_t max_pos;
+	struct commit *commit = lookup_commit(r, oid);
+
+	if (!commit)
+		return; /* should never happen, but be lenient */
+
+	*commit_pos_at(&commit_pos, commit) = max_pos++;
+}
+
+static int commit_pos_cmp(const void *va, const void *vb)
 {
-	return xstrfmt("%s/info/commit-graph", odb->path);
+	const struct commit *a = *(const struct commit **)va;
+	const struct commit *b = *(const struct commit **)vb;
+	return commit_pos_at(&commit_pos, a) -
+	       commit_pos_at(&commit_pos, b);
+}
+
+char *get_commit_graph_filename(struct object_directory *obj_dir)
+{
+	return xstrfmt("%s/info/commit-graph", obj_dir->path);
 }
 
 static char *get_split_graph_filename(struct object_directory *odb,

@@ -1021,6 +1045,8 @@ static int add_packed_commits(const struct object_id *oid,
 	oidcpy(&(ctx->oids.list[ctx->oids.nr]), oid);
 	ctx->oids.nr++;
 
+	set_commit_pos(ctx->r, oid);
+
 	return 0;
 }
 

@@ -1141,6 +1167,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 {
 	int i;
 	struct progress *progress = NULL;
+	struct commit **sorted_commits;
 
 	init_bloom_filters();
 

@@ -1149,13 +1176,18 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 			_("Computing commit changed paths Bloom filters"),
 			ctx->commits.nr);
 
+	ALLOC_ARRAY(sorted_commits, ctx->commits.nr);
+	COPY_ARRAY(sorted_commits, ctx->commits.list, ctx->commits.nr);
+	QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
+
 	for (i = 0; i < ctx->commits.nr; i++) {
-		struct commit *c = ctx->commits.list[i];
+		struct commit *c = sorted_commits[i];
 		struct bloom_filter *filter = get_bloom_filter(ctx->r, c);
 		ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
 		display_progress(progress, i + 1);
 	}
 
+	free(sorted_commits);
 	stop_progress(&progress);
 }
 

gitgitgadget

From: Garima Singh <[email protected]>

When running 'git commit-graph write --changed-paths', we sort the commits by pack-order to save time when computing the changed-paths bloom filters. This does not help when finding the commits via the '--reachable' flag.

If not using pack-order, then sort by generation number before examining the diff. Commits with similar generation are more likely to have many trees in common, making the diff faster.

On the Linux kernel repository, this change reduced the computation time for 'git commit-graph write --reachable --changed-paths' from 3m00s to 1m37s.

---
 commit-graph.c | 33 ++++++++++++++++++++++++++++++---
 1 file changed, 30 insertions(+), 3 deletions(-)

index 31b06f878ce..732c81fa1b2 100644
@@ -70,6 +70,25 @@ static int commit_pos_cmp(const void *va, const void *vb)
 	       commit_pos_at(&commit_pos, b);
 }
 
+static int commit_gen_cmp(const void *va, const void *vb)
+{
+	const struct commit *a = *(const struct commit **)va;
+	const struct commit *b = *(const struct commit **)vb;
+
+	/* lower generation commits first */
+	if (a->generation < b->generation)
+		return -1;
+	else if (a->generation > b->generation)
+		return 1;
+
+	/* use date as a heuristic when generations are equal */
+	if (a->date < b->date)
+		return -1;
+	else if (a->date > b->date)
+		return 1;
+	return 0;
+}
+
 char *get_commit_graph_filename(struct object_directory *obj_dir)
 {
 	return xstrfmt("%s/info/commit-graph", obj_dir->path);

@@ -815,7 +834,8 @@ struct write_commit_graph_context {
 		 report_progress:1,
 		 split:1,
 		 check_oids:1,
-		 changed_paths:1;
+		 changed_paths:1,
+		 order_by_pack:1;
 
 	const struct split_commit_graph_opts *split_opts;
 	size_t total_bloom_filter_data_size;

@@ -1178,7 +1198,11 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 
 	ALLOC_ARRAY(sorted_commits, ctx->commits.nr);
 	COPY_ARRAY(sorted_commits, ctx->commits.list, ctx->commits.nr);
-	QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
+
+	if (ctx->order_by_pack)
+		QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
+	else
+		QSORT(sorted_commits, ctx->commits.nr, commit_gen_cmp);
 
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = sorted_commits[i];

@@ -1884,6 +1908,7 @@ int write_commit_graph(struct object_directory *odb,
 	}
 
 	if (pack_indexes) {
+		ctx->order_by_pack = 1;
 		if ((res = fill_oids_from_packs(ctx, pack_indexes)))
 			goto cleanup;
 	}

@@ -1893,8 +1918,10 @@ int write_commit_graph(struct object_directory *odb,
 			goto cleanup;
 	}
 
-	if (!pack_indexes && !commit_hex)
+	if (!pack_indexes && !commit_hex) {
+		ctx->order_by_pack = 1;
 		fill_oids_from_all_packs(ctx);
+	}
 
 	close_reachable(ctx);
 

gitgitgadget

From: Garima Singh <[email protected]>

When computing changed-path Bloom filters or performing a name-only diff, we do not need the blob contents before completing the diff values. Thus, we do not need to download a pack containing the blobs we do not have on-disk before completing our diff calculation.

This prevents downloading every blob in a partial clone when computing changed path Bloom filters. It also prevents over-aggressive downloads during "git log --raw" commands.

---
 bloom.c | 1 +
 diff.c  | 8 +++++++-
 diff.h  | 1 +
 3 files changed, 9 insertions(+), 1 deletion(-)

index a16eee92331..dbcf594baec 100644
@@ -142,6 +142,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 
 	repo_diff_setup(r, &diffopt);
 	diffopt.flags.recursive = 1;
+	diffopt.detect_rename = 0;
 	diffopt.max_changes = max_changes;
 	diff_setup_done(&diffopt);
 

index 1010d806f50..63376adb011 100644
@@ -4633,6 +4633,10 @@ void diff_setup_done(struct diff_options *options)
 	if (!options->use_color || external_diff())
 		options->color_moved = 0;
 
+	if (!(options->output_format & ~(DIFF_FORMAT_NAME | DIFF_FORMAT_RAW)) &&
+	    !options->detect_rename)
+			options->skip_batch_download_objects = 1;
+
 	FREE_AND_NULL(options->parseopts);
 }
 

@@ -6507,7 +6511,9 @@ static void add_if_missing(struct repository *r,
 
 void diffcore_std(struct diff_options *options)
 {
-	if (options->repo == the_repository && has_promisor_remote()) {
+	if (!options->skip_batch_download_objects &&
+	    options->repo == the_repository &&
+		has_promisor_remote()) {
 		/*
 		 * Prefetch the diff pairs that are about to be flushed.
 		 */

index 9443dc1b003..e9f104309c4 100644
@@ -281,6 +281,7 @@ struct diff_options {
 	int show_rename_progress;
 	int dirstat_permille;
 	int setup;
+	int skip_batch_download_objects;
 
 	/* Number of hexdigits to abbreviate raw format output to. */
 	int abbrev;

gitgitgadget

From: Garima Singh <[email protected]>

Update the technical documentation for commit-graph-format with the formats for the Bloom filter index (BIDX) and Bloom filter data (BDAT) chunks. Write the computed Bloom filters information to the commit graph file using this format.

---
 .../technical/commit-graph-format.txt         |  30 +++++
 commit-graph.c                                | 113 +++++++++++++++++-
 commit-graph.h                                |   5 +
 3 files changed, 147 insertions(+), 1 deletion(-)

index a4f17441aed..de56f9f1efd 100644
@@ -17,6 +17,9 @@ metadata, including:
 - The parents of the commit, stored using positional references within
   the graph file.
 
+- The Bloom filter of the commit carrying the paths that were changed between
+  the commit and its first parent, if requested.
+
 These positional references are stored as unsigned 32-bit integers
 corresponding to the array position within the list of commit OIDs. Due
 to some special constants we use to track parents, we can store at most

@@ -93,6 +96,33 @@ CHUNK DATA:
       positions for the parents until reaching a value with the most-significant
       bit on. The other bits correspond to the position of the last parent.
 
+  Bloom Filter Index (ID: {'B', 'I', 'D', 'X'}) (N * 4 bytes) [Optional]
+    * The ith entry, BIDX[i], stores the number of 8-byte word blocks in all
+      Bloom filters from commit 0 to commit i (inclusive) in lexicographic
+      order. The Bloom filter for the i-th commit spans from BIDX[i-1] to
+      BIDX[i] (plus header length), where BIDX[-1] is 0.
+    * The BIDX chunk is ignored if the BDAT chunk is not present.
+
+  Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
+    * It starts with header consisting of three unsigned 32-bit integers:
+      - Version of the hash algorithm being used. We currently only support
+	value 1 which corresponds to the 32-bit version of the murmur3 hash
+	implemented exactly as described in
+	https://en.wikipedia.org/wiki/MurmurHash#Algorithm and the double
+	hashing technique using seed values 0x293ae76f and 0x7e646e2 as
+	described in https://doi.org/10.1007/978-3-540-30494-4_26 "Bloom Filters
+	in Probabilistic Verification"
+      - The number of times a path is hashed and hence the number of bit positions
+	      that cumulatively determine whether a file is present in the commit.
+      - The minimum number of bits 'b' per entry in the Bloom filter. If the filter
+	      contains 'n' entries, then the filter size is the minimum number of 64-bit
+	      words that contain n*b bits.
+    * The rest of the chunk is the concatenation of all the computed Bloom
+      filters for the commits in lexicographic order.
+    * Note: Commits with no changes or more than 512 changes have Bloom filters
+      of length zero.
+    * The BDAT chunk is present if and only if BIDX is present.
+
   Base Graphs List (ID: {'B', 'A', 'S', 'E'}) [Optional]
       This list of H-byte hashes describe a set of B commit-graph files that
       form a commit-graph chain. The graph position for the ith commit in this

index 86be81219da..8e7a8e0e5b2 100644
@@ -11,6 +11,7 @@
 #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD"
 
 struct commit;
+struct bloom_filter_settings;
 
 char *get_commit_graph_filename(struct object_directory *odb);
 int open_commit_graph(const char *graph_file, int *fd, struct stat *st);

@@ -59,6 +60,10 @@ struct commit_graph {
 	const unsigned char *chunk_commit_data;
 	const unsigned char *chunk_extra_edges;
 	const unsigned char *chunk_base_graphs;
+	const unsigned char *chunk_bloom_indexes;
+	const unsigned char *chunk_bloom_data;
+
+	struct bloom_filter_settings *bloom_filter_settings;
 };
 
 struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st,

gitgitgadget

From: Garima Singh <[email protected]>

Add logic to
a) parse Bloom filter information from the commit graph file and,
b) re-use existing Bloom filters.

See Documentation/technical/commit-graph-format for the format in which the Bloom filter information is written to the commit graph file.

To read Bloom filter for a given commit with lexicographic position 'i' we need to:
1. Read BIDX[i] which essentially gives us the starting index in BDAT for filter of commit i+1. It is essentially the index past the end of the filter of commit i. It is called end_index in the code.

2. For i>0, read BIDX[i-1] which will give us the starting index in BDAT for filter of commit i. It is called the start_index in the code. For the first commit, where i = 0, Bloom filter data starts at the beginning, just past the header in the BDAT chunk. Hence, start_index will be 0.

3. The length of the filter will be end_index - start_index, because BIDX[i] gives the cumulative 8-byte words including the ith commit's filter.

We toggle whether Bloom filters should be recomputed based on the compute_if_not_present flag.

---
 bloom.c               | 49 ++++++++++++++++++++++++++++++++++++++++++-
 bloom.h               |  4 +++-
 commit-graph.c        |  6 +++---
 t/helper/test-bloom.c |  2 +-
 4 files changed, 55 insertions(+), 6 deletions(-)

index dbcf594baec..151d598ce7b 100644
@@ -4,6 +4,8 @@
 #include "diffcore.h"
 #include "revision.h"
 #include "hashmap.h"
+#include "commit-graph.h"
+#include "commit.h"
 
 define_commit_slab(bloom_filter_slab, struct bloom_filter);
 

@@ -26,6 +28,36 @@ static inline unsigned char get_bitmask(uint32_t pos)
 	return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
 }
 
+static int load_bloom_filter_from_graph(struct commit_graph *g,
+				   struct bloom_filter *filter,
+				   struct commit *c)
+{
+	uint32_t lex_pos, start_index, end_index;
+
+	while (c->graph_pos < g->num_commits_in_base)
+		g = g->base_graph;
+
+	/* The commit graph commit 'c' lives in doesn't carry bloom filters. */
+	if (!g->chunk_bloom_indexes)
+		return 0;
+
+	lex_pos = c->graph_pos - g->num_commits_in_base;
+
+	end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
+
+	if (lex_pos > 0)
+		start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1));
+	else
+		start_index = 0;
+
+	filter->len = end_index - start_index;
+	filter->data = (unsigned char *)(g->chunk_bloom_data +
+					sizeof(unsigned char) * start_index +
+					BLOOMDATA_CHUNK_HEADER_SIZE);
+
+	return 1;
+}
+
 /*
  * Calculate the murmur3 32-bit hash value for the given data
  * using the given seed.

@@ -127,7 +159,8 @@ void init_bloom_filters(void)
 }
 
 struct bloom_filter *get_bloom_filter(struct repository *r,
-				      struct commit *c)
+				      struct commit *c,
+					  int compute_if_not_present)
 {
 	struct bloom_filter *filter;
 	struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;

@@ -140,6 +173,20 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 
 	filter = bloom_filter_slab_at(&bloom_filters, c);
 
+	if (!filter->data) {
+		load_commit_graph_info(r, c);
+		if (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&
+			r->objects->commit_graph->chunk_bloom_indexes) {
+			if (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))
+				return filter;
+			else
+				return NULL;
+		}
+	}
+
+	if (filter->data || !compute_if_not_present)
+		return filter;
+
 	repo_diff_setup(r, &diffopt);
 	diffopt.flags.recursive = 1;
 	diffopt.detect_rename = 0;

index 85ab8e9423d..760d7122374 100644
@@ -32,6 +32,7 @@ struct bloom_filter_settings {
 
 #define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10 }
 #define BITS_PER_WORD 8
+#define BLOOMDATA_CHUNK_HEADER_SIZE 3 * sizeof(uint32_t)
 
 /*
  * A bloom_filter struct represents a data segment to

@@ -79,6 +80,7 @@ void add_key_to_filter(const struct bloom_key *key,
 void init_bloom_filters(void);
 
 struct bloom_filter *get_bloom_filter(struct repository *r,
-				      struct commit *c);
+				      struct commit *c,
+				      int compute_if_not_present);
 
 #endif
\ No newline at end of file

index a8b6b5cca5d..77668629e27 100644
@@ -1086,7 +1086,7 @@ static void write_graph_chunk_bloom_indexes(struct hashfile *f,
 			ctx->commits.nr);
 
 	while (list < last) {
-		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
 		cur_pos += filter->len;
 		display_progress(progress, ++i);
 		hashwrite_be32(f, cur_pos);

@@ -1115,7 +1115,7 @@ static void write_graph_chunk_bloom_data(struct hashfile *f,
 	hashwrite_be32(f, settings->bits_per_entry);
 
 	while (list < last) {
-		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
 		display_progress(progress, ++i);
 		hashwrite(f, filter->data, filter->len * sizeof(unsigned char));
 		list++;

@@ -1296,7 +1296,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = sorted_commits[i];
-		struct bloom_filter *filter = get_bloom_filter(ctx->r, c);
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1);
 		ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
 		display_progress(progress, i + 1);
 	}

index f18d1b722e1..ce412664ba9 100644
@@ -39,7 +39,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid)
 	struct bloom_filter *filter;
 	setup_git_directory();
 	c = lookup_commit(the_repository, commit_oid);
-	filter = get_bloom_filter(the_repository, c);
+	filter = get_bloom_filter(the_repository, c, 1);
 	print_bloom_filter(filter);
 }
 

gitgitgadget

From: Garima Singh <[email protected]>

Add --changed-paths option to git commit-graph write. This option will allow users to compute information about the paths that have changed between a commit and its first parent, and write it into the commit graph file. If the option is passed to the write subcommand we set the COMMIT_GRAPH_WRITE_BLOOM_FILTERS flag and pass it down to the commit-graph logic.

---
 Documentation/git-commit-graph.txt | 5 +++++
 builtin/commit-graph.c             | 9 +++++++--
 2 files changed, 12 insertions(+), 2 deletions(-)

index 28d1fee5053..f4b13c005b8 100644
@@ -57,6 +57,11 @@ or `--stdin-packs`.)
 With the `--append` option, include all commits that are present in the
 existing commit-graph file.
 +
+With the `--changed-paths` option, compute and write information about the
+paths changed between a commit and it's first parent. This operation can
+take a while on large repositories. It provides significant performance gains
+for getting history of a directory or a file with `git log -- <path>`.
++
 With the `--split` option, write the commit-graph as a chain of multiple
 commit-graph files stored in `<dir>/info/commit-graphs`. The new commits
 not already in the commit-graph are added in a new "tip" file. This file

index d1ab6625f63..cacb5d04a80 100644
@@ -9,7 +9,7 @@
 
 static char const * const builtin_commit_graph_usage[] = {
 	N_("git commit-graph verify [--object-dir <objdir>] [--shallow] [--[no-]progress]"),
-	N_("git commit-graph write [--object-dir <objdir>] [--append|--split] [--reachable|--stdin-packs|--stdin-commits] [--[no-]progress] <split options>"),
+	N_("git commit-graph write [--object-dir <objdir>] [--append|--split] [--reachable|--stdin-packs|--stdin-commits] [--changed-paths] [--[no-]progress] <split options>"),
 	NULL
 };
 

@@ -19,7 +19,7 @@ static const char * const builtin_commit_graph_verify_usage[] = {
 };
 
 static const char * const builtin_commit_graph_write_usage[] = {
-	N_("git commit-graph write [--object-dir <objdir>] [--append|--split] [--reachable|--stdin-packs|--stdin-commits] [--[no-]progress] <split options>"),
+	N_("git commit-graph write [--object-dir <objdir>] [--append|--split] [--reachable|--stdin-packs|--stdin-commits] [--changed-paths] [--[no-]progress] <split options>"),
 	NULL
 };
 

@@ -32,6 +32,7 @@ static struct opts_commit_graph {
 	int split;
 	int shallow;
 	int progress;
+	int enable_changed_paths;
 } opts;
 
 static struct object_directory *find_odb(struct repository *r,

@@ -135,6 +136,8 @@ static int graph_write(int argc, const char **argv)
 			N_("start walk at commits listed by stdin")),
 		OPT_BOOL(0, "append", &opts.append,
 			N_("include all commits already in the commit-graph file")),
+		OPT_BOOL(0, "changed-paths", &opts.enable_changed_paths,
+			N_("enable computation for changed paths")),
 		OPT_BOOL(0, "progress", &opts.progress, N_("force progress reporting")),
 		OPT_BOOL(0, "split", &opts.split,
 			N_("allow writing an incremental commit-graph file")),

@@ -168,6 +171,8 @@ static int graph_write(int argc, const char **argv)
 		flags |= COMMIT_GRAPH_WRITE_SPLIT;
 	if (opts.progress)
 		flags |= COMMIT_GRAPH_WRITE_PROGRESS;
+	if (opts.enable_changed_paths)
+		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;
 
 	read_replace_refs = 0;
 	odb = find_odb(the_repository, opts.obj_dir);

gitgitgadget

From: Garima Singh <[email protected]>

Revision walk will now use Bloom filters for commits to speed up revision walks for a particular path (for computing history for that path), if they are present in the commit-graph file.

We load the Bloom filters during the prepare_revision_walk step, currently only when dealing with a single pathspec. Extending it to work with multiple pathspecs can be explored and built on top of this series in the future.

While comparing trees in rev_compare_trees(), if the Bloom filter says that the file is not different between the two trees, we don't need to compute the expensive diff. This is where we get our performance gains. The other response of the Bloom filter is '`:maybe', in which case we fall back to the full diff calculation to determine if the path was changed in the commit.

We do not try to use Bloom filters when the '--walk-reflogs' option is specified. The '--walk-reflogs' option does not walk the commit ancestry chain like the rest of the options. Incorporating the performance gains when walking reflog entries would add more complexity, and can be explored in a later series.

Performance Gains:
We tested the performance of git log -- <path> on the git repo, the linux and some internal large repos, with a variety of paths of varying depths.

On the git and linux repos:
- we observed a 2x to 5x speed up.

On a large internal repo with files seated 6-10 levels deep in the tree:
- we observed 10x to 20x speed ups, with some paths going up to 28 times faster.

---
 bloom.c    | 20 +++++++++++++
 bloom.h    |  4 +++
 revision.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
 revision.h | 11 +++++++
 4 files changed, 118 insertions(+), 2 deletions(-)

index 151d598ce7b..dd9bab9bbd6 100644
@@ -254,3 +254,23 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 
 	return filter;
 }
+
+int bloom_filter_contains(const struct bloom_filter *filter,
+			  const struct bloom_key *key,
+			  const struct bloom_filter_settings *settings)
+{
+	int i;
+	uint64_t mod = filter->len * BITS_PER_WORD;
+
+	if (!mod)
+		return -1;
+
+	for (i = 0; i < settings->num_hashes; i++) {
+		uint64_t hash_mod = key->hashes[i] % mod;
+		uint64_t block_pos = hash_mod / BITS_PER_WORD;
+		if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
+			return 0;
+	}
+
+	return 1;
+}
\ No newline at end of file

index 760d7122374..b935186425d 100644
@@ -83,4 +83,8 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 				      struct commit *c,
 				      int compute_if_not_present);
 
+int bloom_filter_contains(const struct bloom_filter *filter,
+			  const struct bloom_key *key,
+			  const struct bloom_filter_settings *settings);
+
 #endif
\ No newline at end of file

index 475f048fb61..7c026fe41fc 100644
@@ -56,6 +56,8 @@ struct repository;
 struct rev_info;
 struct string_list;
 struct saved_parents;
+struct bloom_key;
+struct bloom_filter_settings;
 define_shared_commit_slab(revision_sources, char *);
 
 struct rev_cmdline_info {

@@ -291,6 +293,15 @@ struct rev_info {
 	struct revision_sources *sources;
 
 	struct topo_walk_info *topo_walk_info;
+
+	/* Commit graph bloom filter fields */
+	/* The bloom filter key for the pathspec */
+	struct bloom_key *bloom_key;
+	/*
+	 * The bloom filter settings used to generate the key.
+	 * This is loaded from the commit-graph being used.
+	 */
+	struct bloom_filter_settings *bloom_filter_settings;
 };
 
 int ref_excluded(struct string_list *, const char *path);

gitgitgadget

From: Garima Singh <[email protected]>

Add trace2 statistics around Bloom filter usage and behavior for 'git log -- path' commands that are hoping to benefit from the presence of computed changed paths Bloom filters.

These statistics are great for performance analysis work and for formal testing, which we will see in the commit following this one.

---
 revision.c | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

index d3fcb7c6ff6..2b06ee739c8 100644
@@ -30,6 +30,7 @@
 #include "hashmap.h"
 #include "utf8.h"
 #include "bloom.h"
+#include "json-writer.h"
 
 volatile show_early_output_fn_t show_early_output;
 

@@ -625,6 +626,30 @@ static void file_change(struct diff_options *options,
 	options->flags.has_changes = 1;
 }
 
+static int bloom_filter_atexit_registered;
+static unsigned int count_bloom_filter_maybe;
+static unsigned int count_bloom_filter_definitely_not;
+static unsigned int count_bloom_filter_false_positive;
+static unsigned int count_bloom_filter_not_present;
+static unsigned int count_bloom_filter_length_zero;
+
+static void trace2_bloom_filter_statistics_atexit(void)
+{
+	struct json_writer jw = JSON_WRITER_INIT;
+
+	jw_object_begin(&jw, 0);
+	jw_object_intmax(&jw, "filter_not_present", count_bloom_filter_not_present);
+	jw_object_intmax(&jw, "zero_length_filter", count_bloom_filter_length_zero);
+	jw_object_intmax(&jw, "maybe", count_bloom_filter_maybe);
+	jw_object_intmax(&jw, "definitely_not", count_bloom_filter_definitely_not);
+	jw_object_intmax(&jw, "false_positive", count_bloom_filter_false_positive);
+	jw_end(&jw);
+
+	trace2_data_json("bloom", the_repository, "statistics", &jw);
+
+	jw_release(&jw);
+}
+
 static void prepare_to_use_bloom_filter(struct rev_info *revs)
 {
 	struct pathspec_item *pi;

@@ -661,6 +686,11 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)
 	revs->bloom_key = xmalloc(sizeof(struct bloom_key));
 	fill_bloom_key(path, len, revs->bloom_key, revs->bloom_filter_settings);
 
+	if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
+		atexit(trace2_bloom_filter_statistics_atexit);
+		bloom_filter_atexit_registered = 1;
+	}
+
 	free(path_alloc);
 }
 

@@ -679,10 +709,12 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 	filter = get_bloom_filter(revs->repo, commit, 0);
 
 	if (!filter) {
+		count_bloom_filter_not_present++;
 		return -1;
 	}
 
 	if (!filter->len) {
+		count_bloom_filter_length_zero++;
 		return -1;
 	}
 

@@ -690,6 +722,11 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 				       revs->bloom_key,
 				       revs->bloom_filter_settings);
 
+	if (result)
+		count_bloom_filter_maybe++;
+	else
+		count_bloom_filter_definitely_not++;
+
 	return result;
 }
 

@@ -736,6 +773,10 @@ static int rev_compare_tree(struct rev_info *revs,
 			   &revs->pruning) < 0)
 		return REV_TREE_DIFFERENT;
 
+	if (!nth_parent)
+		if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
+			count_bloom_filter_false_positive++;
+
 	return tree_difference;
 }
 

gitgitgadget

From: Garima Singh <[email protected]>

These tests exercises writing commit graph with Bloom filters and exercises 'git log -- path' with all the applicable options. They check that the output is the same with and without Bloom filters, confirm Bloom filters were used by checking if trace2 statistics were logged correctly.

Also confirms cases where Bloom filters are not used:
1. Multiple path specs,
2. --walk-reflogs (see patch titled 'revision.c: use Bloom filters...' for details,
3. If the latest commit graph does not have Bloom filters

---
 t/helper/test-read-graph.c |   4 +
 t/t4216-log-bloom.sh       | 155 +++++++++++++++++++++++++++++++++++++
 2 files changed, 159 insertions(+)
 create mode 100755 t/t4216-log-bloom.sh

index f8a461767ca..4223ff32fb6 100644
@@ -45,6 +45,10 @@ int cmd__read_graph(int argc, const char **argv)
 		printf(" commit_metadata");
 	if (graph->chunk_extra_edges)
 		printf(" extra_edges");
+	if (graph->chunk_bloom_indexes)
+		printf(" bloom_indexes");
+	if (graph->chunk_bloom_data)
+		printf(" bloom_data");
 	printf("\n");
 
 	UNLEAK(graph);

gitgitgadget

From: Garima Singh <[email protected]>

Add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag to the test setup suite in order to toggle writing Bloom filters when running any of the git tests. If set to true, we will compute and write Bloom filters every time a test calls git commit-graph write, as if the --changed-paths option was passed in.

The test suite passes when GIT_TEST_COMMIT_GRAPH and GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS are enabled.

---
 builtin/commit-graph.c        | 3 ++-
 ci/run-build-and-tests.sh     | 1 +
 commit-graph.h                | 1 +
 t/README                      | 5 +++++
 t/t5318-commit-graph.sh       | 2 ++
 t/t5324-split-commit-graph.sh | 1 +
 6 files changed, 12 insertions(+), 1 deletion(-)

index cacb5d04a80..59009837dc9 100644
@@ -171,7 +171,8 @@ static int graph_write(int argc, const char **argv)
 		flags |= COMMIT_GRAPH_WRITE_SPLIT;
 	if (opts.progress)
 		flags |= COMMIT_GRAPH_WRITE_PROGRESS;
-	if (opts.enable_changed_paths)
+	if (opts.enable_changed_paths ||
+	    git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))
 		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;
 
 	read_replace_refs = 0;

index 4df54c4efea..17e25aade96 100755
@@ -19,6 +19,7 @@ linux-gcc)
 	export GIT_TEST_OE_SIZE=10
 	export GIT_TEST_OE_DELTA_SIZE=5
 	export GIT_TEST_COMMIT_GRAPH=1
+	export GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1
 	export GIT_TEST_MULTI_PACK_INDEX=1
 	export GIT_TEST_ADD_I_USE_BUILTIN=1
 	make test

index 8e7a8e0e5b2..8655d064c14 100644
@@ -9,6 +9,7 @@
 
 #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH"
 #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD"
+#define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS "GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS"
 
 struct commit;
 struct bloom_filter_settings;

index 369e3a9ded8..4f53da53a15 100644
@@ -378,6 +378,11 @@ GIT_TEST_COMMIT_GRAPH=<boolean>, when true, forces the commit-graph to
 be written after every 'git commit' command, and overrides the
 'core.commitGraph' setting to true.
 
+GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=<boolean>, when true, forces
+commit-graph write to compute and write changed path Bloom filters for
+every 'git commit-graph write', as if the `--changed-paths` option was
+passed in.
+
 GIT_TEST_FSMONITOR=$PWD/t7519/fsmonitor-all exercises the fsmonitor
 code path for utilizing a file system monitor to speed up detecting
 new or changed files.

index 9bf920ae171..18304a65e4d 100755
@@ -3,6 +3,8 @@
 test_description='commit graph'
 . ./test-lib.sh
 
+GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0
+
 test_expect_success 'setup full repo' '
 	mkdir full &&
 	cd "$TRASH_DIRECTORY/full" &&

index 53b2e6b4555..d3f1f2c4a71 100755
@@ -4,6 +4,7 @@ test_description='split commit graph'
 . ./test-lib.sh
 
 GIT_TEST_COMMIT_GRAPH=0
+GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0
 
 test_expect_success 'setup repo' '
 	git init &&

gitgitgadget

Hey!

The commit graph feature brought in a lot of performance improvements across multiple commands. However, file based history continues to be a performance pain point, especially in large repositories.

Adopting changed path Bloom filters has been discussed on the list before, and a prototype version was worked on by SZEDER Gábor, Jonathan Tan and Dr. Derrick Stolee [1]. This series is based on Dr. Stolee's proof of concept in
[2]

With the changes in this series, git users will be able to choose to write Bloom filters to the commit-graph using the following command:

'git commit-graph write --changed-paths'

Subsequent 'git log -- path' commands will use these computed Bloom filters to decided which commits are worth exploring further to produce the history of the provided path.

Cost of computing and writing Bloom filters
===========================================

Computing and writing Bloom filters to the commit graph for the first time implies computing the diffs and the resulting Bloom filters for all the commits in the repository. This adds a non trivial amount of time to run time. Every subsequent run is incremental i.e. we reuse the previously computed Bloom filters. So this is a one time cost.

Time taken by 'git commit-graph write' with and w/o --changed-paths, speed up in 'git log -- path' with computed Bloom filters (see a):-

-------------------------------------------------------------------------
| Repo | w/o --changed-paths | with --changed-paths | Speed up |
-------------------------------------------------------------------------

| git [3]     | 0.9 seconds         | 7 seconds            | 2x to 6x   |
| linux [4]   | 16 seconds          | 1 minute 8 seconds   | 2x to 6x   | 
| android [5] | 9 seconds           | 48 seconds           | 2x to 6x   |
| AzDo(see b) | 1 minute            | 5 minutes 2 seconds  | 10x to 30x |

-------------------------------------------------------------------------

a) We tested the performance of git log -- path with randomly chosen paths of varying depths in each repo. The speed up depends on how deep the files are in the hierarchy and how often a file has been touched in the commit history.

b) This internal repository has about 420k commits, 183k files distributed across 34k folders, the size on disk is about 17 GiB. The most massive gains on this repository were for files 6-12 levels deep in the tree.

c) These numbers were collected on a Windows machine, except for the linux repo which was tested on a Linux machine.

Future Work (not included in the scope of this series)
======================================================

1. Supporting multiple path based revision walk
2. Adopting it in git blame logic.
3. Interactions with line log git log -L

Cheers! Garima Singh

[1] https://lore.kernel.org/git/[email protected]/

[2]
https://lore.kernel.org/git/[email protected]/

[3] https://github.com/git/git

[4] https://github.com/torvalds/linux

[5] https://android.googlesource.com/platform/frameworks/base/

[email protected], [email protected], [email protected], [email protected],[email protected], [email protected], [email protected],[email protected]

Derrick Stolee (1):
diff: halt tree-diff early after max_changes

Garima Singh (13):
commit-graph: define and use MAX_NUM_CHUNKS
bloom.c: add the murmur3 hash implementation
bloom.c: introduce core Bloom filter constructs
bloom.c: core Bloom filter implementation for changed paths.
commit-graph: compute Bloom filters for changed paths
commit-graph: examine commits by generation number
commit-graph: write Bloom filters to commit graph file
commit-graph: reuse existing Bloom filters during write
commit-graph: add --changed-paths option to write subcommand revision.c: use Bloom filters to speed up path based revision walks revision.c: add trace2 stats around Bloom filter usage
t4216: add end to end tests for git log with Bloom filters
commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag

Jeff King (1):
commit-graph: examine changed-path objects in pack order

 Documentation/git-commit-graph.txt            |   5 +
 .../technical/commit-graph-format.txt         |  30 ++
 Makefile                                      |   2 +
 bloom.c                                       | 275 ++++++++++++++++++
 bloom.h                                       |  90 ++++++
 builtin/commit-graph.c                        |  10 +-
 ci/run-build-and-tests.sh                     |   1 +
 commit-graph.c                                | 213 +++++++++++++-
 commit-graph.h                                |   9 +-
 diff.h                                        |   5 +
 revision.c                                    | 126 +++++++-
 revision.h                                    |  11 +
 t/README                                      |   5 +
 t/helper/test-bloom.c                         |  81 ++++++
 t/helper/test-read-graph.c                    |   4 +
 t/helper/test-tool.c                          |   1 +
 t/helper/test-tool.h                          |   1 +
 t/t0095-bloom.sh                              | 117 ++++++++
 t/t4216-log-bloom.sh                          | 155 ++++++++++
 t/t5318-commit-graph.sh                       |   2 +
 t/t5324-split-commit-graph.sh                 |   1 +
 tree-diff.c                                   |   6 +
 22 files changed, 1139 insertions(+), 11 deletions(-)
 create mode 100644 bloom.c
 create mode 100644 bloom.h
 create mode 100644 t/helper/test-bloom.c
 create mode 100755 t/t0095-bloom.sh
 create mode 100755 t/t4216-log-bloom.sh

base-commit: 3bab5d56259722843359702bc27111475437ad2a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-497%2Fgarimasi514%2FcoreGit-bloomFilters-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-497/garimasi514/coreGit-bloomFilters-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/497

Range-diff vs v3:

  1:  c3ffd9820d5 =  1:  c3ffd9820d5 commit-graph: define and use MAX_NUM_CHUNKS
  2:  a5aa3415c05 =  2:  a5aa3415c05 bloom.c: add the murmur3 hash implementation
  3:  a7702c1afde =  3:  a7702c1afde bloom.c: introduce core Bloom filter constructs
  4:  8304c297520 =  4:  8304c297520 bloom.c: core Bloom filter implementation for changed paths.
  5:  2d4c0b2da38 =  5:  2d4c0b2da38 diff: halt tree-diff early after max_changes
  6:  c38b9b386ef =  6:  c38b9b386ef commit-graph: compute Bloom filters for changed paths
  7:  d24c85c54ef =  7:  d24c85c54ef commit-graph: examine changed-path objects in pack order
  8:  5ed16f35fed =  8:  5ed16f35fed commit-graph: examine commits by generation number
  9:  55824cda89c <  -:  ----------- diff: skip batch object download when possible
 10:  1e4663523de =  9:  ff6b96aad1e commit-graph: write Bloom filters to commit graph file
 11:  68395d4051b ! 10:  cc8022bdf82 commit-graph: reuse existing Bloom filters during write
     @@ bloom.c: struct bloom_filter *get_bloom_filter(struct repository *r,
      +
       	repo_diff_setup(r, &diffopt);
       	diffopt.flags.recursive = 1;
     - 	diffopt.detect_rename = 0;
     + 	diffopt.max_changes = max_changes;
      
       ## bloom.h ##
      @@ bloom.h: struct bloom_filter_settings {
 12:  7e450e45236 = 11:  c8b86c383ab commit-graph: add --changed-paths option to write subcommand
 13:  b18af58aa3e = 12:  617f549ef25 revision.c: use Bloom filters to speed up path based revision walks
 14:  b5eb280178f = 13:  6beaede7159 revision.c: add trace2 stats around Bloom filter usage
 15:  3019ef72881 = 14:  b899df5c98e t4216: add end to end tests for git log with Bloom filters
 16:  213abb5d895 = 15:  5656e8590e9 commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag

gitgitgadget

From: Garima Singh <[email protected]>

This is a minor cleanup to make it easier to change the number of chunks being written to the commit graph.

---
 commit-graph.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

index f013a84e294..e4f1a5b2f1a 100644
@@ -23,6 +23,7 @@
 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
 #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
+#define MAX_NUM_CHUNKS 5
 
 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
 

@@ -1350,8 +1351,8 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 	int fd;
 	struct hashfile *f;
 	struct lock_file lk = LOCK_INIT;
-	uint32_t chunk_ids[6];
-	uint64_t chunk_offsets[6];
+	uint32_t chunk_ids[MAX_NUM_CHUNKS + 1];
+	uint64_t chunk_offsets[MAX_NUM_CHUNKS + 1];
 	const unsigned hashsz = the_hash_algo->rawsz;
 	struct strbuf progress_title = STRBUF_INIT;
 	int num_chunks = 3;

gitgitgadget

From: Garima Singh <[email protected]>

In preparation for computing changed paths Bloom filters, implement the Murmur3 hash algorithm as described in [1]. It hashes the given data using the given seed and produces a uniformly distributed hash value.

[1] https://en.wikipedia.org/wiki/MurmurHash#Algorithm

---
 Makefile              |  2 ++
 bloom.c               | 73 +++++++++++++++++++++++++++++++++++++++++++
 bloom.h               | 13 ++++++++
 t/helper/test-bloom.c | 13 ++++++++
 t/helper/test-tool.c  |  1 +
 t/helper/test-tool.h  |  1 +
 t/t0095-bloom.sh      | 30 ++++++++++++++++++
 7 files changed, 133 insertions(+)
 create mode 100644 bloom.c
 create mode 100644 bloom.h
 create mode 100644 t/helper/test-bloom.c
 create mode 100755 t/t0095-bloom.sh

index ef1ff2228f0..491f75e68c5 100644
@@ -695,6 +695,7 @@ X =
 PROGRAMS += $(patsubst %.o,git-%$X,$(PROGRAM_OBJS))
 
 TEST_BUILTINS_OBJS += test-advise.o
+TEST_BUILTINS_OBJS += test-bloom.o
 TEST_BUILTINS_OBJS += test-chmtime.o
 TEST_BUILTINS_OBJS += test-config.o
 TEST_BUILTINS_OBJS += test-ctype.o

@@ -840,6 +841,7 @@ LIB_OBJS += base85.o
 LIB_OBJS += bisect.o
 LIB_OBJS += blame.o
 LIB_OBJS += blob.o
+LIB_OBJS += bloom.o
 LIB_OBJS += branch.o
 LIB_OBJS += bulk-checkin.o
 LIB_OBJS += bundle.o

new file mode 100644
index 00000000000..d0fcc5f0aa6
@@ -0,0 +1,13 @@
+#ifndef BLOOM_H
+#define BLOOM_H
+
+/*
+ * Calculate the murmur3 32-bit hash value for the given data
+ * using the given seed.
+ * Produces a uniformly distributed hash value.
+ * Not considered to be cryptographically secure.
+ * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
+ */
+uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len);
+
+#endif
\ No newline at end of file

new file mode 100644
index 00000000000..60ee2043689
@@ -0,0 +1,13 @@
+#include "git-compat-util.h"
+#include "bloom.h"
+#include "test-tool.h"
+
+int cmd__bloom(int argc, const char **argv)
+{
+	if (!strcmp(argv[1], "get_murmur3")) {
+		uint32_t hashed = murmur3_seeded(0, argv[2], strlen(argv[2]));
+		printf("Murmur3 Hash with seed=0:0x%08x\n", hashed);
+	}
+
+	return 0;
+}
\ No newline at end of file

index 31eedcd241f..6e26bd65c97 100644
@@ -15,6 +15,7 @@ struct test_cmd {
 
 static struct test_cmd cmds[] = {
 	{ "advise", cmd__advise_if_enabled },
+	{ "bloom", cmd__bloom },
 	{ "chmtime", cmd__chmtime },
 	{ "config", cmd__config },
 	{ "ctype", cmd__ctype },