git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Jakub Narebski <jnareb@gmail.com>
To: "Garima Singh via GitGitGadget" <gitgitgadget@gmail.com>
Cc: git@vger.kernel.org, stolee@gmail.com, szeder.dev@gmail.com,
	jonathantanmy@google.com, jeffhost@microsoft.com,
	me@ttaylorr.com, peff@peff.net, garimasigit@gmail.com,
	christian.couder@gmail.com, emilyshaffer@gmail.com,
	gitster@pobox.com, Garima Singh <garima.singh@microsoft.com>
Subject: Re: [PATCH v2 10/11] revision.c: use Bloom filters to speed up path based revision walks
Date: Fri, 21 Feb 2020 18:31:50 +0100	[thread overview]
Message-ID: <86o8trdeyh.fsf@gmail.com> (raw)
In-Reply-To: <77f1c561e8205c0598b57bf572640d21d64757f8.1580943390.git.gitgitgadget@gmail.com> (Garima Singh via GitGitGadget's message of "Wed, 05 Feb 2020 22:56:29 +0000")

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

> From: Garima Singh <garima.singh@microsoft.com>
>
> Revision walk will now use Bloom filters for commits to speed up revision
> walks for a particular path (for computing history for that path), if they
> are present in the commit-graph file.

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

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

>
> We load the Bloom filters during the prepare_revision_walk step, but only
> when dealing with a single pathspec.

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

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

All right, looks good.

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

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

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

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

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

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

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

This is good to know.

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

>
> 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>
> ---
>  revision.c                 | 124 +++++++++++++++++++++++++++++++-
>  revision.h                 |  11 +++
>  t/helper/test-read-graph.c |   4 ++
>  t/t4216-log-bloom.sh       | 140 +++++++++++++++++++++++++++++++++++++
>  4 files changed, 277 insertions(+), 2 deletions(-)
>  create mode 100755 t/t4216-log-bloom.sh
>
> diff --git a/revision.c b/revision.c
> index 8136929e23..d1622afa17 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -29,6 +29,8 @@
>  #include "prio-queue.h"
>  #include "hashmap.h"
>  #include "utf8.h"
> +#include "bloom.h"
> +#include "json-writer.h"
>  
>  volatile show_early_output_fn_t show_early_output;
>  
> @@ -624,11 +626,114 @@ static void file_change(struct diff_options *options,
>  	options->flags.has_changes = 1;
>  }
>  
> +static int bloom_filter_atexit_registered;
> +static unsigned int count_bloom_filter_maybe;
> +static unsigned int count_bloom_filter_definitely_not;
> +static unsigned int count_bloom_filter_false_positive;
> +static unsigned int count_bloom_filter_not_present;
> +static unsigned int count_bloom_filter_length_zero;
> +
> +static void trace2_bloom_filter_statistics_atexit(void)
> +{
> +	struct json_writer jw = JSON_WRITER_INIT;
> +
> +	jw_object_begin(&jw, 0);
> +	jw_object_intmax(&jw, "filter_not_present", count_bloom_filter_not_present);
> +	jw_object_intmax(&jw, "zero_length_filter", count_bloom_filter_length_zero);
> +	jw_object_intmax(&jw, "maybe", count_bloom_filter_maybe);
> +	jw_object_intmax(&jw, "definitely_not", count_bloom_filter_definitely_not);
> +	jw_end(&jw);
> +
> +	trace2_data_json("bloom", the_repository, "statistics", &jw);
> +
> +	jw_release(&jw);
> +}

I thought that it would be better to put this part together with tests
that absolutely require this functionality in a separate subsequent
patch, but now I am not so sure.  It is nice to have all or almost all
tests created in a single patch.

Looks good to me, but I don't know much about trace2 API, so take it
with a pinch of salt.

> +
> +static void prepare_to_use_bloom_filter(struct rev_info *revs)
> +{
> +	struct pathspec_item *pi;
> +	char *path_alloc = NULL;
> +	const char *path;
> +	int last_index;
> +	int len;
> +
> +	if (!revs->commits)
> +	    return;

I see that we need this because in next command we dereference
revs->commits to get revs->commits->item.

If I understand it correctly empty pending list may happen with "--all"
or "--glob" options, but somebody with more experience in this area of
code is needed to state for sure.

Should we test `git log --all -- <path>`?

> +
> +	repo_parse_commit(revs->repo, revs->commits->item);

Are we calling this function for its side-effects?  Wouldn't using
prepare_commit_graph(revs->repo) here be a better solution?

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

Looks good to me.  If there is no commit graph, then there are no Bloom
filters to consult.

> +
> +	revs->bloom_filter_settings = revs->repo->objects->commit_graph->bloom_filter_settings;

Hmmm... is that why bloom_filter_settings is a pointer to struct, and
not struct itself?

> +	if (!revs->bloom_filter_settings)
> +		return;

Looks good to me.  If there is no Bloomm filter in the commit-graph
file, then there are no Bloom filters to consult.

> +
> +	pi = &revs->pruning.pathspec.items[0];
> +	last_index = pi->len - 1;
> +

It might be a good idea to add a comment explaining what is happening
here, for example:

  +	/* remove single trailing slash from path, if needed */
> +	if (pi->match[last_index] == '/') {
> +	    path_alloc = xstrdup(pi->match);
> +	    path_alloc[last_index] = '\0';
> +	    path = path_alloc;
> +	} else
> +	    path = pi->match;
> +
> +	len = strlen(path);

We can avoid computing strlen(path) here, because in first branch of
this conditional we have len = last_index, in the second branch we have
len = pi->len.

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

All right, this is the meat of this function: creating bloom_key for a
path.  Looks good to me.

> +
> +	if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
> +		atexit(trace2_bloom_filter_statistics_atexit);
> +		bloom_filter_atexit_registered = 1;
> +	}

OK, here we register trace2 Bloom filter statistics handler, but only
once, and only when needed.

> +
> +	free(path_alloc);

OK, path_alloc is either xstrdup-ed string, or NULL, and is no longer
needed (after possibly being used to create bloom_key).

> +}
> +
> +static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
> +						 struct commit *commit)
> +{
> +	struct bloom_filter *filter;
> +	int result;
> +
> +	if (!revs->repo->objects->commit_graph)
> +		return -1;
> +
> +	if (commit->generation == GENERATION_NUMBER_INFINITY)
> +		return -1;

Idle thought: would it be useful to gather for trace2 statistics also
number of commits encountered that were outside commit-graph?

> +
> +	filter = get_bloom_filter(revs->repo, commit, 0);
> +
> +	if (!filter) {
> +		count_bloom_filter_not_present++;
> +		return -1;
> +	}
> +
> +	if (!filter->len) {
> +		count_bloom_filter_length_zero++;
> +		return -1;
> +	}
> +
> +	result = bloom_filter_contains(filter,
> +				       revs->bloom_key,
> +				       revs->bloom_filter_settings);
> +
> +	if (result)
> +		count_bloom_filter_maybe++;
> +	else
> +		count_bloom_filter_definitely_not++;
> +
> +	return result;
> +}

The whole check_maybe_different_in_bloom_filter() looks good to me,
thanks to designing and building a good API.

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

I don't understand why it is initialized to 1, and not to 0.

>  
>  	if (!t1)
>  		return REV_TREE_NEW;
> @@ -653,11 +758,23 @@ static int rev_compare_tree(struct rev_info *revs,
>  			return REV_TREE_SAME;
>  	}
>  
> +	if (revs->pruning.pathspec.nr == 1 && !revs->reflog_info && !nth_parent) {

Shouldn't we check upfront here that revs->bloom_key is not NULL?
I don't think we check this down the callchain...

Or even better replace the first two checks with it, as revs->bloom_key
is set only if (revs->pruning.pathspec.nr == 1 && !revs->reflog_info),
see addition to prepare_revision_walk() below.

Of course the !nth_parent check needs to be kept, as this changes during
the revision walk (it is a limitation of current version of Bloom filter
in that only changes with respect to first parent are stored in filter).

> +		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
> +
> +		if (bloom_ret == 0)
> +			return REV_TREE_SAME;
> +	}

All right, if we have single pathspec, and we don't walk reflog (?), and
we are interested in first parent, then we query the Bloom filter.

The Bloom filter can return 'no' or 'maybe'; if it returns 'no' then we
can short-circuit and avoid computing the tree diff.

> +
>  	tree_difference = REV_TREE_SAME;
>  	revs->pruning.flags.has_changes = 0;
>  	if (diff_tree_oid(&t1->object.oid, &t2->object.oid, "",
>  			   &revs->pruning) < 0)
>  		return REV_TREE_DIFFERENT;
> +
> +	if (!nth_parent)

Shouldn't this condition be exactly the same as for running
check_maybe_different_in_bloom_filter()?  Otherwise due to initializing
bloom_ret to 1 we would get wrong statistics, isn't it?

> +		if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
> +			count_bloom_filter_false_positive++;
> +

All right, looks good.

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

OK, we are just dding new parameter, with the information needed to
decide whether Bloom filters can be used or not.

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

Well, the limitation that the technique _currently_ works only with a
single pathspec is stated explicitly, but the fact that it is turned off
for some reason for --walk-reflog is not.

Otherwise, looks good to me.

>  	if (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED)
>  		commit_list_sort_by_date(&revs->commits);
>  	if (revs->no_walk)
> @@ -3379,6 +3498,7 @@ int prepare_revision_walk(struct rev_info *revs)
>  		simplify_merges(revs);
>  	if (revs->children.name)
>  		set_children(revs);
> +
>  	return 0;
>  }

Unrelated coding style fixup, but we are doing changes in the
neighborhood.  All right, I can agree to that.

>  
> diff --git a/revision.h b/revision.h
> index 475f048fb6..7c026fe41f 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,15 @@ struct rev_info {
>  	struct revision_sources *sources;
>  
>  	struct topo_walk_info *topo_walk_info;
> +
> +	/* Commit graph bloom filter fields */
> +	/* The bloom filter key for the pathspec */
> +	struct bloom_key *bloom_key;
> +	/*
> +	 * The bloom filter settings used to generate the key.
> +	 * This is loaded from the commit-graph being used.
> +	 */
> +	struct bloom_filter_settings *bloom_filter_settings;

It is nice having those explanatory comments.

Sidenote: if I understand it correctly, revs->bloom_key is allocated but
never free()d.  On the other hand revs->bloom_filter_settings is a weak
reference / is set to the value of other pointer, which is allocated and
free()d together with commit_graph struct.

>  };
>  
>  int ref_excluded(struct string_list *, const char *path);
> diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c
> 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");

This chunk could be moved to the commit adding --changed-paths
option... on the other hand if all tests are to be added by this patch,
it can be left as is.

>  
>  	UNLEAK(graph);
> diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
> new file mode 100755
> index 0000000000..19eca1864b
> --- /dev/null
> +++ b/t/t4216-log-bloom.sh
[...]

I'll leave reviewing tests of this feature for the next email.

Best regards,
-- 
Jakub Narębski

  reply	other threads:[~2020-02-21 17:32 UTC|newest]

Thread overview: 159+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
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-02-02 18:43         ` Jakub Narebski
2020-01-21 23:40 ` Emily Shaffer
2020-01-27 18:24   ` Garima Singh
2020-02-01 23:32   ` Jakub Narebski
2020-02-05 22:56 ` [PATCH v2 00/11] " Garima Singh via GitGitGadget
2020-02-05 22:56   ` [PATCH v2 01/11] commit-graph: use MAX_NUM_CHUNKS Garima Singh via GitGitGadget
2020-02-09 12:39     ` Jakub Narebski
2020-02-05 22:56   ` [PATCH v2 02/11] bloom: core Bloom filter implementation for changed paths Garima Singh via GitGitGadget
2020-02-15 17:17     ` Jakub Narebski
2020-02-16 16:49     ` Jakub Narebski
2020-02-22  0:32       ` Garima Singh
2020-02-23 13:38         ` Jakub Narebski
2020-02-24 17:34           ` Garima Singh
2020-02-24 18:20             ` Jakub Narebski
2020-02-05 22:56   ` [PATCH v2 03/11] diff: halt tree-diff early after max_changes Derrick Stolee via GitGitGadget
2020-02-17  0:00     ` Jakub Narebski
2020-02-22  0:37       ` Garima Singh
2020-02-05 22:56   ` [PATCH v2 04/11] commit-graph: compute Bloom filters for changed paths Garima Singh via GitGitGadget
2020-02-17 21:56     ` Jakub Narebski
2020-02-22  0:55       ` Garima Singh
2020-02-23 17:34         ` Jakub Narebski
2020-02-05 22:56   ` [PATCH v2 05/11] commit-graph: examine changed-path objects in pack order Jeff King via GitGitGadget
2020-02-18 17:59     ` Jakub Narebski
2020-02-24 18:29       ` Garima Singh
2020-02-05 22:56   ` [PATCH v2 06/11] commit-graph: examine commits by generation number Derrick Stolee via GitGitGadget
2020-02-19  0:32     ` Jakub Narebski
2020-02-24 20:45       ` Garima Singh
2020-02-05 22:56   ` [PATCH v2 07/11] commit-graph: write Bloom filters to commit graph file Garima Singh via GitGitGadget
2020-02-19 15:13     ` Jakub Narebski
2020-02-24 21:14       ` Garima Singh
2020-02-25 11:40         ` Jakub Narebski
2020-02-25 15:58           ` Garima Singh
2020-02-05 22:56   ` [PATCH v2 08/11] commit-graph: reuse existing Bloom filters during write Garima Singh via GitGitGadget
2020-02-20 18:48     ` Jakub Narebski
2020-02-24 21:45       ` Garima Singh
2020-02-05 22:56   ` [PATCH v2 09/11] commit-graph: add --changed-paths option to write subcommand Garima Singh via GitGitGadget
2020-02-20 20:28     ` Jakub Narebski
2020-02-24 21:51       ` Garima Singh
2020-02-25 12:10         ` Jakub Narebski
2020-02-20 22:10     ` Bryan Turner
2020-02-22  1:44       ` Garima Singh
2020-02-05 22:56   ` [PATCH v2 10/11] revision.c: use Bloom filters to speed up path based revision walks Garima Singh via GitGitGadget
2020-02-21 17:31     ` Jakub Narebski [this message]
2020-02-21 22:45     ` Jakub Narebski
2020-02-05 22:56   ` [PATCH v2 11/11] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Garima Singh via GitGitGadget
2020-02-22  0:11     ` Jakub Narebski
2020-02-07 13:52   ` [PATCH v2 00/11] Changed Paths Bloom Filters SZEDER Gábor
2020-02-07 15:09     ` Garima Singh
2020-02-07 15:36       ` Derrick Stolee
2020-02-07 16:15         ` SZEDER Gábor
2020-02-07 16:33           ` Derrick Stolee
2020-02-11 19:08       ` Garima Singh
2020-02-08 23:04   ` Jakub Narebski
2020-02-21 17:41     ` Garima Singh
2020-03-29 18:36       ` Junio C Hamano
2020-03-30  0:31   ` [PATCH v3 00/16] " Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 01/16] commit-graph: define and use MAX_NUM_CHUNKS Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 02/16] bloom.c: add the murmur3 hash implementation Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 03/16] bloom.c: introduce core Bloom filter constructs Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 04/16] bloom.c: core Bloom filter implementation for changed paths Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 05/16] diff: halt tree-diff early after max_changes Derrick Stolee via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 06/16] commit-graph: compute Bloom filters for changed paths Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 07/16] commit-graph: examine changed-path objects in pack order Jeff King via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 08/16] commit-graph: examine commits by generation number Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 09/16] diff: skip batch object download when possible Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 10/16] commit-graph: write Bloom filters to commit graph file Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 11/16] commit-graph: reuse existing Bloom filters during write Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 12/16] commit-graph: add --changed-paths option to write subcommand Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 13/16] revision.c: use Bloom filters to speed up path based revision walks Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 14/16] revision.c: add trace2 stats around Bloom filter usage Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 15/16] t4216: add end to end tests for git log with Bloom filters Garima Singh via GitGitGadget
2020-03-30  0:31     ` [PATCH v3 16/16] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Garima Singh via GitGitGadget
2020-04-06 16:59     ` [PATCH v4 00/15] Changed Paths Bloom Filters Garima Singh via GitGitGadget
2020-04-06 16:59       ` [PATCH v4 01/15] commit-graph: define and use MAX_NUM_CHUNKS Garima Singh via GitGitGadget
2020-04-06 16:59       ` [PATCH v4 02/15] bloom.c: add the murmur3 hash implementation Garima Singh via GitGitGadget
2020-04-06 16:59       ` [PATCH v4 03/15] bloom.c: introduce core Bloom filter constructs Garima Singh via GitGitGadget
2020-04-06 16:59       ` [PATCH v4 04/15] bloom.c: core Bloom filter implementation for changed paths Garima Singh via GitGitGadget
2020-06-27 15:53         ` SZEDER Gábor
2020-04-06 16:59       ` [PATCH v4 05/15] diff: halt tree-diff early after max_changes Derrick Stolee via GitGitGadget
2020-08-04 14:47         ` SZEDER Gábor
2020-08-04 16:25           ` Derrick Stolee
2020-08-04 17:00             ` SZEDER Gábor
2020-08-04 17:31               ` Derrick Stolee
2020-08-05 17:08                 ` Derrick Stolee
2020-04-06 16:59       ` [PATCH v4 06/15] commit-graph: compute Bloom filters for changed paths Garima Singh via GitGitGadget
2020-04-06 16:59       ` [PATCH v4 07/15] commit-graph: examine changed-path objects in pack order Jeff King via GitGitGadget
2020-04-06 16:59       ` [PATCH v4 08/15] commit-graph: examine commits by generation number Garima Singh via GitGitGadget
2020-04-06 16:59       ` [PATCH v4 09/15] commit-graph: write Bloom filters to commit graph file Garima Singh via GitGitGadget
2020-05-29  8:57         ` SZEDER Gábor
2020-05-29 13:35           ` Derrick Stolee
2020-05-31 17:23             ` SZEDER Gábor
2020-07-09 17:00         ` [PATCH] commit-graph: fix "Writing out commit graph" progress counter SZEDER Gábor
2020-07-09 18:01           ` Derrick Stolee
2020-07-09 18:20             ` Derrick Stolee
2020-04-06 16:59       ` [PATCH v4 10/15] commit-graph: reuse existing Bloom filters during write Garima Singh via GitGitGadget
2020-06-19 14:02         ` SZEDER Gábor
2020-06-19 19:28           ` Junio C Hamano
2020-07-27 21:33         ` SZEDER Gábor
2020-04-06 16:59       ` [PATCH v4 11/15] commit-graph: add --changed-paths option to write subcommand Garima Singh via GitGitGadget
2020-06-07 22:21         ` SZEDER Gábor
2020-04-06 16:59       ` [PATCH v4 12/15] revision.c: use Bloom filters to speed up path based revision walks Garima Singh via GitGitGadget
2020-06-26  6:34         ` SZEDER Gábor
2020-04-06 16:59       ` [PATCH v4 13/15] revision.c: add trace2 stats around Bloom filter usage Garima Singh via GitGitGadget
2020-04-06 16:59       ` [PATCH v4 14/15] t4216: add end to end tests for git log with Bloom filters Garima Singh via GitGitGadget
2020-04-06 16:59       ` [PATCH v4 15/15] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Garima Singh via GitGitGadget
2020-04-08 15:51       ` [PATCH v4 00/15] Changed Paths Bloom Filters Derrick Stolee
2020-04-08 19:21         ` Junio C Hamano
2020-04-08 20:05         ` Jakub Narębski
2020-04-12 20:34         ` Taylor Blau
2020-03-05 19:49 ` [PATCH 0/9] [RFC] " Garima Singh

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=86o8trdeyh.fsf@gmail.com \
    --to=jnareb@gmail.com \
    --cc=christian.couder@gmail.com \
    --cc=emilyshaffer@gmail.com \
    --cc=garima.singh@microsoft.com \
    --cc=garimasigit@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitgitgadget@gmail.com \
    --cc=gitster@pobox.com \
    --cc=jeffhost@microsoft.com \
    --cc=jonathantanmy@google.com \
    --cc=me@ttaylorr.com \
    --cc=peff@peff.net \
    --cc=stolee@gmail.com \
    --cc=szeder.dev@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).