more miscellaneous Bloom filter improvements
PATCH v4 10/14 commit-graph.c: sort index into commits list
In reply to Taylor BlauFor locality, 'compute_bloom_filters()' sorts the commits for which it wants to compute Bloom filters in a preferred order (cf., 3d11275505 (commit-graph: examine commits by generation number, 2020-03-30) for details).
A future patch will want to recover the new graph position of each commit. Since the 'packed_commit_list' already stores a double-pointer, avoid a 'COPY_ARRAY' and instead keep track of an index into the original list. (Use an integer index instead of a memory address, since this involves a needlessly confusing triple-pointer).
Alter the two sorting routines 'commit_pos_cmp' and 'commit_gen_cmp' to take into account the packed_commit_list they are sorting with respect to. Since 'compute_bloom_filters()' is the only caller for each of those comparison functions, no other call-sites need updating.
--- commit-graph.c | 43 ++++++++++++++++++++++++------------------- 1 file changed, 24 insertions(+), 19 deletions(-)
commit-graph.c +24 -19
@@ -79,10 +79,18 @@ static void set_commit_pos(struct repository *r, const struct object_id *oid) *commit_pos_at (&commit_pos, commit) = max_pos++; } -static int commit_pos_cmp (const void *va,const void *vb) +struct packed_commit_list { +struct commit **list; +int nr; +int alloc; +}; + +static int commit_pos_cmp (const void *va,const void *vb,void *ctx) { -const struct commit *a = *(const struct commit **)va; -const struct commit *b = *(const struct commit **)vb; +struct packed_commit_list *commits = ctx; + +const struct commit *a = commits->list[*(int *)va]; +const struct commit *b = commits->list[*(int *)vb];return commit_pos_at (&commit_pos, a) -commit_pos_at (&commit_pos, b); }
@@ -139,10 +147,12 @@ static struct commit_graph_data *commit_graph_data_at(const struct commit *c)return data; } -static int commit_gen_cmp (const void *va,const void *vb) +static int commit_gen_cmp (const void *va,const void *vb,void *ctx) { -const struct commit *a = *(const struct commit **)va; -const struct commit *b = *(const struct commit **)vb; +struct packed_commit_list *commits = ctx; + +const struct commit *a = commits->list[*(int *)va]; +const struct commit *b = commits->list[*(int *)vb];uint32_t generation_a =commit_graph_generation (a);uint32_t generation_b =commit_graph_generation (b);
@@ -929,11 +939,6 @@ struct tree *get_commit_tree_in_graph(struct repository *r, const struct commitreturn get_commit_tree_in_graph_one (r, r->objects->commit_graph, c); } -struct packed_commit_list { -struct commit **list; -int nr; -int alloc; -};struct packed_oid_list {struct object_id *list;
@@ -1415,7 +1420,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) {int i;struct progress *progress =NULL ; -struct commit **sorted_commits; +int *sorted_commits;init_bloom_filters ();
@@ -1425,16 +1430,16 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) ctx->commits.nr);ALLOC_ARRAY (sorted_commits, ctx->commits.nr); -COPY_ARRAY (sorted_commits, ctx->commits.list, ctx->commits.nr); - -if (ctx->order_by_pack) -QSORT (sorted_commits, ctx->commits.nr, commit_pos_cmp); -else -QSORT (sorted_commits, ctx->commits.nr, commit_gen_cmp); +for (i =0 ; i < ctx->commits.nr; i++) + sorted_commits[i] = i; +QSORT_S (sorted_commits, ctx->commits.nr, + ctx->order_by_pack ? commit_pos_cmp : commit_gen_cmp, + &ctx->commits);for (i =0 ; i < ctx->commits.nr; i++) {int computed =0 ; -struct commit *c = sorted_commits[i]; +int pos = sorted_commits[i]; +struct commit *c = ctx->commits.list[pos]; struct bloom_filter *filter = get_or_compute_bloom_filter( ctx->r, c,
Signature · 1 line
2.27.0.2918.gc99a27ff8f
PATCH v4 11/14 csum-file.h: introduce 'hashwrite_be64()'
In reply to Taylor BlauA small handful of writers who wish to encode 64-bit values in network order have worked around the lack of such a helper by calling the 32-bit variant twice.
The subsequent commit will add another caller who wants to write a 64-bit value. To ease their (and the existing caller's) pain, introduce a helper to do just that, and convert existing call-sites.
--- commit-graph.c | 8 ++------ csum-file.h | 6 ++++++ midx.c | 3 +-- 3 files changed, 9 insertions(+), 8 deletions(-)
commit-graph.c +2 -6
@@ -1791,12 +1791,8 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx) chunk_offset =8 + (num_chunks +1 ) *GRAPH_CHUNKLOOKUP_WIDTH ;for (i =0 ; i <= num_chunks; i++) { -uint32_t chunk_write[3 ]; - - chunk_write[0 ] =htonl (chunks[i].id); - chunk_write[1 ] =htonl (chunk_offset >>32 ); - chunk_write[2 ] =htonl (chunk_offset &0xffffffff ); -hashwrite (f, chunk_write,12 ); +hashwrite_be32 (f, chunks[i].id); +hashwrite_be64 (f, chunk_offset); chunk_offset += chunks[i].size; }
csum-file.h +6 -0
@@ -62,4 +62,10 @@ static inline void hashwrite_be32(struct hashfile *f, uint32_t data) hashwrite(f, &data, sizeof(data)); } +static inline void hashwrite_be64 (struct hashfile *f,uint64_t data) +{ +hashwrite_be32 (f, data >>32 ); +hashwrite_be32 (f, data &0xffffffffUL ); +} +#endif
midx.c +1 -2
@@ -789,8 +789,7 @@ static size_t write_midx_large_offsets(struct hashfile *f, uint32_t nr_large_offif (!(offset >>31 ))continue ; -hashwrite_be32 (f, offset >>32 ); -hashwrite_be32 (f, offset &0xffffffffUL ); +hashwrite_be64 (f, offset); written +=2 *sizeof (uint32_t ); nr_large_offset--;
Signature · 1 line
2.27.0.2918.gc99a27ff8f
Re: [PATCH v4 11/14] csum-file.h: introduce 'hashwrite_be64()'
Am 04.09.20 um 00:46 schrieb Taylor Blau:
Quoted 55 lines
A small handful of writers who wish to encode 64-bit values in network order have worked around the lack of such a helper by calling the 32-bit variant twice.
The subsequent commit will add another caller who wants to write a 64-bit value. To ease their (and the existing caller's) pain, introduce a helper to do just that, and convert existing call-sites.
Suggested-by Derrick Stolee <[email protected]>Signed-off-by Taylor Blau <[email protected]>--- commit-graph.c | 8 ++------ csum-file.h | 6 ++++++ midx.c | 3 +-- 3 files changed, 9 insertions(+), 8 deletions(-)commit-graph.c +2
-6@@ -1791,12 +1791,8 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx) chunk_offset =8 + (num_chunks +1 ) *GRAPH_CHUNKLOOKUP_WIDTH ;for (i =0 ; i <= num_chunks; i++) { -uint32_t chunk_write[3 ]; - - chunk_write[0 ] =htonl (chunks[i].id); - chunk_write[1 ] =htonl (chunk_offset >>32 ); - chunk_write[2 ] =htonl (chunk_offset &0xffffffff ); -hashwrite (f, chunk_write,12 ); +hashwrite_be32 (f, chunks[i].id); +hashwrite_be64 (f, chunk_offset); chunk_offset += chunks[i].size; }csum-file.h +6
-0@@ -62,4 +62,10 @@ static inline void hashwrite_be32(struct hashfile *f, uint32_t data) hashwrite(f, &data, sizeof(data)); } +static inline void hashwrite_be64 (struct hashfile *f,uint64_t data) +{ +hashwrite_be32 (f, data >>32 ); +hashwrite_be32 (f, data &0xffffffffUL ); +} +#endif midx.c +0
-0
midx.c static size_t write_midx_large_offsets(struct hashfile *f, uint32_t nr_large_off · line 793
Quoted 7 lines
midx.c +1
-2@@ -789,8 +789,7 @@ static size_t write_midx_large_offsets(struct hashfile *f, uint32_t nr_large_offif (!(offset >>31 ))continue ; -hashwrite_be32 (f, offset >>32 ); -hashwrite_be32 (f, offset &0xffffffffUL ); +hashwrite_be64 (f, offset); written +=2 *sizeof (uint32_t );
"2 * sizeof(uint32_t)" looks slightly out of sync with the hashwrite_be64() call now; "sizeof(uint64_t)" would be more fitting.
midx.c static size_t write_midx_large_offsets(struct hashfile *f, uint32_t nr_large_off · line 795
Quoted 3 lines
midx.c +0
-0nr_large_offset--;
There's also this potential caller:
midx.c=802=static int write_midx_internal(const char *object_dir, struct multi_pack_index *m,
midx.c:981: hashwrite_be32(f, chunk_ids[i]); midx.c:982: hashwrite_be32(f, chunk_offsets[i] >> 32); midx.c:983: hashwrite_be32(f, chunk_offsets[i]);
Not sure it's worth a reroll, though.
(I'd probably leave those conversions for a later series.)
René
Re: [PATCH v4 11/14] csum-file.h: introduce 'hashwrite_be64()'
Quoted 3 lines · René Scharfe
Am 04.09.20 um 00:46 schrieb Taylor Blau:
"2 *sizeof(uint32_t)" looks slightly out of sync with thehashwrite_be64()call now; "sizeof(uint64_t)" would be more fitting.
Yeah, agreed.
Quoted 6 lines
Quoted 3 lines
nr_large_offset--;
There's also this potential caller:
Quoted 8 lines
midx.c=802=static int write_midx_internal(const char
*object_dir, structmulti_pack_index*m,midx.c:981: hashwrite_be32(f, chunk_ids[i]); midx.c:982: hashwrite_be32(f, chunk_offsets[i] >> 32); midx.c:983: hashwrite_be32(f, chunk_offsets[i]);Not sure it's worth a reroll, though.
(I'd probably leave those conversions for a later series.)
Agreed. If we were earlier on, or there wasn't already a patch that I had swapped out for a manual fixup after sending this v4, I'd certainly fold these in, but I think at this point it's easier to apply this separately on top.
Thanks for pointing them out.
Quoted 1 line
René
Thanks,
Taylor
PATCH v4 12/14 commit-graph: add large-filters bitmap chunk
In reply to Taylor BlauWhen a commit has more than a certain number of changed paths (commonly 512), the commit-graph machinery represents it as a zero-length filter. 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).
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. 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. Initialize this bitmap lazily to avoid paying a linear-time cost upon each commit-graph load even if we do not need the bitmaps themselves.
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 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.
--- .../technical/commit-graph-format.txt | 13 +++ bloom.h | 2 +- commit-graph.c | 100 +++++++++++++++--- commit-graph.h | 10 ++ t/t4216-log-bloom.sh | 25 ++++- 5 files changed, 135 insertions(+), 15 deletions(-)
Documentation/technical/commit-graph-format.txt +13 -0
@@ -128,6 +128,19 @@ 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. + * It then contains a list of 64-bit words in network order (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 entries than is allowed per filter by + the layer that contains it). + * 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
bloom.h +1 -1
@@ -33,7 +33,7 @@ struct bloom_filter_settings {* The maximum number of changed paths per commit * before declaring a Bloom filter to be too-large. * -* Not written to the commit-graph file. +* Written to the 'BFXL' chunk (instead of 'BDAT'). */ uint32_t max_changed_paths; };
commit-graph.c +87 -13
172 lines not on this page · raw message
commit-graph.h +10 -0
@@ -4,6 +4,7 @@#include "git-compat-util.h" #include "object-store.h" #include "oidset.h" +#include "ewah/ewok.h" #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH"#define GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE "GIT_TEST_COMMIT_GRAPH_DIE_ON_PARSE"
@@ -50,6 +51,9 @@ 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); +int get_bloom_filter_large_in_graph (struct commit_graph *g, +const struct commit *c); +struct commit_graph {const unsigned char *data;size_t data_len;
@@ -71,6 +75,10 @@ struct commit_graph {const unsigned char *chunk_base_graphs;const unsigned char *chunk_bloom_indexes;const unsigned char *chunk_bloom_data; +const unsigned char *chunk_bloom_large_filters; + +struct bitmap *bloom_large; +size_t bloom_large_alloc;struct bloom_filter_settings *bloom_filter_settings; };
@@ -83,6 +91,8 @@ struct commit_graph *read_commit_graph_one(struct repository *r,struct commit_graph *parse_commit_graph (struct repository *r,void *graph_map,size_t graph_size); +void prepare_commit_graph_bloom_large (struct commit_graph *g); +/* * Return 1 if and only if the repository has a commit-graph * file and generation numbers are computed in that file.
t/t4216-log-bloom.sh +24 -1
@@ -38,7 +38,7 @@ test_expect_success 'setup test - repo, commits, commit graph, log outputs' ' EOF ' graph_read_expect () { - NUM_CHUNKS=5 + NUM_CHUNKS=6 cat >expect <<- EOF header: 43475048 1 $(test_oid oid_version) $NUM_CHUNKS 0 num_commits: $1
@@ -267,5 +267,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
Signature · 1 line
2.27.0.2918.gc99a27ff8f
PATCH v4 13/14 commit-graph: rename 'split_commit_graph_opts'
In reply to Taylor BlauIn the subsequent commit, additional options will be added to the commit-graph API which have nothing to do with splitting.
Rename the 'split_commit_graph_opts' structure to the more-generic 'commit_graph_opts' to encompass both. Likewise, rename the 'flags' member to instead be 'split_flags' to clarify that it only has to do with the behavior implied by '--split'.
--- builtin/commit-graph.c | 20 ++++++++++---------- commit-graph.c | 40 ++++++++++++++++++++-------------------- commit-graph.h | 8 ++++---- make: *** [Makefile | 0 4 files changed, 34 insertions(+), 34 deletions(-) create mode 100644 make: *** [Makefile
builtin/commit-graph.c +10 -10
@@ -119,7 +119,7 @@ static int graph_verify(int argc, const char **argv) }extern int read_replace_refs; -static struct split_commit_graph_opts split_opts; +static struct commit_graph_opts write_opts;static int write_option_parse_split (const struct option *opt,const char *arg,int unset)
@@ -187,24 +187,24 @@ static int graph_write(int argc, const char **argv)OPT_BOOL (0 ,"changed-paths" , &opts.enable_changed_paths,N_ ("enable computation for changed paths" )),OPT_BOOL (0 ,"progress" , &opts.progress,N_ ("force progress reporting" )), -OPT_CALLBACK_F (0 ,"split" , &split_opts.flags,NULL , +OPT_CALLBACK_F (0 ,"split" , &write_opts.split_flags,NULL ,N_ ("allow writing an incremental commit-graph file" ),PARSE_OPT_OPTARG |PARSE_OPT_NONEG , write_option_parse_split), -OPT_INTEGER (0 ,"max-commits" , &split_opts.max_commits, +OPT_INTEGER (0 ,"max-commits" , &write_opts.max_commits,N_ ("maximum number of commits in a non-base split commit-graph" )), -OPT_INTEGER (0 ,"size-multiple" , &split_opts.size_multiple, +OPT_INTEGER (0 ,"size-multiple" , &write_opts.size_multiple,N_ ("maximum ratio between two levels of a split commit-graph" )), -OPT_EXPIRY_DATE (0 ,"expire-time" , &split_opts.expire_time, +OPT_EXPIRY_DATE (0 ,"expire-time" , &write_opts.expire_time,N_ ("only expire files older than a given date-time" )),OPT_END (), }; opts.progress =isatty (2 ); opts.enable_changed_paths =-1 ; - split_opts.size_multiple =2 ; - split_opts.max_commits =0 ; - split_opts.expire_time =0 ; + write_opts.size_multiple =2 ; + write_opts.max_commits =0 ; + write_opts.expire_time =0 ;trace2_cmd_mode ("write" );
@@ -232,7 +232,7 @@ static int graph_write(int argc, const char **argv) odb =find_odb (the_repository, opts.obj_dir);if (opts.reachable) { -if (write_commit_graph_reachable (odb, flags, &split_opts)) +if (write_commit_graph_reachable (odb, flags, &write_opts))return 1 ;return 0 ; }
@@ -261,7 +261,7 @@ static int graph_write(int argc, const char **argv) opts.stdin_packs ? &pack_indexes : NULL, opts.stdin_commits ? &commits : NULL, flags, - &split_opts)) + &write_opts)) result =1 ; cleanup:
commit-graph.c +20 -20
@@ -1012,7 +1012,7 @@ struct write_commit_graph_context { changed_paths:1 , order_by_pack:1; -const struct split_commit_graph_opts *split_opts; +const struct commit_graph_opts *opts;size_t total_bloom_filter_data_size;const struct bloom_filter_settings *bloom_settings;
@@ -1353,8 +1353,8 @@ static void close_reachable(struct write_commit_graph_context *ctx) {int i;struct commit *commit; -enum commit_graph_split_flags flags = ctx->split_opts ? - ctx->split_opts->flags :COMMIT_GRAPH_SPLIT_UNSPECIFIED ; +enum commit_graph_split_flags flags = ctx->opts ? + ctx->opts->split_flags :COMMIT_GRAPH_SPLIT_UNSPECIFIED ;if (ctx->report_progress) ctx->progress = start_delayed_progress(
@@ -1554,7 +1554,7 @@ static int add_ref_to_set(const char *refname,int write_commit_graph_reachable (struct object_directory *odb,enum commit_graph_write_flags flags, -const struct split_commit_graph_opts *split_opts) +const struct commit_graph_opts *opts) {struct oidset commits =OIDSET_INIT ;struct refs_cb_data data;
@@ -1571,7 +1571,7 @@ int write_commit_graph_reachable(struct object_directory *odb,stop_progress (&data.progress); result =write_commit_graph (odb,NULL , &commits, - flags, split_opts); + flags, opts);oidset_clear (&commits);return result;
@@ -1686,8 +1686,8 @@ static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx)static void copy_oids_to_commits (struct write_commit_graph_context *ctx) {uint32_t i; -enum commit_graph_split_flags flags = ctx->split_opts ? - ctx->split_opts->flags :COMMIT_GRAPH_SPLIT_UNSPECIFIED ; +enum commit_graph_split_flags flags = ctx->opts ? + ctx->opts->split_flags :COMMIT_GRAPH_SPLIT_UNSPECIFIED ; ctx->num_extra_edges =0 ;if (ctx->report_progress)
@@ -1973,13 +1973,13 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)int max_commits =0 ;int size_mult =2 ; -if (ctx->split_opts) { - max_commits = ctx->split_opts->max_commits; +if (ctx->opts) { + max_commits = ctx->opts->max_commits; -if (ctx->split_opts->size_multiple) - size_mult = ctx->split_opts->size_multiple; +if (ctx->opts->size_multiple) + size_mult = ctx->opts->size_multiple; - flags = ctx->split_opts->flags; + flags = ctx->opts->split_flags; } g = ctx->r->objects->commit_graph;
@@ -2157,8 +2157,8 @@ static void expire_commit_graphs(struct write_commit_graph_context *ctx)size_t dirnamelen;timestamp_t expire_time =time (NULL ); -if (ctx->split_opts && ctx->split_opts->expire_time) - expire_time = ctx->split_opts->expire_time; +if (ctx->opts && ctx->opts->expire_time) + expire_time = ctx->opts->expire_time;if (!ctx->split) {char *chain_file_name =get_chain_filename (ctx->odb);unlink (chain_file_name);
@@ -2209,7 +2209,7 @@ int write_commit_graph(struct object_directory *odb,struct string_list *pack_indexes, struct oidset *commits, enum commit_graph_write_flags flags, - const struct split_commit_graph_opts *split_opts) + const struct commit_graph_opts *opts) { struct write_commit_graph_context *ctx;uint32_t i, count_distinct =0 ;
@@ -2226,7 +2226,7 @@ int write_commit_graph(struct object_directory *odb, ctx->append = flags &COMMIT_GRAPH_WRITE_APPEND ?1 :0 ; ctx->report_progress = flags &COMMIT_GRAPH_WRITE_PROGRESS ?1 :0 ; ctx->split = flags &COMMIT_GRAPH_WRITE_SPLIT ?1 :0 ; - ctx->split_opts = split_opts; + ctx->opts = opts; ctx->total_bloom_filter_data_size =0 ; bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
@@ -2274,15 +2274,15 @@ int write_commit_graph(struct object_directory *odb, } } -if (ctx->split_opts) - replace = ctx->split_opts->flags &COMMIT_GRAPH_SPLIT_REPLACE ; +if (ctx->opts) + replace = ctx->opts->split_flags &COMMIT_GRAPH_SPLIT_REPLACE ; } ctx->approx_nr_objects =approximate_object_count (); ctx->oids.alloc = ctx->approx_nr_objects /32 ; -if (ctx->split && split_opts && ctx->oids.alloc > split_opts->max_commits) - ctx->oids.alloc = split_opts->max_commits; +if (ctx->split && opts && ctx->oids.alloc > opts->max_commits) + ctx->oids.alloc = opts->max_commits;if (ctx->append) {prepare_commit_graph_one (ctx->r, ctx->odb);
commit-graph.h +4 -4
@@ -115,11 +115,11 @@ enum commit_graph_split_flags { COMMIT_GRAPH_SPLIT_REPLACE = 2 }; -struct split_commit_graph_opts { +struct commit_graph_opts {int size_multiple;int max_commits;timestamp_t expire_time; -enum commit_graph_split_flags flags; +enum commit_graph_split_flags split_flags; };/*
@@ -130,12 +130,12 @@ struct split_commit_graph_opts {*/ int write_commit_graph_reachable (struct object_directory *odb,enum commit_graph_write_flags flags, -const struct split_commit_graph_opts *split_opts); +const struct commit_graph_opts *opts);int write_commit_graph (struct object_directory *odb,struct string_list *pack_indexes,struct oidset *commits,enum commit_graph_write_flags flags, -const struct split_commit_graph_opts *split_opts); +const struct commit_graph_opts *opts);#define COMMIT_GRAPH_VERIFY_SHALLOW (1 << 0)
make: *** [Makefile new file +0 -0
Signature · 1 line
2.27.0.2918.gc99a27ff8f
Re: [PATCH v4 13/14] commit-graph: rename 'split_commit_graph_opts'
Quoted 2 lines · Taylor Blau
In the subsequent commit, additional options will be added to the commit-graph API which have nothing to do with splitting.
I have no idea how 'make *** [Makefile' snuck into this, but it definitely shouldn't be there. Let's use the below version instead.
--- >8 ---
Subject: [PATCH] commit-graph: rename 'split_commit_graph_opts'
In the subsequent commit, additional options will be added to the commit-graph API which have nothing to do with splitting.
Rename the 'split_commit_graph_opts' structure to the more-generic 'commit_graph_opts' to encompass both. Likewise, rename the 'flags' member to instead be 'split_flags' to clarify that it only has to do with the behavior implied by '--split'.
--- builtin/commit-graph.c | 20 ++++++++++---------- commit-graph.c | 40 ++++++++++++++++++++-------------------- commit-graph.h | 8 ++++---- 3 files changed, 34 insertions(+), 34 deletions(-)
builtin/commit-graph.c +10 -10
@@ -119,7 +119,7 @@ static int graph_verify(int argc, const char **argv) }extern int read_replace_refs; -static struct split_commit_graph_opts split_opts; +static struct commit_graph_opts write_opts;static int write_option_parse_split (const struct option *opt,const char *arg,int unset)
@@ -187,24 +187,24 @@ static int graph_write(int argc, const char **argv)OPT_BOOL (0 ,"changed-paths" , &opts.enable_changed_paths,N_ ("enable computation for changed paths" )),OPT_BOOL (0 ,"progress" , &opts.progress,N_ ("force progress reporting" )), -OPT_CALLBACK_F (0 ,"split" , &split_opts.flags,NULL , +OPT_CALLBACK_F (0 ,"split" , &write_opts.split_flags,NULL ,N_ ("allow writing an incremental commit-graph file" ),PARSE_OPT_OPTARG |PARSE_OPT_NONEG , write_option_parse_split), -OPT_INTEGER (0 ,"max-commits" , &split_opts.max_commits, +OPT_INTEGER (0 ,"max-commits" , &write_opts.max_commits,N_ ("maximum number of commits in a non-base split commit-graph" )), -OPT_INTEGER (0 ,"size-multiple" , &split_opts.size_multiple, +OPT_INTEGER (0 ,"size-multiple" , &write_opts.size_multiple,N_ ("maximum ratio between two levels of a split commit-graph" )), -OPT_EXPIRY_DATE (0 ,"expire-time" , &split_opts.expire_time, +OPT_EXPIRY_DATE (0 ,"expire-time" , &write_opts.expire_time,N_ ("only expire files older than a given date-time" )),OPT_END (), }; opts.progress =isatty (2 ); opts.enable_changed_paths =-1 ; - split_opts.size_multiple =2 ; - split_opts.max_commits =0 ; - split_opts.expire_time =0 ; + write_opts.size_multiple =2 ; + write_opts.max_commits =0 ; + write_opts.expire_time =0 ;trace2_cmd_mode ("write" );
@@ -232,7 +232,7 @@ static int graph_write(int argc, const char **argv) odb =find_odb (the_repository, opts.obj_dir);if (opts.reachable) { -if (write_commit_graph_reachable (odb, flags, &split_opts)) +if (write_commit_graph_reachable (odb, flags, &write_opts))return 1 ;return 0 ; }
@@ -261,7 +261,7 @@ static int graph_write(int argc, const char **argv) opts.stdin_packs ? &pack_indexes : NULL, opts.stdin_commits ? &commits : NULL, flags, - &split_opts)) + &write_opts)) result =1 ; cleanup:
commit-graph.c +20 -20
@@ -1012,7 +1012,7 @@ struct write_commit_graph_context { changed_paths:1 , order_by_pack:1; -const struct split_commit_graph_opts *split_opts; +const struct commit_graph_opts *opts;size_t total_bloom_filter_data_size;const struct bloom_filter_settings *bloom_settings;
@@ -1353,8 +1353,8 @@ static void close_reachable(struct write_commit_graph_context *ctx) {int i;struct commit *commit; -enum commit_graph_split_flags flags = ctx->split_opts ? - ctx->split_opts->flags :COMMIT_GRAPH_SPLIT_UNSPECIFIED ; +enum commit_graph_split_flags flags = ctx->opts ? + ctx->opts->split_flags :COMMIT_GRAPH_SPLIT_UNSPECIFIED ;if (ctx->report_progress) ctx->progress = start_delayed_progress(
@@ -1554,7 +1554,7 @@ static int add_ref_to_set(const char *refname,int write_commit_graph_reachable (struct object_directory *odb,enum commit_graph_write_flags flags, -const struct split_commit_graph_opts *split_opts) +const struct commit_graph_opts *opts) {struct oidset commits =OIDSET_INIT ;struct refs_cb_data data;
@@ -1571,7 +1571,7 @@ int write_commit_graph_reachable(struct object_directory *odb,stop_progress (&data.progress); result =write_commit_graph (odb,NULL , &commits, - flags, split_opts); + flags, opts);oidset_clear (&commits);return result;
@@ -1686,8 +1686,8 @@ static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx)static void copy_oids_to_commits (struct write_commit_graph_context *ctx) {uint32_t i; -enum commit_graph_split_flags flags = ctx->split_opts ? - ctx->split_opts->flags :COMMIT_GRAPH_SPLIT_UNSPECIFIED ; +enum commit_graph_split_flags flags = ctx->opts ? + ctx->opts->split_flags :COMMIT_GRAPH_SPLIT_UNSPECIFIED ; ctx->num_extra_edges =0 ;if (ctx->report_progress)
@@ -1973,13 +1973,13 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)int max_commits =0 ;int size_mult =2 ; -if (ctx->split_opts) { - max_commits = ctx->split_opts->max_commits; +if (ctx->opts) { + max_commits = ctx->opts->max_commits; -if (ctx->split_opts->size_multiple) - size_mult = ctx->split_opts->size_multiple; +if (ctx->opts->size_multiple) + size_mult = ctx->opts->size_multiple; - flags = ctx->split_opts->flags; + flags = ctx->opts->split_flags; } g = ctx->r->objects->commit_graph;
@@ -2157,8 +2157,8 @@ static void expire_commit_graphs(struct write_commit_graph_context *ctx)size_t dirnamelen;timestamp_t expire_time =time (NULL ); -if (ctx->split_opts && ctx->split_opts->expire_time) - expire_time = ctx->split_opts->expire_time; +if (ctx->opts && ctx->opts->expire_time) + expire_time = ctx->opts->expire_time;if (!ctx->split) {char *chain_file_name =get_chain_filename (ctx->odb);unlink (chain_file_name);
@@ -2209,7 +2209,7 @@ int write_commit_graph(struct object_directory *odb,struct string_list *pack_indexes, struct oidset *commits, enum commit_graph_write_flags flags, - const struct split_commit_graph_opts *split_opts) + const struct commit_graph_opts *opts) { struct write_commit_graph_context *ctx;uint32_t i, count_distinct =0 ;
@@ -2226,7 +2226,7 @@ int write_commit_graph(struct object_directory *odb, ctx->append = flags &COMMIT_GRAPH_WRITE_APPEND ?1 :0 ; ctx->report_progress = flags &COMMIT_GRAPH_WRITE_PROGRESS ?1 :0 ; ctx->split = flags &COMMIT_GRAPH_WRITE_SPLIT ?1 :0 ; - ctx->split_opts = split_opts; + ctx->opts = opts; ctx->total_bloom_filter_data_size =0 ; bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
@@ -2274,15 +2274,15 @@ int write_commit_graph(struct object_directory *odb, } } -if (ctx->split_opts) - replace = ctx->split_opts->flags &COMMIT_GRAPH_SPLIT_REPLACE ; +if (ctx->opts) + replace = ctx->opts->split_flags &COMMIT_GRAPH_SPLIT_REPLACE ; } ctx->approx_nr_objects =approximate_object_count (); ctx->oids.alloc = ctx->approx_nr_objects /32 ; -if (ctx->split && split_opts && ctx->oids.alloc > split_opts->max_commits) - ctx->oids.alloc = split_opts->max_commits; +if (ctx->split && opts && ctx->oids.alloc > opts->max_commits) + ctx->oids.alloc = opts->max_commits;if (ctx->append) {prepare_commit_graph_one (ctx->r, ctx->odb);
commit-graph.h +4 -4
@@ -115,11 +115,11 @@ enum commit_graph_split_flags { COMMIT_GRAPH_SPLIT_REPLACE = 2 }; -struct split_commit_graph_opts { +struct commit_graph_opts {int size_multiple;int max_commits;timestamp_t expire_time; -enum commit_graph_split_flags flags; +enum commit_graph_split_flags split_flags; };/*
@@ -130,12 +130,12 @@ struct split_commit_graph_opts {*/ int write_commit_graph_reachable (struct object_directory *odb,enum commit_graph_write_flags flags, -const struct split_commit_graph_opts *split_opts); +const struct commit_graph_opts *opts);int write_commit_graph (struct object_directory *odb,struct string_list *pack_indexes,struct oidset *commits,enum commit_graph_write_flags flags, -const struct split_commit_graph_opts *split_opts); +const struct commit_graph_opts *opts);#define COMMIT_GRAPH_VERIFY_SHALLOW (1 << 0)
--
2.27.0.2918.gc99a27ff8f
PATCH v4 14/14 builtin/commit-graph.c: introduce '--max-new-filters=<n>'
In reply to Taylor BlauIntroduce a command-line flag and configuration variable to fill in the 'max_new_filters' variable introduced two patches ago.
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).
--- Documentation/config/commitgraph.txt | 4 +++ Documentation/git-commit-graph.txt | 6 ++++ bloom.c | 13 +++++--- builtin/commit-graph.c | 39 ++++++++++++++++++++++-- commit-graph.c | 27 ++++++++++++++--- commit-graph.h | 4 ++- t/t4216-log-bloom.sh | 44 ++++++++++++++++++++++++++++ 7 files changed, 125 insertions(+), 12 deletions(-)
Documentation/config/commitgraph.txt +4 -0
@@ -1,3 +1,7 @@ +commitGraph.maxNewFilters:: + Specifies the default value for the `--max-new-filters` option of `git + commit-graph write` (c.f., linkgit:git-commit-graph[1]). + commitGraph.readChangedPaths:: If true, then git will use the changed-path Bloom filters in the commit-graph file (if it exists, and they are present). Defaults to
Documentation/git-commit-graph.txt +6 -0
@@ -67,6 +67,12 @@ this option is given, future commit-graph writes will automatically assume that this option was intended. Use `--no-changed-paths` to stop storing this data. + +With the `--max-new-filters=<n>` option, generate at most `n` new Bloom +filters (if `--changed-paths` is specified). If `n` is `-1`, no limit is +enforced. Commits whose filters are not calculated are stored as a +length zero Bloom filter, and their bit is marked in the `BFXL` chunk. +Overrides the `commitGraph.maxNewFilters` configuration. ++ With the `--split[=<strategy>]` option, write the commit-graph as a chain of multiple commit-graph files stored in `<dir>/info/commit-graphs`. Commit-graph layers are merged based on the
bloom.c +9 -4
@@ -197,16 +197,21 @@ 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->data && 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 ;
builtin/commit-graph.c +36 -3
@@ -13,7 +13,8 @@ static char const * const builtin_commit_graph_usage[] = {N_ ("git commit-graph verify [--object-dir <objdir>] [--shallow] [--[no-]progress]" ),N_ ("git commit-graph write [--object-dir <objdir>] [--append] " "[--split[=<strategy>]] [--reachable|--stdin-packs|--stdin-commits] " -"[--changed-paths] [--[no-]progress] <split options>" ), +"[--changed-paths] [--[no-]max-new-filters <n>] [--[no-]progress] " +"<split options>" ), NULL };
@@ -25,7 +26,8 @@ static const char * const builtin_commit_graph_verify_usage[] = {static const char *const builtin_commit_graph_write_usage[] = {N_ ("git commit-graph write [--object-dir <objdir>] [--append] " "[--split[=<strategy>]] [--reachable|--stdin-packs|--stdin-commits] " -"[--changed-paths] [--[no-]progress] <split options>" ), +"[--changed-paths] [--[no-]max-new-filters <n>] [--[no-]progress] " +"<split options>" ),NULL };
@@ -162,6 +164,23 @@ static int read_one_commit(struct oidset *commits, struct progress *progress,return 0 ; } +static int write_option_max_new_filters (const struct option *opt, +const char *arg, +int unset) +{ +int *to = opt->value; +if (unset) + *to =-1 ; +else { +const char *s; + *to =strtol (arg, (char **)&s,10 ); +if (*s) +return error (_ ("%s expects a numerical value" ), +optname (opt, opt->flags)); + } +return 0 ; +} +static int graph_write (int argc,const char **argv) {struct string_list pack_indexes =STRING_LIST_INIT_NODUP ;
@@ -197,6 +216,9 @@ static int graph_write(int argc, const char **argv) N_("maximum ratio between two levels of a split commit-graph")),OPT_EXPIRY_DATE (0 ,"expire-time" , &write_opts.expire_time,N_ ("only expire files older than a given date-time" )), +OPT_CALLBACK_F (0 ,"max-new-filters" , &write_opts.max_new_filters, +NULL ,N_ ("maximum number of changed-path Bloom filters to compute" ), +0 , write_option_max_new_filters), OPT_END(), };
@@ -205,6 +227,7 @@ static int graph_write(int argc, const char **argv) write_opts.size_multiple =2 ; write_opts.max_commits =0 ; write_opts.expire_time =0 ; + write_opts.max_new_filters =-1 ;trace2_cmd_mode ("write" );
@@ -270,6 +293,16 @@ static int graph_write(int argc, const char **argv)return result; } +static int git_commit_graph_config (const char *var,const char *value,void *cb) +{ +if (!strcmp (var,"commitgraph.maxnewfilters" )) { + write_opts.max_new_filters =git_config_int (var, value); +return 0 ; + } + +return git_default_config (var, value, cb); +} +int cmd_commit_graph (int argc,const char **argv,const char *prefix) {static struct option builtin_commit_graph_options[] = {
@@ -283,7 +316,7 @@ int cmd_commit_graph(int argc, const char **argv, const char *prefix)usage_with_options (builtin_commit_graph_usage, builtin_commit_graph_options); -git_config (git_default_config,NULL ); +git_config (git_commit_graph_config, &opts); argc = parse_options(argc, argv, prefix, builtin_commit_graph_options, builtin_commit_graph_usage,
commit-graph.c +23 -4
@@ -953,7 +953,8 @@ struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit }int get_bloom_filter_large_in_graph (struct commit_graph *g, -const struct commit *c) +const struct commit *c, +uint32_t max_changed_paths) {uint32_t graph_pos;if (!find_commit_in_graph (c, g, &graph_pos))
@@ -976,6 +977,17 @@ int get_bloom_filter_large_in_graph(struct commit_graph *g,if (!g->bloom_large)return 0 ; +if (g->bloom_filter_settings->max_changed_paths != max_changed_paths) { +/* +* Force all commits which are subject to a different +* 'max_changed_paths' limit to be recomputed from scratch. +* +* Note that this could likely be improved, but is ignored since +* all real-world graphs set the maximum number of changed paths +* at 512. +*/ +return 0 ; + }return bitmap_get (g->bloom_large, graph_pos - g->num_commits_in_base); }
@@ -1481,6 +1493,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)int i;struct progress *progress =NULL ;int *sorted_commits; +int max_new_filters;init_bloom_filters (); ctx->bloom_large =bitmap_word_alloc (ctx->commits.nr /BITS_IN_EWORD +1 );
@@ -1497,10 +1510,15 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) ctx->order_by_pack ? commit_pos_cmp : commit_gen_cmp, &ctx->commits); + max_new_filters = ctx->opts && ctx->opts->max_new_filters >=0 ? + ctx->opts->max_new_filters : ctx->commits.nr; +for (i =0 ; i < ctx->commits.nr; i++) {int pos = sorted_commits[i];struct commit *c = ctx->commits.list[pos]; -if (get_bloom_filter_large_in_graph (ctx->r->objects->commit_graph, c)) { +if (get_bloom_filter_large_in_graph (ctx->r->objects->commit_graph, + c, + ctx->bloom_settings->max_changed_paths)) {bitmap_set (ctx->bloom_large, pos); ctx->count_bloom_filter_known_large++; }else {
@@ -1508,7 +1526,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)struct bloom_filter *filter =get_or_compute_bloom_filter ( ctx->r, c, -1 , + ctx->count_bloom_filter_computed < max_new_filters, ctx->bloom_settings, &computed);if (computed) {
@@ -1518,7 +1536,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) ctx->count_bloom_filter_found_large++; } } - ctx->total_bloom_filter_data_size +=sizeof (unsigned char ) * filter->len; +if (filter) + ctx->total_bloom_filter_data_size +=sizeof (unsigned char ) * filter->len; }display_progress (progress, i +1 ); }
commit-graph.h +3 -1
@@ -52,7 +52,8 @@ struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit *c);int get_bloom_filter_large_in_graph (struct commit_graph *g, -const struct commit *c); +const struct commit *c, +uint32_t max_changed_paths);struct commit_graph {const unsigned char *data;
@@ -120,6 +121,7 @@ struct commit_graph_opts {int max_commits;timestamp_t expire_time;enum commit_graph_split_flags split_flags; +int max_new_filters; };/*
t/t4216-log-bloom.sh +44 -0
48 lines not on this page · raw message
Signature · 1 line
2.27.0.2918.gc99a27ff8f
Quoted 2 lines · Taylor Blau
Things seem to have settled down since the review in v3, so I'm hoping that this is what will end up being queued.
I haven't paid close attention to this topic, but I took a close look at v4 and found nothing to improve. I'm happy with this version.
Thanks,
-Stolee