[v4,04/15] bloom.c: core Bloom filter implementation for changed paths.

Commit Message

Johannes Schindelin via GitGitGadget April 6, 2020, 4:59 p.m. UTC

From: Garima Singh <[e-mail]>

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.

Helped-by: Jeff King <[e-mail]>
Helped-by: Derrick Stolee <[e-mail]>
Reviewed-by: Jakub Narębski <[e-mail]>
Signed-off-by: Garima Singh <[e-mail]>
---
 bloom.c               | 97 +++++++++++++++++++++++++++++++++++++++++++
 bloom.h               |  8 ++++
 t/helper/test-bloom.c | 20 +++++++++
 t/t0095-bloom.sh      | 47 +++++++++++++++++++++
 4 files changed, 172 insertions(+)

Comments

SZEDER Gábor June 27, 2020, 3:53 p.m. UTC | #1

On Mon, Apr 06, 2020 at 04:59:44PM +0000, Garima Singh via GitGitGadget wrote:
> From: Garima Singh <[e-mail]>
> 
> 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.
> 
> Helped-by: Jeff King <[e-mail]>
> Helped-by: Derrick Stolee <[e-mail]>
> Reviewed-by: Jakub Narębski <[e-mail]>
> Signed-off-by: Garima Singh <[e-mail]>
> ---
>  bloom.c               | 97 +++++++++++++++++++++++++++++++++++++++++++
>  bloom.h               |  8 ++++
>  t/helper/test-bloom.c | 20 +++++++++
>  t/t0095-bloom.sh      | 47 +++++++++++++++++++++
>  4 files changed, 172 insertions(+)
> 
> diff --git a/bloom.c b/bloom.c
> index 888b67f1ea6..881a9841ede 100644
> --- a/bloom.c
> +++ b/bloom.c
> @@ -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);

So here we define a commit slab for modified path Bloom filters, ...

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

... here initialize the slab ...

> +}
> +
> +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);

... allocate an entry in the slab ...

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

... and here we fill the slab with data, including a memory allocation
for each slab entry.

What is missing in this patch or in any of the followup patches is a
place where we clear the slab and the additional memory attached to
it.

> +
> +		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;
> +}
> diff --git a/bloom.h b/bloom.h
> index b9ce422ca2d..85ab8e9423d 100644
> --- a/bloom.h
> +++ b/bloom.h
> @@ -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
> diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c
> index 20460cde775..f18d1b722e1 100644
> --- a/t/helper/test-bloom.c
> +++ b/t/helper/test-bloom.c
> @@ -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
> diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh
> index 36a086c7c60..8f9eef116dc 100755
> --- a/t/t0095-bloom.sh
> +++ b/t/t0095-bloom.sh
> @@ -67,4 +67,51 @@ test_expect_success 'compute bloom key for test string 2' '
>  	test_cmp expect actual
>  '
>  
> +test_expect_success 'get bloom filters for commit with no changes' '
> +	git init &&
> +	git commit --allow-empty -m "c0" &&
> +	cat >expect <<-\EOF &&
> +	Filter_Length:0
> +	Filter_Data:
> +	EOF
> +	test-tool bloom get_filter_for_commit "$(git rev-parse HEAD)" >actual &&
> +	test_cmp expect actual
> +'
> +
> +test_expect_success 'get bloom filter for commit with 10 changes' '
> +	rm actual &&
> +	rm expect &&
> +	mkdir smallDir &&
> +	for i in $(test_seq 0 9)
> +	do
> +		echo $i >smallDir/$i
> +	done &&
> +	git add smallDir &&
> +	git commit -m "commit with 10 changes" &&
> +	cat >expect <<-\EOF &&
> +	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
> +'
> +
> +test_expect_success EXPENSIVE 'get bloom filter for commit with 513 changes' '
> +	rm actual &&
> +	rm expect &&
> +	mkdir bigDir &&
> +	for i in $(test_seq 0 512)
> +	do
> +		echo $i >bigDir/$i
> +	done &&
> +	git add bigDir &&
> +	git commit -m "commit with 513 changes" &&
> +	cat >expect <<-\EOF &&
> +	Filter_Length:0
> +	Filter_Data:
> +	EOF
> +	test-tool bloom get_filter_for_commit "$(git rev-parse HEAD)" >actual &&
> +	test_cmp expect actual
> +'
> +
>  test_done
> \ No newline at end of file
> -- 
> gitgitgadget
>

Patch

diff --git a/bloom.c b/bloom.c
index 888b67f1ea6..881a9841ede 100644
--- a/bloom.c
+++ b/bloom.c
@@ -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;
+}
diff --git a/bloom.h b/bloom.h
index b9ce422ca2d..85ab8e9423d 100644
--- a/bloom.h
+++ b/bloom.h
@@ -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
diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c
index 20460cde775..f18d1b722e1 100644
--- a/t/helper/test-bloom.c
+++ b/t/helper/test-bloom.c
@@ -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
diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh
index 36a086c7c60..8f9eef116dc 100755
--- a/t/t0095-bloom.sh
+++ b/t/t0095-bloom.sh
@@ -67,4 +67,51 @@  test_expect_success 'compute bloom key for test string 2' '
 	test_cmp expect actual
 '
 
+test_expect_success 'get bloom filters for commit with no changes' '
+	git init &&
+	git commit --allow-empty -m "c0" &&
+	cat >expect <<-\EOF &&
+	Filter_Length:0
+	Filter_Data:
+	EOF
+	test-tool bloom get_filter_for_commit "$(git rev-parse HEAD)" >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'get bloom filter for commit with 10 changes' '
+	rm actual &&
+	rm expect &&
+	mkdir smallDir &&
+	for i in $(test_seq 0 9)
+	do
+		echo $i >smallDir/$i
+	done &&
+	git add smallDir &&
+	git commit -m "commit with 10 changes" &&
+	cat >expect <<-\EOF &&
+	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
+'
+
+test_expect_success EXPENSIVE 'get bloom filter for commit with 513 changes' '
+	rm actual &&
+	rm expect &&
+	mkdir bigDir &&
+	for i in $(test_seq 0 512)
+	do
+		echo $i >bigDir/$i
+	done &&
+	git add bigDir &&
+	git commit -m "commit with 513 changes" &&
+	cat >expect <<-\EOF &&
+	Filter_Length:0
+	Filter_Data:
+	EOF
+	test-tool bloom get_filter_for_commit "$(git rev-parse HEAD)" >actual &&
+	test_cmp expect actual
+'
+
 test_done
\ No newline at end of file