Re: [PATCH v3 14/14] builtin/commit-graph.c: introduce '--max-new-filters=<n>'
- From
Derrick Stolee <stolee@gmail.com>
- Date
- Aug 12, 2020, 12:29 UTC
- Message-ID
- <ee5c0db0-6582-f039-96e1-be64ee4fe7a6@gmail.com>
- In-Reply-To
- <09f6871f66bff838c067a3e0d23cd4622171f3bd.1597178915.git.me@ttaylorr.com>
On 8/11/2020 4:52 PM, Taylor Blau wrote:
Show 11 quoted lines
> Introduce a command-line flag and configuration variable to fill in the > 'max_new_filters' variable introduced by the previous patch. > > The command-line option '--max-new-filters' takes precedence over > 'commitGraph.maxNewFilters', which is the default value. > '--no-max-new-filters' can also be provided, which sets the value back > to '-1', indicating that an unlimited number of new Bloom filters may be > generated. (OPT_INTEGER only allows setting the '--no-' variant back to > '0', hence a custom callback was used instead). > > Signed-off-by: Taylor Blau <me@ttaylorr.com>
...
Show 23 quoted lines
> diff --git a/bloom.c b/bloom.c
> index ed54e96e57..8d07209c6b 100644
> --- a/bloom.c
> +++ b/bloom.c
> @@ -51,6 +51,21 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,
> else
> start_index = 0;
>
> + if ((start_index == end_index) &&
> + (g->bloom_large && !bitmap_get(g->bloom_large, lex_pos))) {
> + /*
> + * If the filter is zero-length, either (1) the filter has no
> + * changes, (2) the filter has too many changes, or (3) it
> + * wasn't computed (eg., due to '--max-new-filters').
> + *
> + * If either (1) or (2) is the case, the 'large' bit will be set
> + * for this Bloom filter. If it is unset, then it wasn't
> + * computed. In that case, return nothing, since we don't have
> + * that filter in the graph.
> + */
> + return 0;
> + }
> +Here, you are creating a distinction between an "empty" filter and a "too large" filter at a place that I don't think is important.
For instance, this code will be triggered by "git log -- <path>" but you only care about the filter being too large when writing the commit-graph. I think this check for a "too large" filter should instead be inside get_or_compute_bloom_filter(). I include a patch below that applies on top of tb/bloom-improvements that gets to my point (and how minor the issue might be).
Thanks, -Stolee
--- >8 ---
From 92a7a3d0f769fad7617426730cb97584a3d07794 Mon Sep 17 00:00:00 2001 From: Derrick Stolee <dstolee@microsoft.com> Date: Wed, 12 Aug 2020 08:20:03 -0400 Subject: [PATCH] commit-graph: lazy-load large Bloom filter bitmap
The bloom_large bitmap in struct commit_graph is currently loaded immediately upon first parse of the commit-graph file (when the chunk exists). This is needed because the current implementation of get_bloom_filter_from_graph() is special-cased to return NULL when the filter is marked as "too large".
This has a slight drawback: before we can read a single commit out of the commit-graph file, we need to load this entire chunk into memory. This happens even for commands that don't need changed-path Bloom filters, such as "git log -1".
This "too large" information is only used when writing a commit-graph file, so we can delay the check for a large filter until after we check compute_if_not_present in get_or_compute_bloom_filter(). Also, place that lazy-load directly in the get_bloom_filter_large_in_graph() method, so we ensure it is ready when needed.
This may be overkill. For a repository with one million commits, this filter size is approximately 125 *kilobytes* of data. My local measurements found that this took between 1 and 2 milliseconds to load into memory. Even for repositories with 10 million commits, this difference would not be noticeable for end-user commands.
On the other hand, these handfuls of milliseconds could add up when running a hosting service using Git, so this extra effort is probably worth it.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- bloom.c | 27 ++++++++------------------- commit-graph.c | 30 +++++++++++++++++------------- commit-graph.h | 8 ++++++++ 3 files changed, 33 insertions(+), 32 deletions(-)
diff --git a/bloom.c b/bloom.c index 8d07209c6b..6d0884fa19 100644 --- a/bloom.c +++ b/bloom.c @@ -51,21 +51,6 @@ static int load_bloom_filter_from_graph(struct commit_graph *g, else start_index = 0; - if ((start_index == end_index) && - (g->bloom_large && !bitmap_get(g->bloom_large, lex_pos))) { - /* - * If the filter is zero-length, either (1) the filter has no - * changes, (2) the filter has too many changes, or (3) it - * wasn't computed (eg., due to '--max-new-filters'). - * - * If either (1) or (2) is the case, the 'large' bit will be set - * for this Bloom filter. If it is unset, then it wasn't - * computed. In that case, return nothing, since we don't have - * that filter in the graph. - */ - return 0; - } - filter->len = end_index - start_index; filter->data = (unsigned char *)(g->chunk_bloom_data + sizeof(unsigned char) * start_index + @@ -212,16 +197,20 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, if (!filter->data) { load_commit_graph_info(r, c); - if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH && - load_bloom_filter_from_graph(r->objects->commit_graph, filter, c)) - return filter; + if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH) + load_bloom_filter_from_graph(r->objects->commit_graph, filter, c); } - if (filter->data) + if (filter && filter->len) return filter; if (!compute_if_not_present) return NULL; + if (filter && !filter->len && + get_bloom_filter_large_in_graph(r->objects->commit_graph, c, + settings->max_changed_paths)) + return filter; + repo_diff_setup(r, &diffopt); diffopt.flags.recursive = 1; diffopt.detect_rename = 0; diff --git a/commit-graph.c b/commit-graph.c index 4aae5471e3..ea89f431cc 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -435,17 +435,9 @@ struct commit_graph *parse_commit_graph(struct repository *r, if (graph->chunk_bloom_large_filters) chunk_repeated = 1; else if (r->settings.commit_graph_read_changed_paths) { - size_t alloc = get_be64(chunk_lookup + 4) - chunk_offset - sizeof(uint32_t); + graph->bloom_large_alloc = get_be64(chunk_lookup + 4) - chunk_offset - sizeof(uint32_t); graph->chunk_bloom_large_filters = data + chunk_offset + sizeof(uint32_t); graph->bloom_filter_settings->max_changed_paths = get_be32(data + chunk_offset); - if (alloc) { - size_t j; - graph->bloom_large = bitmap_word_alloc(alloc); - - for (j = 0; j < graph->bloom_large->word_alloc; j++) - graph->bloom_large->words[j] = get_be64( - graph->chunk_bloom_large_filters + j * sizeof(eword_t)); - } } break; } @@ -953,9 +945,9 @@ struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit return get_commit_tree_in_graph_one(r, r->objects->commit_graph, c); } -static int get_bloom_filter_large_in_graph(struct commit_graph *g, - const struct commit *c, - uint32_t max_changed_paths) +int get_bloom_filter_large_in_graph(struct commit_graph *g, + const struct commit *c, + uint32_t max_changed_paths) { uint32_t graph_pos = commit_graph_position(c); if (graph_pos == COMMIT_NOT_FROM_GRAPH) @@ -964,8 +956,20 @@ static int get_bloom_filter_large_in_graph(struct commit_graph *g, while (g && graph_pos < g->num_commits_in_base) g = g->base_graph; - if (!(g && g->bloom_large)) + if (!g || !g->bloom_large_alloc) return 0; + + if (!g->bloom_large) { + size_t j; + g->bloom_large = bitmap_word_alloc(g->bloom_large_alloc); + + for (j = 0; j < g->bloom_large->word_alloc; j++) { + const void *data = g->chunk_bloom_large_filters + + j * sizeof(eword_t); + g->bloom_large->words[j] = get_be64(data); + } + } + if (g->bloom_filter_settings->max_changed_paths != max_changed_paths) { /* * Force all commits which are subject to a different diff --git a/commit-graph.h b/commit-graph.h index 75ef83708b..126fd43380 100644 --- a/commit-graph.h +++ b/commit-graph.h @@ -51,6 +51,13 @@ void load_commit_graph_info(struct repository *r, struct commit *item); struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit *c); +/* + * Returns 1 if this commit was marked in the BFXL chunk as having more + * than max_changed_paths changes. + */ +int get_bloom_filter_large_in_graph(struct commit_graph *g, + const struct commit *c, + uint32_t max_changed_paths); struct commit_graph { const unsigned char *data; size_t data_len; @@ -74,6 +81,7 @@ struct commit_graph { const unsigned char *chunk_bloom_data; const unsigned char *chunk_bloom_large_filters; + size_t bloom_large_alloc; struct bitmap *bloom_large; struct bloom_filter_settings *bloom_filter_settings;
-- 2.28.0.38.gc6f546511c1