| Message ID | 4653b5b4bcd254a3791797214b46722b4062dc18.1600279373.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | more miscellaneous Bloom filter improvements, redux | expand |
On Wed, Sep 16, 2020 at 02:07:59PM -0400, Taylor Blau wrote: > When a changed-path Bloom filter has either zero, or more than a > certain number (commonly 512) of entries, the commit-graph machinery > encodes it as "missing". More specifically, it sets the indices adjacent > in the BIDX chunk as equal to each other to indicate a "length 0" > filter; that is, that the filter occupies zero bytes on disk. > > This has heretofore been fine, since the commit-graph machinery has no > need to care about these filters with too few or too many changed paths. > Both cases act like no filter has been generated at all, and so there is > no need to store them. > > In a subsequent commit, however, the commit-graph machinery will learn > to only compute Bloom filters for some commits in the current > commit-graph layer. This is a change from the current implementation > which computes Bloom filters for all commits that are in the layer being > written. Critically for this patch, only computing some of the Bloom > filters means adding a third state for length 0 Bloom filters: zero > entries, too many entries, or "hasn't been computed". > > It will be important for that future patch to distinguish between "not > representable" (i.e., zero or too-many changed paths), and "hasn't been > computed". In particular, we don't want to waste time recomputing > filters that have already been computed. > > To that end, change how we store Bloom filters in the "computed but not > representable" category: > > - Bloom filters with no entries are stored as a single byte with all > bits low (i.e., all queries to that Bloom filter will return > "definitely not") > > - Bloom filters with too many entries are stored as a single byte with > all bits set high (i.e., all queries to that Bloom filter will > return "maybe"). > > These rules are sufficient to not incur a behavior change by changing > the on-disk representation of these two classes. Likewise, no > specification changes are necessary for the commit-graph format, either: > > - Filters that were previously empty will be recomputed and stored > according to the new rules, and > > - old clients reading filters generated by new clients will interpret > the filters correctly and be none the wiser to how they were > generated. > > Clients will invoke the Bloom machinery in more cases than before, but > this can be addressed by returning a NULL filter when all bits are set > high. This can be addressed in a future patch. OTOH, clients will invoke the tree-diff machinery in fewer cases than before, because querying the Bloom filter of commits not modifying any files will now return "definitely not". > Finally, note that this does increase the size of on-disk commit-graphs, > but far less than other proposals. In particular, this is generally more > efficient than storing a bitmap for which commits haven't computed their > Bloom filters. Storing a bitmap incurs a penalty of one bit per commit, > whereas storing explicit filters as above incurs a penalty of one byte > per too-large or too-small commit. s/too-small/empty/ > In practice, these boundary commits likely occupy a small proportion of > the overall number of commits, and so the size penalty is likely smaller > than storing a bitmap for all commits. | Percentage of | commits modifying | 0 path | >= 512 paths ---------------+------------+---------------- android-base | 13.20% | 0.13% cmssw | 0.15% | 0.23% cpython | 3.07% | 0.01% elasticsearch | 0.70% | 1.00% gcc | 0.00% | 0.08% gecko-dev | 0.14% | 0.64% git | 0.11% | 0.02% glibc | 0.02% | 0.10% go | 0.00% | 0.07% homebrew-cask | 0.40% | 0.02% homebrew-core | 0.01% | 0.01% jdk | 0.26% | 5.64% linux | 0.01% | 0.51% llvm-project | 0.12% | 0.03% rails | 0.10% | 0.10% rust | 0.07% | 0.17% tensorflow | 0.09% | 1.02% webkit | 0.05% | 0.31% > A test to exercise filters which contain too many changed path entries > will be introduced in a subsequent patch. > diff --git a/bloom.h b/bloom.h > index c6d77e8393..70a8840896 100644 > --- a/bloom.h > +++ b/bloom.h > @@ -93,6 +93,7 @@ enum bloom_filter_computed { > BLOOM_NOT_COMPUTED = (1 << 0), > BLOOM_COMPUTED = (1 << 1), > BLOOM_TRUNC_LARGE = (1 << 2), > + BLOOM_TRUNC_SMALL = (1 << 3), s/SMALL/EMPTY/ This "small" suffix in the constant, variable, and trace2 key names is misleading, because we only mean empty commits. > }; > > struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, > diff --git a/commit-graph.c b/commit-graph.c > index 1ca754f19c..bd4247bca5 100644 > --- a/commit-graph.c > +++ b/commit-graph.c > @@ -974,6 +974,7 @@ struct write_commit_graph_context { > > int count_bloom_filter_computed; > int count_bloom_filter_not_computed; > + int count_bloom_filter_trunc_small; > int count_bloom_filter_trunc_large; > }; >
On Fri, Sep 18, 2020 at 12:13:02AM +0200, SZEDER Gábor wrote: > > Clients will invoke the Bloom machinery in more cases than before, but > > this can be addressed by returning a NULL filter when all bits are set > > high. This can be addressed in a future patch. > > OTOH, clients will invoke the tree-diff machinery in fewer cases than > before, because querying the Bloom filter of commits not modifying any > files will now return "definitely not". Absolutely right. > > Finally, note that this does increase the size of on-disk commit-graphs, > > but far less than other proposals. In particular, this is generally more > > efficient than storing a bitmap for which commits haven't computed their > > Bloom filters. Storing a bitmap incurs a penalty of one bit per commit, > > whereas storing explicit filters as above incurs a penalty of one byte > > per too-large or too-small commit. > > s/too-small/empty/ Fair enough, although I'm not planning to alter this or any other patch now that it's picked up unless there's a real show-stopper (this doesn't seem like one). > > In practice, these boundary commits likely occupy a small proportion of > > the overall number of commits, and so the size penalty is likely smaller > > than storing a bitmap for all commits. > > | Percentage of > | commits modifying > | 0 path | >= 512 paths > ---------------+------------+---------------- > android-base | 13.20% | 0.13% > cmssw | 0.15% | 0.23% > cpython | 3.07% | 0.01% > elasticsearch | 0.70% | 1.00% > gcc | 0.00% | 0.08% > gecko-dev | 0.14% | 0.64% > git | 0.11% | 0.02% > glibc | 0.02% | 0.10% > go | 0.00% | 0.07% > homebrew-cask | 0.40% | 0.02% > homebrew-core | 0.01% | 0.01% > jdk | 0.26% | 5.64% > linux | 0.01% | 0.51% > llvm-project | 0.12% | 0.03% > rails | 0.10% | 0.10% > rust | 0.07% | 0.17% > tensorflow | 0.09% | 1.02% > webkit | 0.05% | 0.31% This is very useful information to have! Without the total number of commits, it's impossible to know whether or not this is a win over the BFXL chunk. But, since the number of commits is probably "large" versus the percentage of boundary commits which is "small", it's almost certainly an advantage. > > A test to exercise filters which contain too many changed path entries > > will be introduced in a subsequent patch. > > > > diff --git a/bloom.h b/bloom.h > > index c6d77e8393..70a8840896 100644 > > --- a/bloom.h > > +++ b/bloom.h > > @@ -93,6 +93,7 @@ enum bloom_filter_computed { > > BLOOM_NOT_COMPUTED = (1 << 0), > > BLOOM_COMPUTED = (1 << 1), > > BLOOM_TRUNC_LARGE = (1 << 2), > > + BLOOM_TRUNC_SMALL = (1 << 3), > > s/SMALL/EMPTY/ > > This "small" suffix in the constant, variable, and trace2 key names is > misleading, because we only mean empty commits. I could buy that it might be misleading; I only picked this since it was the opposite of "large". You could imagine that BLOOM_TRUNC_X means "truncated in the direction of 'x'", but to be honest I don't think that this matters. I understand the churn of coming back to this after the topic has already been merged creates more hassle, but frankly this series has already gone on for quite a while, and it has been holding up important bug fixes that are unrelated to the main feature. So, I think that if it's truly misleading, we could revisit this after the topic is merged. But, I'm not planning on changing anything at this point. Thanks, Taylor
Taylor Blau <me@ttaylorr.com> writes: >> > In practice, these boundary commits likely occupy a small proportion of >> > the overall number of commits, and so the size penalty is likely smaller >> > than storing a bitmap for all commits. >> >> | Percentage of >> | commits modifying >> | 0 path | >= 512 paths >> ---------------+------------+---------------- >> android-base | 13.20% | 0.13% >> cmssw | 0.15% | 0.23% >> cpython | 3.07% | 0.01% >> elasticsearch | 0.70% | 1.00% >> gcc | 0.00% | 0.08% >> gecko-dev | 0.14% | 0.64% >> git | 0.11% | 0.02% >> glibc | 0.02% | 0.10% >> go | 0.00% | 0.07% >> homebrew-cask | 0.40% | 0.02% >> homebrew-core | 0.01% | 0.01% >> jdk | 0.26% | 5.64% >> linux | 0.01% | 0.51% >> llvm-project | 0.12% | 0.03% >> rails | 0.10% | 0.10% >> rust | 0.07% | 0.17% >> tensorflow | 0.09% | 1.02% >> webkit | 0.05% | 0.31% > > This is very useful information to have! Without the total number of > commits, it's impossible to know whether or not this is a win over the > BFXL chunk. But, since the number of commits is probably "large" versus > the percentage of boundary commits which is "small", it's almost > certainly an advantage. Do you want to include it in either the log message in one of the commits, in code comment, or a technical doc? > So, I think that if it's truly misleading, we could revisit this after > the topic is merged. But, I'm not planning on changing anything at this > point. If you do not want to help us go the last-mile to completion, that is sad, but I do not want to see a basically good patch stall like that, so let's find somebody else who can do the helping ;-) Here is what my trial rebase produced. I'll queue it to 'seen' (if you prefer I can send a full v3 patch, but I expect that you know how to fetch from 'seen' and review locally) after checking if the result passes the tests locally; an extra set of eyeballs to verify the result is pretty much appreciated. Thanks. 1: ca6c060171 ! 1: 9b294a0c66 bloom: encode out-of-bounds filters as non-empty @@ Commit message efficient than storing a bitmap for which commits haven't computed their Bloom filters. Storing a bitmap incurs a penalty of one bit per commit, whereas storing explicit filters as above incurs a penalty of one byte - per too-large or too-small commit. + per too-large or empty commit. In practice, these boundary commits likely occupy a small proportion of the overall number of commits, and so the size penalty is likely smaller @@ bloom.c: struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD; + if (!filter->len) { + if (computed) -+ *computed |= BLOOM_TRUNC_SMALL; ++ *computed |= BLOOM_TRUNC_EMPTY; + filter->len = 1; + } filter->data = xcalloc(filter->len, sizeof(unsigned char)); @@ bloom.h: enum bloom_filter_computed { BLOOM_NOT_COMPUTED = (1 << 0), BLOOM_COMPUTED = (1 << 1), BLOOM_TRUNC_LARGE = (1 << 2), -+ BLOOM_TRUNC_SMALL = (1 << 3), ++ BLOOM_TRUNC_EMPTY = (1 << 3), }; struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, @@ commit-graph.c: struct write_commit_graph_context { int count_bloom_filter_computed; int count_bloom_filter_not_computed; -+ int count_bloom_filter_trunc_small; ++ int count_bloom_filter_trunc_empty; int count_bloom_filter_trunc_large; }; @@ commit-graph.c: static void trace2_bloom_filter_write_statistics(struct write_co ctx->count_bloom_filter_computed); trace2_data_intmax("commit-graph", ctx->r, "filter-not-computed", ctx->count_bloom_filter_not_computed); -+ trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-small", -+ ctx->count_bloom_filter_trunc_small); ++ trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-empty", ++ ctx->count_bloom_filter_trunc_empty); trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-large", ctx->count_bloom_filter_trunc_large); } @@ commit-graph.c: static void compute_bloom_filters(struct write_commit_graph_cont &computed); if (computed & BLOOM_COMPUTED) { ctx->count_bloom_filter_computed++; -+ if (computed & BLOOM_TRUNC_SMALL) -+ ctx->count_bloom_filter_trunc_small++; ++ if (computed & BLOOM_TRUNC_EMPTY) ++ ctx->count_bloom_filter_trunc_empty++; if (computed & BLOOM_TRUNC_LARGE) ctx->count_bloom_filter_trunc_large++; } else if (computed & BLOOM_NOT_COMPUTED) @@ t/t4216-log-bloom.sh: test_max_changed_paths () { grep "\"key\":\"filter-computed\",\"value\":\"$1\"" $2 } -+test_filter_trunc_small () { -+ grep "\"key\":\"filter-trunc-small\",\"value\":\"$1\"" $2 ++test_filter_trunc_empty () { ++ grep "\"key\":\"filter-trunc-empty\",\"value\":\"$1\"" $2 +} + test_filter_trunc_large () { @@ t/t4216-log-bloom.sh: test_expect_success 'correctly report changes over limit' ' +test_expect_success 'correctly report commits with no changed paths' ' -+ git init small && -+ test_when_finished "rm -fr small" && ++ git init empty && ++ test_when_finished "rm -fr empty" && + ( -+ cd small && ++ cd empty && + + git commit --allow-empty -m "initial commit" && + @@ t/t4216-log-bloom.sh: test_expect_success 'correctly report changes over limit' + git commit-graph write --reachable --changed-paths && + test_filter_computed 1 trace.event && + test_filter_not_computed 0 trace.event && -+ test_filter_trunc_small 1 trace.event && ++ test_filter_trunc_empty 1 trace.event && + test_filter_trunc_large 0 trace.event + ) +' 2: 11db600d51 = 2: 1b4c861e68 commit-graph: rename 'split_commit_graph_opts' 3: cf49598137 ! 3: d6c1bd395e builtin/commit-graph.c: introduce '--max-new-filters=<n>' @@ t/t4216-log-bloom.sh: test_expect_success 'correctly report commits with no chan + + test_filter_computed 2 trace.event && + test_filter_not_computed 3 trace.event && -+ test_filter_trunc_small 0 trace.event && ++ test_filter_trunc_empty 0 trace.event && + test_filter_trunc_large 0 trace.event + ) +' @@ t/t4216-log-bloom.sh: test_expect_success 'correctly report commits with no chan + --split=replace --max-new-filters=1 && + test_filter_computed 1 trace.event && + test_filter_not_computed 4 trace.event && -+ test_filter_trunc_small 0 trace.event && ++ test_filter_trunc_empty 0 trace.event && + test_filter_trunc_large 0 trace.event + ) +' @@ t/t4216-log-bloom.sh: test_expect_success 'correctly report commits with no chan + --changed-paths --max-new-filters=2 && + test_filter_computed 2 trace.event && + test_filter_not_computed 4 trace.event && -+ test_filter_trunc_small 2 trace.event && ++ test_filter_trunc_empty 2 trace.event && + test_filter_trunc_large 0 trace.event + done && + @@ t/t4216-log-bloom.sh: test_expect_success 'correctly report commits with no chan + --changed-paths --max-new-filters=2 && + test_filter_computed 0 trace.event && + test_filter_not_computed 6 trace.event && -+ test_filter_trunc_small 0 trace.event && ++ test_filter_trunc_empty 0 trace.event && + test_filter_trunc_large 0 trace.event + ) +' 4: 1bc82cd008 ! 4: b0d51fb04a commit-graph: introduce 'commitGraph.maxNewFilters' @@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation is limited by --max- + --split=replace && test_filter_computed 1 trace.event && test_filter_not_computed 4 trace.event && - test_filter_trunc_small 0 trace.event && + test_filter_trunc_empty 0 trace.event && @@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills previously-skipped filters' ' ) ' @@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills previously + --max-new-filters=1 && + test_filter_computed 1 trace.event && + test_filter_not_computed 1 trace.event && -+ test_filter_trunc_small 0 trace.event && ++ test_filter_trunc_empty 0 trace.event && + test_filter_trunc_large 0 trace.event + ) +'
On Thu, Sep 17, 2020 at 05:52:11PM -0700, Junio C Hamano wrote: > Taylor Blau <me@ttaylorr.com> writes: > > >> > In practice, these boundary commits likely occupy a small proportion of > >> > the overall number of commits, and so the size penalty is likely smaller > >> > than storing a bitmap for all commits. > >> > >> | Percentage of > >> | commits modifying > >> | 0 path | >= 512 paths > >> ---------------+------------+---------------- > >> android-base | 13.20% | 0.13% > >> cmssw | 0.15% | 0.23% > >> cpython | 3.07% | 0.01% > >> elasticsearch | 0.70% | 1.00% > >> gcc | 0.00% | 0.08% > >> gecko-dev | 0.14% | 0.64% > >> git | 0.11% | 0.02% > >> glibc | 0.02% | 0.10% > >> go | 0.00% | 0.07% > >> homebrew-cask | 0.40% | 0.02% > >> homebrew-core | 0.01% | 0.01% > >> jdk | 0.26% | 5.64% > >> linux | 0.01% | 0.51% > >> llvm-project | 0.12% | 0.03% > >> rails | 0.10% | 0.10% > >> rust | 0.07% | 0.17% > >> tensorflow | 0.09% | 1.02% > >> webkit | 0.05% | 0.31% > > > > This is very useful information to have! Without the total number of > > commits, it's impossible to know whether or not this is a win over the > > BFXL chunk. But, since the number of commits is probably "large" versus > > the percentage of boundary commits which is "small", it's almost > > certainly an advantage. > > Do you want to include it in either the log message in one of the > commits, in code comment, or a technical doc? Let's put it in the commit message. I think that it's useful enough that people interested enough to dig through the commits would want it, but too detailed to be as visible as in the technical documentation. > > So, I think that if it's truly misleading, we could revisit this after > > the topic is merged. But, I'm not planning on changing anything at this > > point. > > If you do not want to help us go the last-mile to completion, that > is sad, but I do not want to see a basically good patch stall like > that, so let's find somebody else who can do the helping ;-) I'm sorry to give off the impression that I do not want to help; that's not the case. After reading Gàbor's email, I thought that the changes he was suggesting were minor, and was trying to say "let's do this on top and apply the important bug fixes first," not, "I am never going to touch this again". > Here is what my trial rebase produced. I'll queue it to 'seen' (if > you prefer I can send a full v3 patch, but I expect that you know > how to fetch from 'seen' and review locally) after checking if the > result passes the tests locally; an extra set of eyeballs to verify > the result is pretty much appreciated. It looks off to a great start; and thanks for taking the care to make up for my laziness. Everything you did looks good to me. I touched up "bloom: encode out-of-bounds filters as non-empty" locally to include the table above (and some commentary around it), so I'll send a v3 to the list once I have finished running the tests. > Thanks. Thank you, and sorry again. Thanks, Taylor
diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt index 6ddbceba15..6585f1948a 100644 --- a/Documentation/technical/commit-graph-format.txt +++ b/Documentation/technical/commit-graph-format.txt @@ -125,7 +125,7 @@ CHUNK DATA: * The rest of the chunk is the concatenation of all the computed Bloom filters for the commits in lexicographic order. * Note: Commits with no changes or more than 512 changes have Bloom filters - of length zero. + of length one, with either all bits set to zero or one respectively. * The BDAT chunk is present if and only if BIDX is present. Base Graphs List (ID: {'B', 'A', 'S', 'E'}) [Optional] diff --git a/bloom.c b/bloom.c index db9fb82437..d24747a1d5 100644 --- a/bloom.c +++ b/bloom.c @@ -177,6 +177,13 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data, return strcmp(e1->path, e2->path); } +static void init_truncated_large_filter(struct bloom_filter *filter) +{ + filter->data = xmalloc(1); + filter->data[0] = 0xFF; + filter->len = 1; +} + struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, struct commit *c, int compute_if_not_present, @@ -260,12 +267,18 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, } if (hashmap_get_size(&pathmap) > settings->max_changed_paths) { + init_truncated_large_filter(filter); if (computed) *computed |= BLOOM_TRUNC_LARGE; goto cleanup; } filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD; + if (!filter->len) { + if (computed) + *computed |= BLOOM_TRUNC_SMALL; + filter->len = 1; + } filter->data = xcalloc(filter->len, sizeof(unsigned char)); hashmap_for_each_entry(&pathmap, &iter, e, entry) { @@ -279,8 +292,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, } else { for (i = 0; i < diff_queued_diff.nr; i++) diff_free_filepair(diff_queued_diff.queue[i]); - filter->data = NULL; - filter->len = 0; + init_truncated_large_filter(filter); if (computed) *computed |= BLOOM_TRUNC_LARGE; diff --git a/bloom.h b/bloom.h index c6d77e8393..70a8840896 100644 --- a/bloom.h +++ b/bloom.h @@ -93,6 +93,7 @@ enum bloom_filter_computed { BLOOM_NOT_COMPUTED = (1 << 0), BLOOM_COMPUTED = (1 << 1), BLOOM_TRUNC_LARGE = (1 << 2), + BLOOM_TRUNC_SMALL = (1 << 3), }; struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, diff --git a/commit-graph.c b/commit-graph.c index 1ca754f19c..bd4247bca5 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -974,6 +974,7 @@ struct write_commit_graph_context { int count_bloom_filter_computed; int count_bloom_filter_not_computed; + int count_bloom_filter_trunc_small; int count_bloom_filter_trunc_large; }; @@ -1402,6 +1403,8 @@ static void trace2_bloom_filter_write_statistics(struct write_commit_graph_conte ctx->count_bloom_filter_computed); trace2_data_intmax("commit-graph", ctx->r, "filter-not-computed", ctx->count_bloom_filter_not_computed); + trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-small", + ctx->count_bloom_filter_trunc_small); trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-large", ctx->count_bloom_filter_trunc_large); } @@ -1438,6 +1441,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) &computed); if (computed & BLOOM_COMPUTED) { ctx->count_bloom_filter_computed++; + if (computed & BLOOM_TRUNC_SMALL) + ctx->count_bloom_filter_trunc_small++; if (computed & BLOOM_TRUNC_LARGE) ctx->count_bloom_filter_trunc_large++; } else if (computed & BLOOM_NOT_COMPUTED) diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh index 232ba2c485..7e4ab1795f 100755 --- a/t/t0095-bloom.sh +++ b/t/t0095-bloom.sh @@ -71,8 +71,8 @@ test_expect_success 'get bloom filters for commit with no changes' ' git init && git commit --allow-empty -m "c0" && cat >expect <<-\EOF && - Filter_Length:0 - Filter_Data: + Filter_Length:1 + Filter_Data:00| EOF test-tool bloom get_filter_for_commit "$(git rev-parse HEAD)" >actual && test_cmp expect actual @@ -107,8 +107,8 @@ test_expect_success EXPENSIVE 'get bloom filter for commit with 513 changes' ' git add bigDir && git commit -m "commit with 513 changes" && cat >expect <<-\EOF && - Filter_Length:0 - Filter_Data: + Filter_Length:1 + Filter_Data:ff| EOF test-tool bloom get_filter_for_commit "$(git rev-parse HEAD)" >actual && test_cmp expect actual diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index 1ac8f4c4eb..a0c9c9ea23 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -30,6 +30,7 @@ test_expect_success 'setup test - repo, commits, commit graph, log outputs' ' rm file_to_be_deleted && git add . && git commit -m "file removed" && + git commit --allow-empty -m "empty" && git commit-graph write --reachable --changed-paths && test_oid_cache <<-EOF @@ -49,7 +50,7 @@ graph_read_expect () { } test_expect_success 'commit-graph write wrote out the bloom chunks' ' - graph_read_expect 15 + graph_read_expect 16 ' # Turn off any inherited trace2 settings for this test. @@ -156,7 +157,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,\"maybe\":6,\"definitely_not\":8" + bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"maybe\":6,\"definitely_not\":9" setup "$log_args" && grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" && test_cmp log_wo_bloom log_w_bloom @@ -185,10 +186,18 @@ test_max_changed_paths () { grep "\"max_changed_paths\":$1" $2 } +test_filter_not_computed () { + grep "\"key\":\"filter-not-computed\",\"value\":\"$1\"" $2 +} + test_filter_computed () { grep "\"key\":\"filter-computed\",\"value\":\"$1\"" $2 } +test_filter_trunc_small () { + grep "\"key\":\"filter-trunc-small\",\"value\":\"$1\"" $2 +} + test_filter_trunc_large () { grep "\"key\":\"filter-trunc-large\",\"value\":\"$1\"" $2 } @@ -283,4 +292,21 @@ test_expect_success 'correctly report changes over limit' ' ) ' +test_expect_success 'correctly report commits with no changed paths' ' + git init small && + test_when_finished "rm -fr small" && + ( + cd small && + + git commit --allow-empty -m "initial commit" && + + GIT_TRACE2_EVENT="$(pwd)/trace.event" \ + git commit-graph write --reachable --changed-paths && + test_filter_computed 1 trace.event && + test_filter_not_computed 0 trace.event && + test_filter_trunc_small 1 trace.event && + test_filter_trunc_large 0 trace.event + ) +' + test_done
When a changed-path Bloom filter has either zero, or more than a certain number (commonly 512) of entries, the commit-graph machinery encodes it as "missing". More specifically, it sets the indices adjacent in the BIDX chunk as equal to each other to indicate a "length 0" filter; that is, that the filter occupies zero bytes on disk. This has heretofore been fine, since the commit-graph machinery has no need to care about these filters with too few or too many changed paths. Both cases act like no filter has been generated at all, and so there is no need to store them. In a subsequent commit, however, the commit-graph machinery will learn to only compute Bloom filters for some commits in the current commit-graph layer. This is a change from the current implementation which computes Bloom filters for all commits that are in the layer being written. Critically for this patch, only computing some of the Bloom filters means adding a third state for length 0 Bloom filters: zero entries, too many entries, or "hasn't been computed". It will be important for that future patch to distinguish between "not representable" (i.e., zero or too-many changed paths), and "hasn't been computed". In particular, we don't want to waste time recomputing filters that have already been computed. To that end, change how we store Bloom filters in the "computed but not representable" category: - Bloom filters with no entries are stored as a single byte with all bits low (i.e., all queries to that Bloom filter will return "definitely not") - Bloom filters with too many entries are stored as a single byte with all bits set high (i.e., all queries to that Bloom filter will return "maybe"). These rules are sufficient to not incur a behavior change by changing the on-disk representation of these two classes. Likewise, no specification changes are necessary for the commit-graph format, either: - Filters that were previously empty will be recomputed and stored according to the new rules, and - old clients reading filters generated by new clients will interpret the filters correctly and be none the wiser to how they were generated. Clients will invoke the Bloom machinery in more cases than before, but this can be addressed by returning a NULL filter when all bits are set high. This can be addressed in a future patch. Finally, note that this does increase the size of on-disk commit-graphs, but far less than other proposals. In particular, this is generally more efficient than storing a bitmap for which commits haven't computed their Bloom filters. Storing a bitmap incurs a penalty of one bit per commit, whereas storing explicit filters as above incurs a penalty of one byte per too-large or too-small commit. In practice, these boundary commits likely occupy a small proportion of the overall number of commits, and so the size penalty is likely smaller than storing a bitmap for all commits. A test to exercise filters which contain too many changed path entries will be introduced in a subsequent patch. Suggested-by: SZEDER Gábor <szeder.dev@gmail.com> Suggested-by: Jakub Narębski <jnareb@gmail.com> Helped-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Taylor Blau <me@ttaylorr.com> --- .../technical/commit-graph-format.txt | 2 +- bloom.c | 16 ++++++++-- bloom.h | 1 + commit-graph.c | 5 ++++ t/t0095-bloom.sh | 8 ++--- t/t4216-log-bloom.sh | 30 +++++++++++++++++-- 6 files changed, 53 insertions(+), 9 deletions(-)