git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / Atom feed
* [PATCH 0/9] [RFC] Changed Paths Bloom Filters
@ 2019-12-20 22:05 Garima Singh via GitGitGadget
  2019-12-20 22:05 ` [PATCH 1/9] commit-graph: add --changed-paths option to write Garima Singh via GitGitGadget
                   ` (13 more replies)
  0 siblings, 14 replies; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git; +Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff, Junio C Hamano

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 approach [2] and
presents an updated and more polished RFC version of the feature. 

Performance Gains: We tested the performance of git log -- path on the git
repo, the linux repo 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.

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

This series is intended to start the conversation and many of the commit
messages include specific call outs for suggestions and thoughts. 

Cheers! Garima Singh

[1] https://lore.kernel.org/git/20181009193445.21908-1-szeder.dev@gmail.com/
[2] 
https://lore.kernel.org/git/61559c5b-546e-d61b-d2e1-68de692f5972@gmail.com/

Garima Singh (9):
  commit-graph: add --changed-paths option to write
  commit-graph: write changed paths bloom filters
  commit-graph: use MAX_NUM_CHUNKS
  commit-graph: document bloom filter format
  commit-graph: write changed path bloom filters to commit-graph file.
  commit-graph: test commit-graph write --changed-paths
  commit-graph: reuse existing bloom filters during write.
  revision.c: use bloom filters to speed up path based revision walks
  commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag

 Documentation/git-commit-graph.txt            |   5 +
 .../technical/commit-graph-format.txt         |  17 ++
 Makefile                                      |   1 +
 bloom.c                                       | 257 +++++++++++++++++
 bloom.h                                       |  51 ++++
 builtin/commit-graph.c                        |   9 +-
 ci/run-build-and-tests.sh                     |   1 +
 commit-graph.c                                | 116 +++++++-
 commit-graph.h                                |   9 +-
 revision.c                                    |  67 ++++-
 revision.h                                    |   5 +
 t/README                                      |   3 +
 t/helper/test-read-graph.c                    |   4 +
 t/t4216-log-bloom.sh                          |  77 ++++++
 t/t5318-commit-graph.sh                       |   2 +
 t/t5324-split-commit-graph.sh                 |   1 +
 t/t5325-commit-graph-bloom.sh                 | 258 ++++++++++++++++++
 17 files changed, 875 insertions(+), 8 deletions(-)
 create mode 100644 bloom.c
 create mode 100644 bloom.h
 create mode 100755 t/t4216-log-bloom.sh
 create mode 100755 t/t5325-commit-graph-bloom.sh


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

^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 1/9] commit-graph: add --changed-paths option to write
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
@ 2019-12-20 22:05 ` Garima Singh via GitGitGadget
  2020-01-01 20:20   ` Jakub Narebski
  2019-12-20 22:05 ` [PATCH 2/9] commit-graph: write changed paths bloom filters Garima Singh via GitGitGadget
                   ` (12 subsequent siblings)
  13 siblings, 1 reply; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

From: Garima Singh <garima.singh@microsoft.com>

Add --changed-paths option to git commit-graph write. This option will
soon allow users to compute bloom filters for the paths changed between
a commit and its first significant parent, and write this information
into the commit-graph file.

Note: This commit does not change any behavior. It only introduces
the option and passes down the appropriate flag to the commit-graph.

RFC Notes:
1. We named the option --changed-paths to capture what the option does,
   instead of how it does it. The current implementation does this
   using bloom filters. We believe using --changed-paths however keeps
   the implementation open to other data structures.
   All thoughts and suggestions for the name and this approach are
   welcome

2. Currently, a subsequent commit in this series will add tests that
   exercise this option. I plan to split that test commit across the
   series as appropriate.

Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
---
 Documentation/git-commit-graph.txt | 5 +++++
 builtin/commit-graph.c             | 9 +++++++--
 commit-graph.h                     | 3 ++-
 3 files changed, 14 insertions(+), 3 deletions(-)

diff --git a/Documentation/git-commit-graph.txt b/Documentation/git-commit-graph.txt
index bcd85c1976..1efe6e5c5a 100644
--- a/Documentation/git-commit-graph.txt
+++ b/Documentation/git-commit-graph.txt
@@ -54,6 +54,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 file based history logs with `git log`
++
 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
diff --git a/builtin/commit-graph.c b/builtin/commit-graph.c
index e0c6fc4bbf..9bd1e11161 100644
--- a/builtin/commit-graph.c
+++ b/builtin/commit-graph.c
@@ -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_bloom_filters;
 } opts;
 
 static int graph_verify(int argc, const char **argv)
@@ -110,6 +111,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_bloom_filters,
+			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")),
@@ -143,6 +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_bloom_filters)
+		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;
 
 	read_replace_refs = 0;
 
diff --git a/commit-graph.h b/commit-graph.h
index 7f5c933fa2..952a4b83be 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -76,7 +76,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


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 2/9] commit-graph: write changed paths bloom filters
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
  2019-12-20 22:05 ` [PATCH 1/9] commit-graph: add --changed-paths option to write Garima Singh via GitGitGadget
@ 2019-12-20 22:05 ` Garima Singh via GitGitGadget
  2019-12-21 16:48   ` Philip Oakley
  2020-01-06 18:44   ` Jakub Narebski
  2019-12-20 22:05 ` [PATCH 3/9] commit-graph: use MAX_NUM_CHUNKS Garima Singh via GitGitGadget
                   ` (11 subsequent siblings)
  13 siblings, 2 replies; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

From: Garima Singh <garima.singh@microsoft.com>

The changed path bloom filters help determine which paths changed between a
commit and its first parent. We already have the "--changed-paths" option
for the "git commit-graph write" subcommand, now actually compute them under
that option. The COMMIT_GRAPH_WRITE_BLOOM_FILTERS flag enables this
computation.

RFC Notes: Here are some details about the implementation and I would love
to know your thoughts and suggestions for improvements here.

For details on what bloom filters are and how they work, please refer to
Dr. Derrick Stolee's blog post [1].
[1] https://devblogs.microsoft.com/devops/super-charging-the-git-commit-graph-iv-bloom-filters/

1. The implementation sticks to the recommended values of 7 and 10 for the
   number of hashes and the size of each entry, as described in the blog.
   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 so far with these values is
   significant enough to not that we did not need to tweak these settings.
   The cover letter of this series has the details and the commit where we have
   git log use bloom filters.

2. As described in the blog and the linked technical paper therin, 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.

[Call for advice] We currently cap writing bloom filters for commits with
atmost 512 changed files. In the current implementation, we compute the diff,
and then just throw it away once we see it has more than 512 changes.
Any suggestiongs on how to reduce the work we are doing in this case are more
than welcome.

[Call for advice] Would the git community like this commit to be split up into
more granular commits? This commit could possibly be split out further with the
bloom.c code in its own commit, to be used by the commit-graph in a subsequent
commit. While I prefer it being contained in one commit this way, I am open to
suggestions.

[Call for advice] Would a technical document explaining the exact details of
the bloom filter implemenation and the hashing calculations be helpful? I will
be adding details into Documentation/technical/commit-graph-format.txt, but the
bloom filter code is an independent subsystem and could be used outside of the
commit-graph feature. Is it worth a separate document, or should we apply "You
Ain't Gonna Need It" principles?

[Call for advice] I plan to add unit tests for bloom.c, specifically to ensure
that the hash algorithm and bloom key calculations are stable across versions.

Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Helped-by: Derrick Stolee <dstolee@microsoft.com>
---
 Makefile       |   1 +
 bloom.c        | 201 +++++++++++++++++++++++++++++++++++++++++++++++++
 bloom.h        |  46 +++++++++++
 commit-graph.c |  32 +++++++-
 4 files changed, 279 insertions(+), 1 deletion(-)
 create mode 100644 bloom.c
 create mode 100644 bloom.h

diff --git a/Makefile b/Makefile
index 42a061d3fb..9d5e26f5d6 100644
--- a/Makefile
+++ b/Makefile
@@ -838,6 +838,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
diff --git a/bloom.c b/bloom.c
new file mode 100644
index 0000000000..08328cc381
--- /dev/null
+++ b/bloom.c
@@ -0,0 +1,201 @@
+#include "git-compat-util.h"
+#include "bloom.h"
+#include "commit-graph.h"
+#include "object-store.h"
+#include "diff.h"
+#include "diffcore.h"
+#include "revision.h"
+#include "hashmap.h"
+
+#define BITS_PER_BLOCK 64
+
+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_right(uint32_t value, int32_t count)
+{
+	uint32_t mask = 8 * sizeof(uint32_t) - 1;
+	count &= mask;
+	return ((value >> count) | (value << ((-count) & mask)));
+}
+
+static uint32_t seed_murmur3(uint32_t seed, const char *data, int len)
+{
+	const uint32_t c1 = 0xcc9e2d51;
+	const uint32_t c2 = 0x1b873593;
+	const int32_t r1 = 15;
+	const int32_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_BLOCK - 1));
+}
+
+void fill_bloom_key(const char *data,
+		    int len,
+		    struct bloom_key *key,
+		    struct bloom_filter_settings *settings)
+{
+	int i;
+	uint32_t seed0 = 0x293ae76f;
+	uint32_t seed1 = 0x7e646e2c;
+
+	uint32_t hash0 = seed_murmur3(seed0, data, len);
+	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;
+}
+
+static 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_BLOCK;
+
+	for (i = 0; i < settings->num_hashes; i++) {
+		uint64_t hash_mod = key->hashes[i] % mod;
+		uint64_t block_pos = hash_mod / BITS_PER_BLOCK;
+
+		filter->data[block_pos] |= get_bitmask(hash_mod);
+	}
+}
+
+void load_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 rev_info revs;
+	const char *revs_argv[] = {NULL, "HEAD", NULL};
+
+	filter = bloom_filter_slab_at(&bloom_filters, c);
+	init_revisions(&revs, NULL);
+	revs.diffopt.flags.recursive = 1;
+
+	setup_revisions(2, revs_argv, &revs, NULL);
+
+	if (c->parents)
+		diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &revs.diffopt);
+	else
+		diff_tree_oid(NULL, &c->object.oid, "", &revs.diffopt);
+	diffcore_std(&revs.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;
+		    const char* p = 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(p, '/');
+
+				FLEX_ALLOC_STR(e, path, path);
+				hashmap_entry_init(&e->entry, strhash(p));
+				hashmap_add(&pathmap, &e->entry);
+
+				if (!last_slash)
+				    last_slash = (char*)p;
+				*last_slash = '\0';
+
+		    } while (*p);
+
+		    diff_free_filepair(diff_queued_diff.queue[i]);
+		}
+
+		filter->len = (hashmap_get_size(&pathmap) * settings.bits_per_entry + BITS_PER_BLOCK - 1) / BITS_PER_BLOCK;
+		filter->data = xcalloc(filter->len, sizeof(uint64_t));
+
+		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 {
+		filter->data = NULL;
+		filter->len = 0;
+	}
+
+	free(diff_queued_diff.queue);
+	DIFF_QUEUE_CLEAR(&diff_queued_diff);
+
+	return filter;
+}
\ No newline at end of file
diff --git a/bloom.h b/bloom.h
new file mode 100644
index 0000000000..ba8ae70b67
--- /dev/null
+++ b/bloom.h
@@ -0,0 +1,46 @@
+#ifndef BLOOM_H
+#define BLOOM_H
+
+struct commit;
+struct repository;
+
+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 }
+
+/*
+ * 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);
+
+struct bloom_filter *get_bloom_filter(struct repository *r,
+				      struct commit *c);
+
+void fill_bloom_key(const char *data,
+		    int len,
+		    struct bloom_key *key,
+		    struct bloom_filter_settings *settings);
+
+#endif
diff --git a/commit-graph.c b/commit-graph.c
index e771394aff..61e60ff98a 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -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" */
@@ -794,9 +795,11 @@ struct write_commit_graph_context {
 	unsigned append:1,
 		 report_progress:1,
 		 split:1,
-		 check_oids:1;
+		 check_oids:1,
+		 bloom:1;
 
 	const struct split_commit_graph_opts *split_opts;
+	uint32_t total_bloom_filter_size;
 };
 
 static void write_graph_chunk_fanout(struct hashfile *f,
@@ -1139,6 +1142,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;
+
+	load_bloom_filters();
+
+	if (ctx->report_progress)
+		progress = start_progress(
+			_("Computing commit diff 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_size += sizeof(uint64_t) * 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)
@@ -1791,6 +1816,8 @@ int write_commit_graph(const char *obj_dir,
 	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->bloom = flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS ? 1 : 0;
+	ctx->total_bloom_filter_size = 0;
 
 	if (ctx->split) {
 		struct commit_graph *g;
@@ -1885,6 +1912,9 @@ int write_commit_graph(const char *obj_dir,
 
 	compute_generation_numbers(ctx);
 
+	if (ctx->bloom)
+		compute_bloom_filters(ctx);
+
 	res = write_commit_graph_file(ctx);
 
 	if (ctx->split)
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 3/9] commit-graph: use MAX_NUM_CHUNKS
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
  2019-12-20 22:05 ` [PATCH 1/9] commit-graph: add --changed-paths option to write Garima Singh via GitGitGadget
  2019-12-20 22:05 ` [PATCH 2/9] commit-graph: write changed paths bloom filters Garima Singh via GitGitGadget
@ 2019-12-20 22:05 ` Garima Singh via GitGitGadget
  2020-01-07 12:19   ` Jakub Narebski
  2019-12-20 22:05 ` [PATCH 4/9] commit-graph: document bloom filter format Garima Singh via GitGitGadget
                   ` (10 subsequent siblings)
  13 siblings, 1 reply; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

From: Garima Singh <garima.singh@microsoft.com>

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

Signed-off-by: Garima Singh <garima.singh@microsoft.com>
---
 commit-graph.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 61e60ff98a..8c4941eeaa 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -24,6 +24,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)
 
@@ -1381,8 +1382,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


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 4/9] commit-graph: document bloom filter format
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (2 preceding siblings ...)
  2019-12-20 22:05 ` [PATCH 3/9] commit-graph: use MAX_NUM_CHUNKS Garima Singh via GitGitGadget
@ 2019-12-20 22:05 ` Garima Singh via GitGitGadget
  2020-01-07 14:46   ` Jakub Narebski
  2019-12-20 22:05 ` [PATCH 5/9] commit-graph: write changed path bloom filters to commit-graph file Garima Singh via GitGitGadget
                   ` (9 subsequent siblings)
  13 siblings, 1 reply; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

From: Garima Singh <garima.singh@microsoft.com>

Update the technical documentation for commit-graph-format with BIDX
and BDAT chunk information.

RFC Notes:
1. [Call for advice] We specifically mention that we are using bloom
   filters in this technical document. Should this document also be
   made open to other data structures in the future, with versioning
   information?

2. [Call for advice] We are also not describing the explicit nature
   of how we store the bloom filter binary data. Would it be useful
   to document details about the hash algorithm, the number of hashes
   and the specific seed values we are using in a separate document,
   or perhaps in a separate section in this document?

Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
---
 Documentation/technical/commit-graph-format.txt | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
index a4f17441ae..6497f19f08 100644
--- a/Documentation/technical/commit-graph-format.txt
+++ b/Documentation/technical/commit-graph-format.txt
@@ -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 it's first parent.
+
 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,20 @@ 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'}) [Optional]
+      For each commit we store the offset of its bloom filter in the BDAT chunk
+      as follows:
+      BIDX[i] = number of 8-byte words in all the bloom filters from commit 0 to
+		commit i (inclusive)
+
+  Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
+      * It starts with three 32 bit integers for the
+	    - version of the hash algorithm being used
+	    - the number of hashes used in the computation
+	    - the number of bits per entry
+	  * The rest of the chunk is the concatenation of all the computed bloom 
+	  filters for the commits in lexicographic order.
+
   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
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 5/9] commit-graph: write changed path bloom filters to commit-graph file.
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (3 preceding siblings ...)
  2019-12-20 22:05 ` [PATCH 4/9] commit-graph: document bloom filter format Garima Singh via GitGitGadget
@ 2019-12-20 22:05 ` Garima Singh via GitGitGadget
  2020-01-07 16:01   ` Jakub Narebski
  2019-12-20 22:05 ` [PATCH 6/9] commit-graph: test commit-graph write --changed-paths Garima Singh via GitGitGadget
                   ` (8 subsequent siblings)
  13 siblings, 1 reply; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

From: Garima Singh <garima.singh@microsoft.com>

Write bloom filters to the commit-graph using the format described in
Documentation/technical/commit-graph-format.txt

Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
---
 commit-graph.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++-
 commit-graph.h |  5 ++++
 2 files changed, 85 insertions(+), 1 deletion(-)

diff --git a/commit-graph.c b/commit-graph.c
index 8c4941eeaa..def2ade166 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -24,7 +24,9 @@
 #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_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
+#define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
+#define MAX_NUM_CHUNKS 7
 
 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
 
@@ -282,6 +284,32 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 				chunk_repeated = 1;
 			else
 				graph->chunk_base_graphs = data + chunk_offset;
+			break;
+
+		case GRAPH_CHUNKID_BLOOMINDEXES:
+			if (graph->chunk_bloom_indexes)
+				chunk_repeated = 1;
+			else
+				graph->chunk_bloom_indexes = data + chunk_offset;
+			break;
+
+		case GRAPH_CHUNKID_BLOOMDATA:
+			if (graph->chunk_bloom_data)
+				chunk_repeated = 1;
+			else {
+				uint32_t hash_version;
+				graph->chunk_bloom_data = data + chunk_offset;
+				hash_version = get_be32(data + chunk_offset);
+
+				if (hash_version != 1)
+					break;
+
+				graph->settings = xmalloc(sizeof(struct bloom_filter_settings));
+				graph->settings->hash_version = hash_version;
+				graph->settings->num_hashes = get_be32(data + chunk_offset + 4);
+				graph->settings->bits_per_entry = get_be32(data + chunk_offset + 8);
+			}
+			break;
 		}
 
 		if (chunk_repeated) {
@@ -996,6 +1024,39 @@ static void write_graph_chunk_extra_edges(struct hashfile *f,
 	}
 }
 
+static void write_graph_chunk_bloom_indexes(struct hashfile *f,
+					    struct write_commit_graph_context *ctx)
+{
+	struct commit **list = ctx->commits.list;
+	struct commit **last = ctx->commits.list + ctx->commits.nr;
+	uint32_t cur_pos = 0;
+
+	while (list < last) {
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
+		cur_pos += filter->len;
+		hashwrite_be32(f, cur_pos);
+		list++;
+	}
+}
+
+static void write_graph_chunk_bloom_data(struct hashfile *f,
+					 struct write_commit_graph_context *ctx,
+					 struct bloom_filter_settings *settings)
+{
+	struct commit **first = ctx->commits.list;
+	struct commit **last = ctx->commits.list + ctx->commits.nr;
+
+	hashwrite_be32(f, settings->hash_version);
+	hashwrite_be32(f, settings->num_hashes);
+	hashwrite_be32(f, settings->bits_per_entry);
+
+	while (first < last) {
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, *first);
+		hashwrite(f, filter->data, filter->len * sizeof(uint64_t));
+		first++;
+	}
+}
+
 static int oid_compare(const void *_a, const void *_b)
 {
 	const struct object_id *a = (const struct object_id *)_a;
@@ -1388,6 +1449,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 	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;
 
 	if (ctx->split) {
 		struct strbuf tmp_file = STRBUF_INIT;
@@ -1432,6 +1494,12 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 		chunk_ids[num_chunks] = GRAPH_CHUNKID_EXTRAEDGES;
 		num_chunks++;
 	}
+	if (ctx->bloom) {
+		chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMINDEXES;
+		num_chunks++;
+		chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMDATA;
+		num_chunks++;
+	}
 	if (ctx->num_commit_graphs_after > 1) {
 		chunk_ids[num_chunks] = GRAPH_CHUNKID_BASE;
 		num_chunks++;
@@ -1450,6 +1518,13 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 						4 * ctx->num_extra_edges;
 		num_chunks++;
 	}
+	if (ctx->bloom) {
+		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] + sizeof(uint32_t) * ctx->commits.nr;
+		num_chunks++;
+
+		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] + sizeof(uint32_t) * 3 + ctx->total_bloom_filter_size;
+		num_chunks++;
+	}
 	if (ctx->num_commit_graphs_after > 1) {
 		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
 						hashsz * (ctx->num_commit_graphs_after - 1);
@@ -1487,6 +1562,10 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 	write_graph_chunk_data(f, hashsz, ctx);
 	if (ctx->num_extra_edges)
 		write_graph_chunk_extra_edges(f, ctx);
+	if (ctx->bloom) {
+		write_graph_chunk_bloom_indexes(f, ctx);
+		write_graph_chunk_bloom_data(f, ctx, &bloom_settings);
+	}
 	if (ctx->num_commit_graphs_after > 1 &&
 	    write_graph_chunk_base(f, ctx)) {
 		return -1;
diff --git a/commit-graph.h b/commit-graph.h
index 952a4b83be..2202ad91ae 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -10,6 +10,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(const char *obj_dir);
 int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
@@ -58,6 +59,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 *settings;
 };
 
 struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st);
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 6/9] commit-graph: test commit-graph write --changed-paths
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (4 preceding siblings ...)
  2019-12-20 22:05 ` [PATCH 5/9] commit-graph: write changed path bloom filters to commit-graph file Garima Singh via GitGitGadget
@ 2019-12-20 22:05 ` Garima Singh via GitGitGadget
  2020-01-08  0:32   ` Jakub Narebski
  2019-12-20 22:05 ` [PATCH 7/9] commit-graph: reuse existing bloom filters during write Garima Singh via GitGitGadget
                   ` (7 subsequent siblings)
  13 siblings, 1 reply; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

From: Garima Singh <garima.singh@microsoft.com>

Add tests for the --changed-paths feature when writing
commit-graphs.

RFC Notes:
I plan to split this test across some of the earlier commits
as appropriate.

Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
---
 t/helper/test-read-graph.c    |   4 +
 t/t5325-commit-graph-bloom.sh | 255 ++++++++++++++++++++++++++++++++++
 2 files changed, 259 insertions(+)
 create mode 100755 t/t5325-commit-graph-bloom.sh

diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c
index d2884efe0a..aff597c7a3 100644
--- a/t/helper/test-read-graph.c
+++ b/t/helper/test-read-graph.c
@@ -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);
diff --git a/t/t5325-commit-graph-bloom.sh b/t/t5325-commit-graph-bloom.sh
new file mode 100755
index 0000000000..d7ef0e7fb3
--- /dev/null
+++ b/t/t5325-commit-graph-bloom.sh
@@ -0,0 +1,255 @@
+#!/bin/sh
+
+test_description='commit graph with bloom filters'
+. ./test-lib.sh
+
+test_expect_success 'setup repo' '
+	git init &&
+	git config core.commitGraph true &&
+	git config gc.writeCommitGraph false &&
+	infodir=".git/objects/info" &&
+	graphdir="$infodir/commit-graphs" &&
+	test_oid_init
+'
+
+graph_read_expect() {
+	OPTIONAL=""
+	NUM_CHUNKS=5
+	if test ! -z $2
+	then
+		OPTIONAL=" $2"
+		NUM_CHUNKS=$((NUM_CHUNKS + $(echo "$2" | wc -w)))
+	fi
+	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 'create commits and write commit-graph' '
+	for i in $(test_seq 3)
+	do
+		test_commit $i &&
+		git branch commits/$i || return 1
+	done &&
+	git commit-graph write --reachable --changed-paths &&
+	test_path_is_file $infodir/commit-graph &&
+	graph_read_expect 3
+'
+
+graph_git_two_modes() {
+	git -c core.commitGraph=true $1 >output
+	git -c core.commitGraph=false $1 >expect
+	test_cmp expect output
+}
+
+graph_git_behavior() {
+	MSG=$1
+	BRANCH=$2
+	COMPARE=$3
+	test_expect_success "check normal git operations: $MSG" '
+		graph_git_two_modes "log --oneline $BRANCH" &&
+		graph_git_two_modes "log --topo-order $BRANCH" &&
+		graph_git_two_modes "log --graph $COMPARE..$BRANCH" &&
+		graph_git_two_modes "branch -vv" &&
+		graph_git_two_modes "merge-base -a $BRANCH $COMPARE"
+	'
+}
+
+graph_git_behavior 'graph exists' commits/3 commits/1
+
+verify_chain_files_exist() {
+	for hash in $(cat $1/commit-graph-chain)
+	do
+		test_path_is_file $1/graph-$hash.graph || return 1
+	done
+}
+
+test_expect_success 'add more commits, and write a new base graph' '
+	git reset --hard commits/1 &&
+	for i in $(test_seq 4 5)
+	do
+		test_commit $i &&
+		git branch commits/$i || return 1
+	done &&
+	git reset --hard commits/2 &&
+	for i in $(test_seq 6 10)
+	do
+		test_commit $i &&
+		git branch commits/$i || return 1
+	done &&
+	git reset --hard commits/2 &&
+	git merge commits/4 &&
+	git branch merge/1 &&
+	git reset --hard commits/4 &&
+	git merge commits/6 &&
+	git branch merge/2 &&
+	git commit-graph write --reachable --changed-paths &&
+	graph_read_expect 12
+'
+
+test_expect_success 'fork and fail to base a chain on a commit-graph file' '
+	test_when_finished rm -rf fork &&
+	git clone . fork &&
+	(
+		cd fork &&
+		rm .git/objects/info/commit-graph &&
+		echo "$(pwd)/../.git/objects" >.git/objects/info/alternates &&
+		test_commit new-commit &&
+		git commit-graph write --reachable --split --changed-paths &&
+		test_path_is_file $graphdir/commit-graph-chain &&
+		test_line_count = 1 $graphdir/commit-graph-chain &&
+		verify_chain_files_exist $graphdir
+	)
+'
+
+test_expect_success 'add three more commits, write a tip graph' '
+	git reset --hard commits/3 &&
+	git merge merge/1 &&
+	git merge commits/5 &&
+	git merge merge/2 &&
+	git branch merge/3 &&
+	git commit-graph write --reachable --split --changed-paths &&
+	test_path_is_missing $infodir/commit-graph &&
+	test_path_is_file $graphdir/commit-graph-chain &&
+	ls $graphdir/graph-*.graph >graph-files &&
+	test_line_count = 2 graph-files &&
+	verify_chain_files_exist $graphdir
+'
+
+graph_git_behavior 'split commit-graph: merge 3 vs 2' merge/3 merge/2
+
+test_expect_success 'add one commit, write a tip graph' '
+	test_commit 11 &&
+	git branch commits/11 &&
+	git commit-graph write --reachable --split --changed-paths &&
+	test_path_is_missing $infodir/commit-graph &&
+	test_path_is_file $graphdir/commit-graph-chain &&
+	ls $graphdir/graph-*.graph >graph-files &&
+	test_line_count = 3 graph-files &&
+	verify_chain_files_exist $graphdir
+'
+
+graph_git_behavior 'three-layer commit-graph: commit 11 vs 6' commits/11 commits/6
+
+test_expect_success 'add one commit, write a merged graph' '
+	test_commit 12 &&
+	git branch commits/12 &&
+	git commit-graph write --reachable --split --changed-paths &&
+	test_path_is_file $graphdir/commit-graph-chain &&
+	test_line_count = 2 $graphdir/commit-graph-chain &&
+	ls $graphdir/graph-*.graph >graph-files &&
+	test_line_count = 2 graph-files &&
+	verify_chain_files_exist $graphdir
+'
+
+graph_git_behavior 'merged commit-graph: commit 12 vs 6' commits/12 commits/6
+
+test_expect_success 'create fork and chain across alternate' '
+	git clone . fork &&
+	(
+		cd fork &&
+		git config core.commitGraph true &&
+		rm -rf $graphdir &&
+		echo "$(pwd)/../.git/objects" >.git/objects/info/alternates &&
+		test_commit 13 &&
+		git branch commits/13 &&
+		git commit-graph write --reachable --split --changed-paths &&
+		test_path_is_file $graphdir/commit-graph-chain &&
+		test_line_count = 3 $graphdir/commit-graph-chain &&
+		ls $graphdir/graph-*.graph >graph-files &&
+		test_line_count = 1 graph-files &&
+		git -c core.commitGraph=true  rev-list HEAD >expect &&
+		git -c core.commitGraph=false rev-list HEAD >actual &&
+		test_cmp expect actual &&
+		test_commit 14 &&
+		git commit-graph write --reachable --split --changed-paths --object-dir=.git/objects/ &&
+		test_line_count = 3 $graphdir/commit-graph-chain &&
+		ls $graphdir/graph-*.graph >graph-files &&
+		test_line_count = 1 graph-files
+	)
+'
+
+graph_git_behavior 'alternate: commit 13 vs 6' commits/13 commits/6
+
+test_expect_success 'test merge stragety constants' '
+	git clone . merge-2 &&
+	(
+		cd merge-2 &&
+		git config core.commitGraph true &&
+		test_line_count = 2 $graphdir/commit-graph-chain &&
+		test_commit 14 &&
+		git commit-graph write --reachable --split --changed-paths --size-multiple=2 &&
+		test_line_count = 3 $graphdir/commit-graph-chain
+
+	) &&
+	git clone . merge-10 &&
+	(
+		cd merge-10 &&
+		git config core.commitGraph true &&
+		test_line_count = 2 $graphdir/commit-graph-chain &&
+		test_commit 14 &&
+		git commit-graph write --reachable --split --changed-paths --size-multiple=10 &&
+		test_line_count = 1 $graphdir/commit-graph-chain &&
+		ls $graphdir/graph-*.graph >graph-files &&
+		test_line_count = 1 graph-files
+	) &&
+	git clone . merge-10-expire &&
+	(
+		cd merge-10-expire &&
+		git config core.commitGraph true &&
+		test_line_count = 2 $graphdir/commit-graph-chain &&
+		test_commit 15 &&
+		git commit-graph write --reachable --split --changed-paths --size-multiple=10 --expire-time=1980-01-01 &&
+		test_line_count = 1 $graphdir/commit-graph-chain &&
+		ls $graphdir/graph-*.graph >graph-files &&
+		test_line_count = 3 graph-files
+	) &&
+	git clone --no-hardlinks . max-commits &&
+	(
+		cd max-commits &&
+		git config core.commitGraph true &&
+		test_line_count = 2 $graphdir/commit-graph-chain &&
+		test_commit 16 &&
+		test_commit 17 &&
+		git commit-graph write --reachable --split --changed-paths --max-commits=1 &&
+		test_line_count = 1 $graphdir/commit-graph-chain &&
+		ls $graphdir/graph-*.graph >graph-files &&
+		test_line_count = 1 graph-files
+	)
+'
+
+test_expect_success 'remove commit-graph-chain file after flattening' '
+	git clone . flatten &&
+	(
+		cd flatten &&
+		test_line_count = 2 $graphdir/commit-graph-chain &&
+		git commit-graph write --reachable &&
+		test_path_is_missing $graphdir/commit-graph-chain &&
+		ls $graphdir >graph-files &&
+		test_must_be_empty graph-files
+	)
+'
+
+graph_git_behavior 'graph exists' merge/octopus commits/12
+
+test_expect_success 'split across alternate where alternate is not split' '
+	git commit-graph write --reachable &&
+	test_path_is_file .git/objects/info/commit-graph &&
+	cp .git/objects/info/commit-graph . &&
+	git clone --no-hardlinks . alt-split &&
+	(
+		cd alt-split &&
+		rm -f .git/objects/info/commit-graph &&
+		echo "$(pwd)"/../.git/objects >.git/objects/info/alternates &&
+		test_commit 18 &&
+		git commit-graph write --reachable --split --changed-paths &&
+		test_line_count = 1 $graphdir/commit-graph-chain
+	) &&
+	test_cmp commit-graph .git/objects/info/commit-graph
+'
+
+test_done
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 7/9] commit-graph: reuse existing bloom filters during write.
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (5 preceding siblings ...)
  2019-12-20 22:05 ` [PATCH 6/9] commit-graph: test commit-graph write --changed-paths Garima Singh via GitGitGadget
@ 2019-12-20 22:05 ` Garima Singh via GitGitGadget
  2020-01-09 19:12   ` Jakub Narebski
  2019-12-20 22:05 ` [PATCH 8/9] revision.c: use bloom filters to speed up path based revision walks Garima Singh via GitGitGadget
                   ` (6 subsequent siblings)
  13 siblings, 1 reply; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

From: Garima Singh <garima.singh@microsoft.com>

Read previously computed bloom filters from the commit-graph file if possible
to avoid recomputing during commit-graph write.

Reading from the commit-graph is based on the format in which bloom filters are
written in the commit graph file. See method `fill_filter_from_graph` in bloom.c

For reading the bloom filter for commit at lexicographic position i:
1. Read BIDX[i] which essentially gives us the starting index in BDAT for filter
   of commit i+1 (called the next_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 (called the prev_index in the code)
   For i = 0, prev_index will be 0. The first lexicographic commit's filter will
   start at BDAT.

3. The length of the filter will be next_index - prev_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_null
flag.

Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
---
 bloom.c        | 40 ++++++++++++++++++++++++++++++++++++++--
 bloom.h        |  3 ++-
 commit-graph.c |  6 +++---
 3 files changed, 43 insertions(+), 6 deletions(-)

diff --git a/bloom.c b/bloom.c
index 08328cc381..86b1005802 100644
--- a/bloom.c
+++ b/bloom.c
@@ -1,5 +1,7 @@
 #include "git-compat-util.h"
 #include "bloom.h"
+#include "commit.h"
+#include "commit-slab.h"
 #include "commit-graph.h"
 #include "object-store.h"
 #include "diff.h"
@@ -119,13 +121,35 @@ static void add_key_to_filter(struct bloom_key *key,
 	}
 }
 
+static void fill_filter_from_graph(struct commit_graph *g,
+				   struct bloom_filter *filter,
+				   struct commit *c)
+{
+	uint32_t lex_pos, prev_index, next_index;
+
+	while (c->graph_pos < g->num_commits_in_base)
+		g = g->base_graph;
+
+	lex_pos = c->graph_pos - g->num_commits_in_base;
+
+	next_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
+	if (lex_pos)
+		prev_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1));
+	else
+		prev_index = 0;
+
+	filter->len = next_index - prev_index;
+	filter->data = (uint64_t *)(g->chunk_bloom_data + 8 * prev_index + 12);
+}
+
 void load_bloom_filters(void)
 {
 	init_bloom_filter_slab(&bloom_filters);
 }
 
 struct bloom_filter *get_bloom_filter(struct repository *r,
-				      struct commit *c)
+				      struct commit *c,
+				      int compute_if_null)
 {
 	struct bloom_filter *filter;
 	struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
@@ -134,6 +158,18 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 	const char *revs_argv[] = {NULL, "HEAD", NULL};
 
 	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) {
+			fill_filter_from_graph(r->objects->commit_graph, filter, c);
+			return filter;
+		}
+	}
+
+	if (filter->data || !compute_if_null)
+			return filter;
+
 	init_revisions(&revs, NULL);
 	revs.diffopt.flags.recursive = 1;
 
@@ -198,4 +234,4 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 	DIFF_QUEUE_CLEAR(&diff_queued_diff);
 
 	return filter;
-}
\ No newline at end of file
+}
diff --git a/bloom.h b/bloom.h
index ba8ae70b67..101d689bbd 100644
--- a/bloom.h
+++ b/bloom.h
@@ -36,7 +36,8 @@ struct bloom_key {
 void load_bloom_filters(void);
 
 struct bloom_filter *get_bloom_filter(struct repository *r,
-				      struct commit *c);
+				      struct commit *c,
+				      int compute_if_null);
 
 void fill_bloom_key(const char *data,
 		    int len,
diff --git a/commit-graph.c b/commit-graph.c
index def2ade166..0580ce75d5 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1032,7 +1032,7 @@ static void write_graph_chunk_bloom_indexes(struct hashfile *f,
 	uint32_t cur_pos = 0;
 
 	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;
 		hashwrite_be32(f, cur_pos);
 		list++;
@@ -1051,7 +1051,7 @@ static void write_graph_chunk_bloom_data(struct hashfile *f,
 	hashwrite_be32(f, settings->bits_per_entry);
 
 	while (first < last) {
-		struct bloom_filter *filter = get_bloom_filter(ctx->r, *first);
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, *first, 0);
 		hashwrite(f, filter->data, filter->len * sizeof(uint64_t));
 		first++;
 	}
@@ -1218,7 +1218,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 
 	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);
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1);
 		ctx->total_bloom_filter_size += sizeof(uint64_t) * filter->len;
 		display_progress(progress, i + 1);
 	}
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 8/9] revision.c: use bloom filters to speed up path based revision walks
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (6 preceding siblings ...)
  2019-12-20 22:05 ` [PATCH 7/9] commit-graph: reuse existing bloom filters during write Garima Singh via GitGitGadget
@ 2019-12-20 22:05 ` Garima Singh via GitGitGadget
  2020-01-11  0:27   ` Jakub Narebski
  2019-12-20 22:05 ` [PATCH 9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag Garima Singh via GitGitGadget
                   ` (5 subsequent siblings)
  13 siblings, 1 reply; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

From: Garima Singh <garima.singh@microsoft.com>

If bloom filters have been written to the commit-graph file, revision walk will
use them to speed up revision walks for a particular path.
Note: The current implementation does this in the case of single pathspec
case only.

We load the bloom filters during the prepare_revision_walk step 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.

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.

RFC Notes:
I plan to collect the folloowing statistics around this usage of bloom filters
and trace them out using trace2.
- number of bloom filter queries,
- number of "No" responses (file hasn't changed)
- number of "Maybe" responses (file may have changed)
- number of "Commit not parsed" cases (commit had too many changes to have a
  bloom filter written out, currently our limit is 512 diffs)

Helped-by: Derrick Stolee <dstolee@microsoft.com
Helped-by: SZEDER Gábor <szeder.dev@gmail.com>
Helped-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
---
 bloom.c              | 20 ++++++++++++
 bloom.h              |  4 +++
 revision.c           | 67 +++++++++++++++++++++++++++++++++++++--
 revision.h           |  5 +++
 t/t4216-log-bloom.sh | 74 ++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 168 insertions(+), 2 deletions(-)
 create mode 100755 t/t4216-log-bloom.sh

diff --git a/bloom.c b/bloom.c
index 86b1005802..0c7505d3d6 100644
--- a/bloom.c
+++ b/bloom.c
@@ -235,3 +235,23 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 
 	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_BLOCK;
+
+	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_BLOCK;
+		if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
+			return 0;
+	}
+
+	return 1;
+}
diff --git a/bloom.h b/bloom.h
index 101d689bbd..9bdacd0a8e 100644
--- a/bloom.h
+++ b/bloom.h
@@ -44,4 +44,8 @@ void fill_bloom_key(const char *data,
 		    struct bloom_key *key,
 		    struct bloom_filter_settings *settings);
 
+int bloom_filter_contains(struct bloom_filter *filter,
+			  struct bloom_key *key,
+			  struct bloom_filter_settings *settings);
+
 #endif
diff --git a/revision.c b/revision.c
index 39a25e7a5d..01f5330740 100644
--- a/revision.c
+++ b/revision.c
@@ -29,6 +29,7 @@
 #include "prio-queue.h"
 #include "hashmap.h"
 #include "utf8.h"
+#include "bloom.h"
 
 volatile show_early_output_fn_t show_early_output;
 
@@ -624,11 +625,34 @@ static void file_change(struct diff_options *options,
 	options->flags.has_changes = 1;
 }
 
+static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
+						 struct commit *commit,
+						 struct bloom_key *key,
+						 struct bloom_filter_settings *settings)
+{
+	struct bloom_filter *filter;
+
+	if (!revs->repo->objects->commit_graph)
+		return -1;
+	if (commit->generation == GENERATION_NUMBER_INFINITY)
+		return -1;
+	if (!key || !settings)
+		return -1;
+
+	filter = get_bloom_filter(revs->repo, commit, 0);
+
+	if (!filter || !filter->len)
+		return 1;
+
+	return bloom_filter_contains(filter, key, settings);
+}
+
 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,6 +677,16 @@ static int rev_compare_tree(struct rev_info *revs,
 			return REV_TREE_SAME;
 	}
 
+	if (revs->pruning.pathspec.nr == 1 && !nth_parent) {
+		bloom_ret = check_maybe_different_in_bloom_filter(revs,
+								  commit,
+								  revs->bloom_key,
+								  revs->bloom_filter_settings);
+
+		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, "",
@@ -855,7 +889,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
@@ -3342,6 +3376,33 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
 	}
 }
 
+static void prepare_to_use_bloom_filter(struct rev_info *revs)
+{
+	struct pathspec_item *pi;
+	const char *path;
+	size_t len;
+
+	if (!revs->commits)
+	    return;
+
+	parse_commit(revs->commits->item);
+
+	if (!revs->repo->objects->commit_graph)
+		return;
+
+	revs->bloom_filter_settings = revs->repo->objects->commit_graph->settings;
+	if (!revs->bloom_filter_settings)
+		return;
+
+	pi = &revs->pruning.pathspec.items[0];
+	path = pi->match;
+	len = strlen(path);
+
+	load_bloom_filters();
+	revs->bloom_key = xmalloc(sizeof(struct bloom_key));
+	fill_bloom_key(path, len, revs->bloom_key, revs->bloom_filter_settings);
+}
+
 int prepare_revision_walk(struct rev_info *revs)
 {
 	int i;
@@ -3391,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs)
 		simplify_merges(revs);
 	if (revs->children.name)
 		set_children(revs);
+	if (revs->pruning.pathspec.nr == 1)
+	    prepare_to_use_bloom_filter(revs);
 	return 0;
 }
 
diff --git a/revision.h b/revision.h
index a1a804bd3d..65dc11e8f1 100644
--- a/revision.h
+++ b/revision.h
@@ -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,9 @@ struct rev_info {
 	struct revision_sources *sources;
 
 	struct topo_walk_info *topo_walk_info;
+
+	struct bloom_key *bloom_key;
+	struct bloom_filter_settings *bloom_filter_settings;
 };
 
 int ref_excluded(struct string_list *, const char *path);
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
new file mode 100755
index 0000000000..d42f077998
--- /dev/null
+++ b/t/t4216-log-bloom.sh
@@ -0,0 +1,74 @@
+#!/bin/sh
+
+test_description='git log for a path with bloom filters'
+. ./test-lib.sh
+
+test_expect_success 'setup repo' '
+	git init &&
+	git config core.commitGraph true &&
+	git config gc.writeCommitGraph false &&
+	infodir=".git/objects/info" &&
+	graphdir="$infodir/commit-graphs" &&
+	test_oid_init
+'
+
+test_expect_success 'create 9 commits and repack' '
+	test_commit c1 file1 &&
+	test_commit c2 file2 &&
+	test_commit c3 file3 &&
+	test_commit c4 file1 &&
+	test_commit c5 file2 &&
+	test_commit c6 file3 &&
+	test_commit c7 file1 &&
+	test_commit c8 file2 &&
+	test_commit c9 file3
+'
+
+printf "c7\nc4\nc1" > expect_file1
+
+test_expect_success 'log without bloom filters' '
+	git log --pretty="format:%s"  -- file1 > actual &&
+	test_cmp expect_file1 actual
+'
+
+printf "c8\nc7\nc5\nc4\nc2\nc1" > expect_file1_file2
+
+test_expect_success 'multi-path log without bloom filters' '
+	git log --pretty="format:%s"  -- file1 file2 > actual &&
+	test_cmp expect_file1_file2 actual
+'
+
+graph_read_expect() {
+	OPTIONAL=""
+	NUM_CHUNKS=5
+	if test ! -z $2
+	then
+		OPTIONAL=" $2"
+		NUM_CHUNKS=$((3 + $(echo "$2" | wc -w)))
+	fi
+	cat >expect <<- EOF
+	header: 43475048 1 1 $NUM_CHUNKS 0
+	num_commits: $1
+	chunks: oid_fanout oid_lookup commit_metadata bloom_indexes bloom_data$OPTIONAL
+	EOF
+	test-tool read-graph >output &&
+	test_cmp expect output
+}
+
+test_expect_success 'write commit graph with bloom filters' '
+	git commit-graph write --reachable --changed-paths &&
+	test_path_is_file $infodir/commit-graph &&
+	graph_read_expect "9"
+'
+
+test_expect_success 'log using bloom filters' '
+	git log --pretty="format:%s" -- file1 > actual &&
+	test_cmp expect_file1 actual
+'
+
+test_expect_success 'multi-path log using bloom filters' '
+	git log --pretty="format:%s"  -- file1 file2 > actual &&
+	test_cmp expect_file1_file2 actual
+'
+
+test_done
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (7 preceding siblings ...)
  2019-12-20 22:05 ` [PATCH 8/9] revision.c: use bloom filters to speed up path based revision walks Garima Singh via GitGitGadget
@ 2019-12-20 22:05 ` Garima Singh via GitGitGadget
  2020-01-11 19:56   ` Jakub Narebski
  2019-12-20 22:14 ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Junio C Hamano
                   ` (4 subsequent siblings)
  13 siblings, 1 reply; 51+ messages in thread
From: Garima Singh via GitGitGadget @ 2019-12-20 22:05 UTC (permalink / raw)
  To: git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

From: Garima Singh <garima.singh@microsoft.com>

Add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS 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`.

The test suite passes when GIT_TEST_COMMIT_GRAPH and
GIT_COMMIT_GRAPH_BLOOM_FILTERS are enabled.

Helped-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
---
 builtin/commit-graph.c        | 2 +-
 ci/run-build-and-tests.sh     | 1 +
 commit-graph.h                | 1 +
 t/README                      | 3 +++
 t/t4216-log-bloom.sh          | 3 +++
 t/t5318-commit-graph.sh       | 2 ++
 t/t5324-split-commit-graph.sh | 1 +
 t/t5325-commit-graph-bloom.sh | 3 +++
 8 files changed, 15 insertions(+), 1 deletion(-)

diff --git a/builtin/commit-graph.c b/builtin/commit-graph.c
index 9bd1e11161..97167959b2 100644
--- a/builtin/commit-graph.c
+++ b/builtin/commit-graph.c
@@ -146,7 +146,7 @@ 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_bloom_filters)
+	if (opts.enable_bloom_filters || git_env_bool(GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS, 0))
 		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;
 
 	read_replace_refs = 0;
diff --git a/ci/run-build-and-tests.sh b/ci/run-build-and-tests.sh
index ff0ef7f08e..19d0846d34 100755
--- a/ci/run-build-and-tests.sh
+++ b/ci/run-build-and-tests.sh
@@ -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_BLOOM_FILTERS=1
 	export GIT_TEST_MULTI_PACK_INDEX=1
 	make test
 	;;
diff --git a/commit-graph.h b/commit-graph.h
index 2202ad91ae..d914e6abf1 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -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_BLOOM_FILTERS "GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS"
 
 struct commit;
 struct bloom_filter_settings;
diff --git a/t/README b/t/README
index caa125ba9a..399b190437 100644
--- a/t/README
+++ b/t/README
@@ -378,6 +378,9 @@ 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_BLOOM_FILTERS=<boolean>, when true, forces commit-graph
+write to compute and write bloom filters for every 'git commit-graph write'
+
 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.
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index d42f077998..0e092b387c 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -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_BLOOM_FILTERS=0
+
 test_expect_success 'setup repo' '
 	git init &&
 	git config core.commitGraph true &&
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 3f03de6018..613228bb12 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -3,6 +3,8 @@
 test_description='commit graph'
 . ./test-lib.sh
 
+GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS=0
+
 test_expect_success 'setup full repo' '
 	mkdir full &&
 	cd "$TRASH_DIRECTORY/full" &&
diff --git a/t/t5324-split-commit-graph.sh b/t/t5324-split-commit-graph.sh
index c24823431f..181ca7e0cb 100755
--- a/t/t5324-split-commit-graph.sh
+++ b/t/t5324-split-commit-graph.sh
@@ -4,6 +4,7 @@ test_description='split commit graph'
 . ./test-lib.sh
 
 GIT_TEST_COMMIT_GRAPH=0
+GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS=0
 
 test_expect_success 'setup repo' '
 	git init &&
diff --git a/t/t5325-commit-graph-bloom.sh b/t/t5325-commit-graph-bloom.sh
index d7ef0e7fb3..a9c9e9fef6 100755
--- a/t/t5325-commit-graph-bloom.sh
+++ b/t/t5325-commit-graph-bloom.sh
@@ -3,6 +3,9 @@
 test_description='commit graph with bloom filters'
 . ./test-lib.sh
 
+GIT_TEST_COMMIT_GRAPH=0
+GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS=0
+
 test_expect_success 'setup repo' '
 	git init &&
 	git config core.commitGraph true &&
-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (8 preceding siblings ...)
  2019-12-20 22:05 ` [PATCH 9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag Garima Singh via GitGitGadget
@ 2019-12-20 22:14 ` Junio C Hamano
  2019-12-22  9:26 ` Christian Couder
                   ` (3 subsequent siblings)
  13 siblings, 0 replies; 51+ messages in thread
From: Junio C Hamano @ 2019-12-20 22:14 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> 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 approach [2] and
> presents an updated and more polished RFC version of the feature. 

;-)

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 2/9] commit-graph: write changed paths bloom filters
  2019-12-20 22:05 ` [PATCH 2/9] commit-graph: write changed paths bloom filters Garima Singh via GitGitGadget
@ 2019-12-21 16:48   ` Philip Oakley
  2020-01-06 18:44   ` Jakub Narebski
  1 sibling, 0 replies; 51+ messages in thread
From: Philip Oakley @ 2019-12-21 16:48 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget, git
  Cc: stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

spelling nit?

On 20/12/2019 22:05, Garima Singh via GitGitGadget wrote:
> 1. The implementation sticks to the recommended values of 7 and 10 for the
>    number of hashes and the size of each entry, as described in the blog.
>    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 so far with these values is
>    significant enough to not that we did not need to tweak these settings.
s/not/note/ (first occurrence)
>    The cover letter of this series has the details and the commit where we have
>    git log use bloom filters.
Philip

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (9 preceding siblings ...)
  2019-12-20 22:14 ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Junio C Hamano
@ 2019-12-22  9:26 ` Christian Couder
  2019-12-22  9:38   ` Jeff King
  2019-12-22  9:30 ` Jeff King
                   ` (2 subsequent siblings)
  13 siblings, 1 reply; 51+ messages in thread
From: Christian Couder @ 2019-12-22  9:26 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano

Hi,

On Fri, Dec 20, 2019 at 11:07 PM Garima Singh via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> 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 approach [2] and
> presents an updated and more polished RFC version of the feature.

Thanks for working on this!

> Performance Gains: We tested the performance of git log -- path on the git
> repo, the linux repo 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.

Very nice!

I have a question though. Are the performance gains only available
with `git log -- path` or are they already available for example when
doing a partial clone and/or a sparse checkout?

> 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

Great!

> This series is intended to start the conversation and many of the commit
> messages include specific call outs for suggestions and thoughts.

I think Peff said during the Virtual Contributor Summit that he was
interested in using bitmaps to speed up partial clone on the server
side. Would it make sense to use both bitmaps and bloom filters?

Thanks,
Christian.

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (10 preceding siblings ...)
  2019-12-22  9:26 ` Christian Couder
@ 2019-12-22  9:30 ` Jeff King
  2019-12-22  9:32   ` [PATCH 1/3] commit-graph: examine changed-path objects in pack order Jeff King
                     ` (4 more replies)
  2019-12-31 16:45 ` Jakub Narebski
  2020-01-21 23:40 ` Emily Shaffer
  13 siblings, 5 replies; 51+ messages in thread
From: Jeff King @ 2019-12-22  9:30 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, Junio C Hamano

On Fri, Dec 20, 2019 at 10:05:11PM +0000, Garima Singh via GitGitGadget wrote:

> 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 approach [2] and
> presents an updated and more polished RFC version of the feature.

Great to see progress here. I probably won't have time to review this
carefully before the new year, but I did notice some low-hanging fruit
on the generation side.

So here are a few patches to reduce the CPU and memory usage. They could
be squashed in at the appropriate spots, or perhaps taken as inspiration
if there are better solutions (especially for the first one).

I think we could go further still, by actually doing a non-recursive
diff_tree_oid(), and then recursing into sub-trees ourselves. That would
save us having to split apart each path to add the leading paths to the
hashmap (most of which will be duplicates if the commit touched "a/b/c"
and "a/b/d", etc). I doubt it would be that huge a speedup though. We
have to keep a list of the touched paths anyway (since the bloom key
parameters depend on the number of entries), and most of the time is
almost certainly spent inflating the trees in the first place. However
it might be easier to follow the code, and it would make it simpler to
stop traversing at the 512-entry limit, rather than generating a huge
diff only to throw it away.

  [1/3]: commit-graph: examine changed-path objects in pack order
  [2/3]: commit-graph: free large diffs, too
  [3/3]: commit-graph: stop using full rev_info for diffs

 bloom.c        | 18 +++++++++---------
 commit-graph.c | 34 +++++++++++++++++++++++++++++++++-
 2 files changed, 42 insertions(+), 10 deletions(-)

-Peff

^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 1/3] commit-graph: examine changed-path objects in pack order
  2019-12-22  9:30 ` Jeff King
@ 2019-12-22  9:32   ` Jeff King
  2019-12-27 14:51     ` Derrick Stolee
  2019-12-22  9:32   ` [PATCH 2/3] commit-graph: free large diffs, too Jeff King
                     ` (3 subsequent siblings)
  4 siblings, 1 reply; 51+ messages in thread
From: Jeff King @ 2019-12-22  9:32 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, Junio C Hamano

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.

Signed-off-by: Jeff King <peff@peff.net>
---
 commit-graph.c | 34 +++++++++++++++++++++++++++++++++-
 1 file changed, 33 insertions(+), 1 deletion(-)

diff --git a/commit-graph.c b/commit-graph.c
index 0580ce75d5..bf6c663772 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -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" */
@@ -48,6 +49,29 @@
 /* Remember to update object flag allocation in object.h */
 #define REACHABLE       (1u<<15)
 
+/* 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)
+{
+	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);
@@ -1088,6 +1112,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;
 }
 
@@ -1208,6 +1234,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 {
 	int i;
 	struct progress *progress = NULL;
+	struct commit **sorted_by_pos;
 
 	load_bloom_filters();
 
@@ -1216,13 +1243,18 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 			_("Computing commit diff 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);
+
 	for (i = 0; i < ctx->commits.nr; i++) {
-		struct commit *c = ctx->commits.list[i];
+		struct commit *c = sorted_by_pos[i];
 		struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1);
 		ctx->total_bloom_filter_size += sizeof(uint64_t) * filter->len;
 		display_progress(progress, i + 1);
 	}
 
+	free(sorted_by_pos);
 	stop_progress(&progress);
 }
 
-- 
2.24.1.1152.gda0b849012


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 2/3] commit-graph: free large diffs, too
  2019-12-22  9:30 ` Jeff King
  2019-12-22  9:32   ` [PATCH 1/3] commit-graph: examine changed-path objects in pack order Jeff King
@ 2019-12-22  9:32   ` Jeff King
  2019-12-27 14:52     ` Derrick Stolee
  2019-12-22  9:32   ` [PATCH 3/3] commit-graph: stop using full rev_info for diffs Jeff King
                     ` (2 subsequent siblings)
  4 siblings, 1 reply; 51+ messages in thread
From: Jeff King @ 2019-12-22  9:32 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, Junio C Hamano

If a diff we compute for --changed-path has more than 512 entries, we
don't bother generating a bloom filter for it. But since we don't
iterate over diff_queued_diff, we also don't free the filepairs and
filespecs from the diff before clearing the queue. Let's make sure we do
so.

This drops the peak heap usage of "commit-graph write --changed-paths"
on linux.git from ~8GB to ~4GB.

Signed-off-by: Jeff King <peff@peff.net>
---
 bloom.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/bloom.c b/bloom.c
index 0c7505d3d6..d1d3796e11 100644
--- a/bloom.c
+++ b/bloom.c
@@ -226,6 +226,8 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 
 		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;
 	}
-- 
2.24.1.1152.gda0b849012


^ permalink raw reply	[flat|nested] 51+ messages in thread

* [PATCH 3/3] commit-graph: stop using full rev_info for diffs
  2019-12-22  9:30 ` Jeff King
  2019-12-22  9:32   ` [PATCH 1/3] commit-graph: examine changed-path objects in pack order Jeff King
  2019-12-22  9:32   ` [PATCH 2/3] commit-graph: free large diffs, too Jeff King
@ 2019-12-22  9:32   ` Jeff King
  2019-12-27 14:53     ` Derrick Stolee
  2019-12-26 14:21   ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Derrick Stolee
  2019-12-27 16:11   ` Derrick Stolee
  4 siblings, 1 reply; 51+ messages in thread
From: Jeff King @ 2019-12-22  9:32 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, Junio C Hamano

When we perform a diff to get the set of changed paths for a commit,
we initialize a full "struct rev_info" with setup_revisions(). But the
only part of it we use is the diff_options struct. Besides being overly
complex, this also leaks memory, as we use the fake argv to
setup_revisions() create a pending array which is never cleared.

Let's just use diff_options directly. This reduces the peak heap usage
of "git commit-graph write --changed-paths" on linux.git from ~4GB to
~1.2GB.

Signed-off-by: Jeff King <peff@peff.net>
---
 bloom.c | 16 +++++++---------
 1 file changed, 7 insertions(+), 9 deletions(-)

diff --git a/bloom.c b/bloom.c
index d1d3796e11..ea77631cc2 100644
--- a/bloom.c
+++ b/bloom.c
@@ -154,8 +154,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 	struct bloom_filter *filter;
 	struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
 	int i;
-	struct rev_info revs;
-	const char *revs_argv[] = {NULL, "HEAD", NULL};
+	struct diff_options diffopt;
 
 	filter = bloom_filter_slab_at(&bloom_filters, c);
 
@@ -170,16 +169,15 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 	if (filter->data || !compute_if_null)
 			return filter;
 
-	init_revisions(&revs, NULL);
-	revs.diffopt.flags.recursive = 1;
-
-	setup_revisions(2, revs_argv, &revs, NULL);
+	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, "", &revs.diffopt);
+		diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt);
 	else
-		diff_tree_oid(NULL, &c->object.oid, "", &revs.diffopt);
-	diffcore_std(&revs.diffopt);
+		diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
+	diffcore_std(&diffopt);
 
 	if (diff_queued_diff.nr <= 512) {
 		struct hashmap pathmap;
-- 
2.24.1.1152.gda0b849012

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-22  9:26 ` Christian Couder
@ 2019-12-22  9:38   ` Jeff King
  2020-01-01 12:04     ` Jakub Narebski
  0 siblings, 1 reply; 51+ messages in thread
From: Jeff King @ 2019-12-22  9:38 UTC (permalink / raw)
  To: Christian Couder
  Cc: Garima Singh via GitGitGadget, git, Derrick Stolee,
	SZEDER Gábor, Jonathan Tan, Jeff Hostetler, Taylor Blau,
	Junio C Hamano

On Sun, Dec 22, 2019 at 10:26:20AM +0100, Christian Couder wrote:

> I have a question though. Are the performance gains only available
> with `git log -- path` or are they already available for example when
> doing a partial clone and/or a sparse checkout?

From my quick look at the code, anything that feeds a pathspec to a
revision traversal would be helped. I'm not sure if it would help for
partial/sparse traversals, though. There we actually need to know which
blobs correspond to the paths in question, not just whether any
particular commit touched them.

I also took a brief look at adding support to the custom blame-tree
implementation we use at GitHub, and got about a 6x speedup.

> > This series is intended to start the conversation and many of the commit
> > messages include specific call outs for suggestions and thoughts.
> 
> I think Peff said during the Virtual Contributor Summit that he was
> interested in using bitmaps to speed up partial clone on the server
> side. Would it make sense to use both bitmaps and bloom filters?

I think they're orthogonal. For size-based filters on blobs, you'd just
use bitmaps as normal, because you can post-process the result to check
the type and size of each object in the list (and I have patches to do
this, but they need some polishing and we're not yet running them).

For path-based filters like a sparse specification, you can't use
bitmaps at all; you have to do a real traversal. But there you still
generally get all of the commits. I guess if a commit doesn't touch any
path you're interested in, you could avoid walking into its tree at all,
which might help. I haven't given it much thought yet.

-Peff

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-22  9:30 ` Jeff King
                     ` (2 preceding siblings ...)
  2019-12-22  9:32   ` [PATCH 3/3] commit-graph: stop using full rev_info for diffs Jeff King
@ 2019-12-26 14:21   ` Derrick Stolee
  2019-12-29  6:03     ` Jeff King
  2019-12-27 16:11   ` Derrick Stolee
  4 siblings, 1 reply; 51+ messages in thread
From: Derrick Stolee @ 2019-12-26 14:21 UTC (permalink / raw)
  To: Jeff King, Garima Singh via GitGitGadget
  Cc: git, szeder.dev, jonathantanmy, jeffhost, me, Junio C Hamano

On 12/22/2019 4:30 AM, Jeff King wrote:
> On Fri, Dec 20, 2019 at 10:05:11PM +0000, Garima Singh via GitGitGadget wrote:
> 
>> 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 approach [2] and
>> presents an updated and more polished RFC version of the feature.
> 
> Great to see progress here. I probably won't have time to review this
> carefully before the new year, but I did notice some low-hanging fruit
> on the generation side.
> 
> So here are a few patches to reduce the CPU and memory usage. They could
> be squashed in at the appropriate spots, or perhaps taken as inspiration
> if there are better solutions (especially for the first one).
> 
> I think we could go further still, by actually doing a non-recursive
> diff_tree_oid(), and then recursing into sub-trees ourselves. That would
> save us having to split apart each path to add the leading paths to the
> hashmap (most of which will be duplicates if the commit touched "a/b/c"
> and "a/b/d", etc). I doubt it would be that huge a speedup though. We
> have to keep a list of the touched paths anyway (since the bloom key
> parameters depend on the number of entries), and most of the time is
> almost certainly spent inflating the trees in the first place. However
> it might be easier to follow the code, and it would make it simpler to
> stop traversing at the 512-entry limit, rather than generating a huge
> diff only to throw it away.

Thanks for these improvements. This diff machinery is new to us (Garima
and myself).

Here are some recommendations (to Garima) for how to proceed with these
patches. Please let me know if anyone disagrees.

>   [1/3]: commit-graph: examine changed-path objects in pack order

This one is best kept as its own patch, as it shows a clear reason why
we want to do the sort-by-position. It would also be a complicated
patch to include this logic along with the first use of
compute_bloom_filters().

>   [2/3]: commit-graph: free large diffs, too
This one seems best to squash into "commit-graph: write changed paths
bloom filters" with a Helped-by for Peff.

>   [3/3]: commit-graph: stop using full rev_info for diffs

While I appreciate the clear benefit in the commit-message here, it
may be best to also squash this one similarly.

Of course, if we create our own diff logic with the short-circuit
capability, then perhaps these patches become obsolete. I'll spend
a little time playing with options here.

Thanks!
-Stolee

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 1/3] commit-graph: examine changed-path objects in pack order
  2019-12-22  9:32   ` [PATCH 1/3] commit-graph: examine changed-path objects in pack order Jeff King
@ 2019-12-27 14:51     ` Derrick Stolee
  2019-12-29  6:12       ` Jeff King
  0 siblings, 1 reply; 51+ messages in thread
From: Derrick Stolee @ 2019-12-27 14:51 UTC (permalink / raw)
  To: Jeff King, Garima Singh via GitGitGadget
  Cc: git, szeder.dev, jonathantanmy, jeffhost, me, Junio C Hamano

On 12/22/2019 4:32 AM, Jeff King wrote:
> 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.

I'm doing my own perf tests on these patches, and my copy of linux.git
has four packs of varying sizes (corresponding with my rare fetches and
lack of repacks). My time goes from 3m50s to 3m00s. I was confused at
first, but then realized that I used the "--reachable" flag. In that
case, we never run set_commit_pos(), so all positions are equal and the
sort is not helpful.

I thought that inserting some set_commit_pos() calls into close_reachable()
and add_missing_parents() would give some amount of time-order to the
commits as we compute the filters. However, the time did not change at
all.

I've included the patch below for reference, anyway.

Thanks,
-Stolee

-->8--

From e7c63d8db09be81ce213ba7f112bb3d2f537bf4a Mon Sep 17 00:00:00 2001
From: Derrick Stolee <dstolee@microsoft.com>
Date: Fri, 27 Dec 2019 09:47:49 -0500
Subject: [PATCH] commit-graph: set commit positions for --reachable

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.

Add calls to set_commit_pos() when walking the reachable commits,
which provides an ordering similar to a topological ordering.

Unfortunately, the performance did not improve with this change.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/commit-graph.c b/commit-graph.c
index bf6c663772..a6c4ab401e 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1126,6 +1126,8 @@ static void add_missing_parents(struct write_commit_graph_context *ctx, struct c
 			oidcpy(&ctx->oids.list[ctx->oids.nr], &(parent->item->object.oid));
 			ctx->oids.nr++;
 			parent->item->object.flags |= REACHABLE;
+
+			set_commit_pos(ctx->r, &parent->item->object.oid);
 		}
 	}
 }
@@ -1142,8 +1144,10 @@ static void close_reachable(struct write_commit_graph_context *ctx)
 	for (i = 0; i < ctx->oids.nr; i++) {
 		display_progress(ctx->progress, i + 1);
 		commit = lookup_commit(ctx->r, &ctx->oids.list[i]);
-		if (commit)
+		if (commit) {
 			commit->object.flags |= REACHABLE;
+			set_commit_pos(ctx->r, &commit->object.oid);
+		}
 	}
 	stop_progress(&ctx->progress);
 
-- 
2.25.0.rc0


^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 2/3] commit-graph: free large diffs, too
  2019-12-22  9:32   ` [PATCH 2/3] commit-graph: free large diffs, too Jeff King
@ 2019-12-27 14:52     ` Derrick Stolee
  0 siblings, 0 replies; 51+ messages in thread
From: Derrick Stolee @ 2019-12-27 14:52 UTC (permalink / raw)
  To: Jeff King, Garima Singh via GitGitGadget
  Cc: git, szeder.dev, jonathantanmy, jeffhost, me, Junio C Hamano

On 12/22/2019 4:32 AM, Jeff King wrote:
> If a diff we compute for --changed-path has more than 512 entries, we
> don't bother generating a bloom filter for it. But since we don't
> iterate over diff_queued_diff, we also don't free the filepairs and
> filespecs from the diff before clearing the queue. Let's make sure we do
> so.
> 
> This drops the peak heap usage of "commit-graph write --changed-paths"
> on linux.git from ~8GB to ~4GB.

In my testing, the heap size went from ~10gb to ~6gb.

Thanks,
-Stolee

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 3/3] commit-graph: stop using full rev_info for diffs
  2019-12-22  9:32   ` [PATCH 3/3] commit-graph: stop using full rev_info for diffs Jeff King
@ 2019-12-27 14:53     ` Derrick Stolee
  0 siblings, 0 replies; 51+ messages in thread
From: Derrick Stolee @ 2019-12-27 14:53 UTC (permalink / raw)
  To: Jeff King, Garima Singh via GitGitGadget
  Cc: git, szeder.dev, jonathantanmy, jeffhost, me, Junio C Hamano

On 12/22/2019 4:32 AM, Jeff King wrote:
> When we perform a diff to get the set of changed paths for a commit,
> we initialize a full "struct rev_info" with setup_revisions(). But the
> only part of it we use is the diff_options struct. Besides being overly
> complex, this also leaks memory, as we use the fake argv to
> setup_revisions() create a pending array which is never cleared.
> 
> Let's just use diff_options directly. This reduces the peak heap usage
> of "git commit-graph write --changed-paths" on linux.git from ~4GB to
> ~1.2GB.

In my testing, this went from ~6gb to ~4gb.

I'm guessing that my memory difference is related to how poorly my
packs are repacked/redeltified.

Thanks,
-Stolee


^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-22  9:30 ` Jeff King
                     ` (3 preceding siblings ...)
  2019-12-26 14:21   ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Derrick Stolee
@ 2019-12-27 16:11   ` Derrick Stolee
  2019-12-29  6:24     ` Jeff King
  4 siblings, 1 reply; 51+ messages in thread
From: Derrick Stolee @ 2019-12-27 16:11 UTC (permalink / raw)
  To: Jeff King, Garima Singh via GitGitGadget
  Cc: git, szeder.dev, jonathantanmy, jeffhost, me, Junio C Hamano

On 12/22/2019 4:30 AM, Jeff King wrote:
> On Fri, Dec 20, 2019 at 10:05:11PM +0000, Garima Singh via GitGitGadget wrote:
> 
>> 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 approach [2] and
>> presents an updated and more polished RFC version of the feature.
> 
> Great to see progress here. I probably won't have time to review this
> carefully before the new year, but I did notice some low-hanging fruit
> on the generation side.
> 
> So here are a few patches to reduce the CPU and memory usage. They could
> be squashed in at the appropriate spots, or perhaps taken as inspiration
> if there are better solutions (especially for the first one).

I tested these patches with the Linux kernel repo and reported my results
on each patch. However, I wanted to also test on a larger internal repo
(the AzureDevOps repo), which has ~500 commits with more than 512 changes,
and generally has larger diffs than the Linux kernel repo.

| Version  | Time   | Memory |
|----------|--------|--------|
| Garima   | 16m36s | 27.0gb |
| Peff 1   | 6m32s  | 28.0gb |
| Peff 2   | 6m48s  |  5.6gb |
| Peff 3   | 6m14s  |  4.5gb |
| Shortcut | 3m47s  |  4.5gb |

For reference, I found the time and memory information using
"/usr/bin/time --verbose" in a bash script.
 
> I think we could go further still, by actually doing a non-recursive
> diff_tree_oid(), and then recursing into sub-trees ourselves. That would
> save us having to split apart each path to add the leading paths to the
> hashmap (most of which will be duplicates if the commit touched "a/b/c"
> and "a/b/d", etc). I doubt it would be that huge a speedup though. We
> have to keep a list of the touched paths anyway (since the bloom key
> parameters depend on the number of entries), and most of the time is
> almost certainly spent inflating the trees in the first place. However
> it might be easier to follow the code, and it would make it simpler to
> stop traversing at the 512-entry limit, rather than generating a huge
> diff only to throw it away.

By "Shortcut" in the table above, I mean the following patch on top of
Garima's and Peff's changes. It inserts a max_changes option into struct
diff_options to halt the diff early. This seemed like an easier change
than creating a new tree diff algorithm wholesale.

Thanks,
-Stolee

-->8--

From: Derrick Stolee <dstolee@microsoft.com>
Date: Fri, 27 Dec 2019 10:13:48 -0500
Subject: [PATCH] diff: halt tree-diff early after max_changes

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. For a larger repo with more commits changing
many paths, the time reduces from 6 minutes to under 4 minutes.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 bloom.c     | 4 +++-
 diff.h      | 5 +++++
 tree-diff.c | 5 +++++
 3 files changed, 13 insertions(+), 1 deletion(-)

diff --git a/bloom.c b/bloom.c
index ea77631cc2..83dde2378b 100644
--- a/bloom.c
+++ b/bloom.c
@@ -155,6 +155,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;
 
 	filter = bloom_filter_slab_at(&bloom_filters, c);
 
@@ -171,6 +172,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)
@@ -179,7 +181,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;
diff --git a/diff.h b/diff.h
index 6febe7e365..9443dc1b00 100644
--- a/diff.h
+++ b/diff.h
@@ -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)
diff --git a/tree-diff.c b/tree-diff.c
index 33ded7f8b3..16a21d9f34 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -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++;
 		}
 	}
 
-- 
2.25.0.rc0


^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-26 14:21   ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Derrick Stolee
@ 2019-12-29  6:03     ` Jeff King
  0 siblings, 0 replies; 51+ messages in thread
From: Jeff King @ 2019-12-29  6:03 UTC (permalink / raw)
  To: Derrick Stolee
  Cc: Garima Singh via GitGitGadget, git, szeder.dev, jonathantanmy,
	jeffhost, me, Junio C Hamano

On Thu, Dec 26, 2019 at 09:21:36AM -0500, Derrick Stolee wrote:

> Here are some recommendations (to Garima) for how to proceed with these
> patches. Please let me know if anyone disagrees.
> 
> >   [1/3]: commit-graph: examine changed-path objects in pack order
> 
> This one is best kept as its own patch, as it shows a clear reason why
> we want to do the sort-by-position. It would also be a complicated
> patch to include this logic along with the first use of
> compute_bloom_filters().

Yeah, I'd agree this one could be a separate patch. It does need more
work, though (as you found out, it does not cover --reachable at all).

The position counter also probably ought to be an unsigned (or even a
uint32_t, which we usually consider a maximum bound for number of
objects).

-Peff

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 1/3] commit-graph: examine changed-path objects in pack order
  2019-12-27 14:51     ` Derrick Stolee
@ 2019-12-29  6:12       ` Jeff King
  2019-12-29  6:28         ` Jeff King
  2019-12-30 14:37         ` Derrick Stolee
  0 siblings, 2 replies; 51+ messages in thread
From: Jeff King @ 2019-12-29  6:12 UTC (permalink / raw)
  To: Derrick Stolee
  Cc: Garima Singh via GitGitGadget, git, szeder.dev, jonathantanmy,
	jeffhost, me, Junio C Hamano

On Fri, Dec 27, 2019 at 09:51:02AM -0500, Derrick Stolee wrote:

> On 12/22/2019 4:32 AM, Jeff King wrote:
> > 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.
> 
> I'm doing my own perf tests on these patches, and my copy of linux.git
> has four packs of varying sizes (corresponding with my rare fetches and
> lack of repacks). My time goes from 3m50s to 3m00s. I was confused at
> first, but then realized that I used the "--reachable" flag. In that
> case, we never run set_commit_pos(), so all positions are equal and the
> sort is not helpful.
> 
> I thought that inserting some set_commit_pos() calls into close_reachable()
> and add_missing_parents() would give some amount of time-order to the
> commits as we compute the filters. However, the time did not change at
> all.
> 
> I've included the patch below for reference, anyway.

Yeah, I expected that would cover it, too. But instrumenting it to dump
the position of each commit (see patch below), and then decorating "git
log" output with the positions (see script below) shows that we're all
over the map:

  *   3
  |\  
  | * 2791
  | * 5476
  | * 8520
  | * 12040
  | * 16036
  * |   2790
  |\ \  
  | * | 5475
  | * | 8519
  | * | 12039
  | * | 16035
  | * | 20517
  | * | 25527
  | |/  
  * |   5474
  |\ \  
  | * | 8518
  | * | 12038
  * | |   8517
  [...]

I think the root issue is that we never do any date-sorting on the
commits. So:

  - we hit each ref tip in lexical order; with tags, this is quite often
    the opposite of reverse-chronological

  - we traverse breadth-first, but we don't order queue at all. So if we
    see a merge X, then we'll next process X^1 and X^2, and then X^1^,
    and then X^2^, and so forth. So we keep digging equally down
    simultaneous branches, even if one branch is way shorter than the
    other. Whereas a regular Git traversal will order the queue by
    commit timestamp, so it tends to be roughly chronological (of course
    a topo-sort would work too, but that's probably overkill).

I wonder if this would be simpler if "commit-graph --reachable" just
used the regular revision machinery instead of doing its own custom
traversal.

-Peff

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-27 16:11   ` Derrick Stolee
@ 2019-12-29  6:24     ` Jeff King
  2019-12-30 16:04       ` Derrick Stolee
  2019-12-30 17:02       ` Junio C Hamano
  0 siblings, 2 replies; 51+ messages in thread
From: Jeff King @ 2019-12-29  6:24 UTC (permalink / raw)
  To: Derrick Stolee
  Cc: Garima Singh via GitGitGadget, git, szeder.dev, jonathantanmy,
	jeffhost, me, Junio C Hamano

On Fri, Dec 27, 2019 at 11:11:37AM -0500, Derrick Stolee wrote:

> > So here are a few patches to reduce the CPU and memory usage. They could
> > be squashed in at the appropriate spots, or perhaps taken as inspiration
> > if there are better solutions (especially for the first one).
> 
> I tested these patches with the Linux kernel repo and reported my results
> on each patch. However, I wanted to also test on a larger internal repo
> (the AzureDevOps repo), which has ~500 commits with more than 512 changes,
> and generally has larger diffs than the Linux kernel repo.
> 
> | Version  | Time   | Memory |
> |----------|--------|--------|
> | Garima   | 16m36s | 27.0gb |
> | Peff 1   | 6m32s  | 28.0gb |
> | Peff 2   | 6m48s  |  5.6gb |
> | Peff 3   | 6m14s  |  4.5gb |
> | Shortcut | 3m47s  |  4.5gb |
> 
> For reference, I found the time and memory information using
> "/usr/bin/time --verbose" in a bash script.

Thanks for giving it more exercise. My heap profiling was done with
massif, which measures the heap directly. Measuring RSS would cover
that, but will also include the mmap'd packfiles. That's probably why
your linux.git numbers were slightly higher than mine.

(massif is a really great tool if you haven't used it, as it also shows
which allocations were using the memory. But it's part of valgrind, so
it definitely doesn't run on native Windows. It might work under WSL,
though. I'm sure there are also other heap profilers on Windows).

> By "Shortcut" in the table above, I mean the following patch on top of
> Garima's and Peff's changes. It inserts a max_changes option into struct
> diff_options to halt the diff early. This seemed like an easier change
> than creating a new tree diff algorithm wholesale.

Yeah, I'm not opposed to a diff feature like this.

But be careful, because...

> diff --git a/diff.h b/diff.h
> index 6febe7e365..9443dc1b00 100644
> --- a/diff.h
> +++ b/diff.h
> @@ -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;

This is holding internal state in diff_options, but the same
diff_options is often used for multiple diffs (e.g., "git log --raw"
would use the same rev_info.diffopt over and over again).

So it would need to be cleared between diffs. There's a similar feature
in the "has_changes" flag, though it looks like it is cleared manually
by callers. Yuck.

This isn't a problem for commit-graph right now, but:

  - it actually could be using a single diff_options, which would be
    slightly simpler (it doesn't seem to save much CPU, though, because
    the initialization is relatively cheap)

  - it's a bit of a subtle bug to leave hanging around for the next
    person who tries to use the feature

I actually wonder if this could be rolled into the has_changes and
diff_can_quit_early() feature. This really just a generalization of that
feature (which is like setting max_changes to "1").

-Peff

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 1/3] commit-graph: examine changed-path objects in pack order
  2019-12-29  6:12       ` Jeff King
@ 2019-12-29  6:28         ` Jeff King
  2019-12-30 14:37         ` Derrick Stolee
  1 sibling, 0 replies; 51+ messages in thread
From: Jeff King @ 2019-12-29  6:28 UTC (permalink / raw)
  To: Derrick Stolee
  Cc: Garima Singh via GitGitGadget, git, szeder.dev, jonathantanmy,
	jeffhost, me, Junio C Hamano

On Sun, Dec 29, 2019 at 01:12:46AM -0500, Jeff King wrote:

> Yeah, I expected that would cover it, too. But instrumenting it to dump
> the position of each commit (see patch below), and then decorating "git
> log" output with the positions (see script below) shows that we're all
> over the map:

I forgot the patch, of course. :)

I just dumped this trace:

---
diff --git a/commit-graph.c b/commit-graph.c
index a6c4ab401e..1cb77be45f 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -61,6 +61,7 @@ static void set_commit_pos(struct repository *r, const struct object_id *oid)
 	if (!commit)
 		return; /* should never happen, but be lenient */
 
+	trace_printf("pos %s = %d", oid_to_hex(oid), max_pos);
 	*commit_pos_at(&commit_pos, commit) = max_pos++;
 }
 

with:

  rm -f .git/objects/info/commit-graph
  GIT_TRACE=$PWD/trace.out git commit-graph write --changed-paths --reachable

and then used:

  cat >foo.pl <<\EOF
  #!/usr/bin/perl
  
  my %deco = do {
  	open(my $fh, '<', 'trace.out');
  	map { /pos (\S+) = (\d+)/ ? ($1 => $2) : () } <$fh>
  };
  while (<>) {
  	s/([0-9a-f]{40})/$deco{$1}/;
  	print;
  }
  EOF

like so:

  git log --graph --format=%H |
  perl foo.pl |
  less

-Peff

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 1/3] commit-graph: examine changed-path objects in pack order
  2019-12-29  6:12       ` Jeff King
  2019-12-29  6:28         ` Jeff King
@ 2019-12-30 14:37         ` Derrick Stolee
  2019-12-30 14:51           ` Derrick Stolee
  1 sibling, 1 reply; 51+ messages in thread
From: Derrick Stolee @ 2019-12-30 14:37 UTC (permalink / raw)
  To: Jeff King
  Cc: Garima Singh via GitGitGadget, git, szeder.dev, jonathantanmy,
	jeffhost, me, Junio C Hamano

On 12/29/2019 1:12 AM, Jeff King wrote:
> On Fri, Dec 27, 2019 at 09:51:02AM -0500, Derrick Stolee wrote:
> 
>> On 12/22/2019 4:32 AM, Jeff King wrote:
>>> 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.
>>
>> I'm doing my own perf tests on these patches, and my copy of linux.git
>> has four packs of varying sizes (corresponding with my rare fetches and
>> lack of repacks). My time goes from 3m50s to 3m00s. I was confused at
>> first, but then realized that I used the "--reachable" flag. In that
>> case, we never run set_commit_pos(), so all positions are equal and the
>> sort is not helpful.
>>
>> I thought that inserting some set_commit_pos() calls into close_reachable()
>> and add_missing_parents() would give some amount of time-order to the
>> commits as we compute the filters. However, the time did not change at
>> all.
>>
>> I've included the patch below for reference, anyway.
> 
> Yeah, I expected that would cover it, too. But instrumenting it to dump
> the position of each commit (see patch below), and then decorating "git
> log" output with the positions (see script below) shows that we're all
> over the map:
> 
>   *   3
>   |\  
>   | * 2791
>   | * 5476
>   | * 8520
>   | * 12040
>   | * 16036
>   * |   2790
>   |\ \  
>   | * | 5475
>   | * | 8519
>   | * | 12039
>   | * | 16035
>   | * | 20517
>   | * | 25527
>   | |/  
>   * |   5474
>   |\ \  
>   | * | 8518
>   | * | 12038
>   * | |   8517
>   [...]

This makes a lot of sense why the previous approach did not work. Thanks!

> I think the root issue is that we never do any date-sorting on the
> commits. So:
> 
>   - we hit each ref tip in lexical order; with tags, this is quite often
>     the opposite of reverse-chronological
> 
>   - we traverse breadth-first, but we don't order queue at all. So if we
>     see a merge X, then we'll next process X^1 and X^2, and then X^1^,
>     and then X^2^, and so forth. So we keep digging equally down
>     simultaneous branches, even if one branch is way shorter than the
>     other. Whereas a regular Git traversal will order the queue by
>     commit timestamp, so it tends to be roughly chronological (of course
>     a topo-sort would work too, but that's probably overkill).
> 
> I wonder if this would be simpler if "commit-graph --reachable" just
> used the regular revision machinery instead of doing its own custom
> traversal.

Instead, why not use our already-computed generation numbers? That seems
to improve the time a bit. (6m30s to 4m50s)

-->8--

From: Derrick Stolee <dstolee@microsoft.com>
Date: Fri, 27 Dec 2019 09:47:49 -0500
Subject: [PATCH] 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.

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
6m30s to 4m50s.

Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c | 33 ++++++++++++++++++++++++++++++---
 1 file changed, 30 insertions(+), 3 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index bf6c663772..fe4ab545f2 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -72,6 +72,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(const char *obj_dir)
 {
 	char *filename = xstrfmt("%s/info/commit-graph", obj_dir);
@@ -849,7 +868,8 @@ struct write_commit_graph_context {
 		 report_progress:1,
 		 split:1,
 		 check_oids:1,
-		 bloom:1;
+		 bloom:1,
+		 order_by_pack:1;
 
 	const struct split_commit_graph_opts *split_opts;
 	uint32_t total_bloom_filter_size;
@@ -1245,7 +1265,11 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 
 	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);
+
+	if (ctx->order_by_pack)
+		QSORT(sorted_by_pos, ctx->commits.nr, commit_pos_cmp);
+	else
+		QSORT(sorted_by_pos, ctx->commits.nr, commit_gen_cmp);
 
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = sorted_by_pos[i];
@@ -1979,6 +2003,7 @@ int write_commit_graph(const char *obj_dir,
 	}
 
 	if (pack_indexes) {
+		ctx->order_by_pack = 1;
 		if ((res = fill_oids_from_packs(ctx, pack_indexes)))
 			goto cleanup;
 	}
@@ -1988,8 +2013,10 @@ int write_commit_graph(const char *obj_dir,
 			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);
 
-- 
2.25.0.rc0




^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 1/3] commit-graph: examine changed-path objects in pack order
  2019-12-30 14:37         ` Derrick Stolee
@ 2019-12-30 14:51           ` Derrick Stolee
  0 siblings, 0 replies; 51+ messages in thread
From: Derrick Stolee @ 2019-12-30 14:51 UTC (permalink / raw)
  To: Jeff King
  Cc: Garima Singh via GitGitGadget, git, szeder.dev, jonathantanmy,
	jeffhost, me, Junio C Hamano

On 12/30/2019 9:37 AM, Derrick Stolee wrote:
> On the Linux kernel repository, this change reduced the computation
> time for 'git commit-graph write --reachable --changed-paths' from
> 6m30s to 4m50s.

I apologize, these numbers are based on the AzureDevOps repo, not the
Linux kernel repo. After re-running with the Linux kernel repo my
times improve from 3m00s to 1m37s.

-Stolee



^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-29  6:24     ` Jeff King
@ 2019-12-30 16:04       ` Derrick Stolee
  2019-12-30 17:02       ` Junio C Hamano
  1 sibling, 0 replies; 51+ messages in thread
From: Derrick Stolee @ 2019-12-30 16:04 UTC (permalink / raw)
  To: Jeff King
  Cc: Garima Singh via GitGitGadget, git, szeder.dev, jonathantanmy,
	jeffhost, me, Junio C Hamano

On 12/29/2019 1:24 AM, Jeff King wrote:
> On Fri, Dec 27, 2019 at 11:11:37AM -0500, Derrick Stolee wrote:
> 
>>> So here are a few patches to reduce the CPU and memory usage. They could
>>> be squashed in at the appropriate spots, or perhaps taken as inspiration
>>> if there are better solutions (especially for the first one).
>>
>> I tested these patches with the Linux kernel repo and reported my results
>> on each patch. However, I wanted to also test on a larger internal repo
>> (the AzureDevOps repo), which has ~500 commits with more than 512 changes,
>> and generally has larger diffs than the Linux kernel repo.
>>
>> | Version  | Time   | Memory |
>> |----------|--------|--------|
>> | Garima   | 16m36s | 27.0gb |
>> | Peff 1   | 6m32s  | 28.0gb |
>> | Peff 2   | 6m48s  |  5.6gb |
>> | Peff 3   | 6m14s  |  4.5gb |
>> | Shortcut | 3m47s  |  4.5gb |
>>
>> For reference, I found the time and memory information using
>> "/usr/bin/time --verbose" in a bash script.
> 
> Thanks for giving it more exercise. My heap profiling was done with
> massif, which measures the heap directly. Measuring RSS would cover
> that, but will also include the mmap'd packfiles. That's probably why
> your linux.git numbers were slightly higher than mine.

That's interesting. I initially avoided massif because it is so much
slower than /usr/bin/time. However, the inflated numbers could be
explained by that. Also, the distinction between mem_heap and
mem_heap_extra may have interesting implications. Looking online, it
seems that large mem_heap_extra implies the heap is fragmented from
many small allocations.

Here are my findings on the Linux repo:

| Version  | mem_heap | mem_heap_extra |
|----------|----------|----------------|
| Peff 1   |  6,500mb |          913mb |
| Peff 2   |  3,100mb |          286mb |
| Peff 3   |    781mb |          235mb |

These numbers more closely match your numbers (in sum of the two
columns).

> (massif is a really great tool if you haven't used it, as it also shows
> which allocations were using the memory. But it's part of valgrind, so
> it definitely doesn't run on native Windows. It might work under WSL,
> though. I'm sure there are also other heap profilers on Windows).

I am using my Linux machine for my tests. Garima is using her Windows
machine.

>> By "Shortcut" in the table above, I mean the following patch on top of
>> Garima's and Peff's changes. It inserts a max_changes option into struct
>> diff_options to halt the diff early. This seemed like an easier change
>> than creating a new tree diff algorithm wholesale.
> 
> Yeah, I'm not opposed to a diff feature like this.
> 
> But be careful, because...
> 
>> diff --git a/diff.h b/diff.h
>> index 6febe7e365..9443dc1b00 100644
>> --- a/diff.h
>> +++ b/diff.h
>> @@ -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;
> 
> This is holding internal state in diff_options, but the same
> diff_options is often used for multiple diffs (e.g., "git log --raw"
> would use the same rev_info.diffopt over and over again).
> 
> So it would need to be cleared between diffs. There's a similar feature
> in the "has_changes" flag, though it looks like it is cleared manually
> by callers. Yuck.

You're right about this. What if we initialize it in diff_tree_paths()
before it calls the recursive ll_difF_tree_paths()?

> This isn't a problem for commit-graph right now, but:
> 
>   - it actually could be using a single diff_options, which would be
>     slightly simpler (it doesn't seem to save much CPU, though, because
>     the initialization is relatively cheap)
> 
>   - it's a bit of a subtle bug to leave hanging around for the next
>     person who tries to use the feature
> 
> I actually wonder if this could be rolled into the has_changes and
> diff_can_quit_early() feature. This really just a generalization of that
> feature (which is like setting max_changes to "1").

I thought about this at first, but it only takes a struct diff_options
right now. It does have an internally-mutated member (flags.has_changes)
but it also seems a bit wrong to add a uint32_t of the count in this.
Changing the prototype could be messy, too.

There are also multiple callers, and limiting everything to tree-diff.c
limits the impact.

Thanks,
-Stolee

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-29  6:24     ` Jeff King
  2019-12-30 16:04       ` Derrick Stolee
@ 2019-12-30 17:02       ` Junio C Hamano
  1 sibling, 0 replies; 51+ messages in thread
From: Junio C Hamano @ 2019-12-30 17:02 UTC (permalink / raw)
  To: Jeff King
  Cc: Derrick Stolee, Garima Singh via GitGitGadget, git, szeder.dev,
	jonathantanmy, jeffhost, me

Jeff King <peff@peff.net> writes:

> This is holding internal state in diff_options, but the same
> diff_options is often used for multiple diffs (e.g., "git log --raw"
> would use the same rev_info.diffopt over and over again).
>
> So it would need to be cleared between diffs. There's a similar feature
> in the "has_changes" flag, though it looks like it is cleared manually
> by callers. Yuck.

Do you mean we want reset_per_invocation_part_of_diff_options()
helper or something?

> I actually wonder if this could be rolled into the has_changes and
> diff_can_quit_early() feature. This really just a generalization of that
> feature (which is like setting max_changes to "1").

Yeah, I wondered about the same thing, after seeing the impressive
numbers ;-)

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (11 preceding siblings ...)
  2019-12-22  9:30 ` Jeff King
@ 2019-12-31 16:45 ` Jakub Narebski
  2020-01-13 16:54   ` Garima Singh
  2020-01-21 23:40 ` Emily Shaffer
  13 siblings, 1 reply; 51+ messages in thread
From: Jakub Narebski @ 2019-12-31 16:45 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> 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 approach [2] and
> presents an updated and more polished RFC version of the feature. 

It is nice to have this picked up for upstream, finally.  The proof of
concept works[1][2] were started more than a year ago.

On the other hand slow and steady adoption of commit-graph serialization
and then extending it (generation numbers, topological sort, incremental
update) feels like a good approach.

> Performance Gains: We tested the performance of 'git log -- <path>' on the git
> repo, the linux repo 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.

Could you provide some more statistics about this internal repository,
such as number of files, number of commits, perhaps also number of all
objects?  Thanks in advance.

I wonder why such large difference in performance 2-5x vs 10-20x.  Is it
about the depth of the file hierarchy?  How would the numbers look for
files seated closer to the root in the same large repository, like 3-5
levels deep in the tree?

> Future Work (not included in the scope of this series):
>
>  1. Supporting multiple path based revision walk

I wonder if it would ever be possible to support globbing, e.g. '*.c'

>  2. Adopting it in git blame logic.

What about 'git log --follow <path>'?

>  3. Interactions with line log git log -L
>
> This series is intended to start the conversation and many of the commit
> messages include specific call outs for suggestions and thoughts. 
>
> Cheers! Garima Singh
>
> [1] https://lore.kernel.org/git/20181009193445.21908-1-szeder.dev@gmail.com/
> [2] https://lore.kernel.org/git/61559c5b-546e-d61b-d2e1-68de692f5972@gmail.com/
>
> Garima Singh (9):
>   commit-graph: add --changed-paths option to write

This summary is not easy to understand on first glance.  Maybe:

    commit-graph: add --changed-paths option to the write subcommand

or

    commit-graph: add --changed-paths option to 'git commit-graph write'

would be better?

>   commit-graph: write changed paths bloom filters
>   commit-graph: use MAX_NUM_CHUNKS
>   commit-graph: document bloom filter format
>   commit-graph: write changed path bloom filters to commit-graph file.
>   commit-graph: test commit-graph write --changed-paths
>   commit-graph: reuse existing bloom filters during write.
>   revision.c: use bloom filters to speed up path based revision walks
>   commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag
>
>  Documentation/git-commit-graph.txt            |   5 +
>  .../technical/commit-graph-format.txt         |  17 ++
>  Makefile                                      |   1 +
>  bloom.c                                       | 257 +++++++++++++++++
>  bloom.h                                       |  51 ++++
>  builtin/commit-graph.c                        |   9 +-
>  ci/run-build-and-tests.sh                     |   1 +
>  commit-graph.c                                | 116 +++++++-
>  commit-graph.h                                |   9 +-
>  revision.c                                    |  67 ++++-
>  revision.h                                    |   5 +
>  t/README                                      |   3 +
>  t/helper/test-read-graph.c                    |   4 +
>  t/t4216-log-bloom.sh                          |  77 ++++++
>  t/t5318-commit-graph.sh                       |   2 +
>  t/t5324-split-commit-graph.sh                 |   1 +
>  t/t5325-commit-graph-bloom.sh                 | 258 ++++++++++++++++++
>  17 files changed, 875 insertions(+), 8 deletions(-)
>  create mode 100644 bloom.c
>  create mode 100644 bloom.h
>  create mode 100755 t/t4216-log-bloom.sh
>  create mode 100755 t/t5325-commit-graph-bloom.sh
>
>
> base-commit: b02fd2accad4d48078671adf38fe5b5976d77304
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-497%2Fgarimasi514%2FcoreGit-bloomFilters-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-497/garimasi514/coreGit-bloomFilters-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/497

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-22  9:38   ` Jeff King
@ 2020-01-01 12:04     ` Jakub Narebski
  0 siblings, 0 replies; 51+ messages in thread
From: Jakub Narebski @ 2020-01-01 12:04 UTC (permalink / raw)
  To: Jeff King
  Cc: Christian Couder, Garima Singh via GitGitGadget, git,
	Derrick Stolee, SZEDER Gábor, Jonathan Tan, Jeff Hostetler,
	Taylor Blau, Junio C Hamano

Jeff King <peff@peff.net> writes:

> On Sun, Dec 22, 2019 at 10:26:20AM +0100, Christian Couder wrote:
>
>> I have a question though. Are the performance gains only available
>> with `git log -- path` or are they already available for example when
>> doing a partial clone and/or a sparse checkout?
>
> From my quick look at the code, anything that feeds a pathspec to a
> revision traversal would be helped. I'm not sure if it would help for
> partial/sparse traversals, though. There we actually need to know which
> blobs correspond to the paths in question, not just whether any
> particular commit touched them.
>
> I also took a brief look at adding support to the custom blame-tree
> implementation we use at GitHub, and got about a 6x speedup.

Is there any chance of upstreaming the blame-tree algorithm, perhaps as
a separate mode for git-blame (invoked with `git blame <directory>`?
Or is the algorithm too GitHub-specific?

Best,
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 1/9] commit-graph: add --changed-paths option to write
  2019-12-20 22:05 ` [PATCH 1/9] commit-graph: add --changed-paths option to write Garima Singh via GitGitGadget
@ 2020-01-01 20:20   ` Jakub Narebski
  0 siblings, 0 replies; 51+ messages in thread
From: Jakub Narebski @ 2020-01-01 20:20 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Garima Singh <garima.singh@microsoft.com>
>
> Add --changed-paths option to git commit-graph write. This option will
> soon allow users to compute bloom filters for the paths changed between
> a commit and its first significant parent, and write this information
> into the commit-graph file.

A slightly nitpicky comment.

First, I think it is "Bloom filter", not "bloom filter" (from the name
of the person that discovered them, Burton Howard Bloom).

Second, I would rather that the commit message started with at least one
sentence of describing purpose of this new option, not going straight to
the technical details (i.e. using Bloom filters).  Or in any other way
describe that this option would make Git store some helper data that
would help find out faster if a given path was changed in given commit.

> Note: This commit does not change any behavior. It only introduces
> the option and passes down the appropriate flag to the commit-graph.

All right.

Personally, I don't have strong opinion for or against separating this
change into its own patch.

> RFC Notes:
> 1. We named the option --changed-paths to capture what the option does,
>    instead of how it does it. The current implementation does this
>    using bloom filters. We believe using --changed-paths however keeps
>    the implementation open to other data structures.
>    All thoughts and suggestions for the name and this approach are
>    welcome

It is all right name.  Another option could be for example
`git commit-graph write --changeset-info`, or something like that.

>
> 2. Currently, a subsequent commit in this series will add tests that
>    exercise this option. I plan to split that test commit across the
>    series as appropriate.

There is another thing, but one that could be left for the followup
series, namely the configuration variables for this behavior.  In the
future it should be possible to switch some configuration variable to
have this feature on by default when manually or automatically running
`git commit-graph write`.

>
> Helped-by: Derrick Stolee <dstolee@microsoft.com>
> Signed-off-by: Garima Singh <garima.singh@microsoft.com>
> ---
>  Documentation/git-commit-graph.txt | 5 +++++
>  builtin/commit-graph.c             | 9 +++++++--
>  commit-graph.h                     | 3 ++-
>  3 files changed, 14 insertions(+), 3 deletions(-)
>
> diff --git a/Documentation/git-commit-graph.txt b/Documentation/git-commit-graph.txt
> index bcd85c1976..1efe6e5c5a 100644
> --- a/Documentation/git-commit-graph.txt
> +++ b/Documentation/git-commit-graph.txt

It is nice to have option documented.

All right, the 'write' subcommand has the following synopsis:

  'git commit-graph write' <options> [--object-dir <dir>] [--[no-]progress]

so the is no need to adjust it when adding a new option.

> @@ -54,6 +54,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 file based history logs with `git log`
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This might be not entirely clear for someone that is not familiar with
Git jargon.  Perhaps it would better read as "for getting history of a
directory or a file with `git log <path>`", or something like that.

Side note: the sentence is missing its finishing full stop.

> ++
>  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
> diff --git a/builtin/commit-graph.c b/builtin/commit-graph.c
> index e0c6fc4bbf..9bd1e11161 100644
> --- a/builtin/commit-graph.c
> +++ b/builtin/commit-graph.c
> @@ -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
>  };

I was at first wondering why the duplication (not caused by your patch,
though), and then realized that it is to have usage for command, and for
individual subcommands, separately.

> @@ -32,6 +32,7 @@ static struct opts_commit_graph {
>  	int split;
>  	int shallow;
>  	int progress;
> +	int enable_bloom_filters;

Why the field is called `enable_bloom_filters`, while option is called
`--changed-paths`?  I know it is not user-visible thing, so it would be
easy to change if we ever go beyond Bloom filters, though...

So I am not against keeping it as it is currently.

>  } opts;
>  
>  static int graph_verify(int argc, const char **argv)
> @@ -110,6 +111,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_bloom_filters,
> +			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")),
> @@ -143,6 +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_bloom_filters)
> +		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;

Minor nitpick: are we all right having this ordering of options (not for
example having opt.progress last)?

Disregarding this, it looks all right.

>  
>  	read_replace_refs = 0;
>  
> diff --git a/commit-graph.h b/commit-graph.h
> index 7f5c933fa2..952a4b83be 100644
> --- a/commit-graph.h
> +++ b/commit-graph.h
> @@ -76,7 +76,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)

I wonder if we should add comment describing the flag, like for the one
above...

>  };
>  
>  struct split_commit_graph_opts {

Best,
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 2/9] commit-graph: write changed paths bloom filters
  2019-12-20 22:05 ` [PATCH 2/9] commit-graph: write changed paths bloom filters Garima Singh via GitGitGadget
  2019-12-21 16:48   ` Philip Oakley
@ 2020-01-06 18:44   ` Jakub Narebski
  2020-01-13 19:48     ` Garima Singh
  1 sibling, 1 reply; 51+ messages in thread
From: Jakub Narebski @ 2020-01-06 18:44 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano,
	Garima Singh

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Garima Singh <garima.singh@microsoft.com>
>
> The changed path bloom filters help determine which paths changed between a
> commit and its first parent. We already have the "--changed-paths" option
> for the "git commit-graph write" subcommand, now actually compute them under
> that option. The COMMIT_GRAPH_WRITE_BLOOM_FILTERS flag enables this
> computation.
>
> RFC Notes: Here are some details about the implementation and I would love
> to know your thoughts and suggestions for improvements here.
>
> For details on what bloom filters are and how they work, please refer to
> Dr. Derrick Stolee's blog post [1].
> [1] https://devblogs.microsoft.com/devops/super-charging-the-git-commit-graph-iv-bloom-filters/
>
> 1. The implementation sticks to the recommended values of 7 and 10 for the
>    number of hashes and the size of each entry, as described in the blog.

Please provide references to original work for this.  Derrick Stolee
blog post references the following work:

  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

However, we do not use Counting Bloom Filters, but ordinary Bloom
Filters, if used in untypical way: instead of testing many elements
(keys) against single filter, we test single element (path) against
mainy filters.

Also, I'm not sure that values 10 bits per entry and 7 hash functions
are recommended; the work states:

  "For example, when n/m = 10 and k = 7 the false positive probability
  is just over 0.008."

Given false positive probablity we can calculate best choice for n/m and
k.

On the other hand in https://arxiv.org/abs/1912.08258 we have

  "For efficient memory usage, a Bloom filter with a false-positive
   probability ϵ should use about − log_2(ϵ) hash functions
   [Broder2004]. At a false-positive probability of 1%, seven hash
   functions are thus required."

So k=7 being optimal is somewhat confirmed.

>    The implementation while not completely open to it at the moment, is flexible
>    enough to allow for tweaking these settings in the future.

All right.

>    Note: The performance gains we have observed so far with these values is
>    significant enough to not that we did not need to tweak these settings.
                           ^^^
s/not/note/

Did you try to tweak settings, i.e. numbers of bits per entry, number
of hash functions (which is derivative of the former - at least the
optimal number), the size of the block, the cutoff threshold value?
It is not needed to be in this patch series - fine tuning is probably
better left for later.

>    The cover letter of this series has the details and the commit where we have
>    git log use bloom filters.

The second part of this sentence, from "and the commit..." is a bit
unclear.  Did you mean here that the future / subsequent commit in this
patch series that makes Git actually use Bloom filters in `git log --
<path>` will have more details in its commit message?

> 2. As described in the blog and the linked technical paper therin, we do not need
                                                             ^^^^^^
s/therin/therein/

>    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.

The "linked technical paper" in the blog post (which I would prefer to
have linked directly to in the commit message) is

  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

Sidenote: it looks like it is a reference from Wikipedia on Bloom filters.
This is according to authors the original paper with the _double hashing_
technique.

They also examine in much detail the optimal number of hash functions.

> 3. The filters are sized according to the number of changes in the each commit,
>    with minimum size of one 64 bit word.

Do I understand it correctly that the size of filter is 10*(number of
changed files) bits, rounded up to nearest multiple of 64?

How do you count renames and copies?  As two changes?

Do I understand it correctly that commit with no changes in it (which
can rarely happen) would have 64-bits i.e. 8-bytes Bloom filter of all
zeros: 0x0000000000000000?

How merges are handled?  Does the filter uses all changed files, or just
changes compared to first parent?

>
> [Call for advice] We currently cap writing bloom filters for commits with
> atmost 512 changed files. In the current implementation, we compute the diff,
> and then just throw it away once we see it has more than 512 changes.
> Any suggestiongs on how to reduce the work we are doing in this case are more
> than welcome.

This got solved in "[PATCH] diff: halt tree-diff early after max_changes"
https://public-inbox.org/git/e9a4e4ff-5466-dc39-c3f5-c9a8b8f2f11d@gmail.com/

> [Call for advice] Would the git community like this commit to be split up into
> more granular commits? This commit could possibly be split out further with the
> bloom.c code in its own commit, to be used by the commit-graph in a subsequent
> commit. While I prefer it being contained in one commit this way, I am open to
> suggestions.

I think it might be a good idea to split this commit into purely Bloom
filter implementation (bloom.c) AND unit tests for Bloom filter itself
(which would probably involve some new test-tool).

I have not read further messages in the series [edit: they don't], so I
don't know if such tests already exist or not.  One could test for
negative match, maybe also (for specific choice of hash function) for
positive and maybe even false positive match, for filter size depending
on the number of changes, for changes cap (maybe), maybe also for
no-changes scenario.


As for splitting the main part of the series, I would envision it in the
following way (which is of course only one possibility):

1. Implementation of generic-ish Bloom filter (with elements being
   strings / paths, and optimized to test single key against many
   filters, each taking small-ish space, variable size filter, limit on
   maximum number of elements).

   Technical documentation in comments in bloom.h (description of API)
   and bloom.c (details of the algorithm, with references).

   TODO: test-tool and unit tests.

2. Using per-commit Bloom filter(s) to store changeset information
   i.e. changed paths.  This would implement in-memory storage (on slab)
   and creating Bloom filter out of commit and repository information.

   Perhaps this should also get its own unit tests (that Bloom filter
   catches changed files, and excluding false positivess catches
   unchanged files).

3. Storing per-commit Bloom filters in the commit-graph file:

   a.) writing Bloom filters data to commit-graph file, which means
       designing the chunk(s) format,
   b.) verifying Bloom filter chunks, at least sanity-checks
   c.) reading Bloom filters from commit-graph file into memory

   Perhaps also some integration tests that the information is stored
   and retrieved correctly, and that verifying finds bugs in
   intentionally corrupted Bloom filter chunks.

4. Using Bloom filters to speed up `git log -- <path>` (and similar
   commands).

   It would be nice to have some functional tests, and maybe some
   performance tests, if possible.


> [Call for advice] Would a technical document explaining the exact details of
> the bloom filter implemenation and the hashing calculations be helpful? I will
> be adding details into Documentation/technical/commit-graph-format.txt, but the
> bloom filter code is an independent subsystem and could be used outside of the
> commit-graph feature. Is it worth a separate document, or should we apply "You
> Ain't Gonna Need It" principles?

As nowadays technical reference documentation is being moved from
Documentation/technical/api-*.txt to appropriate header files, maybe the
documentation of Bloom filter API (and some technical documentation and
references) be put in bloom.h?  See for example comments in strbuf.h.

> [Call for advice] I plan to add unit tests for bloom.c, specifically to ensure
> that the hash algorithm and bloom key calculations are stable across versions.

Ah, so the unit tests for bloom.c does not exist, yet...

> Signed-off-by: Garima Singh <garima.singh@microsoft.com>
> Helped-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  Makefile       |   1 +
>  bloom.c        | 201 +++++++++++++++++++++++++++++++++++++++++++++++++
>  bloom.h        |  46 +++++++++++
>  commit-graph.c |  32 +++++++-
>  4 files changed, 279 insertions(+), 1 deletion(-)
>  create mode 100644 bloom.c
>  create mode 100644 bloom.h
>
> diff --git a/Makefile b/Makefile
> index 42a061d3fb..9d5e26f5d6 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -838,6 +838,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

I'll put bloom.h first, to make it easier to review.

> diff --git a/bloom.h b/bloom.h
> new file mode 100644
> index 0000000000..ba8ae70b67
> --- /dev/null
> +++ b/bloom.h
> @@ -0,0 +1,46 @@
> +#ifndef BLOOM_H
> +#define BLOOM_H
> +
> +struct commit;
> +struct repository;

This would probably be missing if this patch was split in two:
introducing Bloom filter and saving Bloom filter in the repository
metadata (in commit-graphh file).

> +

O.K., the names of fields are descriptive enough so that this struct
doesn't need detailed description in comment (like the next one).

> +struct bloom_filter_settings {
> +	uint32_t hash_version;

Do we need full half-word for hash version?

> +	uint32_t num_hashes;

Do we need full 32-bits for number of hashes?  The "Bloom Filters in
Probabilistic Verification" paper mentioned in Stolee blog states that
no one should need number of hashes greater than k=32 - the accuracy is
so high that it doesn't matter that it is not optimal.

  "Notice one last thing about Bloom filters in verification, if $m$ is
   several gigabytes or less and $m/n$ calls for more than about 32 index
   functions, the accuracy is going to be so high that there is not much
   reason to use more than 32—for the next several years at least. In
   response to this, 3SPIN currently limits the user to $k = 32$. The
   point of this observation is that we do not have to worry about the
   runtime cost of $k$ being on the order of 64 or 100, because those
   choices do not really buy us anything over 32."

Here 'm' is the number of bits in Bloom filter, and m/n is number of
bits per element added to filter.

> +	uint32_t bits_per_entry;

All right, we wouldn't really want large Bloom filters, as we use one
filter per commit to match againts one key, not single Bloom filter to
match againts many keys.

> +};
> +
> +#define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10 }
> +
> +/*
> + * 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;
> +};

O.K., so it is single variable-sized (in 64-bit increments) Bloom filter
bit vector (bitmap).

> +
> +/*
> + * 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;
> +};

That is smart.  I wonder however if it wouldn't be a good idea to
'typedef' a hash function return type.

I repeat myself: in Git case we have one key that we try to match
against many Bloom filters which are never updated, while in an ordinary
case many keys are matched against single Bloom filter - in many cases
updated (with keys inserted to Bloom filter).

I wonder if somebody from academia have examined such situation.
I couldn't find a good search query.


Sidenote: perhaps Xor or Xor+ filters from Graf & Lemire (2019)
https://arxiv.org/abs/1912.08258 would be better solution - they also
assume unchanging filter.  Though they are a very fresh proposal;
also construction time might be important for Git.
https://github.com/FastFilter/xor_singleheader

> +
> +void load_bloom_filters(void);
> +
> +struct bloom_filter *get_bloom_filter(struct repository *r,
> +				      struct commit *c);

Those two functions really need API documentation on how they are used,
if they are to be used in any other role, especially what is their
calling convention?  Why load_bloom_filters() doesn't take any
parameters?

Anyway, if this patch would be split into pure Bloom filter
implementation and Git use^W store of Bloom filters, then this would be
left for the latter patch.

> +
> +void fill_bloom_key(const char *data,
> +		    int len,
> +		    struct bloom_key *key,
> +		    struct bloom_filter_settings *settings);

It is a bit strange that two basic Bloom filter operations, namely
adding element to Bloom filter (and constructing Bloom filter), and
testing whether element is in Bloom filter are not part of a public
API...

This function should probably be documented, in particular the fact that
*key is an in/out parameter.  This could also be a good place to
document the mechanism itself (i.e. our implementation of Bloom filter,
with references), though it might be better to keep the details of how
it works in the bloom.c - close to the actual source (while keeping
description of API in bloom.h comments).

> +
> +#endif
> diff --git a/bloom.c b/bloom.c
> new file mode 100644
> index 0000000000..08328cc381
> --- /dev/null
> +++ b/bloom.c
> @@ -0,0 +1,201 @@
> +#include "git-compat-util.h"
> +#include "bloom.h"
> +#include "commit-graph.h"
> +#include "object-store.h"
> +#include "diff.h"
> +#include "diffcore.h"
> +#include "revision.h"
> +#include "hashmap.h"
> +
> +#define BITS_PER_BLOCK 64
> +
> +define_commit_slab(bloom_filter_slab, struct bloom_filter);
> +
> +struct bloom_filter_slab bloom_filters;

All right, so the Bloom filter data would be on slab.  This should
probably be mentioned in the commit message, like in
https://lore.kernel.org/git/61559c5b-546e-d61b-d2e1-68de692f5972@gmail.com/

Sidenote: If I remember correctly one of the unmet prerequisites for
switching to generation numbers v2 (corrected commit date with monotonic
offsets) was moving 'generation' field out of 'struct commit' and on to
slab (possibly also 'graph_pos'), and certainly having 'corrected_date'
on slab (Inside-Out Object style).  Which probably could be done with
Coccinelle script...

> +
> +struct pathmap_hash_entry {
> +    struct hashmap_entry entry;
> +    const char path[FLEX_ARRAY];
> +};

Hmmm... I wonder why use hashmap and not string_list.  This is for
adding path with leading directories to the Bloom filter, isn't it?

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

Does it actually work with count being negative?  Shouldn't 'count' be
of unsigned type, and if int32_t is needed, perhaps add an assertion (if
needed)?  I think it does not.

It looks like it is John Regehr [2] safe and compiler-friendly
implementation, with explicit 8 in place of CHAR_BIT from <limits.h>,
which should compile to "rotate" assembly instruction... it looks like
it is the case, see https://godbolt.org/z/5JP1Jb (at least for C++
compiler).

[2]: https://en.wikipedia.org/wiki/Circular_shift


I wonder if this should, in the future, be a part of 'compat/', maybe
even using compiler intrinsics for "rotate right" if available (see
https://stackoverflow.com/a/776523/46058).  But that might be outside of
the scope of this patch (perhaps outside of choosing function name).

> +

It would be nice to have reference to the source of algorithm, or to the
code that was borrowed for this in the header comment for the following
function.

I will be comparing the algorithm itself in Wikipedia
https://en.wikipedia.org/wiki/MurmurHash#Algorithm
and its implementation in C in qLibc library (BSD licensed)
https://github.com/wolkykim/qlibc/blob/03a8ce035391adf88d6d755f9a26967c16a1a567/src/utilities/qhash.c#L258

> +static uint32_t seed_murmur3(uint32_t seed, const char *data, int len)
> +{
> +	const uint32_t c1 = 0xcc9e2d51;
> +	const uint32_t c2 = 0x1b873593;
> +	const int32_t r1 = 15;
> +	const int32_t r2 = 13;

Those two: r1 and r1, probably should be both uint32_t type.

> +	const uint32_t m = 5;
> +	const uint32_t n = 0xe6546b64;
> +	int i;
> +	uint32_t k1 = 0;
> +	const char *tail;

*tail should probably be 'uint8_t', not 'char', isn't it?

> +
> +	int len4 = len / sizeof(uint32_t);

All length variables and parameters, i.e. `len`, `len4`, `i`, could
possibly be `size_t` and not `int` type.

> +
> +	const uint32_t *blocks = (const uint32_t*)data;
> +

Some implementations copy `seed` (or assume seed=0) to the local
variable named `h` or `hash`.

> +	uint32_t k;
> +	for (i = 0; i < len4; i++)
> +	{
> +		k = blocks[i];
> +		k *= c1;
> +		k = rotate_right(k, r1);

Shouldn't it be *rotate_left* (ROL), not rotate_right (ROR)???
This affects all cases / uses.

> +		k *= c2;
> +
> +		seed ^= k;
> +		seed = rotate_right(seed, r2) * m + n;
> +	}
> +
> +	tail = (data + len4 * sizeof(uint32_t));
> +

We could have reused variable `k`, like the implementation in qLibc
does, instead of introducing new `k1` variable, but this way it is more
clean.  Or name it `remainingBytes` instead of `k1`

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

It would be nice to have header comment describing what this function is
intended to actually do.

> +static inline uint64_t get_bitmask(uint32_t pos)
> +{
> +	return ((uint64_t)1) << (pos & (BITS_PER_BLOCK - 1));
> +}

Sidenote: I wonder if ewah/bitmap.c implements something similar.
Certainly possible consolidation, if any possible exists, should be left
for the future.

> +
> +void fill_bloom_key(const char *data,
> +		    int len,
> +		    struct bloom_key *key,
> +		    struct bloom_filter_settings *settings)
> +{
> +	int i;
> +	uint32_t seed0 = 0x293ae76f;
> +	uint32_t seed1 = 0x7e646e2c;

Where did those constants came from?  It would be nice to have a
reference either in header comment (in bloom.h or bloom.c), or in a
commit message, or both.

Note that above *constants* are each used only once.

> +
> +	uint32_t hash0 = seed_murmur3(seed0, data, len);
> +	uint32_t hash1 = seed_murmur3(seed1, data, len);

Those are constant values, so perhaps they should be `const uint32_t`.

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

It looks like this code implements the double hashing technique given in
Eq. (4) in http://www.ccs.neu.edu/home/pete/pub/bloom-filters-verification.pdf
that is "Bloom Filters in Probabilistic Verification".

Note that Dillinger and Manolios in this paper propose also _enhanced_
double hashing algorithm (Algorithm 2 on page 11), which has closed form
given by Eq. (6) - with better science-theoretical properties at
similar cost.


It might be a good idea to explicitly state in the header comment that
all arithmetic is performed with unsigned 32-bit integers, which means
that operations are performed modulo 2^32.  Or it might not be needed.

> +}
> +
> +static 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_BLOCK;
> +
> +	for (i = 0; i < settings->num_hashes; i++) {
> +		uint64_t hash_mod = key->hashes[i] % mod;
> +		uint64_t block_pos = hash_mod / BITS_PER_BLOCK;

All right.  Because Bloom filters for different commits (and the same
key) may have different lengths, we can perform modulo operation only
here.  `hash_mod` is i-th hash modulo size of filter, and `block_pos` is
the block the '1' bit would go into.

> +
> +		filter->data[block_pos] |= get_bitmask(hash_mod);

I'm not quite convinced that get_bitmask() is a good name: this function
returns bitmap with hash_mod's bit set to 1.  On the other hand it
doesn't matter, because it is static (file-local) helper function.

Never mind then.

> +	}
> +}
> +
> +void load_bloom_filters(void)
> +{
> +	init_bloom_filter_slab(&bloom_filters);
> +}

Why *load* if all it does is initialize?

> +
> +struct bloom_filter *get_bloom_filter(struct repository *r,
> +				      struct commit *c)

I will not comment on this function; see Jeff King reply and Derrick
Stolee reply.

> +{
[...]
> +}
> \ No newline at end of file

Why there is no newline at the end of the file?  Accident?

> diff --git a/commit-graph.c b/commit-graph.c
> index e771394aff..61e60ff98a 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -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" */
> @@ -794,9 +795,11 @@ struct write_commit_graph_context {
>  	unsigned append:1,
>  		 report_progress:1,
>  		 split:1,
> -		 check_oids:1;
> +		 check_oids:1,
> +		 bloom:1;

Very minor nitpick: why `bloom` and not `bloom_filter`?

>  
>  	const struct split_commit_graph_opts *split_opts;
> +	uint32_t total_bloom_filter_size;

All right, I guess size of all Bloom filters would fit in uint32_t, no
need for size_t, is it?

Shouldn't it be total_bloom_filters_size -- it is not a single Bloom
filter, but many (minor nitpick)?

>  };
>  
>  static void write_graph_chunk_fanout(struct hashfile *f,
> @@ -1139,6 +1142,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;
> +
> +	load_bloom_filters();
> +
> +	if (ctx->report_progress)
> +		progress = start_progress(
> +			_("Computing commit diff 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_size += sizeof(uint64_t) * filter->len;

Wouldn't it be more future proof instead of using `sizeof(uint64_t)` to
use `sizeof(filter->data[0])` here?  This may be not worth it, and be
less readable (we have hard-coded use of 64-bits blocks in other places).

> +		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)
> @@ -1791,6 +1816,8 @@ int write_commit_graph(const char *obj_dir,
>  	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->bloom = flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS ? 1 : 0;

All right, this flag was defined in [PATCH 1/9].

The ordering of setting `ctx` members looks a bit strange.  Now it is
neither check `flags` firsts, neither keep related stuff together (see
ctx->split vs ctx->split_opts).  This is a very minor nitpick.

> +	ctx->total_bloom_filter_size = 0;
>  
>  	if (ctx->split) {
>  		struct commit_graph *g;
> @@ -1885,6 +1912,9 @@ int write_commit_graph(const char *obj_dir,
>  
>  	compute_generation_numbers(ctx);
>  
> +	if (ctx->bloom)
> +		compute_bloom_filters(ctx);
> +
>  	res = write_commit_graph_file(ctx);
>  
>  	if (ctx->split)

Regards,
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 3/9] commit-graph: use MAX_NUM_CHUNKS
  2019-12-20 22:05 ` [PATCH 3/9] commit-graph: use MAX_NUM_CHUNKS Garima Singh via GitGitGadget
@ 2020-01-07 12:19   ` Jakub Narebski
  0 siblings, 0 replies; 51+ messages in thread
From: Jakub Narebski @ 2020-01-07 12:19 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Garima Singh <garima.singh@microsoft.com>
>
> This is a minor cleanup to make it easier to change the
> number of chunks being written to the commit-graph in the future.

Very minor nit: in the whole commit message it is not stated explicitly
what MAX_NUM_CHUNKS is for, though it is very easy to guess (from the
name itself).

>
> Signed-off-by: Garima Singh <garima.singh@microsoft.com>
> ---
>  commit-graph.c | 5 +++--
>  1 file changed, 3 insertions(+), 2 deletions(-)
>
> diff --git a/commit-graph.c b/commit-graph.c
> index 61e60ff98a..8c4941eeaa 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -24,6 +24,7 @@
>  #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
>  #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
>  #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
> +#define MAX_NUM_CHUNKS 5

Minor nit: MAX_NUM_CHUNKS or MAX_CHUNKS?

>  
>  #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
>  
> @@ -1381,8 +1382,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];

Looks good.  I guess we won't ever have more chunks than 5:
OIDF, OIDL, CDAT, EDGE, BASE (and they cannot repeat, and last two are
optional).

>  	const unsigned hashsz = the_hash_algo->rawsz;
>  	struct strbuf progress_title = STRBUF_INIT;
>  	int num_chunks = 3;

Good.

Looks good to me.
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 4/9] commit-graph: document bloom filter format
  2019-12-20 22:05 ` [PATCH 4/9] commit-graph: document bloom filter format Garima Singh via GitGitGadget
@ 2020-01-07 14:46   ` Jakub Narebski
  0 siblings, 0 replies; 51+ messages in thread
From: Jakub Narebski @ 2020-01-07 14:46 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano,
	Garima Singh

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Garima Singh <garima.singh@microsoft.com>
>
> Update the technical documentation for commit-graph-format with BIDX
> and BDAT chunk information.
>
> RFC Notes:
> 1. [Call for advice] We specifically mention that we are using Bloom
>    filters in this technical document. Should this document also be
>    made open to other data structures in the future, with versioning
>    information?

I'm not sure.  In theory we might want to switch to another
probabilistic set inclusion query structure, like xor filters or cuckoo
hashing.

On one hand side we could use separate chunks (e.g. XIDX, XDAT for xor
filters), on the other hand we need only one such structure.  On the
gripping hand this can be left for the future, if needed.

Sidenote: using Bloom filters is somewhat encoded in the name of chunk
(B from Bloom filter).  I don't have a better poposal for 4-char name
(XIDX / XDAT for cXange?  CHDX / CHDT for CHange?  FIDX / FDAT for
changed Files?... I don't know).

>
> 2. [Call for advice] We are also not describing the explicit nature
>    of how we store the bloom filter binary data. Would it be useful
>    to document details about the hash algorithm, the number of hashes
>    and the specific seed values we are using in a separate document,
>    or perhaps in a separate section in this document?

I think it would be best to keep description of the commit graph format
concise.  The details about Bloom filter implementation would be better
put in Documentation/technical/commit-graph.txt in my opinion, together
with reasoning behind it (perhaps borrowing from Derrick Stolee blog
post).

This could be done as a separate patch.

>
> Helped-by: Derrick Stolee <dstolee@microsoft.com>
> Signed-off-by: Garima Singh <garima.singh@microsoft.com>
> ---
>  Documentation/technical/commit-graph-format.txt | 17 +++++++++++++++++
>  1 file changed, 17 insertions(+)
>
> diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
> index a4f17441ae..6497f19f08 100644
> --- a/Documentation/technical/commit-graph-format.txt
> +++ b/Documentation/technical/commit-graph-format.txt
> @@ -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 it's first parent.

s/bloom/Bloom/ and s/it's/its/

I am not sure about exact wording, but I could at this time think of a
better but concise way of stating it.

> +
>  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,20 @@ 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'}) [Optional]
> +      For each commit we store the offset of its bloom filter in the BDAT chunk
> +      as follows:
> +      BIDX[i] = number of 8-byte words in all the bloom filters from commit 0 to
> +		commit i (inclusive)

I think it would be better for consistency and ease of reading to follow
the example of OID Fanout (OIDF) chunk description:

 +  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 up to commit i (inclusive)
 +      in lexicographical order.

Maybe even add the following to make implementing it easier:

 +      Data for Bloom filter for i-th commit spans from BIDX[i-1] to
 +      BIDX[i] (plus header length), where we take BIDX[-1] to be 0.

Is it possible for (BIDX[i] - BIDX[i-1]) to be zero (no Bloom filter),
for example for commits with more than 512 changes?  Or is this case
handled by 1 8-byte word Bloom filter of all bits sets to '1', i.e.
0xffffffffffffffff?

How the case of too many changes is distingushed from the case of no
changes (`git commit --allow-empty`, or `git merge --ours`)?  Is the
case of no changes uninteresting, i.e. Bloom filter consisting of zero,
that is with all bits set to '0'?

> +
> +  Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]
> +      * It starts with three 32 bit integers for the

I would say "It starts with the header consisting of three unsigned
32-bit integers:" (but current version is not bad).

I wonder if this metadata should perhaps be put in a separate chunk,
BMET... (Bloom filter METadata).

> +	    - version of the hash algorithm being used

This number not only encodes that the base hash algorithm being used is
32-bit Murmur3 hash, but that 'k' hashes used in the computation are
created out of Murmur3 hash using double hashing technique, and
specifies two specific seed values for this double hashing technique.

[Maybe we should store those two seed values here too?]

It might be important to say that the currently supported version is
'1', and if Git encounters unknown hashing algorithm version it should
not use Bloom filter data.

Unless we store encoded _name_ of the hash algorithm, e.g. bytes
'm','u','r','3' for MurmurHash3_32... though it is about more than
a base hash.

Do we need whole 4 bytes for hash version, or is it for ease of use and
alignment?

> +	    - the number of hashes used in the computation

All right.  Perhaps we should test in the future patches that the value
different from the default of 7 would also work.

Also 8-bits / 1 byte for number of hashes (hash functions) should be
enough: as I have written in prevous reply there is no need for k > 32.

> +	    - the number of bits per entry

This is important for construction of Bloom filter, but I think it is
not necessary to use it -- so it may not be necessary to store it.

Would also fit in a single byte: we don't need exceedingly low false
positive probability.

We could use it to estimate the false positive probability, and...

> +	  * The rest of the chunk is the concatenation of all the computed bloom 
> +	  filters for the commits in lexicographic order.

  +	 * The rest of the chunk is the concatenation of all the computed Bloom 
  +	   filters for the commits in lexicographic order.

It would be, I think, a good idea to make it explicit that BDAT is
present iff BIDX is present (iff == if and only if), i.e. that either
both or neither of those chunks should be 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

Best,
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 5/9] commit-graph: write changed path bloom filters to commit-graph file.
  2019-12-20 22:05 ` [PATCH 5/9] commit-graph: write changed path bloom filters to commit-graph file Garima Singh via GitGitGadget
@ 2020-01-07 16:01   ` Jakub Narebski
  2020-01-14 15:14     ` Garima Singh
  0 siblings, 1 reply; 51+ messages in thread
From: Jakub Narebski @ 2020-01-07 16:01 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano,
	Garima Singh

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Garima Singh <garima.singh@microsoft.com>
>
> Write bloom filters to the commit-graph using the format described in
> Documentation/technical/commit-graph-format.txt
>
> Helped-by: Derrick Stolee <dstolee@microsoft.com>
> Signed-off-by: Garima Singh <garima.singh@microsoft.com>

Looks good to me.

> ---
>  commit-graph.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++-
>  commit-graph.h |  5 ++++
>  2 files changed, 85 insertions(+), 1 deletion(-)
>
> diff --git a/commit-graph.c b/commit-graph.c
> index 8c4941eeaa..def2ade166 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -24,7 +24,9 @@
>  #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_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
> +#define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
> +#define MAX_NUM_CHUNKS 7

Very minor nitpick: shouldn't we follow the order in the
commit-graph-format.txt document (i.e. "BASE" as last chunk and last
preprocessor constant)?

>  
>  #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
>  
> @@ -282,6 +284,32 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
>  				chunk_repeated = 1;
>  			else
>  				graph->chunk_base_graphs = data + chunk_offset;
> +			break;
> +
> +		case GRAPH_CHUNKID_BLOOMINDEXES:
> +			if (graph->chunk_bloom_indexes)
> +				chunk_repeated = 1;
> +			else
> +				graph->chunk_bloom_indexes = data + chunk_offset;
> +			break;

All right.

> +
> +		case GRAPH_CHUNKID_BLOOMDATA:
> +			if (graph->chunk_bloom_data)
> +				chunk_repeated = 1;
> +			else {
> +				uint32_t hash_version;
> +				graph->chunk_bloom_data = data + chunk_offset;
> +				hash_version = get_be32(data + chunk_offset);

All right, now I see why all those header values for BDAT chunk are
defined to be 32-bit integers.  For code simplicity.

> +
> +				if (hash_version != 1)
> +					break;

What does it mean for Git?  Behave as if there were no Bloom filter
data?

> +
> +				graph->settings = xmalloc(sizeof(struct bloom_filter_settings));
> +				graph->settings->hash_version = hash_version;
> +				graph->settings->num_hashes = get_be32(data + chunk_offset + 4);
> +				graph->settings->bits_per_entry = get_be32(data + chunk_offset + 8);

All right, looks O.K.

> +			}
> +			break;
>  		}
>  
>  		if (chunk_repeated) {
> @@ -996,6 +1024,39 @@ static void write_graph_chunk_extra_edges(struct hashfile *f,
>  	}
>  }
>  
> +static void write_graph_chunk_bloom_indexes(struct hashfile *f,
> +					    struct write_commit_graph_context *ctx)
> +{
> +	struct commit **list = ctx->commits.list;
> +	struct commit **last = ctx->commits.list + ctx->commits.nr;
> +	uint32_t cur_pos = 0;
> +
> +	while (list < last) {
> +		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
> +		cur_pos += filter->len;
> +		hashwrite_be32(f, cur_pos);
> +		list++;
> +	}

Why not follow the write_graph_chunk_oids() example, instead of
write_graph_chunk_data(), that is use simply:

  +	struct commit **list = ctx->commits.list;
  +	uint32_t cur_pos = 0;
  +
  +	for (count = 0; count < ctx->commits.nr; count++, list++) {
  +		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
  +		cur_pos += filter->len;
  +		hashwrite_be32(f, cur_pos);
  +	}

I guess using here

  +		cur_pos += get_bloom_filter(ctx->r, *list)->len;

would be too cryptic, and hard to debug?

Also, wouldn't we need

  +		display_progress(ctx->progress, ++ctx->progress_cnt);

before hashwrite_be32()?

> +}
> +
> +static void write_graph_chunk_bloom_data(struct hashfile *f,
> +					 struct write_commit_graph_context *ctx,
> +					 struct bloom_filter_settings *settings)
> +{
> +	struct commit **first = ctx->commits.list;

Even if we decide to use `while` loop, like write_graph_chunk_data(),
and not `for` loop, like write_graph_chunk_oids(), why the change from
`struct commit **list = ...` to `struct commit **first = ...`?

> +	struct commit **last = ctx->commits.list + ctx->commits.nr;
> +
> +	hashwrite_be32(f, settings->hash_version);
> +	hashwrite_be32(f, settings->num_hashes);
> +	hashwrite_be32(f, settings->bits_per_entry);

All right, simple.

> +
> +	while (first < last) {
> +		struct bloom_filter *filter = get_bloom_filter(ctx->r, *first);

Hmmm... wouldn't this compute Bloom filter second time?
get_bloom_filter() does work unconditionally.

Wouldn't

  +		struct bloom_filter *filter = bloom_filter_slab_at(&bloom_filters, *first);

be enough?

Or make get_bloom_filter() use *_peek() to check if Bloom filter for
given commit was already computed, and only if it returns NULL do the
work.

> +		hashwrite(f, filter->data, filter->len * sizeof(uint64_t));

Might need display_progress() before hashwrote().

> +		first++;
> +	}
> +}
> +
>  static int oid_compare(const void *_a, const void *_b)
>  {
>  	const struct object_id *a = (const struct object_id *)_a;
> @@ -1388,6 +1449,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
>  	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;
>  
>  	if (ctx->split) {
>  		struct strbuf tmp_file = STRBUF_INIT;
> @@ -1432,6 +1494,12 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
>  		chunk_ids[num_chunks] = GRAPH_CHUNKID_EXTRAEDGES;
>  		num_chunks++;
>  	}
> +	if (ctx->bloom) {
> +		chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMINDEXES;
> +		num_chunks++;
> +		chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMDATA;
> +		num_chunks++;
> +	}

Looks all right.

>  	if (ctx->num_commit_graphs_after > 1) {
>  		chunk_ids[num_chunks] = GRAPH_CHUNKID_BASE;
>  		num_chunks++;
> @@ -1450,6 +1518,13 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
>  						4 * ctx->num_extra_edges;
>  		num_chunks++;
>  	}
> +	if (ctx->bloom) {
> +		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] + sizeof(uint32_t) * ctx->commits.nr;
> +		num_chunks++;
> +
> +		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] + sizeof(uint32_t) * 3 + ctx->total_bloom_filter_size;
> +		num_chunks++;
> +	}

Better wrap those long lines, like above:

  +	if (ctx->bloom) {
  +		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
  +						sizeof(uint32_t) * ctx->commits.nr;
  +		num_chunks++;
  +
  +		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
  +						sizeof(uint32_t) * 3 + ctx->total_bloom_filter_size;
  +		num_chunks++;
  +	}

>  	if (ctx->num_commit_graphs_after > 1) {
>  		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
>  						hashsz * (ctx->num_commit_graphs_after - 1);
> @@ -1487,6 +1562,10 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
>  	write_graph_chunk_data(f, hashsz, ctx);
>  	if (ctx->num_extra_edges)
>  		write_graph_chunk_extra_edges(f, ctx);
> +	if (ctx->bloom) {
> +		write_graph_chunk_bloom_indexes(f, ctx);
> +		write_graph_chunk_bloom_data(f, ctx, &bloom_settings);
> +	}

All right.

>  	if (ctx->num_commit_graphs_after > 1 &&
>  	    write_graph_chunk_base(f, ctx)) {
>  		return -1;
> diff --git a/commit-graph.h b/commit-graph.h
> index 952a4b83be..2202ad91ae 100644
> --- a/commit-graph.h
> +++ b/commit-graph.h
> @@ -10,6 +10,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(const char *obj_dir);
>  int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
> @@ -58,6 +59,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 *settings;

Should this be part of `struct commit_graph`?  Shouldn't we free() this
data, or is it a pointer into xmmap-ped file... no it isn't -- we
xalloc() it, so we should free() it.

I think it should be done in 'cleanup:' section of write_commit_graph(),
but I am not entirely sure.

>  };
>  
>  struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st);

Best,
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 6/9] commit-graph: test commit-graph write --changed-paths
  2019-12-20 22:05 ` [PATCH 6/9] commit-graph: test commit-graph write --changed-paths Garima Singh via GitGitGadget
@ 2020-01-08  0:32   ` Jakub Narebski
  0 siblings, 0 replies; 51+ messages in thread
From: Jakub Narebski @ 2020-01-08  0:32 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano,
	Garima Singh

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Garima Singh <garima.singh@microsoft.com>
>
> Add tests for the --changed-paths feature when writing
> commit-graphs.

It doesn't look however as if this test is actually testing the _Bloom
filter_ functionality itself -- because this test looks like
copy'n'paste of t/t5324-split-commit-graph.sh, just with
`--changed-paths` added to the `git commit-graph write` invocation, and
added checking via enhanced test-tool that there are Bloom filter chunks
("bloom_indexes" and "bloom_data").

Please correct me if I am wrong, but this looks like a simple sanity
check for me.

>
> RFC Notes:
> I plan to split this test across some of the earlier commits
> as appropriate.

About adding tests to earlier commits in this series:

1. Testing Bloom filter functionality:
   - creating Bloom filter and adding elements to it
   - testing Bloom filter functionality
     - for element in set the answer is "maybe"
     - for element not in set the answer is "no" or "maybe"
   - automatic resizing works (6 and 7 elements)
   - it works for different number of hash functions,
     and different number of bits per element (maybe?)

2. Testing Bloom filter for commit changeset:
   - it works for commit with no changes
   - it works for merge commit with no changes to first parent
     (`git merge --strategy=ours`)
   - with number of changes that require filter size change
   - with maximal number of changes, one changed file less,
     one changed file more
   - that for file deeper in hierarchy, path/to/file, all of
     changed directories (path/to/ and path/) are also added

3. Test writing and reading commit-graph with Bloom filters
   - that after writing Bloom filters with `--changed-paths`
     the data is present in commit-graph files
   - it works correctly with split commit-graph
   - it doesn't crash if confronted with unknown settings:
     hash version different than 1, different number of hash
     functions, different number of bits per element

4. Bloom filter specific `git commit-graph verify` parts
   - fail if Bloom filter chunks appear multiple times
   - fail if only one of BIDX or BDAT chunks are present
   - fail if BIDX is not monotonic, that is if size of Bloom filter
     for a commit is negative
   - fail if BDAT size does not agree with BIDX,
     being either too small, or too large
   - check if values of number of hash functions
     and number of bits per element added are sane

5. Using Bloom filters to speed up Git operations
   - test that with and without Bloom filters (or commit-graph)
     the following operations work the same:
     - git log -- <path/to/file>
     - git log -- <path/to/directory>
     - git log -- '*.c'  # or other glob pattern
     - git log -- <file1> <file2>
     - git log --follow <file>
     - maybe also `git log --full-history -- <file>`
   - if possible, add performance tests, see `t/perf`

>
> Helped-by: Derrick Stolee <dstolee@microsoft.com>
> Signed-off-by: Garima Singh <garima.singh@microsoft.com>
> ---
>  t/helper/test-read-graph.c    |   4 +
>  t/t5325-commit-graph-bloom.sh | 255 ++++++++++++++++++++++++++++++++++
>  2 files changed, 259 insertions(+)
>  create mode 100755 t/t5325-commit-graph-bloom.sh
>
> diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c
> index d2884efe0a..aff597c7a3 100644
> --- a/t/helper/test-read-graph.c
> +++ b/t/helper/test-read-graph.c
> @@ -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");

All right, though it is very basic information.

>  	printf("\n");
>  
>  	UNLEAK(graph);
> diff --git a/t/t5325-commit-graph-bloom.sh b/t/t5325-commit-graph-bloom.sh
> new file mode 100755
> index 0000000000..d7ef0e7fb3
> --- /dev/null
> +++ b/t/t5325-commit-graph-bloom.sh
> @@ -0,0 +1,255 @@
> +#!/bin/sh
> +
> +test_description='commit graph with bloom filters'
> +. ./test-lib.sh
> +
> +test_expect_success 'setup repo' '
> +	git init &&
> +	git config core.commitGraph true &&
> +	git config gc.writeCommitGraph false &&
> +	infodir=".git/objects/info" &&
> +	graphdir="$infodir/commit-graphs" &&
> +	test_oid_init
> +'
> +
> +graph_read_expect() {

Style: space between function name and parentheses, i.e.

  +graph_read_expect () {

> +	OPTIONAL=""

Not used anywhere.

> +	NUM_CHUNKS=5
> +	if test ! -z $2

It might be good idea to add names to those parameters by setting some
local variables to $1 and $2; or, alternatively add comment describing
this function.

> +	then
> +		OPTIONAL=" $2"
> +		NUM_CHUNKS=$((NUM_CHUNKS + $(echo "$2" | wc -w)))
> +	fi
> +	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
> +}

No comments below this point...

Best,

  Jakub Narębski


> +
> +test_expect_success 'create commits and write commit-graph' '
> +	for i in $(test_seq 3)
> +	do
> +		test_commit $i &&
> +		git branch commits/$i || return 1
> +	done &&
> +	git commit-graph write --reachable --changed-paths &&
> +	test_path_is_file $infodir/commit-graph &&
> +	graph_read_expect 3
> +'
> +
> +graph_git_two_modes() {
> +	git -c core.commitGraph=true $1 >output
> +	git -c core.commitGraph=false $1 >expect
> +	test_cmp expect output
> +}
> +
> +graph_git_behavior() {
> +	MSG=$1
> +	BRANCH=$2
> +	COMPARE=$3
> +	test_expect_success "check normal git operations: $MSG" '
> +		graph_git_two_modes "log --oneline $BRANCH" &&
> +		graph_git_two_modes "log --topo-order $BRANCH" &&
> +		graph_git_two_modes "log --graph $COMPARE..$BRANCH" &&
> +		graph_git_two_modes "branch -vv" &&
> +		graph_git_two_modes "merge-base -a $BRANCH $COMPARE"
> +	'
> +}
> +
> +graph_git_behavior 'graph exists' commits/3 commits/1
> +
> +verify_chain_files_exist() {
> +	for hash in $(cat $1/commit-graph-chain)
> +	do
> +		test_path_is_file $1/graph-$hash.graph || return 1
> +	done
> +}
> +
> +test_expect_success 'add more commits, and write a new base graph' '
> +	git reset --hard commits/1 &&
> +	for i in $(test_seq 4 5)
> +	do
> +		test_commit $i &&
> +		git branch commits/$i || return 1
> +	done &&
> +	git reset --hard commits/2 &&
> +	for i in $(test_seq 6 10)
> +	do
> +		test_commit $i &&
> +		git branch commits/$i || return 1
> +	done &&
> +	git reset --hard commits/2 &&
> +	git merge commits/4 &&
> +	git branch merge/1 &&
> +	git reset --hard commits/4 &&
> +	git merge commits/6 &&
> +	git branch merge/2 &&
> +	git commit-graph write --reachable --changed-paths &&
> +	graph_read_expect 12
> +'
> +
> +test_expect_success 'fork and fail to base a chain on a commit-graph file' '
> +	test_when_finished rm -rf fork &&
> +	git clone . fork &&
> +	(
> +		cd fork &&
> +		rm .git/objects/info/commit-graph &&
> +		echo "$(pwd)/../.git/objects" >.git/objects/info/alternates &&
> +		test_commit new-commit &&
> +		git commit-graph write --reachable --split --changed-paths &&
> +		test_path_is_file $graphdir/commit-graph-chain &&
> +		test_line_count = 1 $graphdir/commit-graph-chain &&
> +		verify_chain_files_exist $graphdir
> +	)
> +'
> +
> +test_expect_success 'add three more commits, write a tip graph' '
> +	git reset --hard commits/3 &&
> +	git merge merge/1 &&
> +	git merge commits/5 &&
> +	git merge merge/2 &&
> +	git branch merge/3 &&
> +	git commit-graph write --reachable --split --changed-paths &&
> +	test_path_is_missing $infodir/commit-graph &&
> +	test_path_is_file $graphdir/commit-graph-chain &&
> +	ls $graphdir/graph-*.graph >graph-files &&
> +	test_line_count = 2 graph-files &&
> +	verify_chain_files_exist $graphdir
> +'
> +
> +graph_git_behavior 'split commit-graph: merge 3 vs 2' merge/3 merge/2
> +
> +test_expect_success 'add one commit, write a tip graph' '
> +	test_commit 11 &&
> +	git branch commits/11 &&
> +	git commit-graph write --reachable --split --changed-paths &&
> +	test_path_is_missing $infodir/commit-graph &&
> +	test_path_is_file $graphdir/commit-graph-chain &&
> +	ls $graphdir/graph-*.graph >graph-files &&
> +	test_line_count = 3 graph-files &&
> +	verify_chain_files_exist $graphdir
> +'
> +
> +graph_git_behavior 'three-layer commit-graph: commit 11 vs 6' commits/11 commits/6
> +
> +test_expect_success 'add one commit, write a merged graph' '
> +	test_commit 12 &&
> +	git branch commits/12 &&
> +	git commit-graph write --reachable --split --changed-paths &&
> +	test_path_is_file $graphdir/commit-graph-chain &&
> +	test_line_count = 2 $graphdir/commit-graph-chain &&
> +	ls $graphdir/graph-*.graph >graph-files &&
> +	test_line_count = 2 graph-files &&
> +	verify_chain_files_exist $graphdir
> +'
> +
> +graph_git_behavior 'merged commit-graph: commit 12 vs 6' commits/12 commits/6
> +
> +test_expect_success 'create fork and chain across alternate' '
> +	git clone . fork &&
> +	(
> +		cd fork &&
> +		git config core.commitGraph true &&
> +		rm -rf $graphdir &&
> +		echo "$(pwd)/../.git/objects" >.git/objects/info/alternates &&
> +		test_commit 13 &&
> +		git branch commits/13 &&
> +		git commit-graph write --reachable --split --changed-paths &&
> +		test_path_is_file $graphdir/commit-graph-chain &&
> +		test_line_count = 3 $graphdir/commit-graph-chain &&
> +		ls $graphdir/graph-*.graph >graph-files &&
> +		test_line_count = 1 graph-files &&
> +		git -c core.commitGraph=true  rev-list HEAD >expect &&
> +		git -c core.commitGraph=false rev-list HEAD >actual &&
> +		test_cmp expect actual &&
> +		test_commit 14 &&
> +		git commit-graph write --reachable --split --changed-paths --object-dir=.git/objects/ &&
> +		test_line_count = 3 $graphdir/commit-graph-chain &&
> +		ls $graphdir/graph-*.graph >graph-files &&
> +		test_line_count = 1 graph-files
> +	)
> +'
> +
> +graph_git_behavior 'alternate: commit 13 vs 6' commits/13 commits/6
> +
> +test_expect_success 'test merge stragety constants' '
> +	git clone . merge-2 &&
> +	(
> +		cd merge-2 &&
> +		git config core.commitGraph true &&
> +		test_line_count = 2 $graphdir/commit-graph-chain &&
> +		test_commit 14 &&
> +		git commit-graph write --reachable --split --changed-paths --size-multiple=2 &&
> +		test_line_count = 3 $graphdir/commit-graph-chain
> +
> +	) &&
> +	git clone . merge-10 &&
> +	(
> +		cd merge-10 &&
> +		git config core.commitGraph true &&
> +		test_line_count = 2 $graphdir/commit-graph-chain &&
> +		test_commit 14 &&
> +		git commit-graph write --reachable --split --changed-paths --size-multiple=10 &&
> +		test_line_count = 1 $graphdir/commit-graph-chain &&
> +		ls $graphdir/graph-*.graph >graph-files &&
> +		test_line_count = 1 graph-files
> +	) &&
> +	git clone . merge-10-expire &&
> +	(
> +		cd merge-10-expire &&
> +		git config core.commitGraph true &&
> +		test_line_count = 2 $graphdir/commit-graph-chain &&
> +		test_commit 15 &&
> +		git commit-graph write --reachable --split --changed-paths --size-multiple=10 --expire-time=1980-01-01 &&
> +		test_line_count = 1 $graphdir/commit-graph-chain &&
> +		ls $graphdir/graph-*.graph >graph-files &&
> +		test_line_count = 3 graph-files
> +	) &&
> +	git clone --no-hardlinks . max-commits &&
> +	(
> +		cd max-commits &&
> +		git config core.commitGraph true &&
> +		test_line_count = 2 $graphdir/commit-graph-chain &&
> +		test_commit 16 &&
> +		test_commit 17 &&
> +		git commit-graph write --reachable --split --changed-paths --max-commits=1 &&
> +		test_line_count = 1 $graphdir/commit-graph-chain &&
> +		ls $graphdir/graph-*.graph >graph-files &&
> +		test_line_count = 1 graph-files
> +	)
> +'
> +
> +test_expect_success 'remove commit-graph-chain file after flattening' '
> +	git clone . flatten &&
> +	(
> +		cd flatten &&
> +		test_line_count = 2 $graphdir/commit-graph-chain &&
> +		git commit-graph write --reachable &&
> +		test_path_is_missing $graphdir/commit-graph-chain &&
> +		ls $graphdir >graph-files &&
> +		test_must_be_empty graph-files
> +	)
> +'
> +
> +graph_git_behavior 'graph exists' merge/octopus commits/12
> +
> +test_expect_success 'split across alternate where alternate is not split' '
> +	git commit-graph write --reachable &&
> +	test_path_is_file .git/objects/info/commit-graph &&
> +	cp .git/objects/info/commit-graph . &&
> +	git clone --no-hardlinks . alt-split &&
> +	(
> +		cd alt-split &&
> +		rm -f .git/objects/info/commit-graph &&
> +		echo "$(pwd)"/../.git/objects >.git/objects/info/alternates &&
> +		test_commit 18 &&
> +		git commit-graph write --reachable --split --changed-paths &&
> +		test_line_count = 1 $graphdir/commit-graph-chain
> +	) &&
> +	test_cmp commit-graph .git/objects/info/commit-graph
> +'
> +
> +test_done

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 7/9] commit-graph: reuse existing bloom filters during write.
  2019-12-20 22:05 ` [PATCH 7/9] commit-graph: reuse existing bloom filters during write Garima Singh via GitGitGadget
@ 2020-01-09 19:12   ` Jakub Narebski
  0 siblings, 0 replies; 51+ messages in thread
From: Jakub Narebski @ 2020-01-09 19:12 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano,
	Garima Singh

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Garima Singh <garima.singh@microsoft.com>
>
Overly long lines in the commit message.

> Read previously computed bloom filters from the commit-graph file if possible
> to avoid recomputing during commit-graph write.

Hmmm.  This fixes (somewhat) the problem that I have noticed in previous
patch that the Bloom filter was computed at least twice, once for BIDX
chunk, once fo BDAT chunk.

I think the order should be:
 - use Bloom filter on slab, if present
 - fill it from commit graph, if saved there
 - if needed, compute it from scratch (expensive operation!)

If I understand it correctly, it now does it... though possibly with
unnecessary memory allocation if commit-graph file does not include
Bloomm filters data, and (re)computing is not requested (see later).

But I might be wrong here.

>
> Reading from the commit-graph is based on the format in which bloom filters are
> written in the commit graph file. See method `fill_filter_from_graph` in bloom.c

This description reads a bit strange; it looks like it states a truism
(we read in the format we wrote).  It think it should be rephrased in
different way for better readability.

>
> For reading the bloom filter for commit at lexicographic position i:

I think it would better read as:

  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 (called the next_index in the code)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    |
                    \- I think would be not needed with better var name

I would also add that it gives the position [one past] the end of Bloom
filter data for i-th commit.

>
> 2. For i>0, read BIDX[i-1] which will give us the starting index in BDAT for
>    filter of commit i (called the prev_index in the code)

Minor nitpick: Full stops are missing.

Why it is called prev_index and next_index, while it is either
curr_index and next_index or prev_index and curr_index, or maybe even
better beg_index and end_index?

>    For i = 0, prev_index will be 0. The first lexicographic commit's filter will
>    start at BDAT.

I would state it

     For first commit, with i = 0, Bloom filter data starts at the
     beginning, just past the header in BDAT chunk.

>
> 3. The length of the filter will be next_index - prev_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_null
> flag.

All right.
>
> Helped-by: Derrick Stolee <dstolee@microsoft.com>
> Signed-off-by: Garima Singh <garima.singh@microsoft.com>
> ---
>  bloom.c        | 40 ++++++++++++++++++++++++++++++++++++++--
>  bloom.h        |  3 ++-
>  commit-graph.c |  6 +++---
>  3 files changed, 43 insertions(+), 6 deletions(-)
>
> diff --git a/bloom.c b/bloom.c
> index 08328cc381..86b1005802 100644
> --- a/bloom.c
> +++ b/bloom.c
> @@ -1,5 +1,7 @@
>  #include "git-compat-util.h"
>  #include "bloom.h"
> +#include "commit.h"
> +#include "commit-slab.h"
>  #include "commit-graph.h"
>  #include "object-store.h"
>  #include "diff.h"
> @@ -119,13 +121,35 @@ static void add_key_to_filter(struct bloom_key *key,
>  	}
>  }
>  
> +static void fill_filter_from_graph(struct commit_graph *g,
> +				   struct bloom_filter *filter,
> +				   struct commit *c)
> +{
> +	uint32_t lex_pos, prev_index, next_index;
> +

> +	while (c->graph_pos < g->num_commits_in_base)
> +		g = g->base_graph;
> +
> +	lex_pos = c->graph_pos - g->num_commits_in_base;

This part shares common code with load_oid_from_graph(), only without
some of error checking; perhaps it might be good to extract it into a
separate helper function, e.g. `lex_index(&g, c->graph_pos)`.

Minor nitpick about the consistency of function names: why
load_oid_from_graph(), but fill_filter_from_graph(), and not
load_filter_from_graph() / load_bloom_from_graph()?

> +
> +	next_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
> +	if (lex_pos)

I think using

  +	if (lex_pos > 0)

or

  +	if (lex_pos >= 0)

might be easier to reason about.

> +		prev_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1));
> +	else
> +		prev_index = 0;
> +
> +	filter->len = next_index - prev_index;

The above command reads a bit strange: next - prev?  not  next - curr,
or curr - prev?  Wouldn't it be better to name it begin_index and
end_index, or beg_index and end_index for brevity?

> +	filter->data = (uint64_t *)(g->chunk_bloom_data + 8 * prev_index + 12);

Please do not use magic constants; use instead something like:

  +	filter->data = (uint64_t *)(g->chunk_bloom_data +
  +				    sizeof(uint64_t) * prev_index +
  +				    BLOOMDATA_CHUNK_HEADER_SIZE);

Perhaps using `3*sizeof(unit32_t)` instead of magic value 12 would be
enough; but having symbolic name for BDAT chunk header size is better, I
think.

> +}
> +
>  void load_bloom_filters(void)
>  {
>  	init_bloom_filter_slab(&bloom_filters);
>  }
>  
>  struct bloom_filter *get_bloom_filter(struct repository *r,
> -				      struct commit *c)
> +				      struct commit *c,
> +				      int compute_if_null)

I'm not sure about `compute_if_null` name...

>  {
>  	struct bloom_filter *filter;
>  	struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
> @@ -134,6 +158,18 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
>  	const char *revs_argv[] = {NULL, "HEAD", NULL};
>  
>  	filter = bloom_filter_slab_at(&bloom_filters, c);

Note that the documentation for `slab_at(slab, commit)` is documented in
`commit-slab.h` as

 *   This function locates the data associated with the given commit in
 *   the indegree slab, and returns the pointer to it.  The location to
 *   store the data is allocated as necessary.
                       ~~~~~~~~~~~~~~~~~~~~~~

Should we worry about this possibly unnecessary allocation (if there is
no Bloom filter chunk in the commit-graph, and we are not recomputing
it)?

There is `slab_peek(slab_commit)` with the following properties:

 *   This function is similar to indegree_at(), but it will return NULL
 *   until a call to indegree_at() was made for the commit.

> +
> +	if (!filter->data) {

What does the Bloom filter for a commit with no changes looks like?
What about for a commit with more than 512 changes?  Do, in either of
those cases, filter->len is 0?  If yes, what about filter->data?

> +		load_commit_graph_info(r, c);
> +		if (c->graph_pos != COMMIT_NOT_FROM_GRAPH && r->objects->commit_graph->chunk_bloom_indexes) {

Please wrap overly long lines (109 characters seems too long; the
CodingGuidelines states:

 - We try to keep to at most 80 characters per line.

  +		if (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&
  +		    r->objects->commit_graph->chunk_bloom_indexes) {

You seem to assume here that in the chain of commit-graph files either
all of them would have Bloom filters, or all of them would be missing
Bloom filters.  Isn't it however possible for only some of the
commit-graph files in chain to include Bloom filter data chunks?

In such case, the top commit-graph file may have BIDX chunk
(bloom_indexes), but the commit-graph with the commit 'c' might not have
it.  Or the top commit-graph file may be missing BIDX chunk, so Git
would recompute it even if the commit-graph file for commit 'c' includes
it.

If such situation is forbidden, how the restriction is managed?

Note: in any case, this needs to be tested!

> +			fill_filter_from_graph(r->objects->commit_graph, filter, c);
> +			return filter;
> +		}
> +	}

All right, if it is not in slab, we try to read if from the commit
graph.  Looks all right.

> +
> +	if (filter->data || !compute_if_null)
> +			return filter;
                ^^^^^^^^
                 |
                 \- one tab too many

If we have found existing filter (on slab or in the commit-graph), or if
we won't be recomputing it, return it.  O.K.

> +
>  	init_revisions(&revs, NULL);
>  	revs.diffopt.flags.recursive = 1;
>  
> @@ -198,4 +234,4 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
>  	DIFF_QUEUE_CLEAR(&diff_queued_diff);
>  
>  	return filter;
> -}
> \ No newline at end of file
> +}

Accidental change.

> diff --git a/bloom.h b/bloom.h
> index ba8ae70b67..101d689bbd 100644
> --- a/bloom.h
> +++ b/bloom.h
> @@ -36,7 +36,8 @@ struct bloom_key {
>  void load_bloom_filters(void);
>  
>  struct bloom_filter *get_bloom_filter(struct repository *r,
> -				      struct commit *c);
> +				      struct commit *c,
> +				      int compute_if_null);
>

All right, this is just update of the function signature.

>  void fill_bloom_key(const char *data,
>  		    int len,
> diff --git a/commit-graph.c b/commit-graph.c
> index def2ade166..0580ce75d5 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -1032,7 +1032,7 @@ static void write_graph_chunk_bloom_indexes(struct hashfile *f,
>  	uint32_t cur_pos = 0;
>  
>  	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;
>  		hashwrite_be32(f, cur_pos);
>  		list++;
> @@ -1051,7 +1051,7 @@ static void write_graph_chunk_bloom_data(struct hashfile *f,
>  	hashwrite_be32(f, settings->bits_per_entry);
>  
>  	while (first < last) {
> -		struct bloom_filter *filter = get_bloom_filter(ctx->r, *first);
> +		struct bloom_filter *filter = get_bloom_filter(ctx->r, *first, 0);
>  		hashwrite(f, filter->data, filter->len * sizeof(uint64_t));
>  		first++;
>  	}

O.K., so those two do not compute Bloom filters, but they are called
from write_commit_graph_file(), which in turn is called in
write_commit_graph() *after* running compute_bloom_filters().

Looks good to me, then.

> @@ -1218,7 +1218,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
>  
>  	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);
> +		struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1);
>  		ctx->total_bloom_filter_size += sizeof(uint64_t) * filter->len;
>  		display_progress(progress, i + 1);
>  	}

All right, so compute_bloom_filters() ensures that it is actually
computed (if needed).

Looks good to me.

Regards,
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 8/9] revision.c: use bloom filters to speed up path based revision walks
  2019-12-20 22:05 ` [PATCH 8/9] revision.c: use bloom filters to speed up path based revision walks Garima Singh via GitGitGadget
@ 2020-01-11  0:27   ` Jakub Narebski
  2020-01-15  0:08     ` Garima Singh
  0 siblings, 1 reply; 51+ messages in thread
From: Jakub Narebski @ 2020-01-11  0:27 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano,
	Garima Singh

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Garima Singh <garima.singh@microsoft.com>
>
> If bloom filters have been written to the commit-graph file, revision walk will
> use them to speed up revision walks for a particular path.

I'd propose the following change, to make structure of the above
sentence simpler:

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

> Note: The current implementation does this in the case of single pathspec
> case only.
>
> We load the bloom filters during the prepare_revision_walk step when dealing

I think it would flow better with the following change:

s/when dealing/, 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.

Maybe we should also add:

  The other answer we can get from the Bloom filter is "maybe".

>
> 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.

I think you meant `git log <path>`, not `git log --path`.

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

It would be good, I think, to have some specific numbers: starting from
this version, for this path, with and without Bloom filters it takes so
long (and the improvement in %).

While at it, it might be good idea to provide _costs_: how much
additional space on disk Bloom filters take for those specific examples,
and how much extra time (and memory) it takes to compute Bloom filters.

With actual specific numbers we can estimate when it would start to be
worth it to create Bloom filter data...

>
> 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.

It would be nice to see specific numbers, if showing pathnames is
possible.  In any case it would be good to have more information: what
paths give 10x, what give 20x, and what kinds give 28x speedup (what
is path depth, how many objects, etc.).

>
> RFC Notes:
> I plan to collect the folloowing statistics around this usage of bloom filters
> and trace them out using trace2.
> - number of bloom filter queries,
> - number of "No" responses (file hasn't changed)
> - number of "Maybe" responses (file may have changed)
> - number of "Commit not parsed" cases (commit had too many changes to have a
>   bloom filter written out, currently our limit is 512 diffs)

Perhaps also:
  - histogram of bloom filter sizes in 64-bit blocks
    (which is rough histogram of number of changes per commit)

Though I think all those statistics are a bit specific to the
repository, and how you use Git.

>
> Helped-by: Derrick Stolee <dstolee@microsoft.com
> Helped-by: SZEDER Gábor <szeder.dev@gmail.com>
> Helped-by: Jonathan Tan <jonathantanmy@google.com>
> Signed-off-by: Garima Singh <garima.singh@microsoft.com>
> ---
>  bloom.c              | 20 ++++++++++++
>  bloom.h              |  4 +++
>  revision.c           | 67 +++++++++++++++++++++++++++++++++++++--
>  revision.h           |  5 +++
>  t/t4216-log-bloom.sh | 74 ++++++++++++++++++++++++++++++++++++++++++++
>  5 files changed, 168 insertions(+), 2 deletions(-)
>  create mode 100755 t/t4216-log-bloom.sh
>
> diff --git a/bloom.c b/bloom.c
> index 86b1005802..0c7505d3d6 100644
> --- a/bloom.c
> +++ b/bloom.c
> @@ -235,3 +235,23 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
>  
>  	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_BLOCK;
> +
> +	if (!mod)
> +		return 1;

Ah, so filter->len equal to zero denotes too many changes for a Bloom
filter, and this conditional is a short-circuit test: always return
"maybe".

I wonder if we should explicitly check for filter->len = 1 and
filter->data[0] = 0, which should be empty Bloom filter -- for commit
with no changes with respect to first parent, and short-circuit
returning 0 (no file would ever belong).

> +
> +	for (i = 0; i < settings->num_hashes; i++) {
> +		uint64_t hash_mod = key->hashes[i] % mod;
> +		uint64_t block_pos = hash_mod / BITS_PER_BLOCK;

I have seen this code before... ;-)  The add_key_to_filter() function
includes almost identical code, but I am not sure if it is feasible to
eliminate this (slight) code duplication.  Probably not.

> +		if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
> +			return 0;

All right, if at least one hash function does not match, return "no"...

> +	}
> +
> +	return 1;

... else return "maybe".

> +}

I am wondering however if this code should not be moved earlier in the
series, so that commit 2/9 in series actually adds fully functional
[semi-generic] Bloom filter implementation.

> diff --git a/bloom.h b/bloom.h
> index 101d689bbd..9bdacd0a8e 100644
> --- a/bloom.h
> +++ b/bloom.h
> @@ -44,4 +44,8 @@ void fill_bloom_key(const char *data,
>  		    struct bloom_key *key,
>  		    struct bloom_filter_settings *settings);
>  
> +int bloom_filter_contains(struct bloom_filter *filter,
> +			  struct bloom_key *key,
> +			  struct bloom_filter_settings *settings);
> +
>  #endif
> diff --git a/revision.c b/revision.c
> index 39a25e7a5d..01f5330740 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -29,6 +29,7 @@
>  #include "prio-queue.h"
>  #include "hashmap.h"
>  #include "utf8.h"
> +#include "bloom.h"
>  
>  volatile show_early_output_fn_t show_early_output;
>  
> @@ -624,11 +625,34 @@ static void file_change(struct diff_options *options,
>  	options->flags.has_changes = 1;
>  }
>  
> +static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
> +						 struct commit *commit,
> +						 struct bloom_key *key,
> +						 struct bloom_filter_settings *settings)

All right, this function name is certainly descriptive.  I wonder if it
wouldn't be better to use a shorter name, like maybe_different(), or
maybe_not_treesame(), so that the conditional using this function would
read naturally:

  if (!maybe_different(revs, commit, revs->bloom_key,
  		       revs->bloom_filter_settings))
  	return REV_TREE_SAME;

But this might be just a matter of taste.

> +{
> +	struct bloom_filter *filter;
> +
> +	if (!revs->repo->objects->commit_graph)
> +		return -1;
> +	if (commit->generation == GENERATION_NUMBER_INFINITY)
> +		return -1;

O.K., so we check that there is loaded commit graph, and that given
commit is in a commit graph, otherwise we return "no data".

I agree with distinguishing between "no data" value (which is <0, a
convention for denoting errors), and "maybe" value.  Currently this
distinction is not utilized, but it would help in the case of more than
one path given -- in "no data" case there is no need to check other
paths against non-existing Bloom filter.

> +	if (!key || !settings)
> +		return -1;

Why the check for non-NULL 'key' and 'settings' is the last check?

BTW. when it is possible for key or settings to be NULL?  Or is it just
defensive programming?

> +
> +	filter = get_bloom_filter(revs->repo, commit, 0);

O.K., we won't be recomputing Bloom filter if it is not present either
on slab (as "inside-out" auxiliary data for a commit), or in the
commit-graph (in Bloom filter chunks).

> +
> +	if (!filter || !filter->len)
> +		return 1;

Sidenote: bloom_filter_contains() would also indirectly check for
filter->len being zero.  Though this doesn't cost much.

Shouldn't !filter case return value of -1 i.e. "no data", rather than
return value of 1 i.e. "maybe"?

> +
> +	return bloom_filter_contains(filter, key, settings);
> +}

All right.

> +
>  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,6 +677,16 @@ static int rev_compare_tree(struct rev_info *revs,
>  			return REV_TREE_SAME;
>  	}
>  
> +	if (revs->pruning.pathspec.nr == 1 && !nth_parent) {

All right, Bloom filter stores information about changed paths with
respect to first-parent changes only, so if we are asking about is not a
first parent (where nth_parent == 0), we cannot use Bloom filter.

Currently we limit the check to single pathspec only; that is a good
start and a good simplification.

> +		bloom_ret = check_maybe_different_in_bloom_filter(revs,
> +								  commit,
> +								  revs->bloom_key,
> +								  revs->bloom_filter_settings);
> +
> +		if (bloom_ret == 0)
> +			return REV_TREE_SAME;

Pretty straightforward.

> +	}
> +
>  	tree_difference = REV_TREE_SAME;
>  	revs->pruning.flags.has_changes = 0;
>  	if (diff_tree_oid(&t1->object.oid, &t2->object.oid, "",
> @@ -855,7 +889,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)) {

All right, we need to pass information about the index of the parent;
and we have just done that.  Good.

>  		case REV_TREE_SAME:
>  			if (!revs->simplify_history || !relevant_commit(p)) {
>  				/* Even if a merge with an uninteresting
> @@ -3342,6 +3376,33 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
>  	}
>  }
>  
> +static void prepare_to_use_bloom_filter(struct rev_info *revs)

All right, I see that pointers to bloom_key and bloom_filter_settings
were added to the rev_info struct.  I understand why the former is here,
but the latter seems to be there just as a shortcut (to not owned data),
which is fine but a bit strange.

Or is the latter here to allow for Bloom filter settings to possibly
change from commit-graph file in the chain to commit-graph file, and
thus from commit to commit?

> +{
> +	struct pathspec_item *pi;

Maybe 'pathspec' (or the like) instead of short and cryptic 'pi' would
be better a better name... unless 'pi' is used in other places already.

> +	const char *path;
> +	size_t len;
> +
> +	if (!revs->commits)
> +	    return;

When revs->commits may be NULL?  I understand that we need to have this
check because we use revs->commits->item next (sidenote: can revs ever
be NULL?).

Would `git log --all -- <path>` use Bloom filters (as it theoretically
could)?

> +
> +	parse_commit(revs->commits->item);

Why parsing first commit on the list of starting commits is needed here?
Please help me understand this line.

And shouldn't we use repo_parse_commit() here?

> +
> +	if (!revs->repo->objects->commit_graph)
> +		return;
> +
> +	revs->bloom_filter_settings = revs->repo->objects->commit_graph->settings;
> +	if (!revs->bloom_filter_settings)
> +		return;

All right, so if there is no commit graph, or the commit graph does not
include Bloom filter data, there is nothing to do.

Though I worry that it would make Git do not use Bloom filter if the top
commit-graph in the chain does not include Bloom filter data, while
other commit-graph files do (and Git could have used that information to
speed up the file history query).

> +
> +	pi = &revs->pruning.pathspec.items[0];
> +	path = pi->match;
> +	len = strlen(path);


Why not the following, if we do not do any checks for 'pi' value:

  +	path = &revs->pruning.pathspec.items[0]->match;

A question: is the path in the `match` field in `struct pathspec`
normalized with respect to trailing slash (for directories)?  Bloom
filter stores pathnames for directories without trailing slash.

What I mean is if, for example, both of those would use Bloom filter
data:

  $ git log -- Documentation/
  $ git log -- Documentation

> +
> +	load_bloom_filters();
> +	revs->bloom_key = xmalloc(sizeof(struct bloom_key));
> +	fill_bloom_key(path, len, revs->bloom_key, revs->bloom_filter_settings);

All right, looks good.

Though... do we leak revs->bloom_key, as should we worry about it?

> +}
> +
>  int prepare_revision_walk(struct rev_info *revs)
>  {
>  	int i;
> @@ -3391,6 +3452,8 @@ int prepare_revision_walk(struct rev_info *revs)
>  		simplify_merges(revs);
>  	if (revs->children.name)
>  		set_children(revs);
> +	if (revs->pruning.pathspec.nr == 1)
> +	    prepare_to_use_bloom_filter(revs);

Looks good.

Minor nitpick: 4 spaces instead of tab are used for indentation (or, to
be more exact a tab followed by 4 space, instead of two tabs):

  +	if (revs->pruning.pathspec.nr == 1)
  +		prepare_to_use_bloom_filter(revs);

>  	return 0;
>  }
>  
> diff --git a/revision.h b/revision.h
> index a1a804bd3d..65dc11e8f1 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -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,9 @@ struct rev_info {
>  	struct revision_sources *sources;
>  
>  	struct topo_walk_info *topo_walk_info;
> +
> +	struct bloom_key *bloom_key;
> +	struct bloom_filter_settings *bloom_filter_settings;

It might be a good idea to add one-line comment above those newly
introduced fields.  The `struct rev_info` has many subsections of fields
described by such comments (or even block comments), like e.g.

  /* Starting list */
  /* Parents of shown commits */
  /* The end-points specified by the end user */
  /* excluding from --branches, --refs, etc. expansion */
  /* Traversal flags */
  /* diff info for patches and for paths limiting */

  /*
   * Whether the arguments parsed by setup_revisions() included any
   * "input" revisions that might still have yielded an empty pending
   * list (e.g., patterns like "--all" or "--glob").
   */

>  };
>  
>  int ref_excluded(struct string_list *, const char *path);
> diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
> new file mode 100755
> index 0000000000..d42f077998
> --- /dev/null
> +++ b/t/t4216-log-bloom.sh
> @@ -0,0 +1,74 @@
> +#!/bin/sh
> +
> +test_description='git log for a path with bloom filters'
> +. ./test-lib.sh
> +
> +test_expect_success 'setup repo' '
> +	git init &&
> +	git config core.commitGraph true &&
> +	git config gc.writeCommitGraph false &&
> +	infodir=".git/objects/info" &&
> +	graphdir="$infodir/commit-graphs" &&
> +	test_oid_init

Why do you use `test_oid_init`, when you are *not* using `test_oid`?
I guess it is because t5318-commit-graph.sh uses it, isn't it?

The `graphdir` shell variable is not used either.

> +'
> +
> +test_expect_success 'create 9 commits and repack' '
> +	test_commit c1 file1 &&
> +	test_commit c2 file2 &&
> +	test_commit c3 file3 &&
> +	test_commit c4 file1 &&
> +	test_commit c5 file2 &&
> +	test_commit c6 file3 &&
> +	test_commit c7 file1 &&
> +	test_commit c8 file2 &&
> +	test_commit c9 file3
> +'

Wouldn't it be better for this step to be a part of 'setup repo' step?
Anyway, the test name says '... and repack', but `git repack` is missing
(it should be done after last test_commit).

I think it would be good idea to test behavior of Bloom filters with
respect to directories, so at least one file should be in a subdirectory
(maybe even deeper in hierarchy).

We should also test the behavior with respect to merges, and when we are
not following the first parent.  But that might be a separate part of
this test.

> +
> +printf "c7\nc4\nc1" > expect_file1

Doing things outside test is discouraged.  We can create a separate test
that creates those expect_file* files, or it can be a part of 'create
commits' test.

Anyway, instead of doing test without Bloom filters (something that
should have been tested already by other parts of testsuite), and then
doing the same test with Bloom filter, why not compare that the result
without and with Bloom filter is the same.  The t5318-commit-graph.sh
test does this with help of graph_git_two_modes() function:

  graph_git_two_modes () {
  	git -c core.commitGraph=true  $1 >output
  	git -c core.commitGraph=false $1 >expect
  	test_cmp expect output
  }

Sidenote: I wonder if it is high time to create t/lib-commit-graph.sh
helper with, among others, this common function.

> +
> +test_expect_success 'log without bloom filters' '
> +	git log --pretty="format:%s"  -- file1 > actual &&

CodingGuidelines:57: Redirection operators should be written with space
before, but no space after them.  (Minor nitpick)

  +	git log --pretty="format:%s"  -- file1 >actual &&

> +	test_cmp expect_file1 actual
> +'
> +
> +printf "c8\nc7\nc5\nc4\nc2\nc1" > expect_file1_file2

  +printf "c8\nc7\nc5\nc4\nc2\nc1" >expect_file1_file2

> +
> +test_expect_success 'multi-path log without bloom filters' '
> +	git log --pretty="format:%s"  -- file1 file2 > actual &&

  +	git log --pretty="format:%s"  -- file1 file2 >actual &&

> +	test_cmp expect_file1_file2 actual
> +'
> +
> +graph_read_expect() {

CodingGuidelines:144: We prefer a space between the function name and
the parentheses, and no space inside the parentheses.  (Minor nitpick)

  +graph_read_expect () {

> +	OPTIONAL=""
> +	NUM_CHUNKS=5
> +	if test ! -z $2
> +	then
> +		OPTIONAL=" $2"
> +		NUM_CHUNKS=$((3 + $(echo "$2" | wc -w)))

This should be either

  +		NUM_CHUNKS=$((5 + $(echo "$2" | wc -w)))

or more future proof

  +		NUM_CHUNKS=$(($NUM_CHUNKS + $(echo "$2" | wc -w)))

We got away with this bug because we were not using octopus merges, and
there were no optional core chunks, that is we never call
graph_read_expect with second parameter in this test.

> +	fi
> +	cat >expect <<- EOF

Why there is space between "<<-" and "EOF"?

> +	header: 43475048 1 1 $NUM_CHUNKS 0
> +	num_commits: $1
> +	chunks: oid_fanout oid_lookup commit_metadata bloom_indexes bloom_data$OPTIONAL
> +	EOF
> +	test-tool read-graph >output &&
> +	test_cmp expect output
> +}
> +
> +test_expect_success 'write commit graph with bloom filters' '
> +	git commit-graph write --reachable --changed-paths &&
> +	test_path_is_file $infodir/commit-graph &&
> +	graph_read_expect "9"
> +'

All right, this is preparatory step for further tests.

> +
> +test_expect_success 'log using bloom filters' '
> +	git log --pretty="format:%s" -- file1 > actual &&
> +	test_cmp expect_file1 actual
> +'
> +
> +test_expect_success 'multi-path log using bloom filters' '
> +	git log --pretty="format:%s"  -- file1 file2 > actual &&
> +	test_cmp expect_file1_file2 actual
> +'

With graph_git_two_modes() it would be much simpler:

  +test_expect_success 'single-path log' '
  +	git_graph_two_modes "git log --pretty=format:%s -- file1"
  +'

  +test_expect_success 'multi-path log' '
  +	git_graph_two_modes "git log --pretty=format:%s -- file1 file2"
  +'

What is missing is:
1. checking that Git is actually _using_ Bloom filters
   (which might be difficult to do)
2. testing that Bloom filters work also for history of subdirectories
   e.g. "git log -- subdir/" and "git log -- subdir"; this would of
   course require adjusting setup step
3. testing specific behaviors, like "git log --all -- file1"
4. merges with history following second parent
5. commits with no changes and/or merges with no first-parent changes
6. commit with more than 512 changed files (marked as slow test,
   and perhaps created with fast-import interface, like bulk commit
   creation in test_commit_bulk)

> +
> +test_done

Best regards,
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag
  2019-12-20 22:05 ` [PATCH 9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag Garima Singh via GitGitGadget
@ 2020-01-11 19:56   ` Jakub Narebski
  2020-01-15  0:55     ` Garima Singh
  0 siblings, 1 reply; 51+ messages in thread
From: Jakub Narebski @ 2020-01-11 19:56 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Garima Singh <garima.singh@microsoft.com>
>
> Add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS 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`.

OK, so it works in addition to GIT_TEST_COMMIT_GRAPH.

>
> The test suite passes when GIT_TEST_COMMIT_GRAPH and
> GIT_COMMIT_GRAPH_BLOOM_FILTERS are enabled.

Good.  Very good.

No errors found by Continuous Integration setup either?

>
> Helped-by: Derrick Stolee <dstolee@microsoft.com>
> Signed-off-by: Garima Singh <garima.singh@microsoft.com>
> ---
>  builtin/commit-graph.c        | 2 +-
>  ci/run-build-and-tests.sh     | 1 +
>  commit-graph.h                | 1 +
>  t/README                      | 3 +++
>  t/t4216-log-bloom.sh          | 3 +++
>  t/t5318-commit-graph.sh       | 2 ++
>  t/t5324-split-commit-graph.sh | 1 +
>  t/t5325-commit-graph-bloom.sh | 3 +++
>  8 files changed, 15 insertions(+), 1 deletion(-)
>
> diff --git a/builtin/commit-graph.c b/builtin/commit-graph.c
> index 9bd1e11161..97167959b2 100644
> --- a/builtin/commit-graph.c
> +++ b/builtin/commit-graph.c
> @@ -146,7 +146,7 @@ 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_bloom_filters)
> +	if (opts.enable_bloom_filters || git_env_bool(GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS, 0))
>  		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;
>

Very minor nitpick: not to make this line long, I would break it at the
boolean operator, that is write

  -	if (opts.enable_bloom_filters)
  +	if (opts.enable_bloom_filters ||
  +	    git_env_bool(GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS, 0))  
   		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;

I agree that this is a good place to put this check, by pretending that
`--changed-paths` option was given on command line.  Looks good.

>  	read_replace_refs = 0;
> diff --git a/ci/run-build-and-tests.sh b/ci/run-build-and-tests.sh
> index ff0ef7f08e..19d0846d34 100755
> --- a/ci/run-build-and-tests.sh
> +++ b/ci/run-build-and-tests.sh
> @@ -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_BLOOM_FILTERS=1
>  	export GIT_TEST_MULTI_PACK_INDEX=1
>  	make test
>  	;;

All right, adding this to CI would certainly exercise this feature.

> diff --git a/commit-graph.h b/commit-graph.h
> index 2202ad91ae..d914e6abf1 100644
> --- a/commit-graph.h
> +++ b/commit-graph.h
> @@ -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_BLOOM_FILTERS "GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS"
>

All right (the ordering is a mater of taste).

>  struct commit;
>  struct bloom_filter_settings;
> diff --git a/t/README b/t/README
> index caa125ba9a..399b190437 100644
> --- a/t/README
> +++ b/t/README
> @@ -378,6 +378,9 @@ 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_BLOOM_FILTERS=<boolean>, when true, forces commit-graph
> +write to compute and write bloom filters for every 'git commit-graph write'
> +

Thanks for documenting this.

Missing full stop '.' at the end of the sentence.  (Minor nit).

We might want to add ", as if '--changed-paths' option was given.", but
it is not strictly necessary.

>  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.
> diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
> index d42f077998..0e092b387c 100755
> --- a/t/t4216-log-bloom.sh
> +++ b/t/t4216-log-bloom.sh
> @@ -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_BLOOM_FILTERS=0
> +

OK, neither of those setting increase the coverage for this test.

On the other hand they won't make tests fail (or at least they
shouldn't, I think).  The t5318-commit-graph.sh doesn't include 
GIT_TEST_COMMIT_GRAPH=0, after all.

>  test_expect_success 'setup repo' '
>  	git init &&
>  	git config core.commitGraph true &&
> diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
> index 3f03de6018..613228bb12 100755
> --- a/t/t5318-commit-graph.sh
> +++ b/t/t5318-commit-graph.sh
> @@ -3,6 +3,8 @@
>  test_description='commit graph'
>  . ./test-lib.sh
>  
> +GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS=0
> +

All right, adding Bloom filters to commit-graph file would make test
cases utilizing graph_read_expect() fail.

>  test_expect_success 'setup full repo' '
>  	mkdir full &&
>  	cd "$TRASH_DIRECTORY/full" &&
> diff --git a/t/t5324-split-commit-graph.sh b/t/t5324-split-commit-graph.sh
> index c24823431f..181ca7e0cb 100755
> --- a/t/t5324-split-commit-graph.sh
> +++ b/t/t5324-split-commit-graph.sh
> @@ -4,6 +4,7 @@ test_description='split commit graph'
>  . ./test-lib.sh
>  
>  GIT_TEST_COMMIT_GRAPH=0
> +GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS=0

All right, same here: adding Bloom filters to commit-graph would make
test cases utilizing graph_read_expect() fail.

Sidenote: Here without GIT_TEST_COMMIT_GRAPH=0 tests that rely on
precise timing of writing commit-graph to create split commit-graph
would fail.

>  
>  test_expect_success 'setup repo' '
>  	git init &&
> diff --git a/t/t5325-commit-graph-bloom.sh b/t/t5325-commit-graph-bloom.sh
> index d7ef0e7fb3..a9c9e9fef6 100755
> --- a/t/t5325-commit-graph-bloom.sh
> +++ b/t/t5325-commit-graph-bloom.sh
> @@ -3,6 +3,9 @@
>  test_description='commit graph with bloom filters'
>  . ./test-lib.sh
>  
> +GIT_TEST_COMMIT_GRAPH=0
> +GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS=0
> +

This test also includes some split commit-graph test cases, so the above
is necessary.

All right.

>  test_expect_success 'setup repo' '
>  	git init &&
>  	git config core.commitGraph true &&

Best,
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-31 16:45 ` Jakub Narebski
@ 2020-01-13 16:54   ` Garima Singh
  2020-01-20 13:48     ` Jakub Narebski
  0 siblings, 1 reply; 51+ messages in thread
From: Garima Singh @ 2020-01-13 16:54 UTC (permalink / raw)
  To: Jakub Narebski, Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano

On 12/31/2019 11:45 AM, Jakub Narebski wrote:
> "Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:
>> Performance Gains: We tested the performance of 'git log -- <path>' on the git
>> repo, the linux repo 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.
> 
> Could you provide some more statistics about this internal repository,
> such as number of files, number of commits, perhaps also number of all
> objects?  Thanks in advance.
> 
> I wonder why such large difference in performance 2-5x vs 10-20x.  Is it
> about the depth of the file hierarchy?  How would the numbers look for
> files seated closer to the root in the same large repository, like 3-5
> levels deep in the tree?

The internal repository we saw these massive gains on has:
- 413579 commits. 
- 183303 files distributed across 34482 folders
The size on disk is about 17 GiB. 

And yes, the difference is performance gains is mostly because of how 
deep the files were in the hierarchy. How often a file has been touched
also makes a difference. The performance gains are less dramatic if the 
file has a very sparse history even if it is a deep file. 

The numbers from the git and linux repos for instance, are for files 
closer to the root, hence 2x to 5x. 

Thanks! 
Garima Singh

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 2/9] commit-graph: write changed paths bloom filters
  2020-01-06 18:44   ` Jakub Narebski
@ 2020-01-13 19:48     ` Garima Singh
  0 siblings, 0 replies; 51+ messages in thread
From: Garima Singh @ 2020-01-13 19:48 UTC (permalink / raw)
  To: Jakub Narebski, Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano,
	Garima Singh


On 1/6/2020 1:44 PM, Jakub Narebski wrote:

> "Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes: 
>> 3. The filters are sized according to the number of changes in the each commit,
>>    with minimum size of one 64 bit word.
> 
> Do I understand it correctly that the size of filter is 10*(number of
> changed files) bits, rounded up to nearest multiple of 64?
>

Yes.
  
>> +
>> +struct pathmap_hash_entry {
>> +    struct hashmap_entry entry;
>> +    const char path[FLEX_ARRAY];
>> +};
> 
> Hmmm... I wonder why use hashmap and not string_list.  This is for
> adding path with leading directories to the Bloom filter, isn't it?
> 

Yes. We do not want to repeat directories in the filter.

Thanks!
Garima Singh


^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 5/9] commit-graph: write changed path bloom filters to commit-graph file.
  2020-01-07 16:01   ` Jakub Narebski
@ 2020-01-14 15:14     ` Garima Singh
  0 siblings, 0 replies; 51+ messages in thread
From: Garima Singh @ 2020-01-14 15:14 UTC (permalink / raw)
  To: Jakub Narebski, Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano,
	Garima Singh


On 1/7/2020 11:01 AM, Jakub Narebski wrote:
> "Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:
>> +
>> +				if (hash_version != 1)
>> +					break;
> 
> What does it mean for Git?  Behave as if there were no Bloom filter
> data?
>

Yes. We choose to use Bloom filters best effort, and in such cases, we will 
just fall back to the original code path. 

>>  	if (ctx->num_commit_graphs_after > 1 &&
>>  	    write_graph_chunk_base(f, ctx)) {
>>  		return -1;
>> diff --git a/commit-graph.h b/commit-graph.h
>> index 952a4b83be..2202ad91ae 100644
>> --- a/commit-graph.h
>> +++ b/commit-graph.h
>> @@ -10,6 +10,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(const char *obj_dir);
>>  int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
>> @@ -58,6 +59,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 *settings;
> 
> Should this be part of `struct commit_graph`?  Shouldn't we free() this
> data, or is it a pointer into xmmap-ped file... no it isn't -- we
> xalloc() it, so we should free() it.
> 
> I think it should be done in 'cleanup:' section of write_commit_graph(),
> but I am not entirely sure.
> 

Thanks for calling this out! This is definitely a bug in how commit-graph.c
frees up the graph. The right way to free the graph would be to call
free_commit_graph() instead of free(graph) like many places in that file. 

Cleaning up this entire pattern would be orthogonal to this series, so 
I will follow up with a separate series that cleans it up overall. 

For now, I will free up `bloom_filter_settings` in free_commit_graph(). 

Cheers! 
Garima Singh

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 8/9] revision.c: use bloom filters to speed up path based revision walks
  2020-01-11  0:27   ` Jakub Narebski
@ 2020-01-15  0:08     ` Garima Singh
  0 siblings, 0 replies; 51+ messages in thread
From: Garima Singh @ 2020-01-15  0:08 UTC (permalink / raw)
  To: Jakub Narebski, Garima Singh via GitGitGadget
  Cc: git, Derrick Stolee, SZEDER Gábor, Jonathan Tan,
	Jeff Hostetler, Taylor Blau, Jeff King, Junio C Hamano,
	Garima Singh


On 1/10/2020 7:27 PM, Jakub Narebski wrote:
> "Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:
>>  		case REV_TREE_SAME:
>>  			if (!revs->simplify_history || !relevant_commit(p)) {
>>  				/* Even if a merge with an uninteresting
>> @@ -3342,6 +3376,33 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
>>  	}
>>  }
>>  
>> +static void prepare_to_use_bloom_filter(struct rev_info *revs)
> 
> All right, I see that pointers to bloom_key and bloom_filter_settings
> were added to the rev_info struct.  I understand why the former is here,
> but the latter seems to be there just as a shortcut (to not owned data),
> which is fine but a bit strange.
> 
> Or is the latter here to allow for Bloom filter settings to possibly
> change from commit-graph file in the chain to commit-graph file, and
> thus from commit to commit?
> 

The latter. The idea is to keep the implementation open to that 
possibility. Load the bloom filter settings from the commit graph file 
you are dealing with and use those settings to fill out the bloom_key.

>> +	const char *path;
>> +	size_t len;
>> +
>> +	if (!revs->commits)
>> +	    return;
> 
> When revs->commits may be NULL?  I understand that we need to have this
> check because we use revs->commits->item next (sidenote: can revs ever
> be NULL?).
> 
> Would `git log --all -- <path>` use Bloom filters (as it theoretically
> could)?
> 

I am being defensive about revs->commits being NULL for the reason you 
called out. 

And yes, `git log --all <path>` does use Bloom filters if provided a 
single pathspec and when following the first parent.  

>> +
>> +	if (!revs->repo->objects->commit_graph)
>> +		return;
>> +
>> +	revs->bloom_filter_settings = revs->repo->objects->commit_graph->settings;
>> +	if (!revs->bloom_filter_settings)
>> +		return;
> 
> All right, so if there is no commit graph, or the commit graph does not
> include Bloom filter data, there is nothing to do.
> 
> Though I worry that it would make Git do not use Bloom filter if the top
> commit-graph in the chain does not include Bloom filter data, while
> other commit-graph files do (and Git could have used that information to
> speed up the file history query).
> 

Thanks for bringing this up! I need to test this scenario out more. 

>> +
>> +printf "c7\nc4\nc1" > expect_file1
> 
> Doing things outside test is discouraged.  We can create a separate test
> that creates those expect_file* files, or it can be a part of 'create
> commits' test.
> 
> Anyway, instead of doing test without Bloom filters (something that
> should have been tested already by other parts of testsuite), and then
> doing the same test with Bloom filter, why not compare that the result
> without and with Bloom filter is the same.  The t5318-commit-graph.sh
> test does this with help of graph_git_two_modes() function:
> 
>   graph_git_two_modes () {
>   	git -c core.commitGraph=true  $1 >output
>   	git -c core.commitGraph=false $1 >expect
>   	test_cmp expect output
>   }
> 
> Sidenote: I wonder if it is high time to create t/lib-commit-graph.sh
> helper with, among others, this common function.
>

Thank you! I have restructured the test to do almost everything you 
have suggested. 

Also, a note for this v1 RFC series: I am working on proper formal tests 
right now. I didn't want to wait to get these nailed down before sending 
out the RFC series and getting the ball rolling. 

I have taken note of all the testing suggestions you have made in your 
review. They are very helpful and I appreciate it! 

Creating t/lib-commit-graph.sh helper would be orthogonal to this series,
so I will follow up with a separate series that does this. 

Cheers! 
Garima Singh

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag
  2020-01-11 19:56   ` Jakub Narebski
@ 2020-01-15  0:55     ` Garima Singh
  0 siblings, 0 replies; 51+ messages in thread
From: Garima Singh @ 2020-01-15  0:55 UTC (permalink / raw)
  To: Jakub Narebski, Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano, Garima Singh


On 1/11/2020 2:56 PM, Jakub Narebski wrote:
> "Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:
>>
>> The test suite passes when GIT_TEST_COMMIT_GRAPH and
>> GIT_COMMIT_GRAPH_BLOOM_FILTERS are enabled.
> 
> Good.  Very good.
> 
> No errors found by Continuous Integration setup either?
> 

Yes, the CI test pipelines all passed.

Cheers! 
Garima Singh

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2020-01-13 16:54   ` Garima Singh
@ 2020-01-20 13:48     ` Jakub Narebski
  2020-01-21 16:14       ` Garima Singh
  0 siblings, 1 reply; 51+ messages in thread
From: Jakub Narebski @ 2020-01-20 13:48 UTC (permalink / raw)
  To: Garima Singh
  Cc: Garima Singh via GitGitGadget, git, stolee, szeder.dev,
	jonathantanmy, jeffhost, me, peff, Junio C Hamano

Garima Singh <garimasigit@gmail.com> writes:
> On 12/31/2019 11:45 AM, Jakub Narebski wrote:
>> "Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:
>>>
>>> Performance Gains: We tested the performance of 'git log -- <path>' on the git
>>> repo, the linux repo 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.
>> 
>> Could you provide some more statistics about this internal repository,
>> such as number of files, number of commits, perhaps also number of all
>> objects?  Thanks in advance.
>> 
>> I wonder why such large difference in performance 2-5x vs 10-20x.  Is it
>> about the depth of the file hierarchy?  How would the numbers look for
>> files seated closer to the root in the same large repository, like 3-5
>> levels deep in the tree?
>
> The internal repository we saw these massive gains on has:
> - 413579 commits. 
> - 183303 files distributed across 34482 folders
> The size on disk is about 17 GiB. 

Thank you for the data.  Such information would be important
consideration to help to find out whether enabling Bloom filters in
given repository would be worth it.

> And yes, the difference is performance gains is mostly because of how 
> deep the files were in the hierarchy.

Right, this is understandable.  If files are diep in hierarchy, then we
have to unpack more tree objects to find out if the file was changed in
a given commit (provided that finding differences do not terminate early
thanks to hierarchical structure of tree objects).

>                                      How often a file has been touched
> also makes a difference. The performance gains are less dramatic if the 
> file has a very sparse history even if it is a deep file.

This looks a bit strange (or maybe I don't understand something).

Bloom filter can answer "no" and "maybe" to subset inclusion query.
This means that if file was *not* changed, with great probability the
answer from Bloom filter would be "no", and we would skip diff-ing
trees (which may terminate early, though).

On the other hand if file was changed by the commit, and the answer from
a Bloom filter is "maybe", then we have to perform diffing to make sure.

>
> The numbers from the git and linux repos for instance, are for files 
> closer to the root, hence 2x to 5x. 

That is quite nice speedup, anyway (git repository cannot be even
considered large; medium -- maybe).


P.S. I wonder if it would be worth to create some synthetical repository
to test performance gains of Bloom filters, perhaps in t/perf...

Best,
-- 
Jakub Narębski

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2020-01-20 13:48     ` Jakub Narebski
@ 2020-01-21 16:14       ` Garima Singh
  0 siblings, 0 replies; 51+ messages in thread
From: Garima Singh @ 2020-01-21 16:14 UTC (permalink / raw)
  To: Jakub Narebski
  Cc: Garima Singh via GitGitGadget, git, stolee, szeder.dev,
	jonathantanmy, jeffhost, me, peff, Junio C Hamano


On 1/20/2020 8:48 AM, Jakub Narebski wrote: >>                                      How often a file has been touched
>> also makes a difference. The performance gains are less dramatic if the 
>> file has a very sparse history even if it is a deep file.
> 
> This looks a bit strange (or maybe I don't understand something).
> 
> Bloom filter can answer "no" and "maybe" to subset inclusion query.
> This means that if file was *not* changed, with great probability the
> answer from Bloom filter would be "no", and we would skip diff-ing
> trees (which may terminate early, though).
> 
> On the other hand if file was changed by the commit, and the answer from
> a Bloom filter is "maybe", then we have to perform diffing to make sure.
>

Yes. What I meant by statement however is that the performance gain i.e. 
difference in performance between using and not using bloom filters, is not 
always as dramatic if the history is sparse and the trees aren't touched 
as often. So it is largely dependent on the shape of the repo and the shape
of the commit graph. 
 
>>
>> The numbers from the git and linux repos for instance, are for files 
>> closer to the root, hence 2x to 5x. 
> 
> That is quite nice speedup, anyway (git repository cannot be even
> considered large; medium -- maybe).
> 

Yeah. Git and Linux served as nice initial test beds. If you have any 
suggestions for interesting repos it would be worth running performanc 
investigations on, do let me know! 

> 
> P.S. I wonder if it would be worth to create some synthetical repository
> to test performance gains of Bloom filters, perhaps in t/perf...
> 

I will look into this after I get v1 out on the mailing list. 
Thanks! 

Cheers
Garima Singh

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
                   ` (12 preceding siblings ...)
  2019-12-31 16:45 ` Jakub Narebski
@ 2020-01-21 23:40 ` Emily Shaffer
  2020-01-27 18:24   ` Garima Singh
  13 siblings, 1 reply; 51+ messages in thread
From: Emily Shaffer @ 2020-01-21 23:40 UTC (permalink / raw)
  To: Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano

Hi,

On Fri, Dec 20, 2019 at 10:05:11PM +0000, Garima Singh via GitGitGadget wrote:
> This series is intended to start the conversation and many of the commit
> messages include specific call outs for suggestions and thoughts. 

Since it's mostly in RFC stage, I'm holding off on line by line comments
for now. I read the series (thanks for your patience) and I'll try to
leave some review thoughts in the diffspec here.

> Garima Singh (9):
>   [1/9] commit-graph: add --changed-paths option to write
I wonder if this can be combined with 2; without 2 actually the
documentation is wrong for this one, right? Although I suppose you also
mentioned 2 perhaps being too long :)

>   [2/9] commit-graph: write changed paths bloom filters
As I understand it, this one always regenerates the bloom filter pieces,
and doesn't write it down in the commit-graph file. How much longer does
that take now than before? I don't have a great feel for how often 'git
commit-graph' is run, or whether I need to be invoking it manually.

>   [3/9] commit-graph: use MAX_NUM_CHUNKS
>   [4/9] commit-graph: document bloom filter format
I suppose I might like to see this commit squashed with 5, but it's a
nit. I'm thinking it'd be handy to say "git blame commit-graph" and see
some nice doc about the format expected in the commit-graph file.

>   [5/9] commit-graph: write changed path bloom filters to commit-graph file.
Ah, so here we finally write down the result from 2 to disk in the
commit-graph file. And without 7, this gets recalculated every time we
call 'git commit-graph' still.

As for a technical doc around here, I'd really appreciate one. But I'm
speaking selfishly - I'd also be happy if I could watch a talk about
this design to make sure I understand it right :)

>   [6/9] commit-graph: test commit-graph write --changed-paths
>   [7/9] commit-graph: reuse existing bloom filters during write.
I saw an option to give up if there wasn't an existing bloom filter, but
I didn't see an option here to force recalculating. Is there a scenario
when that would be useful? What's the mitigation path if:
 - I have a commit-graph with v0 of the bloom index piece, but update to
   Git which uses v1?
 - My commit-graph file is corrupted in a way that the bloom filter
   results are incorrect and I am missing a blob change (and therefore
   not finding it during the walk)?
I think I understand that without this commit, 8 is not much speedup
because we will be recalculating the filter for each commit, rather than
using the written-down commit-graph file.

>   [8/9] revision.c: use bloom filters to speed up path based revision walks
>   [9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag

Speaking of making sure I understand the change right, I will also
summarize my own understanding in the hopes that I can be corrected and
others can learn too ;)

 - The general idea is that we can write down a hint at the tree level
   saying "something I own did change this commit"; when we look for an
   object later, we can skip the commit where it looks like that path
   didn't change.
 - The change is in two pieces: first, to generate the hints per tree
   (which happens during commit-graph); second, to use those hints to
   optimize a rev walk (which happens in revision.c patch 8)
 - When we calculate the hints during commit-graph, we check the diff of
   each tree compared to its recent ancestor to see if there was a
   change; if so we calculate a hash for each path and use that as a key
   for a map from hash to path. After we look through everything changed
   in the diff, we can add it to a cumulative bloom filter list (one
   filter per commit) so we have a handy in-memory idea of which paths
   changed in each commit.
 - When it's time to do the rev walk, we ask for the bloom filter for
   each commit and check if that commit's map contains the path to the
   object we're worried about; if so, then it's OK to unpack the tree
   and check if the path we are interested in actually did get changed
   during that commit.

Thanks.
 - Emily

> 
>  Documentation/git-commit-graph.txt            |   5 +
>  .../technical/commit-graph-format.txt         |  17 ++
>  Makefile                                      |   1 +
>  bloom.c                                       | 257 +++++++++++++++++
>  bloom.h                                       |  51 ++++
>  builtin/commit-graph.c                        |   9 +-
>  ci/run-build-and-tests.sh                     |   1 +
>  commit-graph.c                                | 116 +++++++-
>  commit-graph.h                                |   9 +-
>  revision.c                                    |  67 ++++-
>  revision.h                                    |   5 +
>  t/README                                      |   3 +
>  t/helper/test-read-graph.c                    |   4 +
>  t/t4216-log-bloom.sh                          |  77 ++++++
>  t/t5318-commit-graph.sh                       |   2 +
>  t/t5324-split-commit-graph.sh                 |   1 +
>  t/t5325-commit-graph-bloom.sh                 | 258 ++++++++++++++++++
>  17 files changed, 875 insertions(+), 8 deletions(-)
>  create mode 100644 bloom.c
>  create mode 100644 bloom.h
>  create mode 100755 t/t4216-log-bloom.sh
>  create mode 100755 t/t5325-commit-graph-bloom.sh
> 
> 
> base-commit: b02fd2accad4d48078671adf38fe5b5976d77304
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-497%2Fgarimasi514%2FcoreGit-bloomFilters-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-497/garimasi514/coreGit-bloomFilters-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/497
> -- 
> gitgitgadget

^ permalink raw reply	[flat|nested] 51+ messages in thread

* Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters
  2020-01-21 23:40 ` Emily Shaffer
@ 2020-01-27 18:24   ` Garima Singh
  0 siblings, 0 replies; 51+ messages in thread
From: Garima Singh @ 2020-01-27 18:24 UTC (permalink / raw)
  To: Emily Shaffer, Garima Singh via GitGitGadget
  Cc: git, stolee, szeder.dev, jonathantanmy, jeffhost, me, peff,
	Junio C Hamano

On 1/21/2020 6:40 PM, Emily Shaffer wrote:>> Garima Singh (9):
>>   [1/9] commit-graph: add --changed-paths option to write
> I wonder if this can be combined with 2; without 2 actually the
> documentation is wrong for this one, right? Although I suppose you also
> mentioned 2 perhaps being too long :)
> 

True. The ordering of these commits has been a very subjective discussion. 
Leaving this commit isolated the way it is, does help separate the option
from the bloom filter computation and commit graph write step. 

Also for clarity, I have changed the message for 2/9 to:
`commit-graph: compute Bloom filters for changed paths`

 
>>   [2/9] commit-graph: write changed paths bloom filters
> As I understand it, this one always regenerates the bloom filter pieces,
> and doesn't write it down in the commit-graph file. How much longer does
> that take now than before? I don't have a great feel for how often 'git
> commit-graph' is run, or whether I need to be invoking it manually.
> 

Yes. Computation and writing the bloom filters to the commit-graph file
(2/9 and 5/9) are ideally one time operations per commit. The time taken
depends on the shape and size of the repo since computation involves 
running a full diff. If you look at the discussions and patches exchanged
by Dr. Stolee and Peff: it has improved greatly since this RFC patch. 
My next submission will carry these patches and more concrete numbers for
time and memory. 

Also, `git commit-graph write` is not run very frequently and is ideally
incremental. A full rewrite is usually only done in case there is a 
corruption caught by `git commit-graph verify` in which case, you delete
and rewrite. These are both manual operations. 
See the docs here: 
https://git-scm.com/docs/git-commit-graph

Note: that fetch.writeCommitGraph is now on by default in which case 
new computations happen automatically for newly fetched commits. But 
I am not adding the --changed-paths option to that yet. So computing, 
writing and using bloom filters will still be an opt-in feature 
that users need to manually run. 
 
>>   [7/9] commit-graph: reuse existing bloom filters during write.
> I saw an option to give up if there wasn't an existing bloom filter, but
> I didn't see an option here to force recalculating. 

The way to force recalculation at the moment would be to delete the commit
graph file and write it again. 

Is there a scenario when that would be useful? 

Yes, if there are algorithm or hash version changes in the changed paths logic
we would need to rewrite. Each of the cases I can think of would involve
triggering a recalculation by deleting and rewriting.

What's the mitigation path if:
>  - I have a commit-graph with v0 of the bloom index piece, but update to
>    Git which uses v1?     
   
     Take a look at 5/9, when we are parsing the commit graph: if the code 
     is expected to work with a particular version (hash_version = 1 in the 
     current version), and the commit graph has a different version, we just 
     ignore it. In the future, this is where we could extend this to support 
     multiple versions.

>  - My commit-graph file is corrupted in a way that the bloom filter
>    results are incorrect and I am missing a blob change (and therefore
>    not finding it during the walk)?
         The mitigation for any commit graph corruption is to delete and 
     rewrite. 

     If however, we are confident that the bloom filter computation itself
     is wrong, the immediate mitigations would be to deleting the commit
     graph file and rewriting without the --changed-paths option; and ofc
     report the bug so it can be investigated and fixed. :) 

> Speaking of making sure I understand the change right, I will also
> summarize my own understanding in the hopes that I can be corrected and
> others can learn too ;)
> 
>  - The general idea is that we can write down a hint at the tree level
>    saying "something I own did change this commit"; when we look for an
>    object later, we can skip the commit where it looks like that path
>    didn't change.

The hint we are storing is a bloom filter which answers "No" or "Maybe"
to the question "Did file A change in commit c"
If the answer is No, we can ignore walking that commit. Else, we fall
back to the diff algorithm like before to confirm if the file changed or
not. 

>  - The change is in two pieces: first, to generate the hints per tree
>    (which happens during commit-graph); second, to use those hints to
>    optimize a rev walk (which happens in revision.c patch 8)

Yes. 

>  - When we calculate the hints during commit-graph, we check the diff of
>    each tree compared to its recent ancestor to see if there was a
>    change; if so we calculate a hash for each path and use that as a key
>    for a map from hash to path. After we look through everything changed
>    in the diff, we can add it to a cumulative bloom filter list (one
>    filter per commit) so we have a handy in-memory idea of which paths
>    changed in each commit.
>  - When it's time to do the rev walk, we ask for the bloom filter for
>    each commit and check if that commit's map contains the path to the
>    object we're worried about; if so, then it's OK to unpack the tree
>    and check if the path we are interested in actually did get changed
>    during that commit.

Essentially yes. There are a few implementation specifics this description
is glossing over, but I understand that is the intention. 

 
> Thanks.
>  - Emily

Cheers! 
Garima Singh

^ permalink raw reply	[flat|nested] 51+ messages in thread

end of thread, back to index

Thread overview: 51+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget
2019-12-20 22:05 ` [PATCH 1/9] commit-graph: add --changed-paths option to write Garima Singh via GitGitGadget
2020-01-01 20:20   ` Jakub Narebski
2019-12-20 22:05 ` [PATCH 2/9] commit-graph: write changed paths bloom filters Garima Singh via GitGitGadget
2019-12-21 16:48   ` Philip Oakley
2020-01-06 18:44   ` Jakub Narebski
2020-01-13 19:48     ` Garima Singh
2019-12-20 22:05 ` [PATCH 3/9] commit-graph: use MAX_NUM_CHUNKS Garima Singh via GitGitGadget
2020-01-07 12:19   ` Jakub Narebski
2019-12-20 22:05 ` [PATCH 4/9] commit-graph: document bloom filter format Garima Singh via GitGitGadget
2020-01-07 14:46   ` Jakub Narebski
2019-12-20 22:05 ` [PATCH 5/9] commit-graph: write changed path bloom filters to commit-graph file Garima Singh via GitGitGadget
2020-01-07 16:01   ` Jakub Narebski
2020-01-14 15:14     ` Garima Singh
2019-12-20 22:05 ` [PATCH 6/9] commit-graph: test commit-graph write --changed-paths Garima Singh via GitGitGadget
2020-01-08  0:32   ` Jakub Narebski
2019-12-20 22:05 ` [PATCH 7/9] commit-graph: reuse existing bloom filters during write Garima Singh via GitGitGadget
2020-01-09 19:12   ` Jakub Narebski
2019-12-20 22:05 ` [PATCH 8/9] revision.c: use bloom filters to speed up path based revision walks Garima Singh via GitGitGadget
2020-01-11  0:27   ` Jakub Narebski
2020-01-15  0:08     ` Garima Singh
2019-12-20 22:05 ` [PATCH 9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag Garima Singh via GitGitGadget
2020-01-11 19:56   ` Jakub Narebski
2020-01-15  0:55     ` Garima Singh
2019-12-20 22:14 ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Junio C Hamano
2019-12-22  9:26 ` Christian Couder
2019-12-22  9:38   ` Jeff King
2020-01-01 12:04     ` Jakub Narebski
2019-12-22  9:30 ` Jeff King
2019-12-22  9:32   ` [PATCH 1/3] commit-graph: examine changed-path objects in pack order Jeff King
2019-12-27 14:51     ` Derrick Stolee
2019-12-29  6:12       ` Jeff King
2019-12-29  6:28         ` Jeff King
2019-12-30 14:37         ` Derrick Stolee
2019-12-30 14:51           ` Derrick Stolee
2019-12-22  9:32   ` [PATCH 2/3] commit-graph: free large diffs, too Jeff King
2019-12-27 14:52     ` Derrick Stolee
2019-12-22  9:32   ` [PATCH 3/3] commit-graph: stop using full rev_info for diffs Jeff King
2019-12-27 14:53     ` Derrick Stolee
2019-12-26 14:21   ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Derrick Stolee
2019-12-29  6:03     ` Jeff King
2019-12-27 16:11   ` Derrick Stolee
2019-12-29  6:24     ` Jeff King
2019-12-30 16:04       ` Derrick Stolee
2019-12-30 17:02       ` Junio C Hamano
2019-12-31 16:45 ` Jakub Narebski
2020-01-13 16:54   ` Garima Singh
2020-01-20 13:48     ` Jakub Narebski
2020-01-21 16:14       ` Garima Singh
2020-01-21 23:40 ` Emily Shaffer
2020-01-27 18:24   ` Garima Singh

git@vger.kernel.org list mirror (unofficial, one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Example config snippet for mirrors

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.io/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/

AGPL code for this site: git clone https://public-inbox.org/public-inbox.git