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

[PATCH v3 16/17] commit-graph: reuse existing Bloom filters where possible

From
Taylor Blau <me@ttaylorr.com>
Date
Oct 10, 2023, 20:34 UTC
Message-ID
<abbef95ae8051401606fc181e9ded9e9fcf51872.1696969994.git.me@ttaylorr.com>
In-Reply-To
<cover.1696969994.git.me@ttaylorr.com>

In 9e4df4da07 (commit-graph: new filter ver. that fixes murmur3, 2023-08-01), a bug was described where it's possible for Git to produce non-murmur3 hashes when the platform's "char" type is signed, and there are paths with characters whose highest bit is set (i.e. all characters

>= 0x80).

That patch allows the caller to control which version of Bloom filters are read and written. However, even on platforms with a signed "char" type, it is possible to reuse existing Bloom filters if and only if there are no changed paths in any commit's first parent tree-diff whose characters have their highest bit set.

When this is the case, we can reuse the existing filter without having to compute a new one. This is done by marking trees which are known to have (or not have) any such paths. When a commit's root tree is verified to not have any such paths, we mark it as such and declare that the commit's Bloom filter is reusable.

Note that this heuristic only goes in one direction. If neither a commit nor its first parent have any paths in their trees with non-ASCII characters, then we know for certain that a path with non-ASCII characters will not appear in a tree-diff against that commit's first parent. The reverse isn't necessarily true: just because the tree-diff doesn't contain any such paths does not imply that no such paths exist in either tree.

So we end up recomputing some Bloom filters that we don't strictly have to (i.e. their bits are the same no matter which version of murmur3 we use). But culling these out is impossible, since we'd have to perform the full tree-diff, which is the same effort as computing the Bloom filter from scratch.

But because we can cache our results in each tree's flag bits, we can often avoid recomputing many filters, thereby reducing the time it takes to run

    $ git commit-graph write --changed-paths --reachable
when upgrading from v1 to v2 Bloom filters.

To benchmark this, let's generate a commit-graph in linux.git with v1 changed-paths in generation order[^1]:

    $ git clone git@github.com:torvalds/linux.git
    $ cd linux
    $ git commit-graph write --reachable --changed-paths
    $ graph=".git/objects/info/commit-graph"
    $ mv $graph{,.bak}

Then let's time how long it takes to go from v1 to v2 filters (with and without the upgrade path enabled), resetting the state of the commit-graph each time:

    $ git config commitGraph.changedPathsVersion 2
    $ hyperfine -p 'cp -f $graph.bak $graph' -L v 0,1 \
        'GIT_TEST_UPGRADE_BLOOM_FILTERS={v} git.compile commit-graph write --reachable --changed-paths'

On linux.git (where there aren't any non-ASCII paths), the timings indicate that this patch represents a speed-up over recomputing all Bloom filters from scratch:

    Benchmark 1: GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths
      Time (mean ± σ):     124.873 s ±  0.316 s    [User: 124.081 s, System: 0.643 s]
      Range (min … max):   124.621 s … 125.227 s    3 runs
    Benchmark 2: GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths
      Time (mean ± σ):     79.271 s ±  0.163 s    [User: 74.611 s, System: 4.521 s]
      Range (min … max):   79.112 s … 79.437 s    3 runs
    Summary
      'GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths' ran
        1.58 ± 0.01 times faster than 'GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths'

On git.git, we do have some non-ASCII paths, giving us a more modest improvement from 4.163 seconds to 3.348 seconds, for a 1.24x speed-up. On my machine, the stats for git.git are:

  - 8,285 Bloom filters computed from scratch
  - 10 Bloom filters generated as empty
  - 4 Bloom filters generated as truncated due to too many changed paths
  - 65,114 Bloom filters were reused when transitioning from v1 to v2.
[^1]: Note that this is is important, since `--stdin-packs` or
  `--stdin-commits` orders commits in the commit-graph by their pack
  position (with `--stdin-packs`) or in the raw input (with
  `--stdin-commits`).
  Since we compute Bloom filters in the same order that commits appear
  in the graph, we must see a commit's (first) parent before we process
  the commit itself. This is only guaranteed to happen when sorting
  commits by their generation number.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 bloom.c              | 90 ++++++++++++++++++++++++++++++++++++++++++--
 bloom.h              |  1 +
 commit-graph.c       |  5 +++
 object.h             |  1 +
 t/t4216-log-bloom.sh | 35 ++++++++++++++++-
 5 files changed, 127 insertions(+), 5 deletions(-)
diff --git a/bloom.c b/bloom.c
index 739fa093ba..24dd874e46 100644
--- a/bloom.c
+++ b/bloom.c
@@ -7,6 +7,9 @@
 #include "commit-graph.h"
 #include "commit.h"
 #include "commit-slab.h"
+#include "tree.h"
+#include "tree-walk.h"
+#include "config.h"
 
 define_commit_slab(bloom_filter_slab, struct bloom_filter);
 
@@ -250,6 +253,73 @@ static void init_truncated_large_filter(struct bloom_filter *filter,
 	filter->version = version;
 }
 
+#define VISITED   (1u<<21)
+#define HIGH_BITS (1u<<22)
+
+static int has_entries_with_high_bit(struct repository *r, struct tree *t)
+{
+	if (parse_tree(t))
+		return 1;
+
+	if (!(t->object.flags & VISITED)) {
+		struct tree_desc desc;
+		struct name_entry entry;
+
+		init_tree_desc(&desc, t->buffer, t->size);
+		while (tree_entry(&desc, &entry)) {
+			size_t i;
+			for (i = 0; i < entry.pathlen; i++) {
+				if (entry.path[i] & 0x80) {
+					t->object.flags |= HIGH_BITS;
+					goto done;
+				}
+			}
+
+			if (S_ISDIR(entry.mode)) {
+				struct tree *sub = lookup_tree(r, &entry.oid);
+				if (sub && has_entries_with_high_bit(r, sub)) {
+					t->object.flags |= HIGH_BITS;
+					goto done;
+				}
+			}
+
+		}
+
+done:
+		t->object.flags |= VISITED;
+	}
+
+	return !!(t->object.flags & HIGH_BITS);
+}
+
+static int commit_tree_has_high_bit_paths(struct repository *r,
+					  struct commit *c)
+{
+	struct tree *t;
+	if (repo_parse_commit(r, c))
+		return 1;
+	t = repo_get_commit_tree(r, c);
+	if (!t)
+		return 1;
+	return has_entries_with_high_bit(r, t);
+}
+
+static struct bloom_filter *upgrade_filter(struct repository *r, struct commit *c,
+					   struct bloom_filter *filter,
+					   int hash_version)
+{
+	struct commit_list *p = c->parents;
+	if (commit_tree_has_high_bit_paths(r, c))
+		return NULL;
+
+	if (p && commit_tree_has_high_bit_paths(r, p->item))
+		return NULL;
+
+	filter->version = hash_version;
+
+	return filter;
+}
+
 struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)
 {
 	struct bloom_filter *filter;
@@ -292,9 +362,23 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
 						     filter, graph_pos);
 	}
 
-	if ((filter->data && filter->len) &&
-	    (!settings || settings->hash_version == filter->version))
-		return filter;
+	if (filter->data && filter->len) {
+		struct bloom_filter *upgrade;
+		if (!settings || settings->hash_version == filter->version)
+			return filter;
+
+		/* version mismatch, see if we can upgrade */
+		if (compute_if_not_present &&
+		    git_env_bool("GIT_TEST_UPGRADE_BLOOM_FILTERS", 1)) {
+			upgrade = upgrade_filter(r, c, filter,
+						 settings->hash_version);
+			if (upgrade) {
+				if (computed)
+					*computed |= BLOOM_UPGRADED;
+				return upgrade;
+			}
+		}
+	}
 	if (!compute_if_not_present)
 		return NULL;
 
diff --git a/bloom.h b/bloom.h
index bfe389e29c..e3a9b68905 100644
--- a/bloom.h
+++ b/bloom.h
@@ -102,6 +102,7 @@ enum bloom_filter_computed {
 	BLOOM_COMPUTED     = (1 << 1),
 	BLOOM_TRUNC_LARGE  = (1 << 2),
 	BLOOM_TRUNC_EMPTY  = (1 << 3),
+	BLOOM_UPGRADED     = (1 << 4),
 };
 
 struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
diff --git a/commit-graph.c b/commit-graph.c
index e0fc62e110..571f38335a 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1109,6 +1109,7 @@ struct write_commit_graph_context {
 	int count_bloom_filter_not_computed;
 	int count_bloom_filter_trunc_empty;
 	int count_bloom_filter_trunc_large;
+	int count_bloom_filter_upgraded;
 };
 
 static int write_graph_chunk_fanout(struct hashfile *f,
@@ -1716,6 +1717,8 @@ static void trace2_bloom_filter_write_statistics(struct write_commit_graph_conte
 			   ctx->count_bloom_filter_trunc_empty);
 	trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-large",
 			   ctx->count_bloom_filter_trunc_large);
+	trace2_data_intmax("commit-graph", ctx->r, "filter-upgraded",
+			   ctx->count_bloom_filter_upgraded);
 }
 
 static void compute_bloom_filters(struct write_commit_graph_context *ctx)
@@ -1757,6 +1760,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 				ctx->count_bloom_filter_trunc_empty++;
 			if (computed & BLOOM_TRUNC_LARGE)
 				ctx->count_bloom_filter_trunc_large++;
+		} else if (computed & BLOOM_UPGRADED) {
+			ctx->count_bloom_filter_upgraded++;
 		} else if (computed & BLOOM_NOT_COMPUTED)
 			ctx->count_bloom_filter_not_computed++;
 		ctx->total_bloom_filter_data_size += filter
diff --git a/object.h b/object.h
index db25714b4e..2e5e08725f 100644
--- a/object.h
+++ b/object.h
@@ -75,6 +75,7 @@ void object_array_init(struct object_array *array);
  * commit-reach.c:                                  16-----19
  * sha1-name.c:                                              20
  * list-objects-filter.c:                                      21
+ * bloom.c:                                                    2122
  * builtin/fsck.c:           0--3
  * builtin/gc.c:             0
  * builtin/index-pack.c:                                     2021
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index 8f8b5d4966..a321d8d713 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -221,6 +221,10 @@ test_filter_trunc_large () {
 	grep "\"key\":\"filter-trunc-large\",\"value\":\"$1\"" $2
 }
 
+test_filter_upgraded () {
+	grep "\"key\":\"filter-upgraded\",\"value\":\"$1\"" $2
+}
+
 test_expect_success 'correctly report changes over limit' '
 	git init limits &&
 	(
@@ -629,10 +633,19 @@ test_expect_success 'when writing another commit graph, preserve existing versio
 test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '
 	git init doublewrite &&
 	test_commit -C doublewrite c "$CENT" &&
+
 	git -C doublewrite config --add commitgraph.changedPathsVersion 1 &&
-	git -C doublewrite commit-graph write --reachable --changed-paths &&
+	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
+		git -C doublewrite commit-graph write --reachable --changed-paths &&
+	test_filter_computed 1 trace2.txt &&
+	test_filter_upgraded 0 trace2.txt &&
+
 	git -C doublewrite config --add commitgraph.changedPathsVersion 2 &&
-	git -C doublewrite commit-graph write --reachable --changed-paths &&
+	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
+		git -C doublewrite commit-graph write --reachable --changed-paths &&
+	test_filter_computed 1 trace2.txt &&
+	test_filter_upgraded 0 trace2.txt &&
+
 	(
 		cd doublewrite &&
 		echo "c01f" >expect &&
@@ -641,4 +654,22 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano
 	)
 '
 
+test_expect_success 'when writing commit graph, reuse changed-path of another version where possible' '
+	git init upgrade &&
+
+	test_commit -C upgrade base no-high-bits &&
+
+	git -C upgrade config --add commitgraph.changedPathsVersion 1 &&
+	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
+		git -C upgrade commit-graph write --reachable --changed-paths &&
+	test_filter_computed 1 trace2.txt &&
+	test_filter_upgraded 0 trace2.txt &&
+
+	git -C upgrade config --add commitgraph.changedPathsVersion 2 &&
+	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
+		git -C upgrade commit-graph write --reachable --changed-paths &&
+	test_filter_computed 0 trace2.txt &&
+	test_filter_upgraded 1 trace2.txt
+'
+
 test_done

-- 
2.42.0.342.g8bb3a896ee
Previous: Taylor BlauNext: Taylor Blau
Message 73 of 76 in “bloom: changed-path Bloom filters v2”
  1. 00/15 bloom: changed-path Bloom filters v2Taylor Blau, Aug 21, 2023
  2. 01/15 gitformat-commit-graph: describe version 2 of BDATTaylor Blau, Aug 21, 2023
  3. 02/15 t/helper/test-read-graph.c: extract `dump_graph_info()`Taylor Blau, Aug 21, 2023
  4. 03/15 bloom.h: make `load_bloom_filter_from_graph()` publicTaylor Blau, Aug 21, 2023
  5. 04/15 t/helper/test-read-graph: implement `bloom-filters` modeTaylor Blau, Aug 21, 2023
  6. 05/15 t4216: test changed path filters with high bit pathsTaylor Blau, Aug 21, 2023
  7. 06/15 repo-settings: introduce commitgraph.changedPathsVersionTaylor Blau, Aug 21, 2023
  8. 07/15 commit-graph: new filter ver. that fixes murmur3Taylor Blau, Aug 21, 2023
  9. SZEDER GáborAug 26, 2023
  10. Jonathan TanAug 29, 2023
  11. SZEDER GáborAug 30, 2023
  12. Jonathan TanSep 1, 2023
  13. Taylor BlauSep 25, 2023
  14. SZEDER GáborOct 8, 2023
  15. Taylor BlauOct 9, 2023
  16. Taylor BlauOct 9, 2023
  17. Junio C HamanoOct 9, 2023
  18. Taylor BlauOct 10, 2023
  19. 08/15 bloom: annotate filters with hash versionTaylor Blau, Aug 21, 2023
  20. 09/15 bloom: prepare to discard incompatible Bloom filtersTaylor Blau, Aug 21, 2023
  21. 10/15 t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`Taylor Blau, Aug 21, 2023
  22. 11/15 commit-graph.c: unconditionally load Bloom filtersTaylor Blau, Aug 21, 2023
  23. 12/15 commit-graph: drop unnecessary `graph_read_bloom_data_context`Taylor Blau, Aug 21, 2023
  24. 13/15 object.h: fix mis-aligned flag bits tableTaylor Blau, Aug 21, 2023
  25. 14/15 commit-graph: reuse existing Bloom filters where possibleTaylor Blau, Aug 21, 2023
  26. 15/15 bloom: introduce `deinit_bloom_filters()`Taylor Blau, Aug 21, 2023
  27. Jonathan TanAug 24, 2023
  28. Jonathan TanAug 25, 2023
  29. Jonathan TanAug 29, 2023
  30. Junio C HamanoAug 29, 2023
  31. 00/15 bloom: changed-path Bloom filters v2Jonathan Tan, Aug 30, 2023
  32. 13/15 object.h: fix mis-aligned flag bits tableJonathan Tan, Aug 30, 2023
  33. 06/15 repo-settings: introduce commitgraph.changedPathsVersionJonathan Tan, Aug 30, 2023
  34. 04/15 t/helper/test-read-graph: implement `bloom-filters` modeJonathan Tan, Aug 30, 2023
  35. 08/15 bloom: annotate filters with hash versionJonathan Tan, Aug 30, 2023
  36. 01/15 gitformat-commit-graph: describe version 2 of BDATJonathan Tan, Aug 30, 2023
  37. 11/15 commit-graph.c: unconditionally load Bloom filtersJonathan Tan, Aug 30, 2023
  38. 10/15 t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`Jonathan Tan, Aug 30, 2023
  39. 09/15 bloom: prepare to discard incompatible Bloom filtersJonathan Tan, Aug 30, 2023
  40. 12/15 commit-graph: drop unnecessary `graph_read_bloom_data_context`Jonathan Tan, Aug 30, 2023
  41. 07/15 commit-graph: new filter ver. that fixes murmur3Jonathan Tan, Aug 30, 2023
  42. 02/15 t/helper/test-read-graph.c: extract `dump_graph_info()`Jonathan Tan, Aug 30, 2023
  43. 05/15 t4216: test changed path filters with high bit pathsJonathan Tan, Aug 30, 2023
  44. 14/15 commit-graph: reuse existing Bloom filters where possibleJonathan Tan, Aug 30, 2023
  45. 03/15 bloom.h: make `load_bloom_filter_from_graph()` publicJonathan Tan, Aug 30, 2023
  46. 15/15 bloom: introduce `deinit_bloom_filters()`Jonathan Tan, Aug 30, 2023
  47. Junio C HamanoAug 30, 2023
  48. 00/17 bloom: changed-path Bloom filters v2 (& sundries)Taylor Blau, Oct 10, 2023
  49. 01/17 t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`Taylor Blau, Oct 10, 2023
  50. 02/17 revision.c: consult Bloom filters for root commitsTaylor Blau, Oct 10, 2023
  51. 04/17 gitformat-commit-graph: describe version 2 of BDATTaylor Blau, Oct 10, 2023
  52. 05/17 t/helper/test-read-graph.c: extract `dump_graph_info()`Taylor Blau, Oct 10, 2023
  53. Patrick SteinhardtOct 17, 2023
  54. Taylor BlauOct 18, 2023
  55. Junio C HamanoOct 18, 2023
  56. 03/17 commit-graph: ensure Bloom filters are read with consistent settingsTaylor Blau, Oct 10, 2023
  57. Patrick SteinhardtOct 17, 2023
  58. 06/17 bloom.h: make `load_bloom_filter_from_graph()` publicTaylor Blau, Oct 10, 2023
  59. 07/17 t/helper/test-read-graph: implement `bloom-filters` modeTaylor Blau, Oct 10, 2023
  60. 09/17 repo-settings: introduce commitgraph.changedPathsVersionTaylor Blau, Oct 10, 2023
  61. 15/17 object.h: fix mis-aligned flag bits tableTaylor Blau, Oct 10, 2023
  62. 12/17 bloom: prepare to discard incompatible Bloom filtersTaylor Blau, Oct 10, 2023
  63. 13/17 commit-graph.c: unconditionally load Bloom filtersTaylor Blau, Oct 10, 2023
  64. Patrick SteinhardtOct 17, 2023
  65. 11/17 bloom: annotate filters with hash versionTaylor Blau, Oct 10, 2023
  66. 14/17 commit-graph: drop unnecessary `graph_read_bloom_data_context`Taylor Blau, Oct 10, 2023
  67. 10/17 commit-graph: new filter ver. that fixes murmur3Taylor Blau, Oct 10, 2023
  68. Patrick SteinhardtOct 17, 2023
  69. Taylor BlauOct 18, 2023
  70. 08/17 t4216: test changed path filters with high bit pathsTaylor Blau, Oct 10, 2023
  71. Patrick SteinhardtOct 17, 2023
  72. Taylor BlauOct 18, 2023
  73. 16/17 commit-graph: reuse existing Bloom filters where possibleTaylor Blau, Oct 10, 2023
  74. 17/17 bloom: introduce `deinit_bloom_filters()`Taylor Blau, Oct 10, 2023
  75. Patrick SteinhardtOct 17, 2023
  76. Taylor BlauOct 18, 2023

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.