git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 5/8] commit-graph: check all leading directories in changed path Bloom filters

From
Taylor Blau <me@ttaylorr.com>
Date
Jun 19, 2020, 17:17 UTC
Message-ID
<20200619171717.GA55911@syl.local>
In-Reply-To
<9975fc96f1269b049ebdd54835a63480c3dcbe4e.1592252093.git.gitgitgadget@gmail.com>
Hi Stolee,
On Mon, Jun 15, 2020 at 08:14:50PM +0000, SZEDER Gábor via GitGitGadget wrote:
Show 103 quoted lines
> From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= <szeder.dev@gmail.com>
>
> The file 'dir/subdir/file' can only be modified if its leading
> directories 'dir' and 'dir/subdir' are modified as well.
>
> So when checking modified path Bloom filters looking for commits
> modifying a path with multiple path components, then check not only
> the full path in the Bloom filters, but all its leading directories as
> well.  Take care to check these paths in "deepest first" order,
> because it's the full path that is least likely to be modified, and
> the Bloom filter queries can short circuit sooner.
>
> This can significantly reduce the average false positive rate, by
> about an order of magnitude or three(!), and can further speed up
> pathspec-limited revision walks.  The table below compares the average
> false positive rate and runtime of
>
>   git rev-list HEAD -- "$path"
>
> before and after this change for 5000+ randomly* selected paths from
> each repository:
>
>                     Average false           Average        Average
>                     positive rate           runtime        runtime
>                   before     after     before     after   difference
>   ------------------------------------------------------------------
>   git             3.220%   0.7853%     0.0558s   0.0387s   -30.6%
>   linux           2.453%   0.0296%     0.1046s   0.0766s   -26.8%
>   tensorflow      2.536%   0.6977%     0.0594s   0.0420s   -29.2%
>
> *Path selection was done with the following pipeline:
>
> 	git ls-tree -r --name-only HEAD | sort -R | head -n 5000
>
> The improvements in runtime are much smaller than the improvements in
> average false positive rate, as we are clearly reaching diminishing
> returns here.  However, all these timings depend on that accessing
> tree objects is reasonably fast (warm caches).  If we had a partial
> clone and the tree objects had to be fetched from a promisor remote,
> e.g.:
>
>   $ git clone --filter=tree:0 --bare file://.../webkit.git webkit.notrees.git
>   $ git -C webkit.git -c core.modifiedPathBloomFilters=1 \
>         commit-graph write --reachable
>   $ cp webkit.git/objects/info/commit-graph webkit.notrees.git/objects/info/
>   $ git -C webkit.notrees.git -c core.modifiedPathBloomFilters=1 \
>         rev-list HEAD -- "$path"
>
> then checking all leading path component can reduce the runtime from
> over an hour to a few seconds (and this is with the clone and the
> promisor on the same machine).
>
> This adjusts the tracing values in t4216-log-bloom.sh, which provides a
> concrete way to notice the improvement.
>
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  revision.c           | 35 ++++++++++++++++++++++++++---------
>  revision.h           |  6 ++++--
>  t/t4216-log-bloom.sh |  2 +-
>  3 files changed, 31 insertions(+), 12 deletions(-)
>
> diff --git a/revision.c b/revision.c
> index c644c660917..027ae3982b4 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -670,9 +670,10 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)
>  {
>  	struct pathspec_item *pi;
>  	char *path_alloc = NULL;
> -	const char *path;
> +	const char *path, *p;
>  	int last_index;
> -	int len;
> +	size_t len;
> +	int path_component_nr = 0, j;
>
>  	if (!revs->commits)
>  		return;
> @@ -705,8 +706,22 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)
>
>  	len = strlen(path);
>
> -	revs->bloom_key = xmalloc(sizeof(struct bloom_key));
> -	fill_bloom_key(path, len, revs->bloom_key, revs->bloom_filter_settings);
> +	p = path;
> +	do {
> +		p = strchrnul(p + 1, '/');
> +		path_component_nr++;
> +	} while (p - path < len);
> +
> +	revs->bloom_keys_nr = path_component_nr;
> +	ALLOC_ARRAY(revs->bloom_keys, revs->bloom_keys_nr);
> +
> +	p = path;
> +	for (j = 0; j < revs->bloom_keys_nr; j++) {
> +		p = strchrnul(p + 1, '/');
> +
> +		fill_bloom_key(path, p - path, &revs->bloom_keys[j],
> +			       revs->bloom_filter_settings);
> +	}
>

Somewhat related to our off-list discussion yesterday, there is a bug in both 2.27 and this patch which produces incorrect results when (1) Bloom filters are enabled, and (2) we are doing a revision walk from root with the pathspec '.'.

What appears to be going on is that our normalization takes '.' -> '', and then we form a Bloom key based on the empty string, which will return 'definitely not' when querying the Bloom filter some of the time, which should never happen. This is a consequence of never inserting the empty key into the Bloom filter upon generation.

As a result, I have patched this in GitHub's fork (which is currently based on 2.27 and doesn't have these patches yet) by doing an early return when 'strlen(path) == 0'. Since it looks like these patches are going to land, here is some clean-up and a fix for the bug that you should feel free to test with and apply on top:

--- >8 ---
diff --git a/revision.c b/revision.c
index 8bd383b1dd..123e72698d 100644
--- a/revision.c
+++ b/revision.c
@@ -670,10 +670,10 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)
 {
        struct pathspec_item *pi;
        char *path_alloc = NULL;
-       const char *path, *p;
+       char *path, *p;
        int last_index;
        size_t len;
-       int path_component_nr = 0, j;
+       int path_component_nr = 1, j;

        if (!revs->commits)
                return;
@@ -698,29 +698,33 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)

        /* 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;
+               path_alloc = xstrdup(pi->match);
+               path_alloc[last_index] = '\0';
+               path = path_alloc;
+       } else {
+               path = pi->match;
+               len = pi->len;
+       }

-       len = strlen(path);
+       if (!len)
+               return;

-       p = path;
        do {
-               p = strchrnul(p + 1, '/');
-               path_component_nr++;
-       } while (p - path < len);
+               if (is_dir_sep(*p)) {
+                       *p = '\0';
+                       path_component_nr++;
+               }
+       } while (*p++);

        revs->bloom_keys_nr = path_component_nr;
        ALLOC_ARRAY(revs->bloom_keys, revs->bloom_keys_nr);

        p = path;
        for (j = 0; j < revs->bloom_keys_nr; j++) {
-               p = strchrnul(p + 1, '/');
-
-               fill_bloom_key(path, p - path, &revs->bloom_keys[j],
+               size_t plen = strlen(p);
+               fill_bloom_key(p, plen, &revs->bloom_keys[j],
                               revs->bloom_filter_settings);
+               p += plen;
        }

        if (trace2_is_enabled() && !bloom_filter_atexit_registered) {

>  	if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
>  		atexit(trace2_bloom_filter_statistics_atexit);
> @@ -720,7 +735,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
>  						 struct commit *commit)
>  {
>  	struct bloom_filter *filter;
> -	int result;
> +	int result = 1, j;
>
>  	if (!revs->repo->objects->commit_graph)
>  		return -1;
> @@ -740,9 +755,11 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
>  		return -1;
>  	}
>
> -	result = bloom_filter_contains(filter,
> -				       revs->bloom_key,
> -				       revs->bloom_filter_settings);
> +	for (j = 0; result && j < revs->bloom_keys_nr; j++) {
> +		result = bloom_filter_contains(filter,
> +					       &revs->bloom_keys[j],
> +					       revs->bloom_filter_settings);
> +	}
>
>  	if (result)
>  		count_bloom_filter_maybe++;
> @@ -782,7 +799,7 @@ static int rev_compare_tree(struct rev_info *revs,
>  			return REV_TREE_SAME;
>  	}
>
> -	if (revs->bloom_key && !nth_parent) {
> +	if (revs->bloom_keys_nr && !nth_parent) {
>  		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
>
>  		if (bloom_ret == 0)
> diff --git a/revision.h b/revision.h
> index 7c026fe41fc..abbfb4ab59a 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -295,8 +295,10 @@ struct rev_info {
>  	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 key(s) for the pathspec */
> +	struct bloom_key *bloom_keys;
> +	int bloom_keys_nr;
> +
>  	/*
>  	 * The bloom filter settings used to generate the key.
>  	 * This is loaded from the commit-graph being used.
> diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
> index c7011f33e2c..c13b97d3bda 100755
> --- a/t/t4216-log-bloom.sh
> +++ b/t/t4216-log-bloom.sh
> @@ -142,7 +142,7 @@ test_expect_success 'setup - add commit-graph to the chain with Bloom filters' '
>
>  test_bloom_filters_used_when_some_filters_are_missing () {
>  	log_args=$1
> -	bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"zero_length_filter\":0,\"maybe\":8,\"definitely_not\":6"
> +	bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"zero_length_filter\":0,\"maybe\":6,\"definitely_not\":8"
>  	setup "$log_args" &&
>  	grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" &&
>  	test_cmp log_wo_bloom log_w_bloom
> --
> gitgitgadget
>
Thanks,
Taylor
Previous: René ScharfeNext: Taylor Blau
Message 15 of 76 in “More commit-graph/Bloom filter improvements”
  1. 0/8 More commit-graph/Bloom filter improvementsDerrick Stolee via GitGitGadget, Jun 15, 2020
  2. 2/8 commit-graph: unify the signatures of all write_graph_chunk_*() functionsSZEDER Gábor via GitGitGadget, Jun 15, 2020
  3. René ScharfeJun 18, 2020
  4. 1/8 commit-graph: place bloom_settings in contextDerrick Stolee via GitGitGadget, Jun 15, 2020
  5. René ScharfeJun 18, 2020
  6. Derrick StoleeJun 19, 2020
  7. 3/8 commit-graph: simplify chunk writes into loopSZEDER Gábor via GitGitGadget, Jun 15, 2020
  8. René ScharfeJun 18, 2020
  9. 6/8 bloom: enforce a minimum size of 8 bytesDerrick Stolee via GitGitGadget, Jun 15, 2020
  10. 7/8 commit-graph: change test to die on parse, not loadDerrick Stolee via GitGitGadget, Jun 15, 2020
  11. 8/8 commit-graph: persist existence of changed-pathsDerrick Stolee via GitGitGadget, Jun 15, 2020
  12. 5/8 commit-graph: check all leading directories in changed path Bloom filtersSZEDER Gábor via GitGitGadget, Jun 15, 2020
  13. René ScharfeJun 18, 2020
  14. René ScharfeJun 19, 2020
  15. Taylor BlauJun 19, 2020
  16. Taylor BlauJun 19, 2020
  17. Derrick StoleeJun 23, 2020
  18. 4/8 commit-graph: check chunk sizes after writingSZEDER Gábor via GitGitGadget, Jun 15, 2020
  19. Junio C HamanoJun 17, 2020
  20. Derrick StoleeJun 18, 2020
  21. 00/11 More commit-graph/Bloom filter improvementsDerrick Stolee via GitGitGadget, Jun 23, 2020
  22. 01/11 commit-graph: place bloom_settings in contextDerrick Stolee via GitGitGadget, Jun 23, 2020
  23. 03/11 bloom: get_bloom_filter() cleanupsDerrick Stolee via GitGitGadget, Jun 23, 2020
  24. René ScharfeJun 25, 2020
  25. 02/11 commit-graph: change test to die on parse, not loadDerrick Stolee via GitGitGadget, Jun 23, 2020
  26. 04/11 commit-graph: persist existence of changed-pathsDerrick Stolee via GitGitGadget, Jun 23, 2020
  27. 05/11 commit-graph: unify the signatures of all write_graph_chunk_*() functionsSZEDER Gábor via GitGitGadget, Jun 23, 2020
  28. René ScharfeJun 25, 2020
  29. 06/11 commit-graph: simplify chunk writes into loopSZEDER Gábor via GitGitGadget, Jun 23, 2020
  30. René ScharfeJun 25, 2020
  31. Derrick StoleeJun 25, 2020
  32. 08/11 revision.c: fix whitespaceDerrick Stolee via GitGitGadget, Jun 23, 2020
  33. 09/11 revision: empty pathspecs should not use Bloom filtersTaylor Blau via GitGitGadget, Jun 23, 2020
  34. 10/11 commit-graph: check all leading directories in changed path Bloom filtersSZEDER Gábor via GitGitGadget, Jun 23, 2020
  35. René ScharfeJun 25, 2020
  36. Derrick StoleeJun 25, 2020
  37. SZEDER GáborJun 26, 2020
  38. Derrick StoleeJun 26, 2020
  39. 11/11 bloom: enforce a minimum size of 8 bytesDerrick Stolee via GitGitGadget, Jun 23, 2020
  40. 07/11 commit-graph: check chunk sizes after writingSZEDER Gábor via GitGitGadget, Jun 23, 2020
  41. René ScharfeJun 25, 2020
  42. Derrick StoleeJun 25, 2020
  43. Junio C HamanoJun 24, 2020
  44. Derrick StoleeJun 24, 2020
  45. Junio C HamanoJun 25, 2020
  46. Derrick StoleeJun 25, 2020
  47. Junio C HamanoJun 25, 2020
  48. 00/10 More commit-graph/Bloom filter improvementsDerrick Stolee via GitGitGadget, Jun 26, 2020
  49. 02/10 commit-graph: change test to die on parse, not loadDerrick Stolee via GitGitGadget, Jun 26, 2020
  50. 01/10 commit-graph: place bloom_settings in contextDerrick Stolee via GitGitGadget, Jun 26, 2020
  51. 03/10 bloom: fix logic in get_bloom_filter()Derrick Stolee via GitGitGadget, Jun 26, 2020
  52. SZEDER GáborJun 27, 2020
  53. Derrick StoleeJun 29, 2020
  54. 04/10 commit-graph: persist existence of changed-pathsDerrick Stolee via GitGitGadget, Jun 26, 2020
  55. 05/10 commit-graph: unify the signatures of all write_graph_chunk_*() functionsSZEDER Gábor via GitGitGadget, Jun 26, 2020
  56. 06/10 commit-graph: simplify chunk writes into loopSZEDER Gábor via GitGitGadget, Jun 26, 2020
  57. 07/10 commit-graph: check chunk sizes after writingSZEDER Gábor via GitGitGadget, Jun 26, 2020
  58. 10/10 commit-graph: check all leading directories in changed path Bloom filtersSZEDER Gábor via GitGitGadget, Jun 26, 2020
  59. 09/10 revision: empty pathspecs should not use Bloom filtersTaylor Blau via GitGitGadget, Jun 26, 2020
  60. 08/10 revision.c: fix whitespaceDerrick Stolee via GitGitGadget, Jun 26, 2020
  61. 00/10 More commit-graph/Bloom filter improvementsDerrick Stolee via GitGitGadget, Jul 1, 2020
  62. 01/10 commit-graph: place bloom_settings in contextDerrick Stolee via GitGitGadget, Jul 1, 2020
  63. 02/10 commit-graph: change test to die on parse, not loadDerrick Stolee via GitGitGadget, Jul 1, 2020
  64. 03/10 bloom: fix logic in get_bloom_filter()Derrick Stolee via GitGitGadget, Jul 1, 2020
  65. 05/10 commit-graph: unify the signatures of all write_graph_chunk_*() functionsSZEDER Gábor via GitGitGadget, Jul 1, 2020
  66. 06/10 commit-graph: simplify chunk writes into loopSZEDER Gábor via GitGitGadget, Jul 1, 2020
  67. 07/10 commit-graph: check chunk sizes after writingSZEDER Gábor via GitGitGadget, Jul 1, 2020
  68. 10/10 commit-graph: check all leading directories in changed path Bloom filtersSZEDER Gábor via GitGitGadget, Jul 1, 2020
  69. 09/10 revision: empty pathspecs should not use Bloom filtersTaylor Blau via GitGitGadget, Jul 1, 2020
  70. 04/10 commit-graph: persist existence of changed-pathsDerrick Stolee via GitGitGadget, Jul 1, 2020
  71. SZEDER GáborOct 15, 2020
  72. Taylor BlauOct 15, 2020
  73. Derrick StoleeOct 16, 2020
  74. Taylor BlauOct 16, 2020
  75. Derrick StoleeOct 16, 2020
  76. 08/10 revision.c: fix whitespaceDerrick Stolee via GitGitGadget, Jul 1, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.