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

From: Jakub Narebski <jnareb@gmail.com>
Date: Feb 21, 2020, 17:31 UTC
Message-ID: <86o8trdeyh.fsf@gmail.com>
In-Reply-To: <77f1c561e8205c0598b57bf572640d21d64757f8.1580943390.git.gitgitgadget@gmail.com>

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

Show 5 quoted lines

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

Show 6 quoted lines

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

Show 52 quoted lines

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

Show 11 quoted lines

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

Show 8 quoted lines

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

Show 5 quoted lines

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

Show 13 quoted lines

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

Show 24 quoted lines

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

Show 8 quoted lines

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

Show 8 quoted lines

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

Show 5 quoted lines

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

Show 8 quoted lines

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

Show 12 quoted lines

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

Show 6 quoted lines

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

Show 10 quoted lines

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

Show 27 quoted lines

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

Show 16 quoted lines

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

Show 7 quoted lines

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