Changed Paths Bloom Filters

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.

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.

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.

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.

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?

Quoted 2 lines

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?

Quoted 4 lines · Garima Singh via GitGitGadget

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

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.

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.

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.

Quoted 4 lines · Garima Singh via GitGitGadget

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.

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

Quoted 1 line

[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().

Quoted 11 lines · Jeff King

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:

Quoted 3 lines

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.

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.

Quoted 20 lines · Derrick Stolee

Quoted 11 lines · Jeff King

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.

Quoted 6 lines

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.

On the Linux kernel repository, this change reduced the computation time for 'git commit-graph write --reachable --changed-paths' from 6m30s to 4m50s.

Quoted 17 lines · Derrick Stolee

Quoted 3 lines

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 |

Quoted 2 lines

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

Quoted 4 lines

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.h struct diff_options { · line 291

Quoted 12 lines

diff.h +4 -0

index 6febe7e365..9443dc1b00 100644
@@ -285,6 +285,11 @@ struct diff_options {
 	/* Number of hexdigits to abbreviate raw format output to. */
 	int abbrev;
 
+	/* If non-zero, then stop computing after this many changes. */
+	int max_changes;
+	/* For internal use only. */
+	int num_changes;

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

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.

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

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/[email protected]/
[2] https://lore.kernel.org/git/[email protected]/

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

Quoted 3 lines · Christian Couder

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.

From: Garima Singh <[email protected]>

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.

Documentation/git-commit-graph.txt +1 -0

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

builtin/commit-graph.c +1 -1

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

builtin/commit-graph.c +2 -0

 } 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")),

builtin/commit-graph.c +0 -0

 	read_replace_refs = 0;
 

commit-graph.h +0 -0

index 7f5c933fa2..952a4b83be 100644

From: Garima Singh <[email protected]>

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 <[email protected]>

Helped-by Derrick Stolee <[email protected]>

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

Makefile +0 -0

index 42a061d3fb..9d5e26f5d6 100644

bloom.h new file +4 -0

+};
+
+#define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10 }
+

bloom.h new file +2 -0

+
+#endif

bloom.c new file +4 -0

new file mode 100644
index 0000000000..08328cc381
@@ -0,0 +1,201 @@
+#include "git-compat-util.h"
+#include "bloom.h"
+#include "commit-graph.h"
+#include "object-store.h"

bloom.c new file +17 -0

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

bloom.c new file +1 -0

+{

+}
\ No newline at end of file

commit-graph.c +1 -0

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

commit-graph.c +6 -0

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

commit-graph.c +6 -0

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

commit-graph.c +1 -0

+	ctx->total_bloom_filter_size = 0;
 
 	if (ctx->split) {
 		struct commit_graph *g;

From: Garima Singh <[email protected]>

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

Signed-off-by Garima Singh <[email protected]>

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

commit-graph.c +0 -0

index 61e60ff98a..8c4941eeaa 100644

From: Garima Singh <[email protected]>

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 <[email protected]>

Signed-off-by Garima Singh <[email protected]>

---
 Documentation/technical/commit-graph-format.txt | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

Documentation/technical/commit-graph-format.txt +0 -0

index a4f17441ae..6497f19f08 100644

From: Garima Singh <[email protected]>

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

Helped-by Derrick Stolee <[email protected]>

Signed-off-by Garima Singh <[email protected]>

---
 commit-graph.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++-
 commit-graph.h |  5 ++++
 2 files changed, 85 insertions(+), 1 deletion(-)

commit-graph.c +0 -0

index 8c4941eeaa..def2ade166 100644

commit-graph.c +0 -0

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

commit-graph.c +5 -0

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

commit-graph.c +5 -0

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

commit-graph.c +0 -0

 	if (ctx->num_commit_graphs_after > 1) {
 		chunk_ids[num_chunks] = GRAPH_CHUNKID_BASE;
 		num_chunks++;

commit-graph.c +0 -0

 	if (ctx->num_commit_graphs_after > 1 &&
 	    write_graph_chunk_base(f, ctx)) {
 		return -1;

commit-graph.h +1 -0

index 952a4b83be..2202ad91ae 100644
@@ -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);

From: Garima Singh <[email protected]>

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 <[email protected]>

Signed-off-by Garima Singh <[email protected]>

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

t/helper/test-read-graph.c +0 -0

index d2884efe0a..aff597c7a3 100644

t/helper/test-read-graph.c +0 -0

 	printf("\n");
 
 	UNLEAK(graph);

t/t5325-commit-graph-bloom.sh new file +5 -0

new file mode 100755
index 0000000000..d7ef0e7fb3
@@ -0,0 +1,255 @@
+#!/bin/sh
+
+test_description='commit graph with bloom filters'
+. ./test-lib.sh
+

t/t5325-commit-graph-bloom.sh new file +225 -0

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

From: Garima Singh <[email protected]>

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 <[email protected]>

Signed-off-by Garima Singh <[email protected]>

---
 bloom.c        | 40 ++++++++++++++++++++++++++++++++++++++--
 bloom.h        |  3 ++-
 commit-graph.c |  6 +++---
 3 files changed, 43 insertions(+), 6 deletions(-)

bloom.c +3 -0

index 08328cc381..86b1005802 100644
@@ -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,

bloom.h +0 -0

 void fill_bloom_key(const char *data,
 		    int len,

commit-graph.c +1 -1

index def2ade166..0580ce75d5 100644
@@ -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++;

From: Garima Singh <[email protected]>

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 <[email protected]

Helped-by SZEDER Gábor <[email protected]>

Helped-by Jonathan Tan <[email protected]>

Signed-off-by Garima Singh <[email protected]>

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

bloom.c +0 -0

index 86b1005802..0c7505d3d6 100644
@@ -235,3 +235,23 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 
 	return filter;
 }

bloom.h +4 -0

index 101d689bbd..9bdacd0a8e 100644
@@ -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

revision.c +1 -0

index 39a25e7a5d..01f5330740 100644
@@ -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;