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

[PATCH v3 07/14] bloom: split 'get_bloom_filter()' in two

From
Taylor Blau <me@ttaylorr.com>
Date
Aug 11, 2020, 20:51 UTC
Message-ID
<eba279487318137064eef776c779ca537a4a711d.1597178915.git.me@ttaylorr.com>
In-Reply-To
<cover.1597178914.git.me@ttaylorr.com>

'get_bloom_filter' takes a flag to control whether it will compute a Bloom filter if the requested one is missing. In the next patch, we'll add yet another parameter to this method, which would force all but one caller to specify an extra 'NULL' parameter at the end.

Instead of doing this, split 'get_bloom_filter' into two functions: 'get_bloom_filter' and 'get_or_compute_bloom_filter'. The former only looks up a Bloom filter (and does not compute one if it's missing, thus dropping the 'compute_if_not_present' flag). The latter does compute missing Bloom filters, with an additional parameter to store whether or not it needed to do so.

This simplifies many call-sites, since the majority of existing callers to 'get_bloom_filter' do not want missing Bloom filters to be computed (so they can drop the parameter entirely and use the simpler version of the function).

While we're at it, instrument the new 'get_or_compute_bloom_filter()' with two counters in the 'write_commit_graph_context' struct which store the number of filters that we computed, and the number of those which were too large to store.

It would be nice to drop the 'compute_if_not_present' flag entirely, since all remaining callers of 'get_or_compute_bloom_filter' pass it as '1', but this will change in a future patch and hence cannot be removed.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 blame.c               |  2 +-
 bloom.c               | 13 ++++++++++---
 bloom.h               | 10 +++++++---
 commit-graph.c        | 38 +++++++++++++++++++++++++++++++++++---
 line-log.c            |  2 +-
 revision.c            |  2 +-
 t/helper/test-bloom.c |  3 ++-
 7 files changed, 57 insertions(+), 13 deletions(-)
diff --git a/blame.c b/blame.c
index 3e5f8787bc..756285fca7 100644
--- a/blame.c
+++ b/blame.c
@@ -1275,7 +1275,7 @@ static int maybe_changed_path(struct repository *r,
 	if (commit_graph_generation(origin->commit) == GENERATION_NUMBER_INFINITY)
 		return 1;
 
-	filter = get_bloom_filter(r, origin->commit, 0);
+	filter = get_bloom_filter(r, origin->commit);
 
 	if (!filter)
 		return 1;
diff --git a/bloom.c b/bloom.c
index cd9380ac62..a8a21762f4 100644
--- a/bloom.c
+++ b/bloom.c
@@ -177,9 +177,10 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data,
 	return strcmp(e1->path, e2->path);
 }
 
-struct bloom_filter *get_bloom_filter(struct repository *r,
-				      struct commit *c,
-				      int compute_if_not_present)
+struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
+						 struct commit *c,
+						 int compute_if_not_present,
+						 int *computed)
 {
 	struct bloom_filter *filter;
 	struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
@@ -187,6 +188,9 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 	struct diff_options diffopt;
 	int max_changes = 512;
 
+	if (computed)
+		*computed = 0;
+
 	if (!bloom_filters.slab_size)
 		return NULL;
 
@@ -273,6 +277,9 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 		filter->len = 0;
 	}
 
+	if (computed)
+		*computed = 1;
+
 	free(diff_queued_diff.queue);
 	DIFF_QUEUE_CLEAR(&diff_queued_diff);
 
diff --git a/bloom.h b/bloom.h
index 0b9b59a6fe..baa91926db 100644
--- a/bloom.h
+++ b/bloom.h
@@ -89,9 +89,13 @@ void add_key_to_filter(const struct bloom_key *key,
 
 void init_bloom_filters(void);
 
-struct bloom_filter *get_bloom_filter(struct repository *r,
-				      struct commit *c,
-				      int compute_if_not_present);
+struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
+						 struct commit *c,
+						 int compute_if_not_present,
+						 int *computed);
+
+#define get_bloom_filter(r, c) get_or_compute_bloom_filter( \
+	(r), (c), 0, NULL)
 
 int bloom_filter_contains(const struct bloom_filter *filter,
 			  const struct bloom_key *key,
diff --git a/commit-graph.c b/commit-graph.c
index 86dd4b979e..ba2a2cfb22 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -964,6 +964,9 @@ struct write_commit_graph_context {
 	const struct split_commit_graph_opts *split_opts;
 	size_t total_bloom_filter_data_size;
 	const struct bloom_filter_settings *bloom_settings;
+
+	int count_bloom_filter_found_large;
+	int count_bloom_filter_computed;
 };
 
 static int write_graph_chunk_fanout(struct hashfile *f,
@@ -1175,7 +1178,7 @@ static int 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, 0);
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
 		size_t len = filter ? filter->len : 0;
 		cur_pos += len;
 		display_progress(ctx->progress, ++ctx->progress_cnt);
@@ -1215,7 +1218,7 @@ static int write_graph_chunk_bloom_data(struct hashfile *f,
 	hashwrite_be32(f, ctx->bloom_settings->bits_per_entry);
 
 	while (list < last) {
-		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
+		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
 		size_t len = filter ? filter->len : 0;
 
 		display_progress(ctx->progress, ++ctx->progress_cnt);
@@ -1385,6 +1388,22 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 	stop_progress(&ctx->progress);
 }
 
+static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context *ctx)
+{
+	struct json_writer jw = JSON_WRITER_INIT;
+
+	jw_object_begin(&jw, 0);
+	jw_object_intmax(&jw, "filter_found_large",
+			 ctx->count_bloom_filter_found_large);
+	jw_object_intmax(&jw, "filter_computed",
+			 ctx->count_bloom_filter_computed);
+	jw_end(&jw);
+
+	trace2_data_json("commit-graph", the_repository, "bloom_statistics", &jw);
+
+	jw_release(&jw);
+}
+
 static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 {
 	int i;
@@ -1407,12 +1426,25 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 		QSORT(sorted_commits, ctx->commits.nr, commit_gen_cmp);
 
 	for (i = 0; i < ctx->commits.nr; i++) {
+		int computed = 0;
 		struct commit *c = sorted_commits[i];
-		struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1);
+		struct bloom_filter *filter = get_or_compute_bloom_filter(
+			ctx->r,
+			c,
+			1,
+			&computed);
+		if (computed) {
+			ctx->count_bloom_filter_computed++;
+			if (filter && !filter->len)
+				ctx->count_bloom_filter_found_large++;
+		}
 		ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
 		display_progress(progress, i + 1);
 	}
 
+	if (trace2_is_enabled())
+		trace2_bloom_filter_write_statistics(ctx);
+
 	free(sorted_commits);
 	stop_progress(&progress);
 }
diff --git a/line-log.c b/line-log.c
index bf73ea95ac..68eeb425f8 100644
--- a/line-log.c
+++ b/line-log.c
@@ -1159,7 +1159,7 @@ static int bloom_filter_check(struct rev_info *rev,
 		return 1;
 
 	if (!rev->bloom_filter_settings ||
-	    !(filter = get_bloom_filter(rev->repo, commit, 0)))
+	    !(filter = get_bloom_filter(rev->repo, commit)))
 		return 1;
 
 	if (!range)
diff --git a/revision.c b/revision.c
index be600186ee..7f58ecc411 100644
--- a/revision.c
+++ b/revision.c
@@ -751,7 +751,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 	if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
 		return -1;
 
-	filter = get_bloom_filter(revs->repo, commit, 0);
+	filter = get_bloom_filter(revs->repo, commit);
 
 	if (!filter) {
 		count_bloom_filter_not_present++;
diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c
index f0aa80b98e..531af439c2 100644
--- a/t/helper/test-bloom.c
+++ b/t/helper/test-bloom.c
@@ -39,7 +39,8 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid)
 	struct bloom_filter *filter;
 	setup_git_directory();
 	c = lookup_commit(the_repository, commit_oid);
-	filter = get_bloom_filter(the_repository, c, 1);
+	filter = get_or_compute_bloom_filter(the_repository, c, 1,
+					     NULL);
 	print_bloom_filter(filter);
 }
 

-- 
2.28.0.rc1.13.ge78abce653
Previous: Taylor BlauNext: Taylor Blau
Message 57 of 117 in “more miscellaneous Bloom filter improvements”
  1. 00/10 more miscellaneous Bloom filter improvementsTaylor Blau, Aug 3, 2020
  2. 01/10 commit-graph: introduce 'get_bloom_filter_settings()'Taylor Blau, Aug 3, 2020
  3. Jeff KingAug 4, 2020
  4. Taylor BlauAug 4, 2020
  5. 02/10 commit-graph: pass a 'struct repository *' in more placesTaylor Blau, Aug 3, 2020
  6. 03/10 t4216: use an '&&'-chainTaylor Blau, Aug 3, 2020
  7. 04/10 t/helper/test-read-graph.c: prepare repo settingsTaylor Blau, Aug 3, 2020
  8. 05/10 commit-graph: respect 'commitgraph.readChangedPaths'Taylor Blau, Aug 3, 2020
  9. 06/10 commit-graph.c: sort index into commits listTaylor Blau, Aug 3, 2020
  10. Derrick StoleeAug 4, 2020
  11. Taylor BlauAug 4, 2020
  12. 07/10 commit-graph: add large-filters bitmap chunkTaylor Blau, Aug 3, 2020
  13. Taylor BlauAug 3, 2020
  14. Derrick StoleeAug 4, 2020
  15. 08/10 bloom: split 'get_bloom_filter()' in twoTaylor Blau, Aug 3, 2020
  16. Derrick StoleeAug 4, 2020
  17. Taylor BlauAug 4, 2020
  18. 09/10 commit-graph: rename 'split_commit_graph_opts'Taylor Blau, Aug 3, 2020
  19. 10/10 builtin/commit-graph.c: introduce '--max-new-filters=<n>'Taylor Blau, Aug 3, 2020
  20. Derrick StoleeAug 4, 2020
  21. Taylor BlauAug 4, 2020
  22. 00/14 more miscellaneous Bloom filter improvementsTaylor Blau, Aug 5, 2020
  23. 01/14 commit-graph: introduce 'get_bloom_filter_settings()'Taylor Blau, Aug 5, 2020
  24. 02/14 t4216: use an '&&'-chainTaylor Blau, Aug 5, 2020
  25. 09/14 bloom/diff: properly short-circuit on max_changesTaylor Blau, Aug 5, 2020
  26. 10/14 commit-graph.c: sort index into commits listTaylor Blau, Aug 5, 2020
  27. 08/14 bloom: use provided 'struct bloom_filter_settings'Taylor Blau, Aug 5, 2020
  28. 07/14 bloom: split 'get_bloom_filter()' in twoTaylor Blau, Aug 5, 2020
  29. 12/14 commit-graph: add large-filters bitmap chunkTaylor Blau, Aug 5, 2020
  30. Junio C HamanoAug 5, 2020
  31. Taylor BlauAug 5, 2020
  32. Junio C HamanoAug 5, 2020
  33. Taylor BlauAug 5, 2020
  34. Taylor BlauAug 11, 2020
  35. Junio C HamanoAug 11, 2020
  36. 11/14 csum-file.h: introduce 'hashwrite_be64()'Taylor Blau, Aug 5, 2020
  37. 13/14 commit-graph: rename 'split_commit_graph_opts'Taylor Blau, Aug 5, 2020
  38. 03/14 commit-graph: pass a 'struct repository *' in more placesTaylor Blau, Aug 5, 2020
  39. 06/14 commit-graph.c: store maximum changed pathsTaylor Blau, Aug 5, 2020
  40. 04/14 t/helper/test-read-graph.c: prepare repo settingsTaylor Blau, Aug 5, 2020
  41. 05/14 commit-graph: respect 'commitGraph.readChangedPaths'Taylor Blau, Aug 5, 2020
  42. 14/14 builtin/commit-graph.c: introduce '--max-new-filters=<n>'Taylor Blau, Aug 5, 2020
  43. 00/14 more miscellaneous Bloom filter improvementsTaylor Blau, Aug 11, 2020
  44. 01/14 commit-graph: introduce 'get_bloom_filter_settings()'Taylor Blau, Aug 11, 2020
  45. SZEDER GáborAug 11, 2020
  46. Taylor BlauAug 11, 2020
  47. SZEDER GáborAug 11, 2020
  48. Taylor BlauAug 11, 2020
  49. SZEDER GáborAug 11, 2020
  50. Derrick StoleeAug 12, 2020
  51. Taylor BlauAug 14, 2020
  52. 02/14 t4216: use an '&&'-chainTaylor Blau, Aug 11, 2020
  53. 03/14 commit-graph: pass a 'struct repository *' in more placesTaylor Blau, Aug 11, 2020
  54. 04/14 t/helper/test-read-graph.c: prepare repo settingsTaylor Blau, Aug 11, 2020
  55. 05/14 commit-graph: respect 'commitGraph.readChangedPaths'Taylor Blau, Aug 11, 2020
  56. 06/14 commit-graph.c: store maximum changed pathsTaylor Blau, Aug 11, 2020
  57. 07/14 bloom: split 'get_bloom_filter()' in twoTaylor Blau, Aug 11, 2020
  58. 11/14 csum-file.h: introduce 'hashwrite_be64()'Taylor Blau, Aug 11, 2020
  59. 08/14 bloom: use provided 'struct bloom_filter_settings'Taylor Blau, Aug 11, 2020
  60. 09/14 bloom/diff: properly short-circuit on max_changesTaylor Blau, Aug 11, 2020
  61. 10/14 commit-graph.c: sort index into commits listTaylor Blau, Aug 11, 2020
  62. 12/14 commit-graph: add large-filters bitmap chunkTaylor Blau, Aug 11, 2020
  63. Derrick StoleeAug 11, 2020
  64. Taylor BlauAug 11, 2020
  65. Taylor BlauAug 11, 2020
  66. SZEDER GáborAug 19, 2020
  67. Taylor BlauSep 2, 2020
  68. SZEDER GáborSep 1, 2020
  69. Taylor BlauSep 2, 2020
  70. 13/14 commit-graph: rename 'split_commit_graph_opts'Taylor Blau, Aug 11, 2020
  71. SZEDER GáborAug 19, 2020
  72. Taylor BlauSep 2, 2020
  73. 14/14 builtin/commit-graph.c: introduce '--max-new-filters=<n>'Taylor Blau, Aug 11, 2020
  74. SZEDER GáborAug 12, 2020
  75. Taylor BlauAug 14, 2020
  76. SZEDER GáborAug 17, 2020
  77. Taylor BlauSep 2, 2020
  78. Derrick StoleeAug 12, 2020
  79. Taylor BlauAug 14, 2020
  80. SZEDER GáborAug 18, 2020
  81. Taylor BlauSep 3, 2020
  82. SZEDER GáborAug 19, 2020
  83. Taylor BlauSep 3, 2020
  84. SZEDER GáborSep 4, 2020
  85. SZEDER GáborSep 1, 2020
  86. Taylor BlauSep 3, 2020
  87. Junio C HamanoSep 3, 2020
  88. Taylor BlauSep 3, 2020
  89. 00/14 more miscellaneous Bloom filter improvementsTaylor Blau, Sep 3, 2020
  90. 01/14 commit-graph: introduce 'get_bloom_filter_settings()'Taylor Blau, Sep 3, 2020
  91. 02/14 t4216: use an '&&'-chainTaylor Blau, Sep 3, 2020
  92. 04/14 t/helper/test-read-graph.c: prepare repo settingsTaylor Blau, Sep 3, 2020
  93. 03/14 commit-graph: pass a 'struct repository *' in more placesTaylor Blau, Sep 3, 2020
  94. 05/14 commit-graph: respect 'commitGraph.readChangedPaths'Taylor Blau, Sep 3, 2020
  95. 06/14 commit-graph.c: store maximum changed pathsTaylor Blau, Sep 3, 2020
  96. 07/14 bloom: split 'get_bloom_filter()' in twoTaylor Blau, Sep 3, 2020
  97. Jakub NarębskiSep 5, 2020
  98. Taylor BlauSep 5, 2020
  99. Jakub NarębskiSep 5, 2020
  100. Taylor BlauSep 5, 2020
  101. Jakub NarębskiSep 5, 2020
  102. Taylor BlauSep 5, 2020
  103. Taylor BlauSep 5, 2020
  104. SZEDER GáborSep 5, 2020
  105. Taylor BlauSep 5, 2020
  106. Junio C HamanoSep 6, 2020
  107. 08/14 bloom: use provided 'struct bloom_filter_settings'Taylor Blau, Sep 3, 2020
  108. 09/14 bloom/diff: properly short-circuit on max_changesTaylor Blau, Sep 3, 2020
  109. 10/14 commit-graph.c: sort index into commits listTaylor Blau, Sep 3, 2020
  110. 11/14 csum-file.h: introduce 'hashwrite_be64()'Taylor Blau, Sep 3, 2020
  111. René ScharfeSep 4, 2020
  112. Taylor BlauSep 4, 2020
  113. 12/14 commit-graph: add large-filters bitmap chunkTaylor Blau, Sep 3, 2020
  114. 13/14 commit-graph: rename 'split_commit_graph_opts'Taylor Blau, Sep 3, 2020
  115. Taylor BlauSep 4, 2020
  116. 14/14 builtin/commit-graph.c: introduce '--max-new-filters=<n>'Taylor Blau, Sep 3, 2020
  117. Derrick StoleeSep 4, 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.