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

Re: [PATCH v3 12/14] commit-graph: add large-filters bitmap chunk

From
SZEDER Gábor <szeder.dev@gmail.com>
Date
Sep 1, 2020, 14:35 UTC
Message-ID
<20200901143546.GA5678@szeder.dev>
In-Reply-To
<619e0c619dd12e2bea2b80c7d249ba66fe2a315c.1597178915.git.me@ttaylorr.com>
On Tue, Aug 11, 2020 at 04:52:07PM -0400, Taylor Blau wrote:
Show 20 quoted lines
> When a commit has more than a certain number of changed paths (commonly
> 512), the commit-graph machinery represents it as a zero-length filter.
> This is done since having many entries in the Bloom filter has
> undesirable effects on the false positivity rate.
> 
> In addition to these too-large filters, the commit-graph machinery also
> represents commits with no filter and commits with no changed paths in
> the same way.
> 
> When writing a commit-graph that aggregates several incremental
> commit-graph layers (eg., with '--split=replace'), the commit-graph
> machinery first computes all of the Bloom filters that it wants to write
> but does not already know about from existing graph layers. Because we
> overload the zero-length filter in the above fashion, this leads to
> recomputing large filters over and over again.
> 
> This is already undesirable, since it means that we are wasting
> considerable effort to discover that a commit with too many changed
> paths, only to throw that effort away (and then repeat the process the
> next time a roll-up is performed).
Is this really the case?

If a commit has a corresponding entry in the Bloom filters chunks, then the commit-graph machinery does know the Bloom filter associated with that commit. The size of that filter should not matter, i.e. even if it is a zero-length filter, the commit-graph machinery should know about it all the same. And as far as I can tell it does indeed, because load_bloom_filter_from_graph() sets a non-NULL 'filter->data' pointer even if 'filter->len' is zero, which get_bloom_filter() treats as "we know about this", and returns early without (re)computing the filter. Even the test 'Bloom generation does not recompute too-large filters' added in this patch is expected to succeed, and my superficial and makeshift testing seems to corroborate this; at least I couldn't find a combination of commands and options that would recompute any existing zero-length Bloom filters.

Am I missing something?
Show 13 quoted lines
> In a subsequent patch, we will add a '--max-new-filters=<n>' option,
> which specifies an upper-bound on the number of new filters we are
> willing to compute from scratch. Suppose that there are 'N' too-large
> filters, and we specify '--max-new-filters=M'. If 'N >= M', it is
> unlikely that any filters will be generated, since we'll spend most of
> our effort on filters that we ultimately throw away. If 'N < M', filters
> will trickle in over time, but only at most 'M - N' per-write.
> 
> To address this, add a new chunk which encodes a bitmap where the ith
> bit is on iff the ith commit has zero or at least 512 changed paths.
> Likewise store the maximum number of changed paths we are willing to
> store in order to prepare for eventually making this value more easily
> customizable.

I don't understand how storing this value would make it any easier to customize.

Show 28 quoted lines
> When computing Bloom filters, first consult the relevant
> bitmap (in the case that we are rolling up existing layers) to see if
> computing the Bloom filter from scratch would be a waste of time.
> 
> This patch implements a new chunk instead of extending the existing BIDX
> and BDAT chunks because modifying these chunks would confuse old
> clients. (Eg., setting the most-significant bit in the BIDX chunk would
> confuse old clients and require a version bump).
> 
> To allow using the existing bitmap code with 64-bit words, we write the
> data in network byte order from the 64-bit words. This means we also
> need to read the array from the commit-graph file by translating each
> word from network byte order using get_be64() when loading the commit
> graph. (Note that this *could* be delayed until first-use, but a later
> patch will rely on this being initialized early, so we assume the
> up-front cost when parsing instead of delaying initialization).
> 
> By avoiding the need to move to new versions of the BDAT and BIDX chunk,
> we can give ourselves more time to consider whether or not other
> modifications to these chunks are worthwhile without holding up this
> change.
> 
> Another approach would be to introduce a new BIDX chunk (say, one
> identified by 'BID2') which is identical to the existing BIDX chunk,
> except the most-significant bit of each offset is interpreted as "this
> filter is too big" iff looking at a BID2 chunk. This avoids having to
> write a bitmap, but forces older clients to rewrite their commit-graphs
> (as well as reduces the theoretical largest Bloom filters we couldl

And it reduces the max possible size of the BDAT chunk, and thus the max number of commits with Bloom filters as well.

s/couldl/could/
> write, and forces us to maintain the code necessary to translate BIDX
> chunks to BID2 ones). Separately from this patch, I implemented this
> alternate approach and did not find it to be advantageous.

Let's take a step back to reconsider what should be stored in this bitmap for a moment. Sure, setting a bit for each commit that doesn't modify any paths or modifies too many makes it possible to repliably identify commits that don't have Bloom filters yet. But isn't it a bit roundabout way? I think it would be better to directly track which commits don't have Bloom filters yet. IOW what you really want is a, say, BNCY "Bloom filter Not Computed Yet" chunk, where we set the corresponding bit for each commit which has an entry in the BIDX chunk but for which a Bloom filter hasn't been computed yet.

  - It's simpler and easier to explain (IMO).
  - This bitmap chunk can easily be made optional: if all Bloom
    filters have been computed, then the bitmap will contain all
    zeros.  So why bother writing it, when we can save a bit of space
    instead?
  - It avoids the unpleasentness of setting a bit in the _Large_ Bloom
    Filters chunks for commits _not_ modifying any paths.
  - Less incentive to spill implementation details to the format
    specification (e.g. 512 modified paths).

Now, let's take another step back: is such a bitmap really necessary? We could write a single-byte Bloom filter with no bits set for commits not modifying any paths, and a single-byte Bloom filter with all bits set for commits modifying too many paths. This is compatible with the specs and any existing implementation should do the right thing when reading such filters, this would allow us to interpret zero-length filters as "not computed yet", and if that bitmap chunk won't be optional, then this would save space as long as less than 1/8 of commits modify no or too many paths. Unfortunately, however, all existing zero-length Bloom filters have to be recomputed.

Show 20 quoted lines
> Signed-off-by: Taylor Blau <me@ttaylorr.com>
> ---
>  .../technical/commit-graph-format.txt         | 12 +++
>  bloom.h                                       |  2 +-
>  commit-graph.c                                | 96 ++++++++++++++++---
>  commit-graph.h                                |  4 +
>  t/t4216-log-bloom.sh                          | 25 ++++-
>  5 files changed, 124 insertions(+), 15 deletions(-)
> 
> diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
> index 440541045d..5f2d9ab4d7 100644
> --- a/Documentation/technical/commit-graph-format.txt
> +++ b/Documentation/technical/commit-graph-format.txt
> @@ -123,6 +123,18 @@ CHUNK DATA:
>        of length zero.
>      * The BDAT chunk is present if and only if BIDX is present.
>  
> +  Large Bloom Filters (ID: {'B', 'F', 'X', 'L'}) [Optional]
> +    * It starts with a 32-bit unsigned integer specifying the maximum number of
> +      changed-paths that can be stored in a single Bloom filter.

Should this value be the same in all elements of a commit-graph chain? Note that in this case having different values won't affect revision walks using modified path Bloom filters.

Show 5 quoted lines
> +    * It then contains a list of 64-bit words (the length of this list is
> +      determined by the width of the chunk) which is a bitmap. The 'i'th bit is
> +      set exactly when the 'i'th commit in the graph has a changed-path Bloom
> +      filter with zero entries (either because the commit is empty, or because
> +      it contains more than 512 changed paths).

Please make clear the byte order of these 64 bit words in the specs as well.

Furthermore, that 512 path limit is an implementation detail, so it would be better if it didn't leak into the specification of this new chunk.

Show 7 quoted lines
> +    * The BFXL chunk is present only when the BIDX and BDAT chunks are
> +      also present.
> +
> +
>    Base Graphs List (ID: {'B', 'A', 'S', 'E'}) [Optional]
>        This list of H-byte hashes describe a set of B commit-graph files that
>        form a commit-graph chain. The graph position for the ith commit in this
Show 45 quoted lines
> diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
> index 21b67677ef..6859d85369 100755
> --- a/t/t4216-log-bloom.sh
> +++ b/t/t4216-log-bloom.sh
> @@ -33,7 +33,7 @@ test_expect_success 'setup test - repo, commits, commit graph, log outputs' '
>  	git commit-graph write --reachable --changed-paths
>  '
>  graph_read_expect () {
> -	NUM_CHUNKS=5
> +	NUM_CHUNKS=6
>  	cat >expect <<- EOF
>  	header: 43475048 1 1 $NUM_CHUNKS 0
>  	num_commits: $1
> @@ -262,5 +262,28 @@ test_expect_success 'correctly report changes over limit' '
>  		done
>  	)
>  '
> +test_bloom_filters_computed () {
> +	commit_graph_args=$1
> +	bloom_trace_prefix="{\"filter_known_large\":$2,\"filter_found_large\":$3,\"filter_computed\":$4"
> +	rm -f "$TRASH_DIRECTORY/trace.event" &&
> +	GIT_TRACE2_EVENT="$TRASH_DIRECTORY/trace.event" git commit-graph write $commit_graph_args &&
> +	grep "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.event"
> +}
> +
> +test_expect_success 'Bloom generation does not recompute too-large filters' '
> +	(
> +		cd limits &&
> +
> +		# start from scratch and rebuild
> +		rm -f .git/objects/info/commit-graph &&
> +		GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS=10 \
> +			git commit-graph write --reachable --changed-paths \
> +			--split=replace &&
> +		test_commit c1 filter &&
> +
> +		test_bloom_filters_computed "--reachable --changed-paths --split=replace" \
> +			2 0 1
> +	)
> +'
>  
>  test_done
> -- 
> 2.28.0.rc1.13.ge78abce653
>
Previous: Taylor BlauNext: Taylor Blau
Message 68 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.