From: "Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> To: git@vger.kernel.org Cc: stolee@gmail.com, szeder.dev@gmail.com, jonathantanmy@google.com, Garima Singh <garima.singh@microsoft.com>, Garima Singh <garima.singh@microsoft.com> Subject: [PATCH v4 10/15] commit-graph: reuse existing Bloom filters during write Date: Mon, 06 Apr 2020 16:59:50 +0000 [thread overview] Message-ID: <cc8022bdf82d0ada326ad546fdd7bb7801fc3675.1586192395.git.gitgitgadget@gmail.com> (raw) In-Reply-To: <pull.497.v4.git.1586192395.gitgitgadget@gmail.com> From: Garima Singh <garima.singh@microsoft.com> Add logic to a) parse Bloom filter information from the commit graph file and, b) re-use existing Bloom filters. See Documentation/technical/commit-graph-format for the format in which the Bloom filter information is written to the commit graph file. To read Bloom filter for a given commit with lexicographic position 'i' we need to: 1. Read BIDX[i] which essentially gives us the starting index in BDAT for filter of commit i+1. It is essentially the index past the end of the filter of commit i. It is called end_index in the code. 2. For i>0, read BIDX[i-1] which will give us the starting index in BDAT for filter of commit i. It is called the start_index in the code. For the first commit, where i = 0, Bloom filter data starts at the beginning, just past the header in the BDAT chunk. Hence, start_index will be 0. 3. The length of the filter will be end_index - start_index, because BIDX[i] gives the cumulative 8-byte words including the ith commit's filter. We toggle whether Bloom filters should be recomputed based on the compute_if_not_present flag. Helped-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Garima Singh <garima.singh@microsoft.com> --- bloom.c | 49 ++++++++++++++++++++++++++++++++++++++++++- bloom.h | 4 +++- commit-graph.c | 6 +++--- t/helper/test-bloom.c | 2 +- 4 files changed, 55 insertions(+), 6 deletions(-) diff --git a/bloom.c b/bloom.c index a16eee92331..0f714dd76ae 100644 --- a/bloom.c +++ b/bloom.c @@ -4,6 +4,8 @@ #include "diffcore.h" #include "revision.h" #include "hashmap.h" +#include "commit-graph.h" +#include "commit.h" define_commit_slab(bloom_filter_slab, struct bloom_filter); @@ -26,6 +28,36 @@ static inline unsigned char get_bitmask(uint32_t pos) return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1)); } +static int load_bloom_filter_from_graph(struct commit_graph *g, + struct bloom_filter *filter, + struct commit *c) +{ + uint32_t lex_pos, start_index, end_index; + + while (c->graph_pos < g->num_commits_in_base) + g = g->base_graph; + + /* The commit graph commit 'c' lives in doesn't carry bloom filters. */ + if (!g->chunk_bloom_indexes) + return 0; + + lex_pos = c->graph_pos - g->num_commits_in_base; + + end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos); + + if (lex_pos > 0) + start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1)); + else + start_index = 0; + + filter->len = end_index - start_index; + filter->data = (unsigned char *)(g->chunk_bloom_data + + sizeof(unsigned char) * start_index + + BLOOMDATA_CHUNK_HEADER_SIZE); + + return 1; +} + /* * Calculate the murmur3 32-bit hash value for the given data * using the given seed. @@ -127,7 +159,8 @@ void init_bloom_filters(void) } struct bloom_filter *get_bloom_filter(struct repository *r, - struct commit *c) + struct commit *c, + int compute_if_not_present) { struct bloom_filter *filter; struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS; @@ -140,6 +173,20 @@ struct bloom_filter *get_bloom_filter(struct repository *r, filter = bloom_filter_slab_at(&bloom_filters, c); + if (!filter->data) { + load_commit_graph_info(r, c); + if (c->graph_pos != COMMIT_NOT_FROM_GRAPH && + r->objects->commit_graph->chunk_bloom_indexes) { + if (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c)) + return filter; + else + return NULL; + } + } + + if (filter->data || !compute_if_not_present) + return filter; + repo_diff_setup(r, &diffopt); diffopt.flags.recursive = 1; diffopt.max_changes = max_changes; diff --git a/bloom.h b/bloom.h index 85ab8e9423d..760d7122374 100644 --- a/bloom.h +++ b/bloom.h @@ -32,6 +32,7 @@ struct bloom_filter_settings { #define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10 } #define BITS_PER_WORD 8 +#define BLOOMDATA_CHUNK_HEADER_SIZE 3 * sizeof(uint32_t) /* * A bloom_filter struct represents a data segment to @@ -79,6 +80,7 @@ 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); + struct commit *c, + int compute_if_not_present); #endif \ No newline at end of file diff --git a/commit-graph.c b/commit-graph.c index a8b6b5cca5d..77668629e27 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -1086,7 +1086,7 @@ static void write_graph_chunk_bloom_indexes(struct hashfile *f, ctx->commits.nr); while (list < last) { - struct bloom_filter *filter = get_bloom_filter(ctx->r, *list); + struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0); cur_pos += filter->len; display_progress(progress, ++i); hashwrite_be32(f, cur_pos); @@ -1115,7 +1115,7 @@ static void write_graph_chunk_bloom_data(struct hashfile *f, hashwrite_be32(f, settings->bits_per_entry); while (list < last) { - struct bloom_filter *filter = get_bloom_filter(ctx->r, *list); + struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0); display_progress(progress, ++i); hashwrite(f, filter->data, filter->len * sizeof(unsigned char)); list++; @@ -1296,7 +1296,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) for (i = 0; i < ctx->commits.nr; i++) { struct commit *c = sorted_commits[i]; - struct bloom_filter *filter = get_bloom_filter(ctx->r, c); + struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1); ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len; display_progress(progress, i + 1); } diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c index f18d1b722e1..ce412664ba9 100644 --- a/t/helper/test-bloom.c +++ b/t/helper/test-bloom.c @@ -39,7 +39,7 @@ 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); + filter = get_bloom_filter(the_repository, c, 1); print_bloom_filter(filter); } -- gitgitgadget
next prev parent reply other threads:[~2020-04-06 17:00 UTC|newest] Thread overview: 159+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget 2019-12-20 22:05 ` [PATCH 1/9] commit-graph: add --changed-paths option to write Garima Singh via GitGitGadget 2020-01-01 20:20 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 2/9] commit-graph: write changed paths bloom filters Garima Singh via GitGitGadget 2019-12-21 16:48 ` Philip Oakley 2020-01-06 18:44 ` Jakub Narebski 2020-01-13 19:48 ` Garima Singh 2019-12-20 22:05 ` [PATCH 3/9] commit-graph: use MAX_NUM_CHUNKS Garima Singh via GitGitGadget 2020-01-07 12:19 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 4/9] commit-graph: document bloom filter format Garima Singh via GitGitGadget 2020-01-07 14:46 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 5/9] commit-graph: write changed path bloom filters to commit-graph file Garima Singh via GitGitGadget 2020-01-07 16:01 ` Jakub Narebski 2020-01-14 15:14 ` Garima Singh 2019-12-20 22:05 ` [PATCH 6/9] commit-graph: test commit-graph write --changed-paths Garima Singh via GitGitGadget 2020-01-08 0:32 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 7/9] commit-graph: reuse existing bloom filters during write Garima Singh via GitGitGadget 2020-01-09 19:12 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 8/9] revision.c: use bloom filters to speed up path based revision walks Garima Singh via GitGitGadget 2020-01-11 0:27 ` Jakub Narebski 2020-01-15 0:08 ` Garima Singh 2019-12-20 22:05 ` [PATCH 9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag Garima Singh via GitGitGadget 2020-01-11 19:56 ` Jakub Narebski 2020-01-15 0:55 ` Garima Singh 2019-12-20 22:14 ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Junio C Hamano 2019-12-22 9:26 ` Christian Couder 2019-12-22 9:38 ` Jeff King 2020-01-01 12:04 ` Jakub Narebski 2019-12-22 9:30 ` Jeff King 2019-12-22 9:32 ` [PATCH 1/3] commit-graph: examine changed-path objects in pack order Jeff King 2019-12-27 14:51 ` Derrick Stolee 2019-12-29 6:12 ` Jeff King 2019-12-29 6:28 ` Jeff King 2019-12-30 14:37 ` Derrick Stolee 2019-12-30 14:51 ` Derrick Stolee 2019-12-22 9:32 ` [PATCH 2/3] commit-graph: free large diffs, too Jeff King 2019-12-27 14:52 ` Derrick Stolee 2019-12-22 9:32 ` [PATCH 3/3] commit-graph: stop using full rev_info for diffs Jeff King 2019-12-27 14:53 ` Derrick Stolee 2019-12-26 14:21 ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Derrick Stolee 2019-12-29 6:03 ` Jeff King 2019-12-27 16:11 ` Derrick Stolee 2019-12-29 6:24 ` Jeff King 2019-12-30 16:04 ` Derrick Stolee 2019-12-30 17:02 ` Junio C Hamano 2019-12-31 16:45 ` Jakub Narebski 2020-01-13 16:54 ` Garima Singh 2020-01-20 13:48 ` Jakub Narebski 2020-01-21 16:14 ` Garima Singh 2020-02-02 18:43 ` Jakub Narebski 2020-01-21 23:40 ` Emily Shaffer 2020-01-27 18:24 ` Garima Singh 2020-02-01 23:32 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 00/11] " Garima Singh via GitGitGadget 2020-02-05 22:56 ` [PATCH v2 01/11] commit-graph: use MAX_NUM_CHUNKS Garima Singh via GitGitGadget 2020-02-09 12:39 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 02/11] bloom: core Bloom filter implementation for changed paths Garima Singh via GitGitGadget 2020-02-15 17:17 ` Jakub Narebski 2020-02-16 16:49 ` Jakub Narebski 2020-02-22 0:32 ` Garima Singh 2020-02-23 13:38 ` Jakub Narebski 2020-02-24 17:34 ` Garima Singh 2020-02-24 18:20 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 03/11] diff: halt tree-diff early after max_changes Derrick Stolee via GitGitGadget 2020-02-17 0:00 ` Jakub Narebski 2020-02-22 0:37 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 04/11] commit-graph: compute Bloom filters for changed paths Garima Singh via GitGitGadget 2020-02-17 21:56 ` Jakub Narebski 2020-02-22 0:55 ` Garima Singh 2020-02-23 17:34 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 05/11] commit-graph: examine changed-path objects in pack order Jeff King via GitGitGadget 2020-02-18 17:59 ` Jakub Narebski 2020-02-24 18:29 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 06/11] commit-graph: examine commits by generation number Derrick Stolee via GitGitGadget 2020-02-19 0:32 ` Jakub Narebski 2020-02-24 20:45 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 07/11] commit-graph: write Bloom filters to commit graph file Garima Singh via GitGitGadget 2020-02-19 15:13 ` Jakub Narebski 2020-02-24 21:14 ` Garima Singh 2020-02-25 11:40 ` Jakub Narebski 2020-02-25 15:58 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 08/11] commit-graph: reuse existing Bloom filters during write Garima Singh via GitGitGadget 2020-02-20 18:48 ` Jakub Narebski 2020-02-24 21:45 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 09/11] commit-graph: add --changed-paths option to write subcommand Garima Singh via GitGitGadget 2020-02-20 20:28 ` Jakub Narebski 2020-02-24 21:51 ` Garima Singh 2020-02-25 12:10 ` Jakub Narebski 2020-02-20 22:10 ` Bryan Turner 2020-02-22 1:44 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 10/11] revision.c: use Bloom filters to speed up path based revision walks Garima Singh via GitGitGadget 2020-02-21 17:31 ` Jakub Narebski 2020-02-21 22:45 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 11/11] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Garima Singh via GitGitGadget 2020-02-22 0:11 ` Jakub Narebski 2020-02-07 13:52 ` [PATCH v2 00/11] Changed Paths Bloom Filters SZEDER Gábor 2020-02-07 15:09 ` Garima Singh 2020-02-07 15:36 ` Derrick Stolee 2020-02-07 16:15 ` SZEDER Gábor 2020-02-07 16:33 ` Derrick Stolee 2020-02-11 19:08 ` Garima Singh 2020-02-08 23:04 ` Jakub Narebski 2020-02-21 17:41 ` Garima Singh 2020-03-29 18:36 ` Junio C Hamano 2020-03-30 0:31 ` [PATCH v3 00/16] " Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 01/16] commit-graph: define and use MAX_NUM_CHUNKS Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 02/16] bloom.c: add the murmur3 hash implementation Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 03/16] bloom.c: introduce core Bloom filter constructs Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 04/16] bloom.c: core Bloom filter implementation for changed paths Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 05/16] diff: halt tree-diff early after max_changes Derrick Stolee via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 06/16] commit-graph: compute Bloom filters for changed paths Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 07/16] commit-graph: examine changed-path objects in pack order Jeff King via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 08/16] commit-graph: examine commits by generation number Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 09/16] diff: skip batch object download when possible Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 10/16] commit-graph: write Bloom filters to commit graph file Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 11/16] commit-graph: reuse existing Bloom filters during write Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 12/16] commit-graph: add --changed-paths option to write subcommand Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 13/16] revision.c: use Bloom filters to speed up path based revision walks Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 14/16] revision.c: add trace2 stats around Bloom filter usage Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 15/16] t4216: add end to end tests for git log with Bloom filters Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 16/16] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 00/15] Changed Paths Bloom Filters Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 01/15] commit-graph: define and use MAX_NUM_CHUNKS Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 02/15] bloom.c: add the murmur3 hash implementation Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 03/15] bloom.c: introduce core Bloom filter constructs Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 04/15] bloom.c: core Bloom filter implementation for changed paths Garima Singh via GitGitGadget 2020-06-27 15:53 ` SZEDER Gábor 2020-04-06 16:59 ` [PATCH v4 05/15] diff: halt tree-diff early after max_changes Derrick Stolee via GitGitGadget 2020-08-04 14:47 ` SZEDER Gábor 2020-08-04 16:25 ` Derrick Stolee 2020-08-04 17:00 ` SZEDER Gábor 2020-08-04 17:31 ` Derrick Stolee 2020-08-05 17:08 ` Derrick Stolee 2020-04-06 16:59 ` [PATCH v4 06/15] commit-graph: compute Bloom filters for changed paths Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 07/15] commit-graph: examine changed-path objects in pack order Jeff King via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 08/15] commit-graph: examine commits by generation number Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 09/15] commit-graph: write Bloom filters to commit graph file Garima Singh via GitGitGadget 2020-05-29 8:57 ` SZEDER Gábor 2020-05-29 13:35 ` Derrick Stolee 2020-05-31 17:23 ` SZEDER Gábor 2020-07-09 17:00 ` [PATCH] commit-graph: fix "Writing out commit graph" progress counter SZEDER Gábor 2020-07-09 18:01 ` Derrick Stolee 2020-07-09 18:20 ` Derrick Stolee 2020-04-06 16:59 ` Garima Singh via GitGitGadget [this message] 2020-06-19 14:02 ` [PATCH v4 10/15] commit-graph: reuse existing Bloom filters during write SZEDER Gábor 2020-06-19 19:28 ` Junio C Hamano 2020-07-27 21:33 ` SZEDER Gábor 2020-04-06 16:59 ` [PATCH v4 11/15] commit-graph: add --changed-paths option to write subcommand Garima Singh via GitGitGadget 2020-06-07 22:21 ` SZEDER Gábor 2020-04-06 16:59 ` [PATCH v4 12/15] revision.c: use Bloom filters to speed up path based revision walks Garima Singh via GitGitGadget 2020-06-26 6:34 ` SZEDER Gábor 2020-04-06 16:59 ` [PATCH v4 13/15] revision.c: add trace2 stats around Bloom filter usage Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 14/15] t4216: add end to end tests for git log with Bloom filters Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 15/15] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Garima Singh via GitGitGadget 2020-04-08 15:51 ` [PATCH v4 00/15] Changed Paths Bloom Filters Derrick Stolee 2020-04-08 19:21 ` Junio C Hamano 2020-04-08 20:05 ` Jakub Narębski 2020-04-12 20:34 ` Taylor Blau 2020-03-05 19:49 ` [PATCH 0/9] [RFC] " Garima Singh
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style List information: http://vger.kernel.org/majordomo-info.html * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=cc8022bdf82d0ada326ad546fdd7bb7801fc3675.1586192395.git.gitgitgadget@gmail.com \ --to=gitgitgadget@gmail.com \ --cc=garima.singh@microsoft.com \ --cc=git@vger.kernel.org \ --cc=jonathantanmy@google.com \ --cc=stolee@gmail.com \ --cc=szeder.dev@gmail.com \ --subject='Re: [PATCH v4 10/15] commit-graph: reuse existing Bloom filters during write' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
Code repositories for project(s) associated with this inbox: https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).