bloom: use bloom filter given multiple pathspec
cover bloom: use bloom filter given multiple pathspec
git won't use bloom filter for multiple pathspec, which makes the command
git log -- file1 file2
significantly slower than
git log -- file1 && git log -- file2
This issue is raised by Kai Koponen at
https://lore.kernel.org/git/CADYQcGqaMC=4jgbmnF9Q11oC11jfrqyvH8EuiRRHytpMXd4wYA@mail.gmail.com/
To fix this, revs->bloom_keys[] needs to become an array of bloom_keys[], one for each literal pathspec element. For convenience, first commit creates a new struct bloom_keyvec to hold all bloom keys for a single pathspec. The second commit add for loop to check if any pathspec's keyvec is contained in a commit's bloom filter, along with code that initialize destory and test multiple pathspec bloom keyvecs.
With this change, testing on Kai's example shows that
git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 -- src/clean.bash src/Make.dist
runs as fast as
git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 -- src/Make.dist && \
git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 -- src/clean.bash
Lidong Yan (2):
bloom: replace struct bloom_key * with struct bloom_keyvec
bloom: enable multiple pathspec bloom keys
bloom.c | 47 +++++++++++++++++ bloom.h | 14 +++++ revision.c | 121 ++++++++++++++++++++++++------------------- revision.h | 5 +- t/t4216-log-bloom.sh | 10 ++-- 5 files changed, 137 insertions(+), 60 deletions(-)
Signature · 1 line
2.50.0.108.g6ae0c543ae
PATCH 1/2 bloom: replace struct bloom_key * with struct bloom_keyvec
struct rev_info uses bloom_keys and bloom_nr to store the bloom keys corresponding to a single pathspec. To allow struct rev_info to store the bloom keys for multiple pathspecs, a new data structure bloom_keyvec is introduced. Each struct bloom_keyvec corresponds to a single pathspec. In rev_info, an array bloom_keyvecs is used to store multiple bloom_keyvec instances, along with its length bloom_keyvec_nr.
New bloom_keyvec_* functions are added to initialize, free, and access elements in a keyvec. bloom_filter_contains_vec() is added to check if all key in struct bloom_keyvec is contained in a bloom filter.
--- bloom.c | 47 +++++++++++++++++++++++++++++++++++++++++++++++ bloom.h | 14 ++++++++++++++ revision.c | 31 ++++++++++++++++--------------- revision.h | 5 +++-- 4 files changed, 80 insertions(+), 17 deletions(-)
bloom.c +47 -0
@@ -280,6 +280,36 @@ void deinit_bloom_filters(void)deep_clear_bloom_filter_slab (&bloom_filters, free_one_bloom_filter); } +void bloom_keyvec_init (struct bloom_keyvec *v,size_t initial_size) +{ +ALLOC_ARRAY (v->keys, initial_size); + v->nr = initial_size; +} + +void bloom_keyvec_clear (struct bloom_keyvec *v) +{ +size_t i; +if (!v->keys) +return ; + +for (i =0 ; i < v->nr; i++) +clear_bloom_key (&v->keys[i]); + +FREE_AND_NULL (v->keys); + v->nr =0 ; +} + +struct bloom_key *bloom_keyvec_at (const struct bloom_keyvec *v,size_t i) +{ +assert (i < v->nr); +return &v->keys[i]; +} + +bool bloom_keyvec_empty (const struct bloom_keyvec *v) +{ +return v->nr ==0 || !v->keys; +} + static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, const struct hashmap_entry *eptr, const struct hashmap_entry *entry_or_key,
@@ -540,3 +570,20 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } + +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *keys, +const struct bloom_filter_settings *settings) +{ +const struct bloom_key *key; +int i, ret; + +for (i =0 ; i < keys->nr; i++) { + key = &keys->keys[i]; + ret =bloom_filter_contains (filter, key, settings); +if (ret <=0 ) +return ret; + } + +return 1 ; +}
bloom.h +14 -0
@@ -74,6 +74,11 @@ struct bloom_key {uint32_t *hashes; }; +struct bloom_keyvec { +struct bloom_key *keys; +size_t nr; +}; +int load_bloom_filter_from_graph (struct commit_graph *g,struct bloom_filter *filter,uint32_t graph_pos);
@@ -100,6 +105,11 @@ void add_key_to_filter(const struct bloom_key *key,void init_bloom_filters (void );void deinit_bloom_filters (void ); +void bloom_keyvec_init (struct bloom_keyvec *v,size_t initial_size); +void bloom_keyvec_clear (struct bloom_keyvec *v); +struct bloom_key *bloom_keyvec_at (const struct bloom_keyvec *v,size_t i); +bool bloom_keyvec_empty (const struct bloom_keyvec *v); +enum bloom_filter_computed {BLOOM_NOT_COMPUTED = (1 <<0 ),BLOOM_COMPUTED = (1 <<1 ),
@@ -137,4 +147,8 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *keys, +const struct bloom_filter_settings *settings); +#endif
revision.c +16 -15
@@ -688,6 +688,7 @@ static int forbid_bloom_filters(struct pathspec *spec)static void prepare_to_use_bloom_filter (struct rev_info *revs) {struct pathspec_item *pi; +struct bloom_keyvec *bloom_keyvec;char *path_alloc =NULL ;const char *path, *p;size_t len;
@@ -736,10 +737,12 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) p++; } - revs->bloom_keys_nr = path_component_nr; -ALLOC_ARRAY (revs->bloom_keys, revs->bloom_keys_nr); + revs->bloom_keyvecs_nr =1 ; +CALLOC_ARRAY (revs->bloom_keyvecs,1 ); + bloom_keyvec = &revs->bloom_keyvecs[0 ]; +bloom_keyvec_init (bloom_keyvec, path_component_nr); -fill_bloom_key (path, len, &revs->bloom_keys[0 ], +fill_bloom_key (path, len,bloom_keyvec_at (bloom_keyvec,0 ), revs->bloom_filter_settings); path_component_nr =1 ;
@@ -747,7 +750,8 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)while (p > path) {if (*p =='/' )fill_bloom_key (path, p - path, - &revs->bloom_keys[path_component_nr++], +bloom_keyvec_at (bloom_keyvec, + path_component_nr++), revs->bloom_filter_settings); p--; }
@@ -779,11 +783,8 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,return -1 ; } -for (j =0 ; result && j < revs->bloom_keys_nr; j++) { - result =bloom_filter_contains (filter, - &revs->bloom_keys[j], - revs->bloom_filter_settings); - } + result =bloom_filter_contains_vec (filter, &revs->bloom_keyvecs[0 ], + revs->bloom_filter_settings);if (result) count_bloom_filter_maybe++;
@@ -823,7 +824,7 @@ static int rev_compare_tree(struct rev_info *revs,return REV_TREE_SAME ; } -if (revs->bloom_keys_nr && !nth_parent) { +if (revs->bloom_keyvecs_nr && !nth_parent) { bloom_ret =check_maybe_different_in_bloom_filter (revs, commit);if (bloom_ret ==0 )
@@ -850,7 +851,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,if (!t1)return 0 ; -if (!nth_parent && revs->bloom_keys_nr) { +if (!nth_parent && revs->bloom_keyvecs_nr) { bloom_ret =check_maybe_different_in_bloom_filter (revs, commit);if (!bloom_ret)return 1 ;
@@ -3230,10 +3231,10 @@ void release_revisions(struct rev_info *revs)line_log_free (revs);oidset_clear (&revs->missing_commits); -for (int i =0 ; i < revs->bloom_keys_nr; i++) -clear_bloom_key (&revs->bloom_keys[i]); -FREE_AND_NULL (revs->bloom_keys); - revs->bloom_keys_nr =0 ; +for (int i =0 ; i < revs->bloom_keyvecs_nr; i++) +bloom_keyvec_clear (&revs->bloom_keyvecs[i]); +FREE_AND_NULL (revs->bloom_keyvecs); + revs->bloom_keyvecs_nr =0 ; }static void add_child (struct rev_info *revs,struct commit *parent,struct commit *child)
revision.h +3 -2
@@ -63,6 +63,7 @@ struct rev_info;struct string_list ;struct saved_parents ;struct bloom_key ; +struct bloom_keyvec ;struct bloom_filter_settings ;struct option ;struct parse_opt_ctx_t ;
@@ -360,8 +361,8 @@ struct rev_info {/* Commit graph bloom filter fields */ /* The bloom filter key(s) for the pathspec */ -struct bloom_key *bloom_keys; -int bloom_keys_nr; +struct bloom_keyvec *bloom_keyvecs; +int bloom_keyvecs_nr;/* * The bloom filter settings used to generate the key.
Signature · 1 line
2.50.0.108.g6ae0c543ae
Re: [PATCH 1/2] bloom: replace struct bloom_key * with struct bloom_keyvec
bloom.c void deinit_bloom_filters(void) · line 287
Quoted 5 lines · Lidong Yan
bloom.c +5
-0+void bloom_keyvec_init (struct bloom_keyvec *v,size_t initial_size) +{ +ALLOC_ARRAY (v->keys, initial_size); + v->nr = initial_size; +}
Hmph, does this ever grow once initialized? When I outlined the solution in the earlier discussion, I was wondering a structure that looks more like
struct bloom_keyvec {
size_t count;
struct bloom_key key[FLEX_ARRAY];
};Also when your primary use of an array is to use one element at a time (as opposed to the entire array as a single "collection"), name it singular, so that key[4] is more naturally understood as "4-th key", not keys[4].
bloom.c void deinit_bloom_filters(void) · line 296
Quoted 8 lines
bloom.c +8
-0+void bloom_keyvec_clear (struct bloom_keyvec *v) +{ +size_t i; +if (!v->keys) +return ; + +for (i =0 ; i < v->nr; i++) +clear_bloom_key (&v->keys[i]);
By doing
for (size_t nr; nr < v->nr; nr++)
you can
- lose the separate local variable definition at the beginning;
- avoid confusing "i", which hints to be an "int", to be of type "size_t"
- limit the scope of "nr" a bit tigher.
If you make keyvec an fixed flex-array, the below would become unnecessary (and the check for NULL-ness of .keys[] array).
bloom.c void deinit_bloom_filters(void) · line 303
Quoted 7 lines
bloom.c +6
-0+ +FREE_AND_NULL (v->keys); + v->nr =0 ; +} +struct bloom_key *bloom_keyvec_at (const struct bloom_keyvec *v,size_t i) +{
Ditto about abusing the name 'i'.
bloom.c int bloom_filter_contains(const struct bloom_filter *filter, · line 589
Quoted 6 lines
bloom.c +5
-0+return ret; + } + +return 1 ; +}
Tell your editor to be more careful, perhaps?
Re: [PATCH 1/2] bloom: replace struct bloom_key * with struct bloom_keyvec
Junio C Hamano <[email protected]> writes
Quoted 13 lines
bloom.c void deinit_bloom_filters(void) · line 287
Quoted 5 lines · Lidong Yan
bloom.c +5
-0+void bloom_keyvec_init (struct bloom_keyvec *v,size_t initial_size) +{ +ALLOC_ARRAY (v->keys, initial_size); + v->nr = initial_size; +}Hmph, does this ever grow once initialized? When I outlined the solution in the earlier discussion, I was wondering a structure that looks more like
Quoted 4 lines
struct
bloom_keyvec{size_tcount;
structbloom_keykey[FLEX_ARRAY];
};
I understand. If we don't need to resize the array dynamically, we should allocate the array elements and the array length together to gain benefits such as spatial locality.
Quoted 4 lines
Also when your primary use of an array is to use one element at a time (as opposed to the entire array as a single "collection"), name it singular, so that key[4] is more naturally understood as "4-th key", not keys[4].
Got it.
Quoted 12 lines
bloom.c void deinit_bloom_filters(void) · line 296
Quoted 9 lines
bloom.c +8
-0+void bloom_keyvec_clear (struct bloom_keyvec *v) +{ +size_t i; +if (!v->keys) +return ; + +for (i =0 ; i < v->nr; i++) +clear_bloom_key (&v->keys[i]);By doing
Quoted 7 lines
for (
size_tnr; nr <v->nr; nr++)you can
- lose the separate local variable definition at the beginning;
- avoid confusing "i", which hints to be an "int", to be of type "size_t"
- limit the scope of "nr" a bit tigher.
Got it.
Quoted 8 lines
If you make keyvec an fixed flex-array, the below would become unnecessary (and the check for NULL-ness of .keys[] array).
bloom.c void deinit_bloom_filters(void) · line 300
Quoted 4 lines
bloom.c +4
-0+ +FREE_AND_NULL (v->keys); + v->nr =0 ; +}
Another benefit to use flex-array.
Quoted 6 lines
Review
Quoted 3 lines
(quoted diff) +2
-0+struct bloom_key *bloom_keyvec_at(const struct bloom_keyvec *v, size_t i) +{Ditto about abusing the name 'i'.
Quoted 8 lines
bloom.c int bloom_filter_contains(const struct bloom_filter *filter, · line 589
Quoted 6 lines
+ return ret;
+ }bloom.c +3
-0+ +return 1 ; +}Tell your editor to be more careful, perhaps?
Seems git clang-format doesn’t add newline for me, I will try .editconfig next time.
Thanks,
Lidong
PATCH 2/2 bloom: enable multiple pathspec bloom keys
In reply to Lidong YanRemove if (spec->nr > 1) to enable bloom filter given multiple pathspec. Wrapped for loop around code in prepare_to_use_bloom_filter() to initialize each pathspec's struct bloom_keyvec. Add for loop in check_maybe_different_in_bloom_filter() to find if at least one pathspec's bloom_keyvec is contained in bloom filter.
Add new function release_revisions_bloom_keyvecs() to free all bloom keyvec owned by rev_info.
Modify t/t4216 to test if bloom filter is still used given multiple pathspec.
--- revision.c | 122 ++++++++++++++++++++++++------------------- t/t4216-log-bloom.sh | 10 ++-- 2 files changed, 73 insertions(+), 59 deletions(-)
revision.c +68 -54
@@ -675,8 +675,6 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ;if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL ))
@@ -685,6 +683,8 @@ static int forbid_bloom_filters(struct pathspec *spec)return 0 ; } +static void release_revisions_bloom_keyvecs (struct rev_info *revs); +static void prepare_to_use_bloom_filter (struct rev_info *revs) {struct pathspec_item *pi;
@@ -692,7 +692,7 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)char *path_alloc =NULL ;const char *path, *p;size_t len; -int path_component_nr =1 ; +int path_component_nr;if (!revs->commits)return ;
@@ -709,51 +709,53 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - pi = &revs->pruning.pathspec.items[0 ]; - -/* remove single trailing slash from path, if needed */ -if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { - path_alloc =xmemdupz (pi->match, pi->len -1 ); - path = path_alloc; - }else - path = pi->match; - - len =strlen (path); -if (!len) { - revs->bloom_filter_settings =NULL ; -free (path_alloc); -return ; - } - - p = path; -while (*p) { -/* -* At this point, the path is normalized to use Unix-style -* path separators. This is required due to how the -* changed-path Bloom filters store the paths. -*/ -if (*p =='/' ) - path_component_nr++; - p++; - } - - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - bloom_keyvec = &revs->bloom_keyvecs[0 ]; -bloom_keyvec_init (bloom_keyvec, path_component_nr); + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { + pi = &revs->pruning.pathspec.items[i]; + path_component_nr =1 ; + +/* remove single trailing slash from path, if needed */ +if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { + path_alloc =xmemdupz (pi->match, pi->len -1 ); + path = path_alloc; + }else + path = pi->match; + + len =strlen (path); +if (!len) + goto fail; + + p = path; +while (*p) { +/* +* At this point, the path is normalized to use +* Unix-style path separators. This is required due to +* how the changed-path Bloom filters store the paths. +*/ +if (*p =='/' ) + path_component_nr++; + p++; + } -fill_bloom_key (path, len,bloom_keyvec_at (bloom_keyvec,0 ), - revs->bloom_filter_settings); - path_component_nr =1 ; + bloom_keyvec = &revs->bloom_keyvecs[i]; +bloom_keyvec_init (bloom_keyvec, path_component_nr); + +fill_bloom_key (path, len,bloom_keyvec_at (bloom_keyvec,0 ), + revs->bloom_filter_settings); + path_component_nr =1 ; + + p = path + len -1 ; +while (p > path) { +if (*p =='/' ) +fill_bloom_key (path, p - path, +bloom_keyvec_at (bloom_keyvec, + path_component_nr++), + revs->bloom_filter_settings); + p--; + } - p = path + len -1 ; -while (p > path) { -if (*p =='/' ) -fill_bloom_key (path, p - path, -bloom_keyvec_at (bloom_keyvec, - path_component_nr++), - revs->bloom_filter_settings); - p--; +FREE_AND_NULL (path_alloc); }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {
@@ -761,14 +763,19 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) bloom_filter_atexit_registered =1 ; } +return ; + +fail: + revs->bloom_filter_settings =NULL ;free (path_alloc); +release_revisions_bloom_keyvecs (revs); }static int check_maybe_different_in_bloom_filter (struct rev_info *revs,struct commit *commit) {struct bloom_filter *filter; -int result =1 , j; +int result =0 ;if (!revs->repo->objects->commit_graph)return -1 ;
@@ -783,8 +790,11 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,return -1 ; } - result =bloom_filter_contains_vec (filter, &revs->bloom_keyvecs[0 ], - revs->bloom_filter_settings); +for (int i =0 ; !result && i < revs->bloom_keyvecs_nr; i++) { + result =bloom_filter_contains_vec (filter, + &revs->bloom_keyvecs[i], + revs->bloom_filter_settings); + }if (result) count_bloom_filter_maybe++;
@@ -3202,6 +3212,14 @@ static void release_revisions_mailmap(struct string_list *mailmap)static void release_revisions_topo_walk_info (struct topo_walk_info *info); +static void release_revisions_bloom_keyvecs (struct rev_info *revs) +{ +for (int i =0 ; i < revs->bloom_keyvecs_nr; i++) +bloom_keyvec_clear (&revs->bloom_keyvecs[i]); +FREE_AND_NULL (revs->bloom_keyvecs); + revs->bloom_keyvecs_nr =0 ; +} +static void free_void_commit_list (void *list) {free_commit_list (list);
@@ -3230,11 +3248,7 @@ void release_revisions(struct rev_info *revs)clear_decoration (&revs->treesame, free);line_log_free (revs);oidset_clear (&revs->missing_commits); - -for (int i =0 ; i < revs->bloom_keyvecs_nr; i++) -bloom_keyvec_clear (&revs->bloom_keyvecs[i]); -FREE_AND_NULL (revs->bloom_keyvecs); - revs->bloom_keyvecs_nr =0 ; +release_revisions_bloom_keyvecs (revs); }static void add_child (struct rev_info *revs,struct commit *parent,struct commit *child)
t/t4216-log-bloom.sh +5 -5
@@ -138,8 +138,8 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' ' test_bloom_filters_not_used "--walk-reflogs -- A" ' -test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" +test_expect_success 'git log -- multiple path specs use Bloom filters' ' + test_bloom_filters_used "-- file4 A/file1" ' test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' '
@@ -151,9 +151,9 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used "-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with wildcard that resolves to a multiple paths uses Bloom filters' ' + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.50.0.108.g6ae0c543ae
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
Quoted 5 lines · Lidong Yan
Remove
if (spec->nr > 1)to enable bloom filter given multiple pathspec. Wrapped for loop around code inprepare_to_use_bloom_filter()to initialize each pathspec's structbloom_keyvec. Add for loop incheck_maybe_different_in_bloom_filter()to find if at least one pathspec'sbloom_keyvecis contained in bloom filter.
Oy. That's too dense enumeration but I suspect are all "what the patch does" that can be read from the diff. The first sentence gives "why", which is excellent.
You'd need to check in forbid_bloom_filters() that none of the pathspec items have magic (other than literal), not just the first one, no?
Totally outside the topic, but I wonder if we can further optimize by adding an early rejection using .nowildcard_len? Instead of allowing a wildcarded "dir/*" pathspec element from disabling the Bloom filter altogether, we could say "dir/ is not possibly altered, so there may be dir/A, dir/B, etc., in the directory, nothing that would match dir/* wildcard would have been modified", couldn't we?
revision.c static int forbid_bloom_filters(struct pathspec *spec) · line 680
Quoted 13 lines
revision.c +0
-2@@ -675,8 +675,6 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ;if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL ))
This last check only looks at the first item. It used to be OK because we didn't look at a pathspec with more than one element, but now shouldn't we care?
Thanks.
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
Quoted 11 lines · Junio C Hamano
Quoted 5 lines · Lidong Yan
Remove
if (spec->nr > 1)to enable bloom filter given multiple pathspec. Wrapped for loop around code inprepare_to_use_bloom_filter()to initialize each pathspec's structbloom_keyvec. Add for loop incheck_maybe_different_in_bloom_filter()to find if at least one pathspec'sbloom_keyvecis contained in bloom filter.Oy. That's too dense enumeration but I suspect are all "what the patch does" that can be read from the diff. The first sentence gives "why", which is excellent.
Got it. I will simply this log message in next version.
Quoted 3 lines
You'd need to check in
forbid_bloom_filters()that none of the pathspec items have magic (other than literal), not just the first one, no?
Yeah, I never notice that. I would add checks in forbid_bloom_filters(). And add test to ensure we don’t use bloom filter if any pathspec item is not literal.
Quoted 7 lines
Totally outside the topic, but I wonder if we can further optimize by adding an early rejection using .nowildcard_len? Instead of allowing a wildcarded "dir/*" pathspec element from disabling the Bloom filter altogether, we could say "dir/ is not possibly altered, so there may be dir/A, dir/B, etc., in the directory, nothing that would match dir/* wildcard would have been modified", couldn't we?
I think it's feasible. In that case, we would need to add a condition .nowildcard_len > 0 to forbid_bloom_filter. I'm happy to write a new patch to address this issue.
Quoted 9 lines
Quoted 9 lines
revision.c +0
-1@@ -675,8 +675,6 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 )
Quoted 8 lines
revision.c static int forbid_bloom_filters(struct pathspec *spec) · line 680
Quoted 4 lines
revision.c +0
-1-return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ;if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL ))This last check only looks at the first item. It used to be OK because we didn't look at a pathspec with more than one element, but now shouldn't we care?
Definitely, I would fix that in 3rd version.
Thanks,
Lidong
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
Quoted 7 lines · Lidong Yan
Quoted 3 lines
You'd need to check in
forbid_bloom_filters()that none of the pathspec items have magic (other than literal), not just the first one, no?Yeah, I never notice that. I would add checks in
forbid_bloom_filters(). And add test to ensure we don’t use bloom filter if any pathspec item is not literal.
Sounds great. I was wondering why your tests did not catch it.
Quoted 10 lines
Quoted 6 lines
Totally outside the topic, but I wonder if we can further optimize by adding an early rejection using .nowildcard_len? Instead of allowing a wildcarded "dir/*" pathspec element from disabling the Bloom filter altogether, we could say "dir/ is not possibly altered, so there may be dir/A, dir/B, etc., in the directory, nothing that would match dir/* wildcard would have been modified", couldn't we?
I think it's feasible. In that case, we would need to add a condition .nowildcard_len > 0 to
forbid_bloom_filter. I'm happy to write a new patch to address this issue.
Let's leave it outside the topic and concentrate on the problem at hand first.
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
In reply to Junio C HamanoQuoted 6 lines · Junio C Hamano
Totally outside the topic, but I wonder if we can further optimize by adding an early rejection using .nowildcard_len? Instead of allowing a wildcarded "dir/*" pathspec element from disabling the Bloom filter altogether, we could say "dir/ is not possibly altered, so there may be dir/A, dir/B, etc., in the directory, nothing that would match dir/* wildcard would have been modified", couldn't we?
I think, except for PATHSPEC_EXCLUDE, all other pathspec magic flags could potentially be optimized using .nowildcard_len by restricting checks to just the dir/ part of each pathspec item.
Here;s are all possible pathspec magic
#define PATHSPEC_FROMTOP (1<<0)
#define PATHSPEC_MAXDEPTH (1<<1)
#define PATHSPEC_LITERAL (1<<2)
#define PATHSPEC_GLOB (1<<3)
#define PATHSPEC_ICASE (1<<4)
#define PATHSPEC_EXCLUDE (1<<5)
#define PATHSPEC_ATTR (1<<6)
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
Quoted 11 lines · Lidong Yan
Quoted 6 lines · Junio C Hamano
Totally outside the topic, but I wonder if we can further optimize by adding an early rejection using .nowildcard_len? Instead of allowing a wildcarded "dir/*" pathspec element from disabling the Bloom filter altogether, we could say "dir/ is not possibly altered, so there may be dir/A, dir/B, etc., in the directory, nothing that would match dir/* wildcard would have been modified", couldn't we?
I think, except for
PATHSPEC_EXCLUDE, all other pathspec magic flags could potentially be optimized using .nowildcard_len by restricting checks to just the dir/ part of each pathspec item.
A good observation.
I do not know about icase; though. Asking about "Dir/Path" and getting "Dir/ or Dir/Path cannot possibly be in the set of paths that were modified" from the changed-path Bloom filter would not help us optimize the tree comparison out, when we do not want to miss modifications for "dir/path".
Quoted 8 lines
Here;s are all possible pathspec magic
#definePATHSPEC_FROMTOP(1<<0)
#definePATHSPEC_MAXDEPTH(1<<1)
#definePATHSPEC_LITERAL(1<<2)
#definePATHSPEC_GLOB(1<<3)
#definePATHSPEC_ICASE(1<<4)
#definePATHSPEC_EXCLUDE(1<<5)
#definePATHSPEC_ATTR(1<<6)
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
Quoted 6 lines · Junio C Hamano
I do not know about icase; though. Asking about "Dir/Path" and getting "Dir/ or Dir/Path cannot possibly be in the set of paths that were modified" from the changed-path Bloom filter would not help us optimize the tree comparison out, when we do not want to miss modifications for "dir/path".
Make sense, both PATHSPEC_EXCLUDE and PATHSPEC_ICASE shouldn’t be optimized by bloom filter.
I found that my [PATCH v3 2/2] contains two unaligned parameters. Should I reroll this patch and introduce the nowildcard_len change in a separate commit?
Quoted 9 lines
Quoted 9 lines
Here;s are all possible pathspec magic
#definePATHSPEC_FROMTOP(1<<0)
#definePATHSPEC_MAXDEPTH(1<<1)
#definePATHSPEC_LITERAL(1<<2)
#definePATHSPEC_GLOB(1<<3)
#definePATHSPEC_ICASE(1<<4)
#definePATHSPEC_EXCLUDE(1<<5)
#definePATHSPEC_ATTR(1<<6)
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
Quoted 10 lines · Lidong Yan
Quoted 6 lines · Junio C Hamano
I do not know about icase; though. Asking about "Dir/Path" and getting "Dir/ or Dir/Path cannot possibly be in the set of paths that were modified" from the changed-path Bloom filter would not help us optimize the tree comparison out, when we do not want to miss modifications for "dir/path".
Make sense, both
PATHSPEC_EXCLUDEandPATHSPEC_ICASEshouldn’t be optimized by bloom filter.
Before concluding so, we may want to double check how Bloom filters are built on case insensitive systems, though. If we normalize the string by downcasing before murmuring the string, the resulting Bloom filter may have more false positives for those who want to (ab)use it to optimize case sensitive queries (without affecting correctness), but case insensitive queries would be helped. I do not think we support (or want to support) a repository that spans across two filesystems with different case sensitivity, so those who worked on our changed-path Bloom filter subsystem may have already placed such an optimization, based on the case sensitivity recorded in the repository (core.ignorecase).
Quoted 2 lines
I found that my [PATCH v3 2/2] contains two unaligned parameters. Should I reroll this patch and introduce the
nowildcard_lenchange in a separate commit?
Updating a patch with a fix to obvious known problems is good.
Extending the scope of the series should be left out for a new separate commit. It may even be a better idea to hold it while the current set of patches are still being polished, and then sent out as a new series after the dust settles (even if you internally developed that part as a direct extension to the current effort).
Thanks.
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
Quoted 12 lines · Junio C Hamano
Before concluding so, we may want to double check how Bloom filters are built on case insensitive systems, though. If we normalize the string by downcasing before murmuring the string, the resulting Bloom filter may have more false positives for those who want to (ab)use it to optimize case sensitive queries (without affecting correctness), but case insensitive queries would be helped. I do not think we support (or want to support) a repository that spans across two filesystems with different case sensitivity, so those who worked on our changed-path Bloom filter subsystem may have already placed such an optimization, based on the case sensitivity recorded in the repository (core.ignorecase).
I understand. I should check whether commit graph file's change path bloom filter is case sensitive. If the change path bloom filter is case insensitive, we could optimize PATHSPEC_ICASE as well.
Quoted 8 lines
Updating a patch with a fix to obvious known problems is good.
Extending the scope of the series should be left out for a new separate commit. It may even be a better idea to hold it while the current set of patches are still being polished, and then sent out as a new series after the dust settles (even if you internally developed that part as a direct extension to the current effort).
Got it. So for now I should just polish this current patch.
Thanks,
Lidong
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
In reply to Junio C HamanoQuoted 12 lines · Junio C Hamano
Before concluding so, we may want to double check how Bloom filters are built on case insensitive systems, though. If we normalize the string by downcasing before murmuring the string, the resulting Bloom filter may have more false positives for those who want to (ab)use it to optimize case sensitive queries (without affecting correctness), but case insensitive queries would be helped. I do not think we support (or want to support) a repository that spans across two filesystems with different case sensitivity, so those who worked on our changed-path Bloom filter subsystem may have already placed such an optimization, based on the case sensitivity recorded in the repository (core.ignorecase).
In bloom.c:get_or_compute_bloom_filter(), the computation of a bloom filter looks like:
diff_tree_oid(c’s parent or NULL, &c->object.oid, "", &diffopt);
diffcore_std(&diffopt);
struct hashmap path_hashmap;
for (path : diff_queue_diff) {
Add all parts of path to path_hashmap;
}
for_each(path_hashmap) {
Add path to filter
}All these steps do not check config.ignoreCase, so I believe the Bloom filter we build in the commit graph is case-sensitive.
To demonstrate this assumption—and since I happen to be a Mac user (where config.ignoreCase is true by default)—I ran the following commands under the llvm-project repository:
$ git commit-graph write --split --reachable --changed-paths $ time git log -5 -t -- README.md > /dev/null real 0m0.089s user 0m0.067s sys 0m0.021s $ time git log -5 -t -- ':(icase)README.md' > /dev/null real 0m0.281s user 0m0.239s sys 0m0.041s $ time git log -5 -t -- ‘rEADME.md’ > /dev/null real 0m0.458s user 0m0.394s sys 0m0.061s
And I think it proves that changed-path Bloom filter doesn’t optimize icase pathspec item in case insensitive file system.
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
In reply to Junio C HamanoQuoted 6 lines · Junio C Hamano
Totally outside the topic, but I wonder if we can further optimize by adding an early rejection using .nowildcard_len? Instead of allowing a wildcarded "dir/*" pathspec element from disabling the Bloom filter altogether, we could say "dir/ is not possibly altered, so there may be dir/A, dir/B, etc., in the directory, nothing that would match dir/* wildcard would have been modified", couldn't we?
Indeed, that's what I demonstrated back in:
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
Quoted 9 lines · SZEDER Gábor
Quoted 6 lines · Junio C Hamano
Totally outside the topic, but I wonder if we can further optimize by adding an early rejection using .nowildcard_len? Instead of allowing a wildcarded "dir/*" pathspec element from disabling the Bloom filter altogether, we could say "dir/ is not possibly altered, so there may be dir/A, dir/B, etc., in the directory, nothing that would match dir/* wildcard would have been modified", couldn't we?
Quoted 3 lines
Indeed, that's what I demonstrated back in:
That's interesting. Though I find the bloom part of code changed and I can't reuse your patch.
Have you ever considered to optimize other kind of pathspec magic? I am
not perfectly sure whether it is feasible to use the same trick (using bloom filter on dir/ path) on patchspec magic except PATHSPEC_EXCLUDE.
Thanks,
Lidong
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
In reply to SZEDER GáborQuoted 11 lines · SZEDER Gábor
Quoted 6 lines · Junio C Hamano
Totally outside the topic, but I wonder if we can further optimize by adding an early rejection using .nowildcard_len? Instead of allowing a wildcarded "dir/*" pathspec element from disabling the Bloom filter altogether, we could say "dir/ is not possibly altered, so there may be dir/A, dir/B, etc., in the directory, nothing that would match dir/* wildcard would have been modified", couldn't we?
Indeed, that's what I demonstrated back in:
Heh, I am always impressed that some people seem to have infinitely long scrollback buffer ;-) It is curious why nobody else noticed and advocated for your patch back then.
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
In reply to Lidong YanLidong Yan <[email protected]> writes:
This is a tangent, but I have to say that whoever wrote the original test does not understand shells very well. When you have files A and B in your working tree, to your $command, the following two does not make any difference:
$command ?
$command A B
In fact it cannot even tell which form was used when composing the command line. So this original test ...
t/t4216-log-bloom.sh test_expect_success 'git log with wildcard that resolves to a single path uses B · line 156
Quoted 3 lines
t/t4216-log-bloom.sh +0
-3-test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*"
... is misleading to say the least.
t/t4216-log-bloom.sh test_expect_success 'git log with wildcard that resolves to a single path uses B · line 157
Quoted 4 lines
t/t4216-log-bloom.sh +3
-0+test_expect_success 'git log with wildcard that resolves to a multiple paths uses Bloom filters' ' + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" '
I think you should just retitle this to say
git log with multiple literal paths use Bloom filter
or something.
Also the setup helper test_bloom_filters_{not_,}used helpers call is written in a way to make it impossible to pass a real wildcard and see how "$git log" would behave, because it does this:
git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom &&
It probably should use 'eval' so that the caller can pass a quoted wildcard, perhaps like
eval git -c core.commitgraph=false \ log --pretty=format:%s "$1" >log_wo_bloom &&
Then a test we can add to see how wildcards prevent Bloom from kicking in would look like
test_bloom_filters_used "-- file*" && test_bloom_filters_not_used "-- file4 file\*" &&
The former lets the shell expand file* when the above "eval" evaluates its (concatenated) strings, while the latter leaves the backslash before the asterisk in the strings fed to "eval", so the "log" will see a pathspec with wildcard.
If we were to fix that setup() thing, we of course need to be a bit careful about existing tests.
Thanks.
Re: [PATCH 2/2] bloom: enable multiple pathspec bloom keys
Quoted 5 lines · Junio C Hamano
Also the setup helper test_bloom_filters_{not_,}used helpers call is written in a way to make it impossible to pass a real wildcard and see how "$git log" would behave, because it does this:
git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom &&
Yeah, if $1 contains * and because $1 is not quotes, * would trigger file name expansion.
Quoted 9 lines
It probably should use 'eval' so that the caller can pass a quoted wildcard, perhaps like
eval git -c core.commitgraph=false \ log --pretty=format:%s "$1" >log_wo_bloom &&Then a test we can add to see how wildcards prevent Bloom from kicking in would look like
Quoted 7 lines
test_bloom_filters_used"-- file*" &&test_bloom_filters_not_used"-- file4 file\*" &&The former lets the shell expand file* when the above "eval" evaluates its (concatenated) strings, while the latter leaves the backslash before the asterisk in the strings fed to "eval", so the "log" will see a pathspec with wildcard.
Wow, this solution is very clever.
Quoted 2 lines
If we were to fix that
setup()thing, we of course need to be a bit careful about existing tests.
Though the uses of test_bloom_filters_(not_)used are not too much, I think replace
git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom &&
with
git -c core.commitGraph=false log --pretty="format:%s” “$*" >log_wo_bloom &&
is not better than add the “eval …” solution, I will just use eval
Thanks,
Lidong
Quoted 1 line · Lidong Yan
git won't use bloom filter for multiple pathspec, which makes the command
Let's get the terminology straight. A pathspec consists of one or more pathspec elements (or pathspec items).
Also, "git won't" is overly general. The series title shares the same issue ("given multiple pathspec" does not even hint that this is about revision traversal---you are not making filter used with pathspec with more than one element in other code paths).
Perhaps like:
The revision traversal limited by pathspec has optimization when the pathspec has only one element, it does not use any pathspec magic (other than literal), and there is no wildcard.
While it is much harder to lift the latter two limitations, supporting a pathspec with multiple elements is relatively easy. Just make sure we hash each of them separately and ask the bloom filter about them, and if we see none of them can possibly be affected by the commit, we can skip without tree comparison.
or something along that line?
Quoted 7 lines
git log -- file1 file2
significantly slower than
git log -- file1 && git log -- file2This issue is raised by Kai Koponen at
https://lore.kernel.org/git/CADYQcGqaMC=4jgbmnF9Q11oC11jfrqyvH8EuiRRHytpMXd4wYA@mail.gmail.com/
Quoted 6 lines
To fix this, revs->bloom_keys[] needs to become an array of bloom_keys[], one for each literal pathspec element. For convenience, first commit creates a new struct
bloom_keyvecto hold all bloom keys for a single pathspec. The second commit add for loop to check if any pathspec's keyvec is contained in a commit's bloom filter, along with code that initialize destory and test multiple pathspec bloom keyvecs.
It is nice to outline an approach to the solution one day, and see an almost exact implementation of it appear on the list a few days later. I wish all the development would go like this ;-)
Quoted 5 lines
bloom.c | 47 +++++++++++++++++ bloom.h | 14 +++++ revision.c | 121 ++++++++++++++++++++++++------------------- revision.h | 5 +- t/t4216-log-bloom.sh | 10 ++--
Can we have a set of real tests to make sure that the updated filter code still identifies commits that touch the files without false negatives? False positives are OK as we will follow them with real tree comparison to determine what exactly got changed, but false negatives are absolute no-no.
Testing to see that the filter code path is activated is much less interesting than the filter code path still functions correctly with these changes presented here. I have a feeling that with the changes to the test in this series, you wouldn't even find a bug where you simply added subpaths for all pathspec elements into a single array and use the original "bloom has to say 'possibly yes' to all array elements" logic (which would incorrectly require that both file1 and file2 must be modified).
Thanks.
Quoted 7 lines · Junio C Hamano
Quoted 1 line · Lidong Yan
git won't use bloom filter for multiple pathspec, which makes the command
Let's get the terminology straight. A pathspec consists of one or more pathspec elements (or pathspec items).
Thanks for the clarification. I will be more precise with the terminology in v2.
Quoted 11 lines
Also, "git won't" is overly general. The series title shares the same issue ("given multiple pathspec" does not even hint that this is about revision traversal---you are not making filter used with pathspec with more than one element in other code paths).
Perhaps like:
The revision traversal limited by pathspec has optimization when the pathspec has only one element, it does not use any pathspec magic (other than literal), and there is no wildcard.
Quoted 8 lines
While it is much harder to lift the latter two limitations, supporting a pathspec with multiple elements is relatively easy. Just make sure we hash each of them separately and ask the bloom filter about them, and if we see none of them can possibly be affected by the commit, we can skip without tree comparison.
or something along that line?
What you wrote makes perfect sense to me, I’ll just copy and paste
those paragraphs into my cover letter. And the title would be
"bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal"
Quoted 6 lines
Can we have a set of real tests to make sure that the updated filter code still identifies commits that touch the files without false negatives? False positives are OK as we will follow them with real tree comparison to determine what exactly got changed, but false negatives are absolute no-no.
Quoted 8 lines
Testing to see that the filter code path is activated is much less interesting than the filter code path still functions correctly with these changes presented here. I have a feeling that with the changes to the test in this series, you wouldn't even find a bug where you simply added subpaths for all pathspec elements into a single array and use the original "bloom has to say 'possibly yes' to all array elements" logic (which would incorrectly require that both file1 and file2 must be modified).
I assume that t4216/test_bloom_filters_used has already verified that using bloom filters with multiple pathspec elements produces the same results as when bloom filters are not used. But I would love to add more test cases to check no false negative happened.
Thanks,
Lidong
Quoted 4 lines · Lidong Yan
I assume that t4216/test_bloom_filters_used has already verified that using bloom filters with multiple pathspec elements produces the same results as when bloom filters are not used. But I would love to add more test cases to check no false negative happened.
If we are sure we have enough test coverage, then it is great. If not, it is superb if you can add some test coverage there.
Thanks.
v2 cover bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
In reply to Lidong YanThe revision traversal limited by pathspec has optimization when the pathspec has only one element, it does not use any pathspec magic (other than literal), and there is no wildcard. The absence of optimization for multiple pathspec elements in revision traversal cause an issue raised by Kai Koponen at
https://lore.kernel.org/git/CADYQcGqaMC=4jgbmnF9Q11oC11jfrqyvH8EuiRRHytpMXd4wYA@mail.gmail.com/
While it is much harder to lift the latter two limitations, supporting a pathspec with multiple elements is relatively easy. Just make sure we hash each of them separately and ask the bloom filter about them, and if we see none of them can possibly be affected by the commit, we can skip without tree comparison.
First commit creates a new data structure struct bloom_keyvec to hold all bloom keys for a single pathspec item. Second commit add for loop to check if any pathspec item's keyvec is contained in a commit's bloom filter.
With this change, testing on Kai's example shows that
git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 -- src/clean.bash src/Make.dist
runs as fast as
git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 -- src/Make.dist && \
git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 -- src/clean.bash
Lidong Yan (2):
bloom: replace struct bloom_key * with struct bloom_keyvec
bloom: optimize multiple pathspec items in revision traversal
bloom.c | 31 +++++++++++ bloom.h | 20 +++++++ revision.c | 121 ++++++++++++++++++++++++------------------- revision.h | 6 +-- t/t4216-log-bloom.sh | 10 ++-- 5 files changed, 127 insertions(+), 61 deletions(-)
Signature · 1 line
2.50.0.108.g6ae0c543ae
v3 cover bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
This series enables bloom filter optimization for multiple pathspec elements. Compared to v2, v3 fixed bugs in forbid_bloom_filter() and add one more test case in t/t4216-log-bloom.sh.
Lidong Yan (2):
bloom: replace struct bloom_key * with struct bloom_keyvec
bloom: optimize multiple pathspec items in revision traversal
bloom.c | 31 +++++++++++ bloom.h | 20 +++++++ revision.c | 126 ++++++++++++++++++++++++------------------- revision.h | 6 +-- t/t4216-log-bloom.sh | 23 ++++---- 5 files changed, 139 insertions(+), 67 deletions(-)
Signature · 1 line
2.50.0.108.g6ae0c543ae
v4 cover bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
This series enables bloom filter optimization for multiple pathspec elements. Compared to v3, v4 rename *_bloom_key and *_bloom_keyvec methods to bloom_key_* and bloom_keyvec_*, respectively, to follow the git code guidelines. Also, it adds a new test helper to return murmur3 hash.
Lidong Yan (4):
bloom: add test helper to return murmur3 hash
bloom: rename function operates on bloom_key
bloom: replace struct bloom_key * with struct bloom_keyvec
bloom: optimize multiple pathspec items in revision traversal
blame.c | 2 +- bloom.c | 52 +++++++++++++++-- bloom.h | 41 +++++++++---- line-log.c | 4 +- revision.c | 131 +++++++++++++++++++++++------------------- revision.h | 6 +- t/helper/test-bloom.c | 8 +-- t/t4216-log-bloom.sh | 23 +++++--- 8 files changed, 174 insertions(+), 93 deletions(-)
Signature · 1 line
2.50.0.107.g33b6ec8c79
PATCH v4 1/4 bloom: add test helper to return murmur3 hash
In bloom.h, murmur3_seeded_v2() is exported for the use of test murmur3 hash. To clarify that murmur3_seeded_v2() is exported solely for testing purposes, a new helper function test_murmur3_seeded() was added instead of exporting murmur3_seeded_v2() directly.
--- bloom.c | 13 ++++++++++++- bloom.h | 12 +++--------- t/helper/test-bloom.c | 4 ++-- 3 files changed, 17 insertions(+), 12 deletions(-)
bloom.c +12 -1
@@ -107,7 +107,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,* Not considered to be cryptographically secure. * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm */ -uint32_t murmur3_seeded_v2 (uint32_t seed,const char *data,size_t len) +static uint32_t murmur3_seeded_v2 (uint32_t seed,const char *data,size_t len) {const uint32_t c1 =0xcc9e2d51 ;const uint32_t c2 =0x1b873593 ;
@@ -540,3 +540,14 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } + +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len, +int version) +{ +assert (version ==1 || version ==2 ); + +if (version ==2 ) +return murmur3_seeded_v2 (seed, data, len); +else +return murmur3_seeded_v1 (seed, data, len); +}
bloom.h +3 -9
@@ -78,15 +78,6 @@ int load_bloom_filter_from_graph(struct commit_graph *g,struct bloom_filter *filter, uint32_t graph_pos); -/* -* Calculate the murmur3 32-bit hash value for the given data -* using the given seed. -* Produces a uniformly distributed hash value. -* Not considered to be cryptographically secure. -* Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm -*/ -uint32_t murmur3_seeded_v2 (uint32_t seed,const char *data,size_t len); - void fill_bloom_key(const char *data, size_t len, struct bloom_key *key,
@@ -137,4 +128,7 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len, +int version); +#endif
t/helper/test-bloom.c +2 -2
@@ -61,13 +61,13 @@ int cmd__bloom(int argc, const char **argv)uint32_t hashed;if (argc <3 )usage (bloom_usage); - hashed =murmur3_seeded_v2 (0 , argv[2 ],strlen (argv[2 ])); + hashed =test_bloom_murmur3_seeded (0 , argv[2 ],strlen (argv[2 ]),2 );printf ("Murmur3 Hash with seed=0:0x%08x\n" , hashed); }if (!strcmp (argv[1 ],"get_murmur3_seven_highbit" )) {uint32_t hashed; - hashed =murmur3_seeded_v2 (0 ,"\x99\xaa\xbb\xcc\xdd\xee\xff" ,7 ); + hashed =test_bloom_murmur3_seeded (0 ,"\x99\xaa\xbb\xcc\xdd\xee\xff" ,7 ,2 );printf ("Murmur3 Hash with seed=0:0x%08x\n" , hashed); }
Signature · 1 line
2.50.0.107.g33b6ec8c79
PATCH v4 2/4 bloom: rename function operates on bloom_key
In reply to Lidong Yangit code style requires that functions operating on a struct S should be named in the form S_verb. However, the functions operating on struct bloom_key do not follow this convention. Therefore, fill_bloom_key() and clear_bloom_key() are renamed to bloom_key_fill() and bloom_key_clear(), respectively.
--- blame.c | 2 +- bloom.c | 8 ++++---- bloom.h | 4 ++-- line-log.c | 4 ++-- revision.c | 6 +++--- t/helper/test-bloom.c | 4 ++-- 6 files changed, 14 insertions(+), 14 deletions(-)
blame.c +1 -1
@@ -1310,7 +1310,7 @@ static void add_bloom_key(struct blame_bloom_data *bd, } bd->keys[bd->nr] =xmalloc (sizeof (struct bloom_key )); -fill_bloom_key (path,strlen (path), bd->keys[bd->nr], bd->settings); +bloom_key_fill (path,strlen (path), bd->keys[bd->nr], bd->settings); bd->nr++; }
bloom.c +4 -4
@@ -221,7 +221,7 @@ static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len)return seed; } -void fill_bloom_key (const char *data, +void bloom_key_fill (const char *data,size_t len,struct bloom_key *key,const struct bloom_filter_settings *settings)
@@ -243,7 +243,7 @@ void fill_bloom_key(const char *data, key->hashes[i] = hash0 + i * hash1; } -void clear_bloom_key (struct bloom_key *key) +void bloom_key_clear (struct bloom_key *key) {FREE_AND_NULL (key->hashes); }
@@ -500,9 +500,9 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,hashmap_for_each_entry (&pathmap, &iter, e, entry) {struct bloom_key key; -fill_bloom_key (e->path,strlen (e->path), &key, settings); +bloom_key_fill (e->path,strlen (e->path), &key, settings);add_key_to_filter (&key, filter, settings); -clear_bloom_key (&key); +bloom_key_clear (&key); } cleanup:
bloom.h +2 -2
@@ -78,11 +78,11 @@ int load_bloom_filter_from_graph(struct commit_graph *g,struct bloom_filter *filter, uint32_t graph_pos); -void fill_bloom_key (const char *data, +void bloom_key_fill (const char *data,size_t len,struct bloom_key *key,const struct bloom_filter_settings *settings); -void clear_bloom_key (struct bloom_key *key); +void bloom_key_clear (struct bloom_key *key); void add_key_to_filter(const struct bloom_key *key, struct bloom_filter *filter,
line-log.c +2 -2
@@ -1172,12 +1172,12 @@ static int bloom_filter_check(struct rev_info *rev,return 0 ;while (!result && range) { -fill_bloom_key (range->path,strlen (range->path), &key, rev->bloom_filter_settings); +bloom_key_fill (range->path,strlen (range->path), &key, rev->bloom_filter_settings);if (bloom_filter_contains (filter, &key, rev->bloom_filter_settings)) result =1 ; -clear_bloom_key (&key); +bloom_key_clear (&key); range = range->next; }
revision.c +3 -3
@@ -739,14 +739,14 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) revs->bloom_keys_nr = path_component_nr;ALLOC_ARRAY (revs->bloom_keys, revs->bloom_keys_nr); -fill_bloom_key (path, len, &revs->bloom_keys[0 ], +bloom_key_fill (path, len, &revs->bloom_keys[0 ], revs->bloom_filter_settings); path_component_nr =1 ; p = path + len -1 ;while (p > path) {if (*p =='/' ) -fill_bloom_key (path, p - path, +bloom_key_fill (path, p - path, &revs->bloom_keys[path_component_nr++], revs->bloom_filter_settings); p--;
@@ -3231,7 +3231,7 @@ void release_revisions(struct rev_info *revs)oidset_clear (&revs->missing_commits);for (int i =0 ; i < revs->bloom_keys_nr; i++) -clear_bloom_key (&revs->bloom_keys[i]); +bloom_key_clear (&revs->bloom_keys[i]);FREE_AND_NULL (revs->bloom_keys); revs->bloom_keys_nr =0 ; }
t/helper/test-bloom.c +2 -2
@@ -12,13 +12,13 @@ static struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;static void add_string_to_filter (const char *data,struct bloom_filter *filter) {struct bloom_key key; -fill_bloom_key (data,strlen (data), &key, &settings); +bloom_key_fill (data,strlen (data), &key, &settings);printf ("Hashes:" );for (size_t i =0 ; i < settings.num_hashes; i++)printf ("0x%08x|" , key.hashes[i]);printf ("\n" );add_key_to_filter (&key, filter, &settings); -clear_bloom_key (&key); +bloom_key_clear (&key); }static void print_bloom_filter (struct bloom_filter *filter) {
Signature · 1 line
2.50.0.107.g33b6ec8c79
PATCH v4 3/4 bloom: replace struct bloom_key * with struct bloom_keyvec
In reply to Lidong YanThe revision traversal limited by pathspec has optimization when the pathspec has only one element. To support optimization for multiple pathspec items, we need to modify the data structures in struct rev_info.
struct rev_info uses bloom_keys and bloom_nr to store the bloom keys corresponding to a single pathspec item. To allow struct rev_info to store bloom keys for multiple pathspec items, a new data structure struct bloom_keyvec is introduced. Each struct bloom_keyvec corresponds to a single pathspec item.
In struct rev_info, replace bloom_keys and bloom_nr with bloom_keyvecs and bloom_keyvec_nr. This commit still optimize one pathspec item, thus bloom_keyvec_nr can only be 0 or 1.
New bloom_keyvec_* functions are added to create and destroy a keyvec. bloom_filter_contains_vec() is added to check if all key in keyvec is contained in a bloom filter. bloom_keyvec_fill_key() is added to initialize a key in keyvec.
--- bloom.c | 31 +++++++++++++++++++++++++++++++ bloom.h | 25 +++++++++++++++++++++++++ revision.c | 39 +++++++++++++++++++++------------------ revision.h | 6 +++--- 4 files changed, 80 insertions(+), 21 deletions(-)
bloom.c +31 -0
@@ -280,6 +280,25 @@ void deinit_bloom_filters(void)deep_clear_bloom_filter_slab (&bloom_filters, free_one_bloom_filter); } +struct bloom_keyvec *bloom_keyvec_new (size_t count) +{ +struct bloom_keyvec *vec; +size_t sz =sizeof (struct bloom_keyvec ); + sz += count *sizeof (struct bloom_key ); + vec = (struct bloom_keyvec *)xcalloc (1 , sz); + vec->count = count; +return vec; +} + +void bloom_keyvec_free (struct bloom_keyvec *vec) +{ +if (!vec) +return ; +for (size_t nr =0 ; nr < vec->count; nr++) +bloom_key_clear (&vec->key[nr]); +free (vec); +} + static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, const struct hashmap_entry *eptr, const struct hashmap_entry *entry_or_key,
@@ -541,6 +560,18 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *vec, +const struct bloom_filter_settings *settings) +{ +int ret =1 ; + +for (size_t nr =0 ; ret >0 && nr < vec->count; nr++) + ret =bloom_filter_contains (filter, &vec->key[nr], settings); + +return ret; +} +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len,int version) {
bloom.h +25 -0
@@ -74,6 +74,16 @@ struct bloom_key {uint32_t *hashes; }; +/* +* A bloom_keyvec is a vector of bloom_keys, which +* can be used to store multiple keys for a single +* pathspec item. +*/ +struct bloom_keyvec { +size_t count; +struct bloom_key key[FLEX_ARRAY ]; +}; +int load_bloom_filter_from_graph (struct commit_graph *g,struct bloom_filter *filter,uint32_t graph_pos);
@@ -84,6 +94,17 @@ void bloom_key_fill(const char *data, const struct bloom_filter_settings *settings);void bloom_key_clear (struct bloom_key *key); +struct bloom_keyvec *bloom_keyvec_new (size_t count); +void bloom_keyvec_free (struct bloom_keyvec *vec); + +static inline void bloom_keyvec_fill_key (const char *data,size_t len, +struct bloom_keyvec *vec,size_t nr, +const struct bloom_filter_settings *settings) +{ +assert (nr < vec->count); +bloom_key_fill (data, len, &vec->key[nr], settings); +} +void add_key_to_filter (const struct bloom_key *key,struct bloom_filter *filter,const struct bloom_filter_settings *settings);
@@ -128,6 +149,10 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *v, +const struct bloom_filter_settings *settings); +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len,int version);
revision.c +21 -18
@@ -688,6 +688,7 @@ static int forbid_bloom_filters(struct pathspec *spec)static void prepare_to_use_bloom_filter (struct rev_info *revs) {struct pathspec_item *pi; +struct bloom_keyvec *bloom_keyvec;char *path_alloc =NULL ;const char *path, *p;size_t len;
@@ -736,19 +737,21 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) p++; } - revs->bloom_keys_nr = path_component_nr; -ALLOC_ARRAY (revs->bloom_keys, revs->bloom_keys_nr); + revs->bloom_keyvecs_nr =1 ; +CALLOC_ARRAY (revs->bloom_keyvecs,1 ); + bloom_keyvec =bloom_keyvec_new (path_component_nr); + revs->bloom_keyvecs[0 ] = bloom_keyvec; -bloom_key_fill (path, len, &revs->bloom_keys[0 ], - revs->bloom_filter_settings); +bloom_keyvec_fill_key (path, len, bloom_keyvec,0 , + revs->bloom_filter_settings); path_component_nr =1 ; p = path + len -1 ;while (p > path) {if (*p =='/' ) -bloom_key_fill (path, p - path, - &revs->bloom_keys[path_component_nr++], - revs->bloom_filter_settings); +bloom_keyvec_fill_key (path, p - path, bloom_keyvec, + path_component_nr++, + revs->bloom_filter_settings); p--; }
@@ -764,7 +767,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs, struct commit *commit) {struct bloom_filter *filter; -int result =1 , j; +int result =0 ;if (!revs->repo->objects->commit_graph)return -1 ;
@@ -779,10 +782,10 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,return -1 ; } -for (j =0 ; result && j < revs->bloom_keys_nr; j++) { - result =bloom_filter_contains (filter, - &revs->bloom_keys[j], - revs->bloom_filter_settings); +for (size_t nr =0 ; !result && nr < revs->bloom_keyvecs_nr; nr++) { + result =bloom_filter_contains_vec (filter, + revs->bloom_keyvecs[nr], + revs->bloom_filter_settings); }if (result)
@@ -823,7 +826,7 @@ static int rev_compare_tree(struct rev_info *revs,return REV_TREE_SAME ; } -if (revs->bloom_keys_nr && !nth_parent) { +if (revs->bloom_keyvecs_nr && !nth_parent) { bloom_ret =check_maybe_different_in_bloom_filter (revs, commit);if (bloom_ret ==0 )
@@ -850,7 +853,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,if (!t1)return 0 ; -if (!nth_parent && revs->bloom_keys_nr) { +if (!nth_parent && revs->bloom_keyvecs_nr) { bloom_ret =check_maybe_different_in_bloom_filter (revs, commit);if (!bloom_ret)return 1 ;
@@ -3230,10 +3233,10 @@ void release_revisions(struct rev_info *revs)line_log_free (revs);oidset_clear (&revs->missing_commits); -for (int i =0 ; i < revs->bloom_keys_nr; i++) -bloom_key_clear (&revs->bloom_keys[i]); -FREE_AND_NULL (revs->bloom_keys); - revs->bloom_keys_nr =0 ; +for (size_t i =0 ; i < revs->bloom_keyvecs_nr; i++) +bloom_keyvec_free (revs->bloom_keyvecs[i]); +FREE_AND_NULL (revs->bloom_keyvecs); + revs->bloom_keyvecs_nr =0 ; }static void add_child (struct rev_info *revs,struct commit *parent,struct commit *child)
revision.h +3 -3
@@ -62,7 +62,7 @@ struct repository;struct rev_info ;struct string_list ;struct saved_parents ; -struct bloom_key ; +struct bloom_keyvec ;struct bloom_filter_settings ;struct option ;struct parse_opt_ctx_t ;
@@ -360,8 +360,8 @@ struct rev_info {/* Commit graph bloom filter fields */ /* The bloom filter key(s) for the pathspec */ -struct bloom_key *bloom_keys; -int bloom_keys_nr; +struct bloom_keyvec **bloom_keyvecs; +int bloom_keyvecs_nr;/* * The bloom filter settings used to generate the key.
Signature · 1 line
2.50.0.107.g33b6ec8c79
Re: [PATCH v4 3/4] bloom: replace struct bloom_key * with struct bloom_keyvec
Quoted 4 lines · Lidong Yan
The revision traversal limited by pathspec has optimization when the pathspec has only one element. To support optimization for multiple pathspec items, we need to modify the data structures in struct
rev_info.
You are correct that the revision-walking abandons bloom filters when there are multiple pathspecs, and fixing this is a valuable effort.
The need for this change is subtle and could use some extra context to be sure reviewers understand:
This change is writing over some code that was created in c525ce95b46 (commit-graph: check all leading directories in changed path Bloom filters, 2020-07-01) to allow storing multiple bloom keys during the revision walk. The multiple keys are focusing on multiple path components of the literal pathspec.
The point is that after the initialization, the bloom key array is used directly as a filter for reporting TREESAME commits: a commit is automatically reported as TREESAME to its first parent if any bloom key results in a "No, definitely not changed" result with that commit's bloom filter.
The reason we need a new data structure is that we need to adjust the conditionals.
BEFORE: "NOT TREESAME if there EXISTS a bloom key that reports NO"
AFTER: "NOT TREESAME if FOR EVERY pathspec there EXISTS a bloom key
that reports NO."
This "FOR EVERY" condition makes it impossible to use a flat array of bloom keys for multiple pathspecs, justifying this change.
What is further confusing here is that we already have logic that deals with arrays of bloom keys, so I expected that the vector was the single structure storing a list of those arrays. Instead, the vector is replacing the array itself. This is made clear by using the vector immediately in the existing implementation.
bloom.c void deinit_bloom_filters(void) · line 288
Quoted 6 lines
bloom.c +6
-0+struct bloom_keyvec *bloom_keyvec_new (size_t count) +{ +struct bloom_keyvec *vec; +size_t sz =sizeof (struct bloom_keyvec ); + sz += count *sizeof (struct bloom_key ); + vec = (struct bloom_keyvec *)xcalloc (1 , sz);
You could use CALLOC_ARRAY() to simplify this and drop the 'sz' variable.
Quoted 21 lines
bloom.c +14
-0+ vec->count = count; +return vec; +} + +void bloom_keyvec_free (struct bloom_keyvec *vec) +{ +if (!vec) +return ; +for (size_t nr =0 ; nr < vec->count; nr++) +bloom_key_clear (&vec->key[nr]); +free (vec); +} + static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, const struct hashmap_entry *eptr, const struct hashmap_entry *entry_or_key,@@ -541,6 +560,18 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } +int bloom_filter_contains_vec(const struct bloom_filter *filter,
bloom.c int bloom_filter_contains(const struct bloom_filter *filter, · line 573
Quoted 10 lines
bloom.c +10
-0+const struct bloom_keyvec *vec, + const struct bloom_filter_settings *settings) +{ + int ret = 1; + +for (size_t nr =0 ; ret >0 && nr < vec->count; nr++) + ret =bloom_filter_contains (filter, &vec->key[nr], settings); + +return ret; +}
This implementation is where the subtle detail comes in. Might be worth a comment to say "if any key in this list is not contained in the filter, then the filter doesn't match this vector."
Re: [PATCH v4 3/4] bloom: replace struct bloom_key * with struct bloom_keyvec
Quoted 6 lines · Derrick Stolee
BEFORE: "NOT TREESAME if there EXISTS a bloom key that reports NO"
AFTER: "NOT TREESAME if FOR EVERY pathspec there EXISTS a bloom key
that reports NO."
Quoted 8 lines
This "FOR EVERY" condition makes it impossible to use a flat array of bloom keys for multiple pathspecs, justifying this change.
What is further confusing here is that we already have logic that deals with arrays of bloom keys, so I expected that the vector was the single structure storing a list of those arrays. Instead, the vector is replacing the array itself. This is made clear by using the vector immediately in the existing implementation.
I think the problem here is that it clearly enough in my comments. When writing the code, I thought about converting the original one-dimensional array struct bloom_key *keys into a two-dimensional array struct bloom_key **. Then I came up with the idea that this two-dimensional array could be designed as struct bloom_keyvec *keyvecs, which might be clearer. Each struct bloom_keyvec would represent all the bloom_key elements for a single pathspec item.
Quoted 8 lines
bloom.c void deinit_bloom_filters(void) · line 288
Quoted 6 lines
bloom.c +6
-0+struct bloom_keyvec *bloom_keyvec_new (size_t count) +{ +struct bloom_keyvec *vec; +size_t sz =sizeof (struct bloom_keyvec ); + sz += count *sizeof (struct bloom_key ); + vec = (struct bloom_keyvec *)xcalloc (1 , sz);You could use
CALLOC_ARRAY()to simplify this and drop the 'sz' variable.
You are right. I think you suggest to write struct bloom_keyvec like:
———————-
| count |
———————
| *keys | ——> key0 | key1 | key2 | … |
———————
And I am doing here makes struct bloom_keyvec looks like
———————
| count |
———————
| key[0] |
———————
| key[1] |
———————
| … |
Although bloom_keyvec_new() appears more complex, the advantage is that bloom_keyvec_destroy() no longer needs to free keys manually. And if I understand correctly, junio had suggested to use the second way [here](https://lore.kernel.org/git/[email protected]/).
Quoted 21 lines
Quoted 21 lines
+
vec->count= count;
+ return vec;bloom.c +11
-0+} + +void bloom_keyvec_free (struct bloom_keyvec *vec) +{ +if (!vec) +return ; +for (size_t nr =0 ; nr < vec->count; nr++) +bloom_key_clear (&vec->key[nr]); +free (vec); +} +static int pathmap_cmp(const void
*hashmap_cmp_fn_dataUNUSED,
const structhashmap_entry*eptr,
const structhashmap_entry*entry_or_key,bloom.c +0
-0@@ -541,6 +560,18 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; }
Quoted 15 lines
bloom.c int bloom_filter_contains(const struct bloom_filter *filter, · line 573
Quoted 11 lines
bloom.c +11
-0+int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *vec, +const struct bloom_filter_settings *settings) +{ +int ret =1 ; + +for (size_t nr =0 ; ret >0 && nr < vec->count; nr++) + ret =bloom_filter_contains (filter, &vec->key[nr], settings); + +return ret; +}This implementation is where the subtle detail comes in. Might be worth a comment to say "if any key in this list is not contained in the filter, then the filter doesn't match this vector."
I will add comment in the next version
Thank you for your review,
Lidong
PATCH v4 4/4 bloom: optimize multiple pathspec items in revision traversal
In reply to Lidong YanTo enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in forbid_bloom_filters(). Add code to initialize and check each pathspec item's bloom_keyvec.
Add new function release_revisions_bloom_keyvecs() to free all bloom keyvec owned by rev_info.
Add new test cases in t/t4216-log-bloom.sh to ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
--- revision.c | 118 ++++++++++++++++++++++++------------------- t/t4216-log-bloom.sh | 23 +++++---- 2 files changed, 79 insertions(+), 62 deletions(-)
revision.c +65 -53
@@ -675,16 +675,17 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ; -if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL )) -return 1 ; +for (size_t nr =0 ; nr < spec->nr; nr++) +if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +return 1 ;return 0 ; } +static void release_revisions_bloom_keyvecs (struct rev_info *revs); +static void prepare_to_use_bloom_filter (struct rev_info *revs) {struct pathspec_item *pi;
@@ -692,7 +693,7 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)char *path_alloc =NULL ;const char *path, *p;size_t len; -int path_component_nr =1 ; +int path_component_nr;if (!revs->commits)return ;
@@ -709,50 +710,52 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - pi = &revs->pruning.pathspec.items[0 ]; - -/* remove single trailing slash from path, if needed */ -if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { - path_alloc =xmemdupz (pi->match, pi->len -1 ); - path = path_alloc; - }else - path = pi->match; - - len =strlen (path); -if (!len) { - revs->bloom_filter_settings =NULL ; -free (path_alloc); -return ; - } - - p = path; -while (*p) { -/* -* At this point, the path is normalized to use Unix-style -* path separators. This is required due to how the -* changed-path Bloom filters store the paths. -*/ -if (*p =='/' ) - path_component_nr++; - p++; - } - - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - bloom_keyvec =bloom_keyvec_new (path_component_nr); - revs->bloom_keyvecs[0 ] = bloom_keyvec; - -bloom_keyvec_fill_key (path, len, bloom_keyvec,0 , - revs->bloom_filter_settings); - path_component_nr =1 ; + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { + pi = &revs->pruning.pathspec.items[i]; + path_component_nr =1 ; + +/* remove single trailing slash from path, if needed */ +if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { + path_alloc =xmemdupz (pi->match, pi->len -1 ); + path = path_alloc; + }else + path = pi->match; + + len =strlen (path); +if (!len) + goto fail; + + p = path; +while (*p) { +/* +* At this point, the path is normalized to use +* Unix-style path separators. This is required due to +* how the changed-path Bloom filters store the paths. +*/ +if (*p =='/' ) + path_component_nr++; + p++; + } - p = path + len -1 ; -while (p > path) { -if (*p =='/' ) -bloom_keyvec_fill_key (path, p - path, bloom_keyvec, - path_component_nr++, - revs->bloom_filter_settings); - p--; + bloom_keyvec =bloom_keyvec_new (path_component_nr); + revs->bloom_keyvecs[i] = bloom_keyvec; + +bloom_keyvec_fill_key (path, len, bloom_keyvec,0 , + revs->bloom_filter_settings); + path_component_nr =1 ; + + p = path + len -1 ; +while (p > path) { +if (*p =='/' ) +bloom_keyvec_fill_key (path, p - path, + bloom_keyvec, + path_component_nr++, + revs->bloom_filter_settings); + p--; + } +FREE_AND_NULL (path_alloc); }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {
@@ -760,7 +763,12 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) bloom_filter_atexit_registered =1 ; } +return ; + +fail: + revs->bloom_filter_settings =NULL ;free (path_alloc); +release_revisions_bloom_keyvecs (revs); } static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
@@ -3204,6 +3212,14 @@ static void release_revisions_mailmap(struct string_list *mailmap)static void release_revisions_topo_walk_info (struct topo_walk_info *info); +static void release_revisions_bloom_keyvecs (struct rev_info *revs) +{ +for (size_t nr =0 ; nr < revs->bloom_keyvecs_nr; nr++) +bloom_keyvec_free (revs->bloom_keyvecs[nr]); +FREE_AND_NULL (revs->bloom_keyvecs); + revs->bloom_keyvecs_nr =0 ; +} +static void free_void_commit_list (void *list) {free_commit_list (list);
@@ -3232,11 +3248,7 @@ void release_revisions(struct rev_info *revs)clear_decoration (&revs->treesame, free);line_log_free (revs);oidset_clear (&revs->missing_commits); - -for (size_t i =0 ; i < revs->bloom_keyvecs_nr; i++) -bloom_keyvec_free (revs->bloom_keyvecs[i]); -FREE_AND_NULL (revs->bloom_keyvecs); - revs->bloom_keyvecs_nr =0 ; +release_revisions_bloom_keyvecs (revs); }static void add_child (struct rev_info *revs,struct commit *parent,struct commit *child)
t/t4216-log-bloom.sh +14 -9
@@ -66,8 +66,9 @@ sane_unset GIT_TRACE2_CONFIG_PARAMS setup () { rm -f "$TRASH_DIRECTORY/trace.perf" && - git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom && - GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom + eval git -c core.commitGraph=false log --pretty="format:%s" "$1" >log_wo_bloom && + eval "GIT_TRACE2_PERF=\"$TRASH_DIRECTORY/trace.perf\"" \ + git -c core.commitGraph=true log --pretty="format:%s" "$1" >log_w_bloom } test_bloom_filters_used () {
@@ -138,10 +139,6 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' ' test_bloom_filters_not_used "--walk-reflogs -- A" ' -test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" -' - test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' ' test_bloom_filters_not_used "-- ." '
@@ -151,9 +148,17 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used "-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with multiple literal paths uses Bloom filter' ' + test_bloom_filters_used "-- file4 A/file1" && + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" +' + +test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' + test_bloom_filters_not_used "-- file\*" && + test_bloom_filters_not_used "-- A/\* file4" && + test_bloom_filters_not_used "-- file4 A/\*" && + test_bloom_filters_not_used "-- * A/\*" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.50.0.107.g33b6ec8c79
Re: [PATCH v4 4/4] bloom: optimize multiple pathspec items in revision traversal
Quoted 4 lines · Lidong Yan
To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in
forbid_bloom_filters(). Add code to initialize and check each pathspec item'sbloom_keyvec.
Quoted 8 lines
Add new function
release_revisions_bloom_keyvecs()to free all bloom keyvec owned byrev_info.Add new test cases in
t/t4216-log-bloom.shto ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
This would be a great time to add some performance statistics when using this feature with multiple pathspecs on some standard repos (git and the Linux kernel repo are two good examples).
We don't have a great performance script for this, since each test repo will have different paths to use for comparisons, but you can use 'hyperfine' to assemble your own comparisons before and after this change and report them here (and in your cover letter).
Quoted 13 lines
Signed-off-by Lidong Yan <[email protected]>--- revision.c | 118 ++++++++++++++++++++++++------------------- t/t4216-log-bloom.sh | 23 +++++---- 2 files changed, 79 insertions(+), 62 deletions(-)revision.c +0
-0@@ -675,16 +675,17 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)
revision.c static int forbid_bloom_filters(struct pathspec *spec) · line 682
Quoted 10 lines
revision.c +3
-4return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ; -if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL )) -return 1 ; +for (size_t nr =0 ; nr < spec->nr; nr++) +if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +return 1 ;
This is a good check: if any is non-literal, then we can't use bloom filters.
revision.c static void prepare_to_use_bloom_filter(struct rev_info *revs) · line 696
Quoted 11 lines
revision.c +3
-1+static void release_revisions_bloom_keyvecs (struct rev_info *revs); +static void prepare_to_use_bloom_filter (struct rev_info *revs) {struct pathspec_item *pi;@@ -692,7 +693,7 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)char *path_alloc =NULL ;const char *path, *p;size_t len; -int path_component_nr =1 ; +int path_component_nr;
We can move this into the interior of the loop, right?
Quoted 32 lines
revision.c +0
-26if (!revs->commits)return ;@@ -709,50 +710,52 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - pi = &revs->pruning.pathspec.items[0 ]; - -/* remove single trailing slash from path, if needed */ -if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { - path_alloc =xmemdupz (pi->match, pi->len -1 ); - path = path_alloc; - }else - path = pi->match; - - len =strlen (path); -if (!len) { - revs->bloom_filter_settings =NULL ; -free (path_alloc); -return ; - } - - p = path; -while (*p) { -/* -* At this point, the path is normalized to use Unix-style -* path separators. This is required due to how the -* changed-path Bloom filters store the paths. -*/ -if (*p =='/' ) - path_component_nr++; - p++;
revision.c static void prepare_to_use_bloom_filter(struct rev_info *revs) · line 747
Quoted 10 lines
revision.c +0
-10- } - - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - bloom_keyvec =bloom_keyvec_new (path_component_nr); - revs->bloom_keyvecs[0 ] = bloom_keyvec; - -bloom_keyvec_fill_key (path, len, bloom_keyvec,0 , - revs->bloom_filter_settings); - path_component_nr =1 ;
The size of this diff is unfortunate. I wonder if there could first be an extraction of this logic to operate on a single pathspec and bloom_keyvec in a way that would be an obvious code move, then this patch could call that method in a loop now that we have an array of bloom_keyvecs.
I think it would make a cleaner patch and a cleaner final result.
Quoted 53 lines
revision.c +45
-7+ revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { + pi = &revs->pruning.pathspec.items[i]; + path_component_nr =1 ; + +/* remove single trailing slash from path, if needed */ +if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { + path_alloc =xmemdupz (pi->match, pi->len -1 ); + path = path_alloc; + }else + path = pi->match; + + len =strlen (path); +if (!len) + goto fail; + + p = path; +while (*p) { +/* +* At this point, the path is normalized to use +* Unix-style path separators. This is required due to +* how the changed-path Bloom filters store the paths. +*/ +if (*p =='/' ) + path_component_nr++; + p++; + } - p = path + len -1 ; -while (p > path) { -if (*p =='/' ) -bloom_keyvec_fill_key (path, p - path, bloom_keyvec, - path_component_nr++, - revs->bloom_filter_settings); - p--; + bloom_keyvec =bloom_keyvec_new (path_component_nr); + revs->bloom_keyvecs[i] = bloom_keyvec; + +bloom_keyvec_fill_key (path, len, bloom_keyvec,0 , + revs->bloom_filter_settings); + path_component_nr =1 ; + + p = path + len -1 ; +while (p > path) { +if (*p =='/' ) +bloom_keyvec_fill_key (path, p - path, + bloom_keyvec, + path_component_nr++, + revs->bloom_filter_settings); + p--; + } +FREE_AND_NULL (path_alloc);
...
revision.c
Quoted 4 lines
revision.c +0
-4-test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used"-- file4 A/file1" -' -
Love to see this.
Quoted 12 lines
test_expect_success'git log -- "." pathspec at root does not use Bloom filters' 'revision.c +2
-3test_bloom_filters_not_used"-- ." '@@ -151,9 +148,17 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used"-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used"-- *" && - test_bloom_filters_not_used"-- file*" +test_expect_success 'git log with multiple literal paths uses Bloom filter' ' + test_bloom_filters_used "-- file4 A/file1" &&
revision.c test_expect_success 'git log with wildcard that resolves to a single path uses B · line 162
Quoted 10 lines
revision.c +9
-0+ test_bloom_filters_used"-- *" && + test_bloom_filters_used"-- file*" +' + +test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' + test_bloom_filters_not_used"-- file\*" && + test_bloom_filters_not_used"-- A/\* file4" && + test_bloom_filters_not_used"-- file4 A/\*" && + test_bloom_filters_not_used"-- * A/\*" '
And these new test cases are great.
Thanks for this work. I'm happy to see the feature be added and my suggestions are purely cosmetic as the proof is in your tests.
Thanks,
-Stolee
Re: [PATCH v4 4/4] bloom: optimize multiple pathspec items in revision traversal
Quoted 15 lines · Derrick Stolee
Quoted 4 lines · Lidong Yan
To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in
forbid_bloom_filters(). Add code to initialize and check each pathspec item'sbloom_keyvec.Quoted 8 lines
Add new function
release_revisions_bloom_keyvecs()to free all bloom keyvec owned byrev_info.Add new test cases in
t/t4216-log-bloom.shto ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
Quoted 8 lines
This would be a great time to add some performance statistics when using this feature with multiple pathspecs on some standard repos (git and the Linux kernel repo are two good examples).
We don't have a great performance script for this, since each test repo will have different paths to use for comparisons, but you can use 'hyperfine' to assemble your own comparisons before and after this change and report them here (and in your cover letter).
Got it, I will add statistics in the next version.
Quoted 3 lines
Quoted 1 line
+ int
path_component_nr;We can move this into the interior of the loop, right?
Yes, move this into loop looks better.
Quoted 6 lines
The size of this diff is unfortunate. I wonder if there could first be an extraction of this logic to operate on a single pathspec and
bloom_keyvecin a way that would be an obvious code move, then this patch could call that method in a loop now that we have an array ofbloom_keyvecs.
I will try to figure out a way to make diff cleaner.
Thanks,
Lidong
Re: [PATCH v4 4/4] bloom: optimize multiple pathspec items in revision traversal
In reply to Derrick StoleeQuoted 14 lines · Derrick Stolee
Quoted 4 lines · Lidong Yan
To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in
forbid_bloom_filters(). Add code to initialize and check each pathspec item'sbloom_keyvec.Quoted 8 lines
Add new function
release_revisions_bloom_keyvecs()to free all bloom keyvec owned byrev_info.Add new test cases in
t/t4216-log-bloom.shto ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
Quoted 8 lines
This would be a great time to add some performance statistics when using this feature with multiple pathspecs on some standard repos (git and the Linux kernel repo are two good examples).
We don't have a great performance script for this, since each test repo will have different paths to use for comparisons, but you can use 'hyperfine' to assemble your own comparisons before and after this change and report them here (and in your cover letter).
Excellent suggestion. Very much appreciated.
Quoted 7 lines
The size of this diff is unfortunate. I wonder if there could first be an extraction of this logic to operate on a single pathspec and
bloom_keyvecin a way that would be an obvious code move, then this patch could call that method in a loop now that we have an array ofbloom_keyvecs.I think it would make a cleaner patch and a cleaner final result.
Hmph. Didn't think of that extra "preliminary clean-up" step myself, but I think you have a point. That would likely make the resulting series easier to follow.
Thanks.
v5 cover bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
In reply to Lidong YanThe revision traversal limited by pathspec has optimization when the pathspec has only one element, it does not use any pathspec magic (other than literal), and there is no wildcard. The absence of optimization for multiple pathspec elements in revision traversal cause an issue raised by Kai Koponen at
https://lore.kernel.org/git/CADYQcGqaMC=4jgbmnF9Q11oC11jfrqyvH8EuiRRHytpMXd4wYA@mail.gmail.com/
While it is much harder to lift the latter two limitations, supporting a pathspec with multiple elements is relatively easy. Just make sure we hash each of them separately and ask the bloom filter about them, and if we see none of them can possibly be affected by the commit, we can skip without tree comparison.
The difference from v4 is:
- for the bloom_key_* functions, we now pass struct bloom_key * as the first parameter.
- bloom_keyvec_fill_key() and bloom_keyvec_new() have been merged into a single function, so that each key is filled during the creation of the bloom_keyvec.
Below is a comparison of the time taken to run git log on Git and LLVM repositories before and after applying this patch.
Setup commit-graph:
$ cd ~/src/git && git commit-graph write --split --reachable --changed-paths $ cd ~/src/llvm && git commit-graph write --split --reachable --changed-paths
Run git log on Git repository
$ cd ~/src/git $ hash -p /usr/bin/git git # my system git binary is 2.43.0 $ time git log -100 -- commit.c commit-graph.c >/dev/null real 0m0.055s user 0m0.040s sys 0m0.015s $ hash -p ~/bin/git/bin/git git $ time git log -100 -- commit.c commit-graph.c >/dev/null real 0m0.039s user 0m0.020s sys 0m0.020s
Run git log in LLVM repository
$ cd ~/src/llvm $ hash -p /usr/bin/git git # my system git binary is 2.43.0 $ time git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h >/dev/null real 0m2.365s user 0m2.252s sys 0m0.113s $ hash -p ~/bin/git/bin/git git $ time git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h >/dev/null real 0m0.240s user 0m0.158s sys 0m0.064s
Lidong Yan (4):
bloom: add test helper to return murmur3 hash
bloom: rename function operates on bloom_key
bloom: replace struct bloom_key * with struct bloom_keyvec
bloom: optimize multiple pathspec items in revision traversal
blame.c | 2 +- bloom.c | 84 +++++++++++++++++++++++++++++++++--- bloom.h | 54 +++++++++++++++++------ line-log.c | 5 ++- revision.c | 99 +++++++++++++++++++------------------------ revision.h | 6 +-- t/helper/test-bloom.c | 8 ++-- t/t4216-log-bloom.sh | 23 ++++++---- 8 files changed, 187 insertions(+), 94 deletions(-)
Range-diff against v4:
1: d6883e9d6c = 1: 31c048dcdb bloom: add test helper to return murmur3 hash
2: f114556c0f ! 2: d2603c1752 bloom: rename function operates on bloom_key
@@ blame.c: static void add_bloom_key(struct blame_bloom_data *bd,
bd->keys[bd->nr] = xmalloc(sizeof(struct bloom_key));
- fill_bloom_key(path, strlen(path), bd->keys[bd->nr], bd->settings);
-+ bloom_key_fill(path, strlen(path), bd->keys[bd->nr], bd->settings);
++ bloom_key_fill(bd->keys[bd->nr], path, strlen(path), bd->settings);
bd->nr++;
}
@@ bloom.c: static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size
}
-void fill_bloom_key(const char *data,
-+void bloom_key_fill(const char *data,
- size_t len,
- struct bloom_key *key,
+- size_t len,
+- struct bloom_key *key,
++void bloom_key_fill(struct bloom_key *key, const char *data, size_t len,
const struct bloom_filter_settings *settings)
+ {
+ int i;
@@ bloom.c: void fill_bloom_key(const char *data,
key->hashes[i] = hash0 + i * hash1;
}
@@ bloom.c: struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
hashmap_for_each_entry(&pathmap, &iter, e, entry) {
struct bloom_key key;
- fill_bloom_key(e->path, strlen(e->path), &key, settings);
-+ bloom_key_fill(e->path, strlen(e->path), &key, settings);
++ bloom_key_fill(&key, e->path, strlen(e->path), settings);
add_key_to_filter(&key, filter, settings);
- clear_bloom_key(&key);
+ bloom_key_clear(&key);
@@ bloom.h: int load_bloom_filter_from_graph(struct commit_graph *g,
uint32_t graph_pos);
-void fill_bloom_key(const char *data,
-+void bloom_key_fill(const char *data,
- size_t len,
- struct bloom_key *key,
+- size_t len,
+- struct bloom_key *key,
++void bloom_key_fill(struct bloom_key *key, const char *data, size_t len,
const struct bloom_filter_settings *settings);
-void clear_bloom_key(struct bloom_key *key);
+void bloom_key_clear(struct bloom_key *key);
@@ line-log.c: static int bloom_filter_check(struct rev_info *rev,
while (!result && range) {
- fill_bloom_key(range->path, strlen(range->path), &key, rev->bloom_filter_settings);
-+ bloom_key_fill(range->path, strlen(range->path), &key, rev->bloom_filter_settings);
++ bloom_key_fill(&key, range->path, strlen(range->path),
++ rev->bloom_filter_settings);
if (bloom_filter_contains(filter, &key, rev->bloom_filter_settings))
result = 1;
@@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)
ALLOC_ARRAY(revs->bloom_keys, revs->bloom_keys_nr);
- fill_bloom_key(path, len, &revs->bloom_keys[0],
-+ bloom_key_fill(path, len, &revs->bloom_keys[0],
++ bloom_key_fill(&revs->bloom_keys[0], path, len,
revs->bloom_filter_settings);
path_component_nr = 1;
@@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)
while (p > path) {
if (*p == '/')
- fill_bloom_key(path, p - path,
-+ bloom_key_fill(path, p - path,
- &revs->bloom_keys[path_component_nr++],
+- &revs->bloom_keys[path_component_nr++],
++ bloom_key_fill(&revs->bloom_keys[path_component_nr++],
++ path, p - path,
revs->bloom_filter_settings);
p--;
+ }
@@ revision.c: void release_revisions(struct rev_info *revs)
oidset_clear(&revs->missing_commits);
@@ t/helper/test-bloom.c: static struct bloom_filter_settings settings = DEFAULT_BL
struct bloom_key key;
- fill_bloom_key(data, strlen(data), &key, &settings);
-+ bloom_key_fill(data, strlen(data), &key, &settings);
++ bloom_key_fill(&key, data, strlen(data), &settings);
printf("Hashes:");
for (size_t i = 0; i < settings.num_hashes; i++)
printf("0x%08x|", key.hashes[i]);
3: c042907b92 ! 3: 60a3b16bbb bloom: replace struct bloom_key * with struct bloom_keyvec
@@ Metadata
## Commit message ##
bloom: replace struct bloom_key * with struct bloom_keyvec
- The revision traversal limited by pathspec has optimization when
- the pathspec has only one element. To support optimization for
- multiple pathspec items, we need to modify the data structures
- in struct rev_info.
+ Previously, we stored bloom keys in a flat array and marked a commit
+ as NOT TREESAME if any key reported "definitely not changed".
- struct rev_info uses bloom_keys and bloom_nr to store the bloom keys
- corresponding to a single pathspec item. To allow struct rev_info
- to store bloom keys for multiple pathspec items, a new data structure
- `struct bloom_keyvec` is introduced. Each `struct bloom_keyvec`
- corresponds to a single pathspec item.
+ To support multiple pathspec items, we now require that for each
+ pathspec item, there exists a bloom key reporting "definitely not
+ changed".
- In `struct rev_info`, replace bloom_keys and bloom_nr with bloom_keyvecs
- and bloom_keyvec_nr. This commit still optimize one pathspec item, thus
- bloom_keyvec_nr can only be 0 or 1.
+ This "for every" condition makes a flat array insufficient, so we
+ introduce a new structure to group keys by a single pathspec item.
+ `struct bloom_keyvec` is introduced to replace `struct bloom_key *`
+ and `bloom_key_nr`. And because we want to support multiple pathspec
+ items, we added a bloom_keyvec * and a bloom_keyvec_nr field to
+ `struct rev_info` to represent an array of bloom_keyvecs. This commit
+ still optimize only one pathspec item, thus bloom_keyvec_nr can only
+ be 0 or 1.
New bloom_keyvec_* functions are added to create and destroy a keyvec.
bloom_filter_contains_vec() is added to check if all key in keyvec is
- contained in a bloom filter. bloom_keyvec_fill_key() is added to
- initialize a key in keyvec.
+ contained in a bloom filter.
Signed-off-by: Lidong Yan <[email protected]>
@@ bloom.c: void deinit_bloom_filters(void)
deep_clear_bloom_filter_slab(&bloom_filters, free_one_bloom_filter);
}
-+struct bloom_keyvec *bloom_keyvec_new(size_t count)
++struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len,
++ const struct bloom_filter_settings *settings)
+{
+ struct bloom_keyvec *vec;
-+ size_t sz = sizeof(struct bloom_keyvec);
-+ sz += count * sizeof(struct bloom_key);
++ const char *p;
++ size_t sz;
++ size_t nr = 1;
++
++ p = path;
++ while (*p) {
++ /*
++ * At this point, the path is normalized to use Unix-style
++ * path separators. This is required due to how the
++ * changed-path Bloom filters store the paths.
++ */
++ if (*p == '/')
++ nr++;
++ p++;
++ }
++
++ sz = sizeof(struct bloom_keyvec);
++ sz += nr * sizeof(struct bloom_key);
+ vec = (struct bloom_keyvec *)xcalloc(1, sz);
-+ vec->count = count;
++ if (!vec)
++ return NULL;
++ vec->count = nr;
++
++ bloom_key_fill(&vec->key[0], path, len, settings);
++ nr = 1;
++ p = path + len - 1;
++ while (p > path) {
++ if (*p == '/') {
++ bloom_key_fill(&vec->key[nr++], path, p - path, settings);
++ }
++ p--;
++ }
++ assert(nr == vec->count);
+ return vec;
+}
+
@@ bloom.h: struct bloom_key {
int load_bloom_filter_from_graph(struct commit_graph *g,
struct bloom_filter *filter,
uint32_t graph_pos);
-@@ bloom.h: void bloom_key_fill(const char *data,
+@@ bloom.h: void bloom_key_fill(struct bloom_key *key, const char *data, size_t len,
const struct bloom_filter_settings *settings);
void bloom_key_clear(struct bloom_key *key);
-+struct bloom_keyvec *bloom_keyvec_new(size_t count);
++/*
++ * bloom_keyvec_fill - Allocate and populate a bloom_keyvec with keys for the
++ * given path.
++ *
++ * This function splits the input path by '/' and generates a bloom key for each
++ * prefix, in reverse order of specificity. For example, given the input
++ * "a/b/c", it will generate bloom keys for:
++ * - "a/b/c"
++ * - "a/b"
++ * - "a"
++ *
++ * The resulting keys are stored in a newly allocated bloom_keyvec.
++ */
++struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len,
++ const struct bloom_filter_settings *settings);
+void bloom_keyvec_free(struct bloom_keyvec *vec);
-+
-+static inline void bloom_keyvec_fill_key(const char *data, size_t len,
-+ struct bloom_keyvec *vec, size_t nr,
-+ const struct bloom_filter_settings *settings)
-+{
-+ assert(nr < vec->count);
-+ bloom_key_fill(data, len, &vec->key[nr], settings);
-+}
+
void add_key_to_filter(const struct bloom_key *key,
struct bloom_filter *filter,
@@ bloom.h: int bloom_filter_contains(const struct bloom_filter *filter,
const struct bloom_key *key,
const struct bloom_filter_settings *settings);
++/*
++ * bloom_filter_contains_vec - Check if all keys in a key vector are in the
++ * Bloom filter.
++ *
++ * Returns 1 if **all** keys in the vector are present in the filter,
++ * 0 if **any** key is not present.
++ */
+int bloom_filter_contains_vec(const struct bloom_filter *filter,
+ const struct bloom_keyvec *v,
+ const struct bloom_filter_settings *settings);
@@ bloom.h: int bloom_filter_contains(const struct bloom_filter *filter,
## revision.c ##
@@ revision.c: static int forbid_bloom_filters(struct pathspec *spec)
+ return 0;
+ }
+
++static void release_revisions_bloom_keyvecs(struct rev_info *revs);
++
static void prepare_to_use_bloom_filter(struct rev_info *revs)
{
struct pathspec_item *pi;
@@ revision.c: static int forbid_bloom_filters(struct pathspec *spec)
char *path_alloc = NULL;
const char *path, *p;
size_t len;
+- int path_component_nr = 1;
+
+ if (!revs->commits)
+ return;
@@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)
- p++;
- }
+ if (!revs->pruning.pathspec.nr)
+ return;
-- revs->bloom_keys_nr = path_component_nr;
-- ALLOC_ARRAY(revs->bloom_keys, revs->bloom_keys_nr);
+ revs->bloom_keyvecs_nr = 1;
+ CALLOC_ARRAY(revs->bloom_keyvecs, 1);
-+ bloom_keyvec = bloom_keyvec_new(path_component_nr);
-+ revs->bloom_keyvecs[0] = bloom_keyvec;
+ pi = &revs->pruning.pathspec.items[0];
+
+ /* remove single trailing slash from path, if needed */
+@@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)
+ path = pi->match;
-- bloom_key_fill(path, len, &revs->bloom_keys[0],
+ len = strlen(path);
+- if (!len) {
+- revs->bloom_filter_settings = NULL;
+- free(path_alloc);
+- return;
+- }
+-
+- p = path;
+- while (*p) {
+- /*
+- * At this point, the path is normalized to use Unix-style
+- * path separators. This is required due to how the
+- * changed-path Bloom filters store the paths.
+- */
+- if (*p == '/')
+- path_component_nr++;
+- p++;
+- }
+-
+- revs->bloom_keys_nr = path_component_nr;
+- ALLOC_ARRAY(revs->bloom_keys, revs->bloom_keys_nr);
++ if (!len)
++ goto fail;
+
+- bloom_key_fill(&revs->bloom_keys[0], path, len,
- revs->bloom_filter_settings);
-+ bloom_keyvec_fill_key(path, len, bloom_keyvec, 0,
-+ revs->bloom_filter_settings);
- path_component_nr = 1;
-
- p = path + len - 1;
- while (p > path) {
- if (*p == '/')
-- bloom_key_fill(path, p - path,
-- &revs->bloom_keys[path_component_nr++],
+- path_component_nr = 1;
+-
+- p = path + len - 1;
+- while (p > path) {
+- if (*p == '/')
+- bloom_key_fill(&revs->bloom_keys[path_component_nr++],
+- path, p - path,
- revs->bloom_filter_settings);
-+ bloom_keyvec_fill_key(path, p - path, bloom_keyvec,
-+ path_component_nr++,
-+ revs->bloom_filter_settings);
- p--;
+- p--;
+- }
++ revs->bloom_keyvecs[0] =
++ bloom_keyvec_new(path, len, revs->bloom_filter_settings);
+
+ if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
+ atexit(trace2_bloom_filter_statistics_atexit);
+ bloom_filter_atexit_registered = 1;
}
-@@ revision.c: static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
++ return;
++
++fail:
++ revs->bloom_filter_settings = NULL;
+ free(path_alloc);
++ release_revisions_bloom_keyvecs(revs);
+ }
+
+ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
struct commit *commit)
{
struct bloom_filter *filter;
@@ revision.c: static int rev_same_tree_as_empty(struct rev_info *revs, struct comm
bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
if (!bloom_ret)
return 1;
+@@ revision.c: static void release_revisions_mailmap(struct string_list *mailmap)
+
+ static void release_revisions_topo_walk_info(struct topo_walk_info *info);
+
++static void release_revisions_bloom_keyvecs(struct rev_info *revs)
++{
++ for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
++ bloom_keyvec_free(revs->bloom_keyvecs[nr]);
++ FREE_AND_NULL(revs->bloom_keyvecs);
++ revs->bloom_keyvecs_nr = 0;
++}
++
+ static void free_void_commit_list(void *list)
+ {
+ free_commit_list(list);
@@ revision.c: void release_revisions(struct rev_info *revs)
+ clear_decoration(&revs->treesame, free);
line_log_free(revs);
oidset_clear(&revs->missing_commits);
-
+-
- for (int i = 0; i < revs->bloom_keys_nr; i++)
- bloom_key_clear(&revs->bloom_keys[i]);
- FREE_AND_NULL(revs->bloom_keys);
- revs->bloom_keys_nr = 0;
-+ for (size_t i = 0; i < revs->bloom_keyvecs_nr; i++)
-+ bloom_keyvec_free(revs->bloom_keyvecs[i]);
-+ FREE_AND_NULL(revs->bloom_keyvecs);
-+ revs->bloom_keyvecs_nr = 0;
++ release_revisions_bloom_keyvecs(revs);
}
static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child)
4: de4d554b55 ! 4: 198a7da17c bloom: optimize multiple pathspec items in revision traversal
@@ Commit message
To enable optimize multiple pathspec items in revision traversal,
return 0 if all pathspec item is literal in forbid_bloom_filters().
- Add code to initialize and check each pathspec item's bloom_keyvec.
-
- Add new function release_revisions_bloom_keyvecs() to free all bloom
- keyvec owned by rev_info.
+ Add for loops to initialize and check each pathspec item's bloom_keyvec
+ when optimization is possible.
Add new test cases in t/t4216-log-bloom.sh to ensure
- consistent results between the optimization for multiple pathspec
@@ revision.c: static int forbid_bloom_filters(struct pathspec *spec)
return 0;
}
-
-+static void release_revisions_bloom_keyvecs(struct rev_info *revs);
-+
- static void prepare_to_use_bloom_filter(struct rev_info *revs)
- {
- struct pathspec_item *pi;
-@@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)
- char *path_alloc = NULL;
- const char *path, *p;
- size_t len;
-- int path_component_nr = 1;
-+ int path_component_nr;
-
- if (!revs->commits)
- return;
@@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)
if (!revs->pruning.pathspec.nr)
return;
+- revs->bloom_keyvecs_nr = 1;
+- CALLOC_ARRAY(revs->bloom_keyvecs, 1);
- pi = &revs->pruning.pathspec.items[0];
--
++ revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr;
++ CALLOC_ARRAY(revs->bloom_keyvecs, revs->bloom_keyvecs_nr);
++ for (int i = 0; i < revs->pruning.pathspec.nr; i++) {
++ pi = &revs->pruning.pathspec.items[i];
+
- /* remove single trailing slash from path, if needed */
- if (pi->len > 0 && pi->match[pi->len - 1] == '/') {
- path_alloc = xmemdupz(pi->match, pi->len - 1);
- path = path_alloc;
- } else
- path = pi->match;
--
-- len = strlen(path);
-- if (!len) {
-- revs->bloom_filter_settings = NULL;
-- free(path_alloc);
-- return;
-- }
--
-- p = path;
-- while (*p) {
-- /*
-- * At this point, the path is normalized to use Unix-style
-- * path separators. This is required due to how the
-- * changed-path Bloom filters store the paths.
-- */
-- if (*p == '/')
-- path_component_nr++;
-- p++;
-- }
--
-- revs->bloom_keyvecs_nr = 1;
-- CALLOC_ARRAY(revs->bloom_keyvecs, 1);
-- bloom_keyvec = bloom_keyvec_new(path_component_nr);
-- revs->bloom_keyvecs[0] = bloom_keyvec;
--
-- bloom_keyvec_fill_key(path, len, bloom_keyvec, 0,
-- revs->bloom_filter_settings);
-- path_component_nr = 1;
-+ revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr;
-+ CALLOC_ARRAY(revs->bloom_keyvecs, revs->bloom_keyvecs_nr);
-+ for (int i = 0; i < revs->pruning.pathspec.nr; i++) {
-+ pi = &revs->pruning.pathspec.items[i];
-+ path_component_nr = 1;
-+
+ /* remove single trailing slash from path, if needed */
+ if (pi->len > 0 && pi->match[pi->len - 1] == '/') {
+ path_alloc = xmemdupz(pi->match, pi->len - 1);
+ path = path_alloc;
+ } else
+ path = pi->match;
-+
+
+- len = strlen(path);
+- if (!len)
+- goto fail;
+ len = strlen(path);
+ if (!len)
+ goto fail;
-+
-+ p = path;
-+ while (*p) {
-+ /*
-+ * At this point, the path is normalized to use
-+ * Unix-style path separators. This is required due to
-+ * how the changed-path Bloom filters store the paths.
-+ */
-+ if (*p == '/')
-+ path_component_nr++;
-+ p++;
-+ }
-- p = path + len - 1;
-- while (p > path) {
-- if (*p == '/')
-- bloom_keyvec_fill_key(path, p - path, bloom_keyvec,
-- path_component_nr++,
-- revs->bloom_filter_settings);
-- p--;
-+ bloom_keyvec = bloom_keyvec_new(path_component_nr);
-+ revs->bloom_keyvecs[i] = bloom_keyvec;
-+
-+ bloom_keyvec_fill_key(path, len, bloom_keyvec, 0,
-+ revs->bloom_filter_settings);
-+ path_component_nr = 1;
-+
-+ p = path + len - 1;
-+ while (p > path) {
-+ if (*p == '/')
-+ bloom_keyvec_fill_key(path, p - path,
-+ bloom_keyvec,
-+ path_component_nr++,
-+ revs->bloom_filter_settings);
-+ p--;
-+ }
+- revs->bloom_keyvecs[0] =
+- bloom_keyvec_new(path, len, revs->bloom_filter_settings);
++ revs->bloom_keyvecs[i] =
++ bloom_keyvec_new(path, len, revs->bloom_filter_settings);
+ FREE_AND_NULL(path_alloc);
- }
++ }
if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
-@@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)
- bloom_filter_atexit_registered = 1;
- }
-
-+ return;
-+
-+fail:
-+ revs->bloom_filter_settings = NULL;
- free(path_alloc);
-+ release_revisions_bloom_keyvecs(revs);
- }
-
- static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
-@@ revision.c: static void release_revisions_mailmap(struct string_list *mailmap)
-
- static void release_revisions_topo_walk_info(struct topo_walk_info *info);
-
-+static void release_revisions_bloom_keyvecs(struct rev_info *revs)
-+{
-+ for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
-+ bloom_keyvec_free(revs->bloom_keyvecs[nr]);
-+ FREE_AND_NULL(revs->bloom_keyvecs);
-+ revs->bloom_keyvecs_nr = 0;
-+}
-+
- static void free_void_commit_list(void *list)
- {
- free_commit_list(list);
-@@ revision.c: void release_revisions(struct rev_info *revs)
- clear_decoration(&revs->treesame, free);
- line_log_free(revs);
- oidset_clear(&revs->missing_commits);
--
-- for (size_t i = 0; i < revs->bloom_keyvecs_nr; i++)
-- bloom_keyvec_free(revs->bloom_keyvecs[i]);
-- FREE_AND_NULL(revs->bloom_keyvecs);
-- revs->bloom_keyvecs_nr = 0;
-+ release_revisions_bloom_keyvecs(revs);
- }
-
- static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child)
+ atexit(trace2_bloom_filter_statistics_atexit);
## t/t4216-log-bloom.sh ##
@@ t/t4216-log-bloom.sh: sane_unset GIT_TRACE2_CONFIG_PARAMSSignature · 1 line
2.50.0.107.g33b6ec8c79
PATCH v5 1/4 bloom: add test helper to return murmur3 hash
In bloom.h, murmur3_seeded_v2() is exported for the use of test murmur3 hash. To clarify that murmur3_seeded_v2() is exported solely for testing purposes, a new helper function test_murmur3_seeded() was added instead of exporting murmur3_seeded_v2() directly.
--- bloom.c | 13 ++++++++++++- bloom.h | 12 +++--------- t/helper/test-bloom.c | 4 ++-- 3 files changed, 17 insertions(+), 12 deletions(-)
bloom.c +12 -1
@@ -107,7 +107,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,* Not considered to be cryptographically secure. * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm */ -uint32_t murmur3_seeded_v2 (uint32_t seed,const char *data,size_t len) +static uint32_t murmur3_seeded_v2 (uint32_t seed,const char *data,size_t len) {const uint32_t c1 =0xcc9e2d51 ;const uint32_t c2 =0x1b873593 ;
@@ -540,3 +540,14 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } + +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len, +int version) +{ +assert (version ==1 || version ==2 ); + +if (version ==2 ) +return murmur3_seeded_v2 (seed, data, len); +else +return murmur3_seeded_v1 (seed, data, len); +}
bloom.h +3 -9
@@ -78,15 +78,6 @@ int load_bloom_filter_from_graph(struct commit_graph *g,struct bloom_filter *filter, uint32_t graph_pos); -/* -* Calculate the murmur3 32-bit hash value for the given data -* using the given seed. -* Produces a uniformly distributed hash value. -* Not considered to be cryptographically secure. -* Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm -*/ -uint32_t murmur3_seeded_v2 (uint32_t seed,const char *data,size_t len); - void fill_bloom_key(const char *data, size_t len, struct bloom_key *key,
@@ -137,4 +128,7 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len, +int version); +#endif
t/helper/test-bloom.c +2 -2
@@ -61,13 +61,13 @@ int cmd__bloom(int argc, const char **argv)uint32_t hashed;if (argc <3 )usage (bloom_usage); - hashed =murmur3_seeded_v2 (0 , argv[2 ],strlen (argv[2 ])); + hashed =test_bloom_murmur3_seeded (0 , argv[2 ],strlen (argv[2 ]),2 );printf ("Murmur3 Hash with seed=0:0x%08x\n" , hashed); }if (!strcmp (argv[1 ],"get_murmur3_seven_highbit" )) {uint32_t hashed; - hashed =murmur3_seeded_v2 (0 ,"\x99\xaa\xbb\xcc\xdd\xee\xff" ,7 ); + hashed =test_bloom_murmur3_seeded (0 ,"\x99\xaa\xbb\xcc\xdd\xee\xff" ,7 ,2 );printf ("Murmur3 Hash with seed=0:0x%08x\n" , hashed); }
Signature · 1 line
2.50.0.107.g33b6ec8c79
PATCH v5 2/4 bloom: rename function operates on bloom_key
In reply to Lidong Yangit code style requires that functions operating on a struct S should be named in the form S_verb. However, the functions operating on struct bloom_key do not follow this convention. Therefore, fill_bloom_key() and clear_bloom_key() are renamed to bloom_key_fill() and bloom_key_clear(), respectively.
--- blame.c | 2 +- bloom.c | 10 ++++------ bloom.h | 6 ++---- line-log.c | 5 +++-- revision.c | 8 ++++---- t/helper/test-bloom.c | 4 ++-- 6 files changed, 16 insertions(+), 19 deletions(-)
blame.c +1 -1
@@ -1310,7 +1310,7 @@ static void add_bloom_key(struct blame_bloom_data *bd, } bd->keys[bd->nr] =xmalloc (sizeof (struct bloom_key )); -fill_bloom_key (path,strlen (path), bd->keys[bd->nr], bd->settings); +bloom_key_fill (bd->keys[bd->nr], path,strlen (path), bd->settings); bd->nr++; }
bloom.c +4 -6
@@ -221,9 +221,7 @@ static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len)return seed; } -void fill_bloom_key (const char *data, -size_t len, -struct bloom_key *key, +void bloom_key_fill (struct bloom_key *key,const char *data,size_t len,const struct bloom_filter_settings *settings) {int i;
@@ -243,7 +241,7 @@ void fill_bloom_key(const char *data, key->hashes[i] = hash0 + i * hash1; } -void clear_bloom_key (struct bloom_key *key) +void bloom_key_clear (struct bloom_key *key) {FREE_AND_NULL (key->hashes); }
@@ -500,9 +498,9 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,hashmap_for_each_entry (&pathmap, &iter, e, entry) {struct bloom_key key; -fill_bloom_key (e->path,strlen (e->path), &key, settings); +bloom_key_fill (&key, e->path,strlen (e->path), settings);add_key_to_filter (&key, filter, settings); -clear_bloom_key (&key); +bloom_key_clear (&key); } cleanup:
bloom.h +2 -4
@@ -78,11 +78,9 @@ int load_bloom_filter_from_graph(struct commit_graph *g,struct bloom_filter *filter, uint32_t graph_pos); -void fill_bloom_key (const char *data, -size_t len, -struct bloom_key *key, +void bloom_key_fill (struct bloom_key *key,const char *data,size_t len,const struct bloom_filter_settings *settings); -void clear_bloom_key (struct bloom_key *key); +void bloom_key_clear (struct bloom_key *key); void add_key_to_filter(const struct bloom_key *key, struct bloom_filter *filter,
line-log.c +3 -2
@@ -1172,12 +1172,13 @@ static int bloom_filter_check(struct rev_info *rev,return 0 ;while (!result && range) { -fill_bloom_key (range->path,strlen (range->path), &key, rev->bloom_filter_settings); +bloom_key_fill (&key, range->path,strlen (range->path), + rev->bloom_filter_settings);if (bloom_filter_contains (filter, &key, rev->bloom_filter_settings)) result =1 ; -clear_bloom_key (&key); +bloom_key_clear (&key); range = range->next; }
revision.c +4 -4
@@ -739,15 +739,15 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) revs->bloom_keys_nr = path_component_nr;ALLOC_ARRAY (revs->bloom_keys, revs->bloom_keys_nr); -fill_bloom_key (path, len, &revs->bloom_keys[0 ], +bloom_key_fill (&revs->bloom_keys[0 ], path, len, revs->bloom_filter_settings); path_component_nr =1 ; p = path + len -1 ;while (p > path) {if (*p =='/' ) -fill_bloom_key (path, p - path, - &revs->bloom_keys[path_component_nr++], +bloom_key_fill (&revs->bloom_keys[path_component_nr++], + path, p - path, revs->bloom_filter_settings); p--; }
@@ -3231,7 +3231,7 @@ void release_revisions(struct rev_info *revs)oidset_clear (&revs->missing_commits);for (int i =0 ; i < revs->bloom_keys_nr; i++) -clear_bloom_key (&revs->bloom_keys[i]); +bloom_key_clear (&revs->bloom_keys[i]);FREE_AND_NULL (revs->bloom_keys); revs->bloom_keys_nr =0 ; }
t/helper/test-bloom.c +2 -2
@@ -12,13 +12,13 @@ static struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;static void add_string_to_filter (const char *data,struct bloom_filter *filter) {struct bloom_key key; -fill_bloom_key (data,strlen (data), &key, &settings); +bloom_key_fill (&key, data,strlen (data), &settings);printf ("Hashes:" );for (size_t i =0 ; i < settings.num_hashes; i++)printf ("0x%08x|" , key.hashes[i]);printf ("\n" );add_key_to_filter (&key, filter, &settings); -clear_bloom_key (&key); +bloom_key_clear (&key); }static void print_bloom_filter (struct bloom_filter *filter) {
Signature · 1 line
2.50.0.107.g33b6ec8c79
PATCH v5 3/4 bloom: replace struct bloom_key * with struct bloom_keyvec
In reply to Lidong YanPreviously, we stored bloom keys in a flat array and marked a commit as NOT TREESAME if any key reported "definitely not changed".
To support multiple pathspec items, we now require that for each pathspec item, there exists a bloom key reporting "definitely not changed".
This "for every" condition makes a flat array insufficient, so we introduce a new structure to group keys by a single pathspec item. struct bloom_keyvec is introduced to replace struct bloom_key * and bloom_key_nr. And because we want to support multiple pathspec items, we added a bloom_keyvec * and a bloom_keyvec_nr field to struct rev_info to represent an array of bloom_keyvecs. This commit still optimize only one pathspec item, thus bloom_keyvec_nr can only be 0 or 1.
New bloom_keyvec_* functions are added to create and destroy a keyvec. bloom_filter_contains_vec() is added to check if all key in keyvec is contained in a bloom filter.
--- bloom.c | 61 ++++++++++++++++++++++++++++++++++++++++++++ bloom.h | 38 +++++++++++++++++++++++++++ revision.c | 75 ++++++++++++++++++++++-------------------------------- revision.h | 6 ++--- 4 files changed, 132 insertions(+), 48 deletions(-)
bloom.c +61 -0
@@ -278,6 +278,55 @@ void deinit_bloom_filters(void)deep_clear_bloom_filter_slab (&bloom_filters, free_one_bloom_filter); } +struct bloom_keyvec *bloom_keyvec_new (const char *path,size_t len, +const struct bloom_filter_settings *settings) +{ +struct bloom_keyvec *vec; +const char *p; +size_t sz; +size_t nr =1 ; + + p = path; +while (*p) { +/* +* At this point, the path is normalized to use Unix-style +* path separators. This is required due to how the +* changed-path Bloom filters store the paths. +*/ +if (*p =='/' ) + nr++; + p++; + } + + sz =sizeof (struct bloom_keyvec ); + sz += nr *sizeof (struct bloom_key ); + vec = (struct bloom_keyvec *)xcalloc (1 , sz); +if (!vec) +return NULL ; + vec->count = nr; + +bloom_key_fill (&vec->key[0 ], path, len, settings); + nr =1 ; + p = path + len -1 ; +while (p > path) { +if (*p =='/' ) { +bloom_key_fill (&vec->key[nr++], path, p - path, settings); + } + p--; + } +assert (nr == vec->count); +return vec; +} + +void bloom_keyvec_free (struct bloom_keyvec *vec) +{ +if (!vec) +return ; +for (size_t nr =0 ; nr < vec->count; nr++) +bloom_key_clear (&vec->key[nr]); +free (vec); +} + static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, const struct hashmap_entry *eptr, const struct hashmap_entry *entry_or_key,
@@ -539,6 +588,18 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *vec, +const struct bloom_filter_settings *settings) +{ +int ret =1 ; + +for (size_t nr =0 ; ret >0 && nr < vec->count; nr++) + ret =bloom_filter_contains (filter, &vec->key[nr], settings); + +return ret; +} +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len,int version) {
bloom.h +38 -0
@@ -74,6 +74,16 @@ struct bloom_key {uint32_t *hashes; }; +/* +* A bloom_keyvec is a vector of bloom_keys, which +* can be used to store multiple keys for a single +* pathspec item. +*/ +struct bloom_keyvec { +size_t count; +struct bloom_key key[FLEX_ARRAY ]; +}; +int load_bloom_filter_from_graph (struct commit_graph *g,struct bloom_filter *filter,uint32_t graph_pos);
@@ -82,6 +92,23 @@ void bloom_key_fill(struct bloom_key *key, const char *data, size_t len, const struct bloom_filter_settings *settings);void bloom_key_clear (struct bloom_key *key); +/* +* bloom_keyvec_fill - Allocate and populate a bloom_keyvec with keys for the +* given path. +* +* This function splits the input path by '/' and generates a bloom key for each +* prefix, in reverse order of specificity. For example, given the input +* "a/b/c", it will generate bloom keys for: +* - "a/b/c" +* - "a/b" +* - "a" +* +* The resulting keys are stored in a newly allocated bloom_keyvec. +*/ +struct bloom_keyvec *bloom_keyvec_new (const char *path,size_t len, +const struct bloom_filter_settings *settings); +void bloom_keyvec_free (struct bloom_keyvec *vec); +void add_key_to_filter (const struct bloom_key *key,struct bloom_filter *filter,const struct bloom_filter_settings *settings);
@@ -126,6 +153,17 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +/* +* bloom_filter_contains_vec - Check if all keys in a key vector are in the +* Bloom filter. +* +* Returns 1 if **all** keys in the vector are present in the filter, +* 0 if **any** key is not present. +*/ +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *v, +const struct bloom_filter_settings *settings); +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len,int version);
revision.c +30 -45
143 lines not on this page · raw message
revision.h +3 -3
@@ -62,7 +62,7 @@ struct repository;struct rev_info ;struct string_list ;struct saved_parents ; -struct bloom_key ; +struct bloom_keyvec ;struct bloom_filter_settings ;struct option ;struct parse_opt_ctx_t ;
@@ -360,8 +360,8 @@ struct rev_info {/* Commit graph bloom filter fields */ /* The bloom filter key(s) for the pathspec */ -struct bloom_key *bloom_keys; -int bloom_keys_nr; +struct bloom_keyvec **bloom_keyvecs; +int bloom_keyvecs_nr;/* * The bloom filter settings used to generate the key.
Signature · 1 line
2.50.0.107.g33b6ec8c79
Re: [PATCH v5 3/4] bloom: replace struct bloom_key * with struct bloom_keyvec
revision.c static int forbid_bloom_filters(struct pathspec *spec) · line 693
Quoted 4 lines · Lidong Yan
static void
prepare_to_use_bloom_filter(struct rev_info *revs){revision.c +1
-0struct pathspec_item *pi; +struct bloom_keyvec *bloom_keyvec;
This new variable is no longer used, since the code to create a new keyvec is in a helper function and its return value is directly stored in the array of keyvecs.
revision.c static int forbid_bloom_filters(struct pathspec *spec) · line 695
Quoted 2 lines
revision.c +0
-0char *path_alloc =NULL ;const char *path, *p;
And the "p" variable no longer is used, because the logic it used to create a new keyvec is moved elsewhere.
Re: [PATCH v5 3/4] bloom: replace struct bloom_key * with struct bloom_keyvec
Junio C Hamano <[email protected]> write:
Quoted 12 lines
Quoted 4 lines · Lidong Yan
static void
prepare_to_use_bloom_filter(struct rev_info *revs){
structpathspec_item*pi;
+ structbloom_keyvec*bloom_keyvec;This new variable is no longer used, since the code to create a new keyvec is in a helper function and its return value is directly stored in the array of keyvecs.
Quoted 5 lines
Quoted 2 lines
char
*path_alloc= NULL;
const char *path, *p;And the "p" variable no longer is used, because the logic it used to create a new keyvec is moved elsewhere.
Will fix in v6, Thanks,
Lidong
Re: [PATCH v5 3/4] bloom: replace struct bloom_key * with struct bloom_keyvec
Quoted 13 lines · Lidong Yan
Junio C Hamano <[email protected]> write:
Quoted 12 lines
Quoted 4 lines · Lidong Yan
static void
prepare_to_use_bloom_filter(struct rev_info *revs){
structpathspec_item*pi;
+ structbloom_keyvec*bloom_keyvec;This new variable is no longer used, since the code to create a new keyvec is in a helper function and its return value is directly stored in the array of keyvecs.
Quoted 7 lines
Quoted 5 lines
Quoted 2 lines
char
*path_alloc= NULL;
const char *path, *p;And the "p" variable no longer is used, because the logic it used to create a new keyvec is moved elsewhere.
Will fix in v6, Thanks,
FWIW, what I queued have these two already removed from v5.
Thanks.
PATCH v5 4/4 bloom: optimize multiple pathspec items in revision traversal
In reply to Lidong YanTo enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in forbid_bloom_filters(). Add for loops to initialize and check each pathspec item's bloom_keyvec when optimization is possible.
Add new test cases in t/t4216-log-bloom.sh to ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
--- revision.c | 38 ++++++++++++++++++++------------------ t/t4216-log-bloom.sh | 23 ++++++++++++++--------- 2 files changed, 34 insertions(+), 27 deletions(-)
revision.c +20 -18
@@ -675,12 +675,11 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ; -if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL )) -return 1 ; +for (size_t nr =0 ; nr < spec->nr; nr++) +if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +return 1 ;return 0 ; }
@@ -710,23 +709,26 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - pi = &revs->pruning.pathspec.items[0 ]; + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { + pi = &revs->pruning.pathspec.items[i]; -/* remove single trailing slash from path, if needed */ -if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { - path_alloc =xmemdupz (pi->match, pi->len -1 ); - path = path_alloc; - }else - path = pi->match; +/* remove single trailing slash from path, if needed */ +if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { + path_alloc =xmemdupz (pi->match, pi->len -1 ); + path = path_alloc; + }else + path = pi->match; - len =strlen (path); -if (!len) - goto fail; + len =strlen (path); +if (!len) + goto fail; - revs->bloom_keyvecs[0 ] = -bloom_keyvec_new (path, len, revs->bloom_filter_settings); + revs->bloom_keyvecs[i] = +bloom_keyvec_new (path, len, revs->bloom_filter_settings); +FREE_AND_NULL (path_alloc); + }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {atexit (trace2_bloom_filter_statistics_atexit);
t/t4216-log-bloom.sh +14 -9
@@ -66,8 +66,9 @@ sane_unset GIT_TRACE2_CONFIG_PARAMS setup () { rm -f "$TRASH_DIRECTORY/trace.perf" && - git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom && - GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom + eval git -c core.commitGraph=false log --pretty="format:%s" "$1" >log_wo_bloom && + eval "GIT_TRACE2_PERF=\"$TRASH_DIRECTORY/trace.perf\"" \ + git -c core.commitGraph=true log --pretty="format:%s" "$1" >log_w_bloom } test_bloom_filters_used () {
@@ -138,10 +139,6 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' ' test_bloom_filters_not_used "--walk-reflogs -- A" ' -test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" -' - test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' ' test_bloom_filters_not_used "-- ." '
@@ -151,9 +148,17 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used "-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with multiple literal paths uses Bloom filter' ' + test_bloom_filters_used "-- file4 A/file1" && + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" +' + +test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' + test_bloom_filters_not_used "-- file\*" && + test_bloom_filters_not_used "-- A/\* file4" && + test_bloom_filters_not_used "-- file4 A/\*" && + test_bloom_filters_not_used "-- * A/\*" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.50.0.107.g33b6ec8c79
PATCH 1/1 revision: make helper for pathspec to bloom key
Quoted 28 lines · Lidong Yan
(quoted diff) +10
-12@@ -710,23 +709,26 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) if (!revs->pruning.pathspec.nr) return; - revs->bloom_keyvecs_nr = 1; - CALLOC_ARRAY(revs->bloom_keyvecs, 1); - pi = &revs->pruning.pathspec.items[0]; + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; + CALLOC_ARRAY(revs->bloom_keyvecs, revs->bloom_keyvecs_nr); + for (int i = 0; i < revs->pruning.pathspec.nr; i++) { + pi = &revs->pruning.pathspec.items[i]; - /* remove single trailing slash from path, if needed */ - if (pi->len > 0 && pi->match[pi->len - 1] == '/') { - path_alloc = xmemdupz(pi->match, pi->len - 1); - path = path_alloc; - } else - path = pi->match; + /* remove single trailing slash from path, if needed */ + if (pi->len > 0 && pi->match[pi->len - 1] == '/') { + path_alloc = xmemdupz(pi->match, pi->len - 1); + path = path_alloc; + } else + path = pi->match; - len = strlen(path); - if (!len) - goto fail;
Review static void prepare_to_use_bloom_filter(struct rev_info *revs) · line 731
Quoted 10 lines
(quoted diff) +7
-2+ len = strlen(path); + if (!len) + goto fail; - revs->bloom_keyvecs[0] = - bloom_keyvec_new(path, len, revs->bloom_filter_settings); + revs->bloom_keyvecs[i] = + bloom_keyvec_new(path, len, revs->bloom_filter_settings); + FREE_AND_NULL(path_alloc); + }
This diff is still bigger than I was hoping, so I'm sending a couple of patches that simplify this code movement. Feel free to ignore them as being too nit-picky.
--- >8 ---
From 69fa36dc615e140ae842b536f7da792beaebb272 Mon Sep 17 00:00:00 2001
From: Derrick Stolee <[email protected]>
Date: Thu, 10 Jul 2025 08:06:29 -0400
Subject: [PATCH v5.1 3.5/4] revision: make helper for pathspec to bloom key
When preparing to use bloom filters in a revision walk, Git populates a boom_keyvec with an array of bloom keys for the components of a path. Before we create the ability to map multiple pathspecs to multiple bloom_keyvecs, extract the conversion from a pathspec to a bloom_keyvec into its own helper method. This simplifies the state that persists in prepare_to_use_bloom_filter() as well as makes the next change much simpler.
--- revision.c | 50 +++++++++++++++++++++++++++++++------------------- 1 file changed, 31 insertions(+), 19 deletions(-)
revision.c +31 -19
@@ -687,14 +687,37 @@ static int forbid_bloom_filters(struct pathspec *spec)static void release_revisions_bloom_keyvecs (struct rev_info *revs); -static void prepare_to_use_bloom_filter (struct rev_info *revs) +static int convert_pathspec_to_filter (const struct pathspec_item *pi, +struct bloom_keyvec **bloom_keyvec, +const struct bloom_filter_settings *settings) { -struct pathspec_item *pi; -struct bloom_keyvec *bloom_keyvec; -char *path_alloc =NULL ; -const char *path, *p;size_t len; +const char *path; +char *path_alloc =NULL ; +int res =0 ; + +/* remove single trailing slash from path, if needed */ +if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { + path_alloc =xmemdupz (pi->match, pi->len -1 ); + path = path_alloc; + }else + path = pi->match; + + len =strlen (path); +if (!len) { + res =-1 ; + goto cleanup; + } + + *bloom_keyvec =bloom_keyvec_new (path, len, settings); +cleanup: +FREE_AND_NULL (path_alloc); +return res; +} + +static void prepare_to_use_bloom_filter (struct rev_info *revs) +{if (!revs->commits)return ;
@@ -712,22 +735,12 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) revs->bloom_keyvecs_nr =1 ;CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - pi = &revs->pruning.pathspec.items[0 ]; -/* remove single trailing slash from path, if needed */ -if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { - path_alloc =xmemdupz (pi->match, pi->len -1 ); - path = path_alloc; - }else - path = pi->match; - - len =strlen (path); -if (!len) +if (convert_pathspec_to_filter (&revs->pruning.pathspec.items[0 ], + &revs->bloom_keyvecs[0 ], + revs->bloom_filter_settings)) goto fail; - revs->bloom_keyvecs[0 ] = -bloom_keyvec_new (path, len, revs->bloom_filter_settings); -if (trace2_is_enabled () && !bloom_filter_atexit_registered) {atexit (trace2_bloom_filter_statistics_atexit); bloom_filter_atexit_registered =1 ;
@@ -737,7 +750,6 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) fail: revs->bloom_filter_settings =NULL ; -free (path_alloc);release_revisions_bloom_keyvecs (revs); }
Signature · 1 line
2.47.2.vfs.0.2
Re: [PATCH v5.1 3.5/4] revision: make helper for pathspec to bloom key
Quoted 54 lines · Derrick Stolee
This diff is still bigger than I was hoping, so I'm sending a couple of patches that simplify this code movement. Feel free to ignore them as being too nit-picky.
--- >8 ---
From
69fa36dc615e140ae842b536f7da792beaebb272Mon Sep 17 00:00:00 2001
From: Derrick Stolee <[email protected]>
Date: Thu, 10 Jul 2025 08:06:29 -0400
Subject: [PATCH v5.1 3.5/4] revision: make helper for pathspec to bloom keyWhen preparing to use bloom filters in a revision walk, Git populates a
boom_keyvecwith an array of bloom keys for the components of a path. Before we create the ability to map multiple pathspecs to multiplebloom_keyvecs, extract the conversion from a pathspec to abloom_keyvecinto its own helper method. This simplifies the state that persists inprepare_to_use_bloom_filter()as well as makes the next change much simpler.Signed-off-by Derrick Stolee <[email protected]>---
revision.c| 50 +++++++++++++++++++++++++++++++-------------------1 file changed, 31 insertions(+), 19 deletions(-)revision.c +14
-5@@ -687,14 +687,37 @@ static int forbid_bloom_filters(struct pathspec *spec)static void release_revisions_bloom_keyvecs (struct rev_info *revs); -static void prepare_to_use_bloom_filter (struct rev_info *revs) +static int convert_pathspec_to_filter (const struct pathspec_item *pi, +struct bloom_keyvec **bloom_keyvec, +const struct bloom_filter_settings *settings) { -struct pathspec_item *pi; -struct bloom_keyvec *bloom_keyvec; -char *path_alloc =NULL ; -const char *path, *p;size_t len; +const char *path; +char *path_alloc =NULL ; +int res =0 ; + +/* remove single trailing slash from path, if needed */ +if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { + path_alloc =xmemdupz (pi->match, pi->len -1 ); + path = path_alloc; + }else + path = pi->match; +
revision.c static int forbid_bloom_filters(struct pathspec *spec) · line 715
Quoted 10 lines
revision.c +9
-0+ len =strlen (path); +if (!len) { + res =-1 ; + goto cleanup; + } + + *bloom_keyvec =bloom_keyvec_new (path, len, settings); +cleanup: +FREE_AND_NULL (path_alloc);
I think we don’t need to NULL path_alloc here, but it doesn’t hurt.
Quoted 36 lines
revision.c +8
-13+return res; +} + +static void prepare_to_use_bloom_filter (struct rev_info *revs) +{if (!revs->commits)return ;@@ -712,22 +735,12 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) revs->bloom_keyvecs_nr =1 ;CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - pi = &revs->pruning.pathspec.items[0 ]; -/* remove single trailing slash from path, if needed */ -if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { - path_alloc =xmemdupz (pi->match, pi->len -1 ); - path = path_alloc; - }else - path = pi->match; - - len =strlen (path); -if (!len) +if (convert_pathspec_to_filter (&revs->pruning.pathspec.items[0 ], + &revs->bloom_keyvecs[0 ], + revs->bloom_filter_settings)) goto fail; - revs->bloom_keyvecs[0 ] = -bloom_keyvec_new (path, len, revs->bloom_filter_settings); -if (trace2_is_enabled () && !bloom_filter_atexit_registered) {atexit (trace2_bloom_filter_statistics_atexit); bloom_filter_atexit_registered =1 ;@@ -737,7 +750,6 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)
Quoted 8 lines
fail:
revs->bloom_filter_settings= NULL;
-free(path_alloc);release_revisions_bloom_keyvecs(revs);
}Signature · 1 line
2.47.2.vfs.0.2
This looks perfect to me. I would squash patch 3.5 to patch 3 in v6.
Thanks for your patch,
Lidong
PATCH 4/4 bloom: optimize multiple pathspec items in revision
In reply to Lidong YanQuoted 28 lines · Lidong Yan
(quoted diff) +10
-12@@ -710,23 +709,26 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) if (!revs->pruning.pathspec.nr) return; - revs->bloom_keyvecs_nr = 1; - CALLOC_ARRAY(revs->bloom_keyvecs, 1); - pi = &revs->pruning.pathspec.items[0]; + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; + CALLOC_ARRAY(revs->bloom_keyvecs, revs->bloom_keyvecs_nr); + for (int i = 0; i < revs->pruning.pathspec.nr; i++) { + pi = &revs->pruning.pathspec.items[i]; - /* remove single trailing slash from path, if needed */ - if (pi->len > 0 && pi->match[pi->len - 1] == '/') { - path_alloc = xmemdupz(pi->match, pi->len - 1); - path = path_alloc; - } else - path = pi->match; + /* remove single trailing slash from path, if needed */ + if (pi->len > 0 && pi->match[pi->len - 1] == '/') { + path_alloc = xmemdupz(pi->match, pi->len - 1); + path = path_alloc; + } else + path = pi->match; - len = strlen(path); - if (!len) - goto fail;
Review static void prepare_to_use_bloom_filter(struct rev_info *revs) · line 731
Quoted 10 lines
(quoted diff) +7
-2+ len = strlen(path); + if (!len) + goto fail; - revs->bloom_keyvecs[0] = - bloom_keyvec_new(path, len, revs->bloom_filter_settings); + revs->bloom_keyvecs[i] = + bloom_keyvec_new(path, len, revs->bloom_filter_settings); + FREE_AND_NULL(path_alloc); + }
Focus on the change to this diff when the patch below is applied on top of the 3.5/4 I sent earlier, resulting in this diff:
@@ -733,13 +732,14 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)
if (!revs->pruning.pathspec.nr)
return;
- revs->bloom_keyvecs_nr = 1;
- CALLOC_ARRAY(revs->bloom_keyvecs, 1);
-
- if (convert_pathspec_to_filter(&revs->pruning.pathspec.items[0],
- &revs->bloom_keyvecs[0],
- revs->bloom_filter_settings))
- goto fail;
+ revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr;
+ CALLOC_ARRAY(revs->bloom_keyvecs, revs->bloom_keyvecs_nr);
+ for (int i = 0; i < revs->pruning.pathspec.nr; i++) {
+ if (convert_pathspec_to_filter(&revs->pruning.pathspec.items[i],
+ &revs->bloom_keyvecs[i],
+ revs->bloom_filter_settings))
+ goto fail;
+ }
if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
atexit(trace2_bloom_filter_statistics_atexit);
Also, I've included the hyperfine performance output in the commit message.
Thanks,
-Stolee
--- >8 ---
From fe255b1acfbe90fa8e4c335435ae18ee95e6243c Mon Sep 17 00:00:00 2001
From: Lidong Yan <[email protected]>
Date: Thu, 10 Jul 2025 08:04:34 -0400
Subject: [PATCH v5.1 4/4] bloom: optimize multiple pathspec items in revision
traversal
To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in forbid_bloom_filters(). Add for loops to initialize and check each pathspec item's bloom_keyvec when optimization is possible.
Add new test cases in t/t4216-log-bloom.sh to ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
With these optimizations, we get some improvements for multi-pathspec runs of 'git log'. First, in the Git repository we see these modest results:
Benchmark 1: old
Time (mean ± σ): 73.1 ms ± 2.9 ms Range (min … max): 69.9 ms … 84.5 ms 42 runs
Benchmark 2: new
Time (mean ± σ): 55.1 ms ± 2.9 ms Range (min … max): 51.1 ms … 61.2 ms 52 runs
Summary
'new' ran
1.33 ± 0.09 times faster than 'old'
But in a larger repo, such as the LLVM project repo below, we get even better results:
Benchmark 1: old
Time (mean ± σ): 1.974 s ± 0.006 s
Range (min … max): 1.960 s … 1.983 s 10 runs
Benchmark 2: new
Time (mean ± σ): 262.9 ms ± 2.4 ms
Range (min … max): 257.7 ms … 266.2 ms 11 runs
Summary
'new' ran
7.51 ± 0.07 times faster than 'old'
--- revision.c | 22 +++++++++++----------- t/t4216-log-bloom.sh | 23 ++++++++++++++--------- 2 files changed, 25 insertions(+), 20 deletions(-)
revision.c +11 -11
@@ -675,12 +675,11 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ; -if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL )) -return 1 ; +for (size_t nr =0 ; nr < spec->nr; nr++) +if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +return 1 ;return 0 ; }
@@ -733,13 +732,14 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - -if (convert_pathspec_to_filter (&revs->pruning.pathspec.items[0 ], - &revs->bloom_keyvecs[0 ], - revs->bloom_filter_settings)) - goto fail; + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { +if (convert_pathspec_to_filter (&revs->pruning.pathspec.items[i], + &revs->bloom_keyvecs[i], + revs->bloom_filter_settings)) + goto fail; + }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {atexit (trace2_bloom_filter_statistics_atexit);
t/t4216-log-bloom.sh +14 -9
@@ -66,8 +66,9 @@ sane_unset GIT_TRACE2_CONFIG_PARAMS setup () { rm -f "$TRASH_DIRECTORY/trace.perf" && - git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom && - GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom + eval git -c core.commitGraph=false log --pretty="format:%s" "$1" >log_wo_bloom && + eval "GIT_TRACE2_PERF=\"$TRASH_DIRECTORY/trace.perf\"" \ + git -c core.commitGraph=true log --pretty="format:%s" "$1" >log_w_bloom } test_bloom_filters_used () {
@@ -138,10 +139,6 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' ' test_bloom_filters_not_used "--walk-reflogs -- A" ' -test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" -' - test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' ' test_bloom_filters_not_used "-- ." '
@@ -151,9 +148,17 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used "-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with multiple literal paths uses Bloom filter' ' + test_bloom_filters_used "-- file4 A/file1" && + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" +' + +test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' + test_bloom_filters_not_used "-- file\*" && + test_bloom_filters_not_used "-- A/\* file4" && + test_bloom_filters_not_used "-- file4 A/\*" && + test_bloom_filters_not_used "-- * A/\*" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.47.2.vfs.0.2
Re: [PATCH v5.1 4/4] bloom: optimize multiple pathspec items in revision
Quoted 42 lines · Derrick Stolee
--- >8 ---
From
fe255b1acfbe90fa8e4c335435ae18ee95e6243cMon Sep 17 00:00:00 2001
From: Lidong Yan <[email protected]>
Date: Thu, 10 Jul 2025 08:04:34 -0400
Subject: [PATCH v5.1 4/4] bloom: optimize multiple pathspec items in revision traversalTo enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in
forbid_bloom_filters(). Add for loops to initialize and check each pathspec item'sbloom_keyvecwhen optimization is possible.Add new test cases in
t/t4216-log-bloom.shto ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.With these optimizations, we get some improvements for multi-pathspec runs of 'git log'. First, in the Git repository we see these modest results:
Benchmark 1: old
Time (mean ± σ): 73.1 ms ± 2.9 ms Range (min … max): 69.9 ms … 84.5 ms 42 runsBenchmark 2: new
Time (mean ± σ): 55.1 ms ± 2.9 ms Range (min … max): 51.1 ms … 61.2 ms 52 runsSummary
'new' ran
1.33 ± 0.09 times faster than 'old'But in a larger repo, such as the LLVM project repo below, we get even better results:
Benchmark 1: old
Time (mean ± σ): 1.974 s ± 0.006 s
Range (min … max): 1.960 s … 1.983 s 10 runs
Quoted 7 lines
Benchmark 2: new
Time (mean ± σ): 262.9 ms ± 2.4 ms
Range (min … max): 257.7 ms … 266.2 ms 11 runsSummary
'new' ran
7.51 ± 0.07 times faster than 'old'
Hyperfine do looks better. I will put this into commit message and cover letter in v6.
Quoted 97 lines
Signed-off-by Lidong Yan <[email protected]>Signed-off-by Derrick Stolee <[email protected]>---
revision.c| 22 +++++++++++-----------t/t4216-log-bloom.sh| 23 ++++++++++++++---------2 files changed, 25 insertions(+), 20 deletions(-)revision.c +11
-11@@ -675,12 +675,11 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ; -if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL )) -return 1 ; +for (size_t nr =0 ; nr < spec->nr; nr++) +if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +return 1 ;return 0 ; }@@ -733,13 +732,14 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - -if (convert_pathspec_to_filter (&revs->pruning.pathspec.items[0 ], - &revs->bloom_keyvecs[0 ], - revs->bloom_filter_settings)) - goto fail; + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { +if (convert_pathspec_to_filter (&revs->pruning.pathspec.items[i], + &revs->bloom_keyvecs[i], + revs->bloom_filter_settings)) + goto fail; + }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {atexit (trace2_bloom_filter_statistics_atexit);t/t4216-log-bloom.sh +0
-0@@ -66,8 +66,9 @@ sane_unset GIT_TRACE2_CONFIG_PARAMS setup () {rm -f "$TRASH_DIRECTORY/trace.perf" &&
- git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom &&
- GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom
+ eval git -c core.commitGraph=false log --pretty="format:%s" "$1" >log_wo_bloom &&
+ eval "GIT_TRACE2_PERF=\"$TRASH_DIRECTORY/trace.perf\"" \
+ git -c core.commitGraph=true log --pretty="format:%s" "$1" >log_w_bloom
}
test_bloom_filters_used() {t/t4216-log-bloom.sh +0
-0@@ -138,10 +139,6 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' '
test_bloom_filters_not_used"--walk-reflogs -- A"
't/t4216-log-bloom.sh +0
-4-test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" -' -
test_expect_success'git log -- "." pathspec at root does not use Bloom filters' 'test_bloom_filters_not_used"-- ."
't/t4216-log-bloom.sh +0
-0@@ -151,9 +148,17 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B
test_bloom_filters_used"-- *renamed"
't/t4216-log-bloom.sh +11
-3-test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with multiple literal paths uses Bloom filter' ' + test_bloom_filters_used "-- file4 A/file1" && + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" +' + +test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' + test_bloom_filters_not_used "-- file\*" && + test_bloom_filters_not_used "-- A/\* file4" && + test_bloom_filters_not_used "-- file4 A/\*" && + test_bloom_filters_not_used "-- * A/\*"'
Quoted 4 lines
test_expect_success'setup - add commit-graph to the chain without Bloom filters' 'Signature · 1 line
2.47.2.vfs.0.2
Looks great, I will apply this above patch 3.
Thanks,
Lidong
Re: [PATCH v5 0/4] bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
In reply to Lidong YanQuoted 28 lines · Lidong Yan
The difference from v4 is:
- for the bloom_key_* functions, we now pass structbloom_key* as the first parameter.
-bloom_keyvec_fill_key()andbloom_keyvec_new()have been merged into a single function, so that each key is filled during the creation of thebloom_keyvec.Below is a comparison of the time taken to run git log on Git and LLVM repositories before and after applying this patch.
Setup commit-graph:
$ cd ~/src/git && git commit-graph write --split --reachable --changed-paths $ cd ~/src/llvm && git commit-graph write --split --reachable --changed-pathsRun git log on Git repository
$ cd ~/src/git $ hash -p /usr/bin/git git # my system git binary is 2.43.0 $ time git log -100 -- commit.c commit-graph.c >/dev/null real 0m0.055s user 0m0.040s sys 0m0.015s $ hash -p ~/bin/git/bin/git git $ time git log -100 -- commit.c commit-graph.c >/dev/null real 0m0.039s user 0m0.020s sys 0m0.020sRun git log in LLVM repository
Quoted 11 lines
$ cd ~/src/llvm $ hash -p /usr/bin/git git # my system git binary is 2.43.0 $ time git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h >/dev/null real 0m2.365s user 0m2.252s sys 0m0.113s $ hash -p ~/bin/git/bin/git git $ time git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h >/dev/null real 0m0.240s user 0m0.158s sys 0m0.064s
Thanks for these stats, though I'd recommend trying hyperfine [1] which with this setup would let you run these experiments as the following:
$ $ hyperfine --warmup=3 \
Review
Quoted 2 lines
(quoted diff) +0
-2-n 'old' '~/_git/git-sparse-checkout-clean/git log -100 -- commit.c commit-graph.c' \ -n 'new' '~/_git/git/git log -100 -- commit.c commit-graph.c'
Benchmark 1: old
Time (mean ± σ): 73.1 ms ± 2.9 ms [User: 48.8 ms, System: 23.9 ms] Range (min … max): 69.9 ms … 84.5 ms 42 runs
Benchmark 2: new
Time (mean ± σ): 55.1 ms ± 2.9 ms [User: 30.5 ms, System: 24.4 ms] Range (min … max): 51.1 ms … 61.2 ms 52 runs
Summary
'new' ran
1.33 ± 0.09 times faster than 'old'
And for LLVM:
$ hyperfine --warmup=3 \
Review
Quoted 2 lines
(quoted diff) +0
-2-n 'old' '~/_git/git-sparse-checkout-clean/git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h' \ -n 'new' '~/_git/git/git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h'
Benchmark 1: old
Time (mean ± σ): 1.974 s ± 0.006 s [User: 1.877 s, System: 0.097 s]
Range (min … max): 1.960 s … 1.983 s 10 runs
Benchmark 2: new
Time (mean ± σ): 262.9 ms ± 2.4 ms [User: 214.2 ms, System: 48.4 ms]
Range (min … max): 257.7 ms … 266.2 ms 11 runs
Summary
'new' ran
7.51 ± 0.07 times faster than 'old'
[1] https://github.com/sharkdp/hyperfine
Finally, putting these performance numbers in the commit message will make the results permanently findable in the repo history.
Quoted 37 lines
3:
c042907b92! 3:60a3b16bbbbloom: replace structbloom_key* with structbloom_keyvec-+struct bloom_keyvec *bloom_keyvec_new(size_t count) ++struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len, ++ const struct bloom_filter_settings *settings) +{ + struct bloom_keyvec *vec; -+ size_t sz = sizeof(struct bloom_keyvec); -+ sz += count * sizeof(struct bloom_key); ++ const char *p; ++ size_t sz; ++ size_t nr = 1; ++ ++ p = path; ++ while (*p) { ++ /* ++ * At this point, the path is normalized to use Unix-style ++ * path separators. This is required due to how the ++ * changed-path Bloom filters store the paths. ++ */ ++ if (*p == '/') ++ nr++; ++ p++; ++ } ++ ++ sz = sizeof(struct bloom_keyvec); ++ sz += nr * sizeof(struct bloom_key); + vec = (struct bloom_keyvec *)xcalloc(1, sz); -+ vec->count = count; ++ if (!vec) ++ return NULL; ++ vec->count = nr; ++ ++ bloom_key_fill(&vec->key[0], path, len, settings); ++ nr = 1; ++ p = path + len - 1; ++ while (p > path) {
Quoted 8 lines
++ if (*p == '/') {
++ bloom_key_fill(&vec->key[nr++], path, p - path, settings);
++ }
++ p--;
++ }
++ assert(nr == vec->count);
+ return vec;
+}These additions to bloom_keyvec_new() certainly help simplify some of the code movement I was talking about, but there is more that can be done to simplify patch 4. I'll send a couple example patches in reply to patch 4 with what I mean.
Overall, the patch series is correct. My complaints are stylistic more than anything.
Thanks,
-Stolee
v6 cover bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
In reply to Lidong YanThe revision traversal limited by pathspec has optimization when the pathspec has only one element, it does not use any pathspec magic (other than literal), and there is no wildcard. The absence of optimization for multiple pathspec elements in revision traversal cause an issue raised by Kai Koponen at
https://lore.kernel.org/git/CADYQcGqaMC=4jgbmnF9Q11oC11jfrqyvH8EuiRRHytpMXd4wYA@mail.gmail.com/
While it is much harder to lift the latter two limitations, supporting a pathspec with multiple elements is relatively easy. Just make sure we hash each of them separately and ask the bloom filter about them, and if we see none of them can possibly be affected by the commit, we can skip without tree comparison.
The difference from v5 is:
- extract convert pathspec item to bloom_keyvec logic to
a separate function, which simplifies the prepare_to_use_bloom_filter() function.
- fix few bugs in v5.
Below is a comparison of the time taken to run git log on Git and LLVM repositories before and after applying this patch. These statistics are given by Derrick Stolee at
https://lore.kernel.org/git/[email protected]/
Setup commit-graph:
$ cd ~/src/git && git commit-graph write --split --reachable --changed-paths $ cd ~/src/llvm && git commit-graph write --split --reachable --changed-paths
Running hyperfine [1] on Git repository:
$ hyperfine --warmup=3 \
Review
Quoted 2 lines
(quoted diff) +0
-2-n 'old' '~/_git/git-sparse-checkout-clean/git log -100 -- commit.c commit-graph.c' \ -n 'new' '~/_git/git/git log -100 -- commit.c commit-graph.c'
Benchmark 1: old
Time (mean ± σ): 73.1 ms ± 2.9 ms [User: 48.8 ms, System: 23.9 ms] Range (min … max): 69.9 ms … 84.5 ms 42 runs
Benchmark 2: new
Time (mean ± σ): 55.1 ms ± 2.9 ms [User: 30.5 ms, System: 24.4 ms] Range (min … max): 51.1 ms … 61.2 ms 52 runs
Summary
'new' ran
1.33 ± 0.09 times faster than 'old'
And for LLVM:
$ hyperfine --warmup=3 \
Review
Quoted 2 lines
(quoted diff) +0
-2-n 'old' '~/_git/git-sparse-checkout-clean/git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h' \ -n 'new' '~/_git/git/git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h'
Benchmark 1: old
Time (mean ± σ): 1.974 s ± 0.006 s [User: 1.877 s, System: 0.097 s]
Range (min … max): 1.960 s … 1.983 s 10 runs
Benchmark 2: new
Time (mean ± σ): 262.9 ms ± 2.4 ms [User: 214.2 ms, System: 48.4 ms]
Range (min … max): 257.7 ms … 266.2 ms 11 runs
Summary
'new' ran
7.51 ± 0.07 times faster than 'old'
[1] https://github.com/sharkdp/hyperfine
Lidong Yan (5):
bloom: add test helper to return murmur3 hash
bloom: rename function operates on bloom_key
bloom: replace struct bloom_key * with struct bloom_keyvec
revision: make helper for pathspec to bloom keyvec
To enable optimize multiple pathspec items in revision traversal,
return 0 if all pathspec item is literal in forbid_bloom_filters(). Add for loops to initialize and check each pathspec item's bloom_keyvec when optimization is possible.
blame.c | 2 +- bloom.c | 84 ++++++++++++++++++++++++++--- bloom.h | 54 ++++++++++++++----- line-log.c | 5 +- revision.c | 122 +++++++++++++++++++++--------------------- revision.h | 6 +-- t/helper/test-bloom.c | 8 +-- t/t4216-log-bloom.sh | 23 ++++---- 8 files changed, 204 insertions(+), 100 deletions(-)
Range-diff against v5:
1: 4d8f60e5ff = 1: f5ab19063d bloom: add test helper to return murmur3 hash
2: acee03e397 = 2: 51a180daa6 bloom: rename function operates on bloom_key
3: d7690bd02c ! 3: e17249ab4b bloom: replace struct bloom_key * with struct bloom_keyvec
@@ bloom.h: void bloom_key_fill(struct bloom_key *key, const char *data, size_t len
void bloom_key_clear(struct bloom_key *key);
+/*
-+ * bloom_keyvec_fill - Allocate and populate a bloom_keyvec with keys for the
++ * bloom_keyvec_new - Allocate and populate a bloom_keyvec with keys for the
+ * given path.
+ *
+ * This function splits the input path by '/' and generates a bloom key for each
@@ revision.c: static int forbid_bloom_filters(struct pathspec *spec)
static void prepare_to_use_bloom_filter(struct rev_info *revs)
{
struct pathspec_item *pi;
-+ struct bloom_keyvec *bloom_keyvec;
char *path_alloc = NULL;
- const char *path, *p;
+- const char *path, *p;
++ const char *path;
size_t len;
- int path_component_nr = 1;-: ---------- > 4: b3c1f5bcd1 revision: make helper for pathspec to bloom keyvec
4: e577aa1bfd ! 5: 785bd43674 bloom: optimize multiple pathspec items in revision traversal
@@ Metadata
Author: Lidong Yan <[email protected]>
## Commit message ##
- bloom: optimize multiple pathspec items in revision traversal
-
To enable optimize multiple pathspec items in revision traversal,
return 0 if all pathspec item is literal in forbid_bloom_filters().
Add for loops to initialize and check each pathspec item's bloom_keyvec
when optimization is possible.
Add new test cases in t/t4216-log-bloom.sh to ensure
- - consistent results between the optimization for multiple pathspec
- items using bloom filter and the case without bloom filter
- optimization.
- - does not use bloom filter if any pathspec item is not literal.
+ - consistent results between the optimization for multiple pathspec
+ items using bloom filter and the case without bloom filter
+ optimization.
+ - does not use bloom filter if any pathspec item is not literal.
+
+ With these optimizations, we get some improvements for multi-pathspec runs
+ of 'git log'. First, in the Git repository we see these modest results:
+
+ Benchmark 1: old
+ Time (mean ± σ): 73.1 ms ± 2.9 ms
+ Range (min … max): 69.9 ms … 84.5 ms 42 runs
+
+ Benchmark 2: new
+ Time (mean ± σ): 55.1 ms ± 2.9 ms
+ Range (min … max): 51.1 ms … 61.2 ms 52 runs
+
+ Summary
+ 'new' ran
+ 1.33 ± 0.09 times faster than 'old'
+
+ But in a larger repo, such as the LLVM project repo below, we get even
+ better results:
+
+ Benchmark 1: old
+ Time (mean ± σ): 1.974 s ± 0.006 s
+ Range (min … max): 1.960 s … 1.983 s 10 runs
+
+ Benchmark 2: new
+ Time (mean ± σ): 262.9 ms ± 2.4 ms
+ Range (min … max): 257.7 ms … 266.2 ms 11 runs
+
+ Summary
+ 'new' ran
+ 7.51 ± 0.07 times faster than 'old'
Signed-off-by: Lidong Yan <[email protected]>
+ Signed-off-by: Derrick Stolee <[email protected]>
## revision.c ##
@@ revision.c: static int forbid_bloom_filters(struct pathspec *spec)
@@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)
- revs->bloom_keyvecs_nr = 1;
- CALLOC_ARRAY(revs->bloom_keyvecs, 1);
-- pi = &revs->pruning.pathspec.items[0];
+ revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr;
+ CALLOC_ARRAY(revs->bloom_keyvecs, revs->bloom_keyvecs_nr);
-+ for (int i = 0; i < revs->pruning.pathspec.nr; i++) {
-+ pi = &revs->pruning.pathspec.items[i];
-- /* remove single trailing slash from path, if needed */
-- if (pi->len > 0 && pi->match[pi->len - 1] == '/') {
-- path_alloc = xmemdupz(pi->match, pi->len - 1);
-- path = path_alloc;
-- } else
-- path = pi->match;
-+ /* remove single trailing slash from path, if needed */
-+ if (pi->len > 0 && pi->match[pi->len - 1] == '/') {
-+ path_alloc = xmemdupz(pi->match, pi->len - 1);
-+ path = path_alloc;
-+ } else
-+ path = pi->match;
-
-- len = strlen(path);
-- if (!len)
+- if (convert_pathspec_to_bloom_keyvec(&revs->bloom_keyvecs[0],
+- &revs->pruning.pathspec.items[0],
+- revs->bloom_filter_settings))
- goto fail;
-+ len = strlen(path);
-+ if (!len)
++ for (int i = 0; i < revs->pruning.pathspec.nr; i++) {
++ if (convert_pathspec_to_bloom_keyvec(&revs->bloom_keyvecs[i],
++ &revs->pruning.pathspec.items[i],
++ revs->bloom_filter_settings))
+ goto fail;
-
-- revs->bloom_keyvecs[0] =
-- bloom_keyvec_new(path, len, revs->bloom_filter_settings);
-+ revs->bloom_keyvecs[i] =
-+ bloom_keyvec_new(path, len, revs->bloom_filter_settings);
-+ FREE_AND_NULL(path_alloc);
+ }
if (trace2_is_enabled() && !bloom_filter_atexit_registered) {Signature · 1 line
2.39.5 (Apple Git-154)
PATCH v6 1/5 bloom: add test helper to return murmur3 hash
In bloom.h, murmur3_seeded_v2() is exported for the use of test murmur3 hash. To clarify that murmur3_seeded_v2() is exported solely for testing purposes, a new helper function test_murmur3_seeded() was added instead of exporting murmur3_seeded_v2() directly.
--- bloom.c | 13 ++++++++++++- bloom.h | 12 +++--------- t/helper/test-bloom.c | 4 ++-- 3 files changed, 17 insertions(+), 12 deletions(-)
bloom.c +12 -1
@@ -107,7 +107,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,* Not considered to be cryptographically secure. * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm */ -uint32_t murmur3_seeded_v2 (uint32_t seed,const char *data,size_t len) +static uint32_t murmur3_seeded_v2 (uint32_t seed,const char *data,size_t len) {const uint32_t c1 =0xcc9e2d51 ;const uint32_t c2 =0x1b873593 ;
@@ -540,3 +540,14 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } + +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len, +int version) +{ +assert (version ==1 || version ==2 ); + +if (version ==2 ) +return murmur3_seeded_v2 (seed, data, len); +else +return murmur3_seeded_v1 (seed, data, len); +}
bloom.h +3 -9
@@ -78,15 +78,6 @@ int load_bloom_filter_from_graph(struct commit_graph *g,struct bloom_filter *filter, uint32_t graph_pos); -/* -* Calculate the murmur3 32-bit hash value for the given data -* using the given seed. -* Produces a uniformly distributed hash value. -* Not considered to be cryptographically secure. -* Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm -*/ -uint32_t murmur3_seeded_v2 (uint32_t seed,const char *data,size_t len); - void fill_bloom_key(const char *data, size_t len, struct bloom_key *key,
@@ -137,4 +128,7 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len, +int version); +#endif
t/helper/test-bloom.c +2 -2
@@ -61,13 +61,13 @@ int cmd__bloom(int argc, const char **argv)uint32_t hashed;if (argc <3 )usage (bloom_usage); - hashed =murmur3_seeded_v2 (0 , argv[2 ],strlen (argv[2 ])); + hashed =test_bloom_murmur3_seeded (0 , argv[2 ],strlen (argv[2 ]),2 );printf ("Murmur3 Hash with seed=0:0x%08x\n" , hashed); }if (!strcmp (argv[1 ],"get_murmur3_seven_highbit" )) {uint32_t hashed; - hashed =murmur3_seeded_v2 (0 ,"\x99\xaa\xbb\xcc\xdd\xee\xff" ,7 ); + hashed =test_bloom_murmur3_seeded (0 ,"\x99\xaa\xbb\xcc\xdd\xee\xff" ,7 ,2 );printf ("Murmur3 Hash with seed=0:0x%08x\n" , hashed); }
Signature · 1 line
2.39.5 (Apple Git-154)
PATCH v6 2/5 bloom: rename function operates on bloom_key
In reply to Lidong Yangit code style requires that functions operating on a struct S should be named in the form S_verb. However, the functions operating on struct bloom_key do not follow this convention. Therefore, fill_bloom_key() and clear_bloom_key() are renamed to bloom_key_fill() and bloom_key_clear(), respectively.
--- blame.c | 2 +- bloom.c | 10 ++++------ bloom.h | 6 ++---- line-log.c | 5 +++-- revision.c | 8 ++++---- t/helper/test-bloom.c | 4 ++-- 6 files changed, 16 insertions(+), 19 deletions(-)
blame.c +1 -1
@@ -1310,7 +1310,7 @@ static void add_bloom_key(struct blame_bloom_data *bd, } bd->keys[bd->nr] =xmalloc (sizeof (struct bloom_key )); -fill_bloom_key (path,strlen (path), bd->keys[bd->nr], bd->settings); +bloom_key_fill (bd->keys[bd->nr], path,strlen (path), bd->settings); bd->nr++; }
bloom.c +4 -6
@@ -221,9 +221,7 @@ static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len)return seed; } -void fill_bloom_key (const char *data, -size_t len, -struct bloom_key *key, +void bloom_key_fill (struct bloom_key *key,const char *data,size_t len,const struct bloom_filter_settings *settings) {int i;
@@ -243,7 +241,7 @@ void fill_bloom_key(const char *data, key->hashes[i] = hash0 + i * hash1; } -void clear_bloom_key (struct bloom_key *key) +void bloom_key_clear (struct bloom_key *key) {FREE_AND_NULL (key->hashes); }
@@ -500,9 +498,9 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,hashmap_for_each_entry (&pathmap, &iter, e, entry) {struct bloom_key key; -fill_bloom_key (e->path,strlen (e->path), &key, settings); +bloom_key_fill (&key, e->path,strlen (e->path), settings);add_key_to_filter (&key, filter, settings); -clear_bloom_key (&key); +bloom_key_clear (&key); } cleanup:
bloom.h +2 -4
@@ -78,11 +78,9 @@ int load_bloom_filter_from_graph(struct commit_graph *g,struct bloom_filter *filter, uint32_t graph_pos); -void fill_bloom_key (const char *data, -size_t len, -struct bloom_key *key, +void bloom_key_fill (struct bloom_key *key,const char *data,size_t len,const struct bloom_filter_settings *settings); -void clear_bloom_key (struct bloom_key *key); +void bloom_key_clear (struct bloom_key *key); void add_key_to_filter(const struct bloom_key *key, struct bloom_filter *filter,
line-log.c +3 -2
@@ -1172,12 +1172,13 @@ static int bloom_filter_check(struct rev_info *rev,return 0 ;while (!result && range) { -fill_bloom_key (range->path,strlen (range->path), &key, rev->bloom_filter_settings); +bloom_key_fill (&key, range->path,strlen (range->path), + rev->bloom_filter_settings);if (bloom_filter_contains (filter, &key, rev->bloom_filter_settings)) result =1 ; -clear_bloom_key (&key); +bloom_key_clear (&key); range = range->next; }
revision.c +4 -4
@@ -739,15 +739,15 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) revs->bloom_keys_nr = path_component_nr;ALLOC_ARRAY (revs->bloom_keys, revs->bloom_keys_nr); -fill_bloom_key (path, len, &revs->bloom_keys[0 ], +bloom_key_fill (&revs->bloom_keys[0 ], path, len, revs->bloom_filter_settings); path_component_nr =1 ; p = path + len -1 ;while (p > path) {if (*p =='/' ) -fill_bloom_key (path, p - path, - &revs->bloom_keys[path_component_nr++], +bloom_key_fill (&revs->bloom_keys[path_component_nr++], + path, p - path, revs->bloom_filter_settings); p--; }
@@ -3231,7 +3231,7 @@ void release_revisions(struct rev_info *revs)oidset_clear (&revs->missing_commits);for (int i =0 ; i < revs->bloom_keys_nr; i++) -clear_bloom_key (&revs->bloom_keys[i]); +bloom_key_clear (&revs->bloom_keys[i]);FREE_AND_NULL (revs->bloom_keys); revs->bloom_keys_nr =0 ; }
t/helper/test-bloom.c +2 -2
@@ -12,13 +12,13 @@ static struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;static void add_string_to_filter (const char *data,struct bloom_filter *filter) {struct bloom_key key; -fill_bloom_key (data,strlen (data), &key, &settings); +bloom_key_fill (&key, data,strlen (data), &settings);printf ("Hashes:" );for (size_t i =0 ; i < settings.num_hashes; i++)printf ("0x%08x|" , key.hashes[i]);printf ("\n" );add_key_to_filter (&key, filter, &settings); -clear_bloom_key (&key); +bloom_key_clear (&key); }static void print_bloom_filter (struct bloom_filter *filter) {
Signature · 1 line
2.39.5 (Apple Git-154)
PATCH v6 3/5 bloom: replace struct bloom_key * with struct bloom_keyvec
In reply to Lidong YanPreviously, we stored bloom keys in a flat array and marked a commit as NOT TREESAME if any key reported "definitely not changed".
To support multiple pathspec items, we now require that for each pathspec item, there exists a bloom key reporting "definitely not changed".
This "for every" condition makes a flat array insufficient, so we introduce a new structure to group keys by a single pathspec item. struct bloom_keyvec is introduced to replace struct bloom_key * and bloom_key_nr. And because we want to support multiple pathspec items, we added a bloom_keyvec * and a bloom_keyvec_nr field to struct rev_info to represent an array of bloom_keyvecs. This commit still optimize only one pathspec item, thus bloom_keyvec_nr can only be 0 or 1.
New bloom_keyvec_* functions are added to create and destroy a keyvec. bloom_filter_contains_vec() is added to check if all key in keyvec is contained in a bloom filter.
--- bloom.c | 61 +++++++++++++++++++++++++++++++++++++++++++ bloom.h | 38 +++++++++++++++++++++++++++ revision.c | 76 +++++++++++++++++++++--------------------------------- revision.h | 6 ++--- 4 files changed, 132 insertions(+), 49 deletions(-)
bloom.c +61 -0
@@ -278,6 +278,55 @@ void deinit_bloom_filters(void)deep_clear_bloom_filter_slab (&bloom_filters, free_one_bloom_filter); } +struct bloom_keyvec *bloom_keyvec_new (const char *path,size_t len, +const struct bloom_filter_settings *settings) +{ +struct bloom_keyvec *vec; +const char *p; +size_t sz; +size_t nr =1 ; + + p = path; +while (*p) { +/* +* At this point, the path is normalized to use Unix-style +* path separators. This is required due to how the +* changed-path Bloom filters store the paths. +*/ +if (*p =='/' ) + nr++; + p++; + } + + sz =sizeof (struct bloom_keyvec ); + sz += nr *sizeof (struct bloom_key ); + vec = (struct bloom_keyvec *)xcalloc (1 , sz); +if (!vec) +return NULL ; + vec->count = nr; + +bloom_key_fill (&vec->key[0 ], path, len, settings); + nr =1 ; + p = path + len -1 ; +while (p > path) { +if (*p =='/' ) { +bloom_key_fill (&vec->key[nr++], path, p - path, settings); + } + p--; + } +assert (nr == vec->count); +return vec; +} + +void bloom_keyvec_free (struct bloom_keyvec *vec) +{ +if (!vec) +return ; +for (size_t nr =0 ; nr < vec->count; nr++) +bloom_key_clear (&vec->key[nr]); +free (vec); +} + static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, const struct hashmap_entry *eptr, const struct hashmap_entry *entry_or_key,
@@ -539,6 +588,18 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *vec, +const struct bloom_filter_settings *settings) +{ +int ret =1 ; + +for (size_t nr =0 ; ret >0 && nr < vec->count; nr++) + ret =bloom_filter_contains (filter, &vec->key[nr], settings); + +return ret; +} +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len,int version) {
bloom.h +38 -0
@@ -74,6 +74,16 @@ struct bloom_key {uint32_t *hashes; }; +/* +* A bloom_keyvec is a vector of bloom_keys, which +* can be used to store multiple keys for a single +* pathspec item. +*/ +struct bloom_keyvec { +size_t count; +struct bloom_key key[FLEX_ARRAY ]; +}; +int load_bloom_filter_from_graph (struct commit_graph *g,struct bloom_filter *filter,uint32_t graph_pos);
@@ -82,6 +92,23 @@ void bloom_key_fill(struct bloom_key *key, const char *data, size_t len, const struct bloom_filter_settings *settings);void bloom_key_clear (struct bloom_key *key); +/* +* bloom_keyvec_new - Allocate and populate a bloom_keyvec with keys for the +* given path. +* +* This function splits the input path by '/' and generates a bloom key for each +* prefix, in reverse order of specificity. For example, given the input +* "a/b/c", it will generate bloom keys for: +* - "a/b/c" +* - "a/b" +* - "a" +* +* The resulting keys are stored in a newly allocated bloom_keyvec. +*/ +struct bloom_keyvec *bloom_keyvec_new (const char *path,size_t len, +const struct bloom_filter_settings *settings); +void bloom_keyvec_free (struct bloom_keyvec *vec); +void add_key_to_filter (const struct bloom_key *key,struct bloom_filter *filter,const struct bloom_filter_settings *settings);
@@ -126,6 +153,17 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +/* +* bloom_filter_contains_vec - Check if all keys in a key vector are in the +* Bloom filter. +* +* Returns 1 if **all** keys in the vector are present in the filter, +* 0 if **any** key is not present. +*/ +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *v, +const struct bloom_filter_settings *settings); +uint32_t test_bloom_murmur3_seeded (uint32_t seed,const char *data,size_t len,int version);
revision.c +30 -46
143 lines not on this page · raw message
revision.h +3 -3
@@ -62,7 +62,7 @@ struct repository;struct rev_info ;struct string_list ;struct saved_parents ; -struct bloom_key ; +struct bloom_keyvec ;struct bloom_filter_settings ;struct option ;struct parse_opt_ctx_t ;
@@ -360,8 +360,8 @@ struct rev_info {/* Commit graph bloom filter fields */ /* The bloom filter key(s) for the pathspec */ -struct bloom_key *bloom_keys; -int bloom_keys_nr; +struct bloom_keyvec **bloom_keyvecs; +int bloom_keyvecs_nr;/* * The bloom filter settings used to generate the key.
Signature · 1 line
2.39.5 (Apple Git-154)
PATCH v6 4/5 revision: make helper for pathspec to bloom keyvec
In reply to Lidong YanWhen preparing to use bloom filters in a revision walk, Git populates a boom_keyvec with an array of bloom keys for the components of a path. Before we create the ability to map multiple pathspecs to multiple bloom_keyvecs, extract the conversion from a pathspec to a bloom_keyvec into its own helper method. This simplifies the state that persists in prepare_to_use_bloom_filter() as well as makes the future change much simpler.
--- revision.c | 45 +++++++++++++++++++++++++++++---------------- 1 file changed, 29 insertions(+), 16 deletions(-)
revision.c +29 -16
@@ -687,13 +687,37 @@ static int forbid_bloom_filters(struct pathspec *spec)static void release_revisions_bloom_keyvecs (struct rev_info *revs); -static void prepare_to_use_bloom_filter (struct rev_info *revs) +static int convert_pathspec_to_bloom_keyvec (struct bloom_keyvec **out, +const struct pathspec_item *pi, +const struct bloom_filter_settings *settings) { -struct pathspec_item *pi;char *path_alloc =NULL ;const char *path;size_t len; +int res =0 ; + +/* remove single trailing slash from path, if needed */ +if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { + path_alloc =xmemdupz (pi->match, pi->len -1 ); + path = path_alloc; + }else + path = pi->match; + + len =strlen (path); +if (!len) { + res =-1 ; + goto cleanup; + } + *out =bloom_keyvec_new (path, len, settings); + +cleanup: +free (path_alloc); +return res; +} + +static void prepare_to_use_bloom_filter (struct rev_info *revs) +{if (!revs->commits)return ;
@@ -711,22 +735,12 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) revs->bloom_keyvecs_nr =1 ;CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - pi = &revs->pruning.pathspec.items[0 ]; -/* remove single trailing slash from path, if needed */ -if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { - path_alloc =xmemdupz (pi->match, pi->len -1 ); - path = path_alloc; - }else - path = pi->match; - - len =strlen (path); -if (!len) +if (convert_pathspec_to_bloom_keyvec (&revs->bloom_keyvecs[0 ], + &revs->pruning.pathspec.items[0 ], + revs->bloom_filter_settings)) goto fail; - revs->bloom_keyvecs[0 ] = -bloom_keyvec_new (path, len, revs->bloom_filter_settings); -if (trace2_is_enabled () && !bloom_filter_atexit_registered) {atexit (trace2_bloom_filter_statistics_atexit); bloom_filter_atexit_registered =1 ;
@@ -736,7 +750,6 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) fail: revs->bloom_filter_settings =NULL ; -free (path_alloc);release_revisions_bloom_keyvecs (revs); }
Signature · 1 line
2.39.5 (Apple Git-154)
PATCH v6 5/5 To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in forbid_bloom_filters(). Add for loops to initialize and check each pathspec item's bloom_keyvec when optimization is possible.
In reply to Lidong YanAdd new test cases in t/t4216-log-bloom.sh to ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
With these optimizations, we get some improvements for multi-pathspec runs of 'git log'. First, in the Git repository we see these modest results:
Benchmark 1: old
Time (mean ± σ): 73.1 ms ± 2.9 ms Range (min … max): 69.9 ms … 84.5 ms 42 runs
Benchmark 2: new
Time (mean ± σ): 55.1 ms ± 2.9 ms Range (min … max): 51.1 ms … 61.2 ms 52 runs
Summary
'new' ran
1.33 ± 0.09 times faster than 'old'
But in a larger repo, such as the LLVM project repo below, we get even better results:
Benchmark 1: old
Time (mean ± σ): 1.974 s ± 0.006 s
Range (min … max): 1.960 s … 1.983 s 10 runs
Benchmark 2: new
Time (mean ± σ): 262.9 ms ± 2.4 ms
Range (min … max): 257.7 ms … 266.2 ms 11 runs
Summary
'new' ran
7.51 ± 0.07 times faster than 'old'
--- revision.c | 21 +++++++++++---------- t/t4216-log-bloom.sh | 23 ++++++++++++++--------- 2 files changed, 25 insertions(+), 19 deletions(-)
revision.c +11 -10
@@ -675,12 +675,11 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ; -if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL )) -return 1 ; +for (size_t nr =0 ; nr < spec->nr; nr++) +if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +return 1 ;return 0 ; }
@@ -733,13 +732,15 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); -if (convert_pathspec_to_bloom_keyvec (&revs->bloom_keyvecs[0 ], - &revs->pruning.pathspec.items[0 ], - revs->bloom_filter_settings)) - goto fail; +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { +if (convert_pathspec_to_bloom_keyvec (&revs->bloom_keyvecs[i], + &revs->pruning.pathspec.items[i], + revs->bloom_filter_settings)) + goto fail; + }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {atexit (trace2_bloom_filter_statistics_atexit);
t/t4216-log-bloom.sh +14 -9
@@ -66,8 +66,9 @@ sane_unset GIT_TRACE2_CONFIG_PARAMS setup () { rm -f "$TRASH_DIRECTORY/trace.perf" && - git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom && - GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom + eval git -c core.commitGraph=false log --pretty="format:%s" "$1" >log_wo_bloom && + eval "GIT_TRACE2_PERF=\"$TRASH_DIRECTORY/trace.perf\"" \ + git -c core.commitGraph=true log --pretty="format:%s" "$1" >log_w_bloom } test_bloom_filters_used () {
@@ -138,10 +139,6 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' ' test_bloom_filters_not_used "--walk-reflogs -- A" ' -test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" -' - test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' ' test_bloom_filters_not_used "-- ." '
@@ -151,9 +148,17 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used "-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with multiple literal paths uses Bloom filter' ' + test_bloom_filters_used "-- file4 A/file1" && + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" +' + +test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' + test_bloom_filters_not_used "-- file\*" && + test_bloom_filters_not_used "-- A/\* file4" && + test_bloom_filters_not_used "-- file4 A/\*" && + test_bloom_filters_not_used "-- * A/\*" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.39.5 (Apple Git-154)
Re: [PATCH v6 5/5] To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in forbid_bloom_filters(). Add for loops to initialize and check each pathspec item's bloom_keyvec when optimization is possible.
Quoted 9 lines · Lidong Yan
Add new test cases in
t/t4216-log-bloom.shto ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.With these optimizations, we get some improvements for multi-pathspec runs of 'git log'. First, in the Git repository we see these modest results:
Sorry, seems like I wrote bad commit message, I will resend patch 5/5 soon.
PATCH v6 5/5 bloom: optimize multiple pathspec items in revision
To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in forbid_bloom_filters(). Add for loops to initialize and check each pathspec item's bloom_keyvec when optimization is possible.
Add new test cases in t/t4216-log-bloom.sh to ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
With these optimizations, we get some improvements for multi-pathspec runs of 'git log'. First, in the Git repository we see these modest results:
Benchmark 1: old
Time (mean ± σ): 73.1 ms ± 2.9 ms Range (min … max): 69.9 ms … 84.5 ms 42 runs
Benchmark 2: new
Time (mean ± σ): 55.1 ms ± 2.9 ms Range (min … max): 51.1 ms … 61.2 ms 52 runs
Summary
'new' ran
1.33 ± 0.09 times faster than 'old'
But in a larger repo, such as the LLVM project repo below, we get even better results:
Benchmark 1: old
Time (mean ± σ): 1.974 s ± 0.006 s
Range (min … max): 1.960 s … 1.983 s 10 runs
Benchmark 2: new
Time (mean ± σ): 262.9 ms ± 2.4 ms
Range (min … max): 257.7 ms … 266.2 ms 11 runs
Summary
'new' ran
7.51 ± 0.07 times faster than 'old'
--- revision.c | 21 +++++++++++---------- t/t4216-log-bloom.sh | 23 ++++++++++++++--------- 2 files changed, 25 insertions(+), 19 deletions(-)
revision.c +11 -10
@@ -675,12 +675,11 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ; -if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL )) -return 1 ; +for (size_t nr =0 ; nr < spec->nr; nr++) +if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +return 1 ;return 0 ; }
@@ -733,13 +732,15 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); -if (convert_pathspec_to_bloom_keyvec (&revs->bloom_keyvecs[0 ], - &revs->pruning.pathspec.items[0 ], - revs->bloom_filter_settings)) - goto fail; +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { +if (convert_pathspec_to_bloom_keyvec (&revs->bloom_keyvecs[i], + &revs->pruning.pathspec.items[i], + revs->bloom_filter_settings)) + goto fail; + }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {atexit (trace2_bloom_filter_statistics_atexit);
t/t4216-log-bloom.sh +14 -9
@@ -66,8 +66,9 @@ sane_unset GIT_TRACE2_CONFIG_PARAMS setup () { rm -f "$TRASH_DIRECTORY/trace.perf" && - git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom && - GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom + eval git -c core.commitGraph=false log --pretty="format:%s" "$1" >log_wo_bloom && + eval "GIT_TRACE2_PERF=\"$TRASH_DIRECTORY/trace.perf\"" \ + git -c core.commitGraph=true log --pretty="format:%s" "$1" >log_w_bloom } test_bloom_filters_used () {
@@ -138,10 +139,6 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' ' test_bloom_filters_not_used "--walk-reflogs -- A" ' -test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" -' - test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' ' test_bloom_filters_not_used "-- ." '
@@ -151,9 +148,17 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used "-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with multiple literal paths uses Bloom filter' ' + test_bloom_filters_used "-- file4 A/file1" && + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" +' + +test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' + test_bloom_filters_not_used "-- file\*" && + test_bloom_filters_not_used "-- A/\* file4" && + test_bloom_filters_not_used "-- file4 A/\*" && + test_bloom_filters_not_used "-- * A/\*" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.39.5 (Apple Git-154)
Re: [PATCH v6 5/5] bloom: optimize multiple pathspec items in revision
Quoted 4 lines · Lidong Yan
To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in
forbid_bloom_filters(). Add for loops to initialize and check each pathspec item'sbloom_keyvecwhen optimization is possible.
The patch itself is good.
Quoted 2 lines
Signed-off-by Lidong Yan <[email protected]>Signed-off-by Derrick Stolee <[email protected]>
Here, I'll just point out that your sign-off should follow mine because you were the last to touch the patch. In this way, the sign-off gives a kind of timestamp to who made the most-recent changes (and that those changes have that person's sign-off, and may not have been vetted by previous signers).
Thanks,
-Stolee
Re: [PATCH v6 5/5] bloom: optimize multiple pathspec items in revision
Quoted 8 lines · Derrick Stolee
Quoted 4 lines · Lidong Yan
To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in
forbid_bloom_filters(). Add for loops to initialize and check each pathspec item'sbloom_keyvecwhen optimization is possible.The patch itself is good.
Quoted 8 lines
Quoted 2 lines
Signed-off-by Lidong Yan <[email protected]>Signed-off-by Derrick Stolee <[email protected]>Here, I'll just point out that your sign-off should follow mine because you were the last to touch the patch. In this way, the sign-off gives a kind of timestamp to who made the most-recent changes (and that those changes have that person's sign-off, and may not have been vetted by previous signers).
Thanks for pointing it out. Also perhaps a single-liner attribution to clarify who did what, e.g.
would be more helpful.
Re: [PATCH v6 5/5] bloom: optimize multiple pathspec items in revision
Quoted 20 lines · Junio C Hamano
Quoted 8 lines · Derrick Stolee
Quoted 4 lines · Lidong Yan
To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in
forbid_bloom_filters(). Add for loops to initialize and check each pathspec item'sbloom_keyvecwhen optimization is possible.The patch itself is good.
Quoted 8 lines
Quoted 2 lines
Signed-off-by Lidong Yan <[email protected]>Signed-off-by Derrick Stolee <[email protected]>Here, I'll just point out that your sign-off should follow mine because you were the last to touch the patch. In this way, the sign-off gives a kind of timestamp to who made the most-recent changes (and that those changes have that person's sign-off, and may not have been vetted by previous signers).
Quoted 6 lines
Thanks for pointing it out. Also perhaps a single-liner attribution to clarify who did what, e.g.
Signed-off-by Derrick[ly: did this and that to derrick's code to adjust]Signed-off-by Lidong
I will fix the order of the sign-offs, add the attributes, and resend PATCH v6 5/5.
Thanks,
Lidong
PATCH RESEND v6 5/5 bloom: optimize multiple pathspec items in revision
To enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in forbid_bloom_filters(). Add for loops to initialize and check each pathspec item's bloom_keyvec when optimization is possible.
Add new test cases in t/t4216-log-bloom.sh to ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
With these optimizations, we get some improvements for multi-pathspec runs of 'git log'. First, in the Git repository we see these modest results:
Benchmark 1: old
Time (mean ± σ): 73.1 ms ± 2.9 ms Range (min … max): 69.9 ms … 84.5 ms 42 runs
Benchmark 2: new
Time (mean ± σ): 55.1 ms ± 2.9 ms Range (min … max): 51.1 ms … 61.2 ms 52 runs
Summary
'new' ran
1.33 ± 0.09 times faster than 'old'
But in a larger repo, such as the LLVM project repo below, we get even better results:
Benchmark 1: old
Time (mean ± σ): 1.974 s ± 0.006 s
Range (min … max): 1.960 s … 1.983 s 10 runs
Benchmark 2: new
Time (mean ± σ): 262.9 ms ± 2.4 ms
Range (min … max): 257.7 ms … 266.2 ms 11 runs
Summary
'new' ran
7.51 ± 0.07 times faster than 'old'
--- revision.c | 21 +++++++++++---------- t/t4216-log-bloom.sh | 23 ++++++++++++++--------- 2 files changed, 25 insertions(+), 19 deletions(-)
revision.c +11 -10
@@ -675,12 +675,11 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ; -if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL )) -return 1 ; +for (size_t nr =0 ; nr < spec->nr; nr++) +if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +return 1 ;return 0 ; }
@@ -733,13 +732,15 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); -if (convert_pathspec_to_bloom_keyvec (&revs->bloom_keyvecs[0 ], - &revs->pruning.pathspec.items[0 ], - revs->bloom_filter_settings)) - goto fail; +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { +if (convert_pathspec_to_bloom_keyvec (&revs->bloom_keyvecs[i], + &revs->pruning.pathspec.items[i], + revs->bloom_filter_settings)) + goto fail; + }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {atexit (trace2_bloom_filter_statistics_atexit);
t/t4216-log-bloom.sh +14 -9
@@ -66,8 +66,9 @@ sane_unset GIT_TRACE2_CONFIG_PARAMS setup () { rm -f "$TRASH_DIRECTORY/trace.perf" && - git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom && - GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom + eval git -c core.commitGraph=false log --pretty="format:%s" "$1" >log_wo_bloom && + eval "GIT_TRACE2_PERF=\"$TRASH_DIRECTORY/trace.perf\"" \ + git -c core.commitGraph=true log --pretty="format:%s" "$1" >log_w_bloom } test_bloom_filters_used () {
@@ -138,10 +139,6 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' ' test_bloom_filters_not_used "--walk-reflogs -- A" ' -test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" -' - test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' ' test_bloom_filters_not_used "-- ." '
@@ -151,9 +148,17 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used "-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with multiple literal paths uses Bloom filter' ' + test_bloom_filters_used "-- file4 A/file1" && + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" +' + +test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' + test_bloom_filters_not_used "-- file\*" && + test_bloom_filters_not_used "-- A/\* file4" && + test_bloom_filters_not_used "-- file4 A/\*" && + test_bloom_filters_not_used "-- * A/\*" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.39.5 (Apple Git-154)
Re: [PATCH v6 0/5] bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
In reply to Lidong YanQuoted 5 lines · Lidong Yan
The difference from v5 is:
- extract convert pathspec item tobloom_keyveclogic to
a separate function, which simplifies theprepare_to_use_bloom_filter()function.
- fix few bugs in v5.
Thanks for making these changes. Including your fixed patch 5, this version looks ready to me.
I wouldn't say "fix a few bugs" but instead "fix some compile-time linting complaints when using DEVELOPER=1" to be clear that the functionality hasn't changed but the code is cleaner.
Thanks,
-Stolee
Re: [PATCH v6 0/5] bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
Quoted 8 lines · Derrick Stolee
Quoted 5 lines · Lidong Yan
The difference from v5 is:
- extract convert pathspec item tobloom_keyveclogic to
a separate function, which simplifies theprepare_to_use_bloom_filter()function.
- fix few bugs in v5.
Quoted 6 lines
Thanks for making these changes. Including your fixed patch 5, this version looks ready to me.
I wouldn't say "fix a few bugs" but instead "fix some compile-time linting complaints when using DEVELOPER=1" to be clear that the functionality hasn't changed but the code is cleaner.
Thanks both, for polishing and reviewing.
Re: [PATCH v6 0/5] bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
In reply to Derrick StoleeQuoted 9 lines · Derrick Stolee
Quoted 5 lines · Lidong Yan
The difference from v5 is:
- extract convert pathspec item tobloom_keyveclogic to
a separate function, which simplifies theprepare_to_use_bloom_filter()function.
- fix few bugs in v5.
Quoted 6 lines
Thanks for making these changes. Including your fixed patch 5, this version looks ready to me.
I wouldn't say "fix a few bugs" but instead "fix some compile-time linting complaints when using DEVELOPER=1" to be clear that the functionality hasn't changed but the code is cleaner.
I just learned that make DEVELOPER=1 treats warnings as errors. Since this is just a cover letter issue, I feel it might not be worth rerolling the patch again.
Thanks,
Lidong
Re: [PATCH v6 0/5] bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
Quoted 13 lines · Lidong Yan
Quoted 12 lines · Derrick Stolee
Quoted 5 lines · Lidong Yan
The difference from v5 is:
- extract convert pathspec item tobloom_keyveclogic to
a separate function, which simplifies theprepare_to_use_bloom_filter()function.
- fix few bugs in v5.Thanks for making these changes. Including your fixed patch 5, this version looks ready to me.
Quoted 7 lines
Quoted 3 lines
I wouldn't say "fix a few bugs" but instead "fix some compile-time linting complaints when using DEVELOPER=1" to be clear that the functionality hasn't changed but the code is cleaner.
I just learned that
make DEVELOPER=1treats warnings as errors. Since this is just a cover letter issue, I feel it might not be worth rerolling the patch again.
No need to reroll anything, I think. Junio's got the right fixups in place.
This was just a comment to help you next time.
Thanks,
-Stolee
Re: [PATCH v6 0/5] bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal
Quoted 4 lines · Derrick Stolee
No need to reroll anything, I think. Junio's got the right fixups in place.
This was just a comment to help you next time.
Thanks.
PATCH v3 1/2 bloom: replace struct bloom_key * with struct bloom_keyvec
In reply to Lidong YanThe revision traversal limited by pathspec has optimization when the pathspec has only one element. To support optimization for multiple pathspec items, we need to modify the data structures in struct rev_info.
struct rev_info uses bloom_keys and bloom_nr to store the bloom keys corresponding to a single pathspec item. To allow struct rev_info to store bloom keys for multiple pathspec items, a new data structure struct bloom_keyvec is introduced. Each struct bloom_keyvec corresponds to a single pathspec item.
In struct rev_info, replace bloom_keys and bloom_nr with bloom_keyvecs and bloom_keyvec_nr. This commit still optimize one pathspec item, thus bloom_keyvec_nr can only be 0 or 1.
New *_bloom_keyvec functions are added to create and destroy a keyvec. bloom_filter_contains_vec() is added to check if all key in keyvec is contained in a bloom filter. fill_bloom_keyvec_key() is added to initialize a key in keyvec.
--- bloom.c | 31 +++++++++++++++++++++++++++++++ bloom.h | 20 ++++++++++++++++++++ revision.c | 36 ++++++++++++++++++------------------ revision.h | 6 +++--- 4 files changed, 72 insertions(+), 21 deletions(-)
bloom.c +31 -0
@@ -280,6 +280,25 @@ void deinit_bloom_filters(void)deep_clear_bloom_filter_slab (&bloom_filters, free_one_bloom_filter); } +struct bloom_keyvec *create_bloom_keyvec (size_t count) +{ +struct bloom_keyvec *vec; +size_t sz =sizeof (struct bloom_keyvec ); + sz += count *sizeof (struct bloom_key ); + vec = (struct bloom_keyvec *)xcalloc (1 , sz); + vec->count = count; +return vec; +} + +void destroy_bloom_keyvec (struct bloom_keyvec *vec) +{ +if (!vec) +return ; +for (size_t nr =0 ; nr < vec->count; nr++) +clear_bloom_key (&vec->key[nr]); +free (vec); +} + static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, const struct hashmap_entry *eptr, const struct hashmap_entry *entry_or_key,
@@ -540,3 +559,15 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } + +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *vec, +const struct bloom_filter_settings *settings) +{ +int ret =1 ; + +for (size_t nr =0 ; ret >0 && nr < vec->count; nr++) + ret =bloom_filter_contains (filter, &vec->key[nr], settings); + +return ret; +}
bloom.h +20 -0
@@ -74,6 +74,11 @@ struct bloom_key {uint32_t *hashes; }; +struct bloom_keyvec { +size_t count; +struct bloom_key key[FLEX_ARRAY ]; +}; +int load_bloom_filter_from_graph (struct commit_graph *g,struct bloom_filter *filter,uint32_t graph_pos);
@@ -100,6 +105,17 @@ void add_key_to_filter(const struct bloom_key *key,void init_bloom_filters (void );void deinit_bloom_filters (void ); +struct bloom_keyvec *create_bloom_keyvec (size_t count); +void destroy_bloom_keyvec (struct bloom_keyvec *vec); + +static inline void fill_bloom_keyvec_key (const char *data,size_t len, +struct bloom_keyvec *vec,size_t nr, +const struct bloom_filter_settings *settings) +{ +assert (nr < vec->count); +fill_bloom_key (data, len, &vec->key[nr], settings); +} +enum bloom_filter_computed {BLOOM_NOT_COMPUTED = (1 <<0 ),BLOOM_COMPUTED = (1 <<1 ),
@@ -137,4 +153,8 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *v, +const struct bloom_filter_settings *settings); +#endif
revision.c +18 -18
@@ -688,6 +688,7 @@ static int forbid_bloom_filters(struct pathspec *spec)static void prepare_to_use_bloom_filter (struct rev_info *revs) {struct pathspec_item *pi; +struct bloom_keyvec *bloom_keyvec;char *path_alloc =NULL ;const char *path, *p;size_t len;
@@ -736,19 +737,21 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) p++; } - revs->bloom_keys_nr = path_component_nr; -ALLOC_ARRAY (revs->bloom_keys, revs->bloom_keys_nr); + revs->bloom_keyvecs_nr =1 ; +CALLOC_ARRAY (revs->bloom_keyvecs,1 ); + bloom_keyvec =create_bloom_keyvec (path_component_nr); + revs->bloom_keyvecs[0 ] = bloom_keyvec; -fill_bloom_key (path, len, &revs->bloom_keys[0 ], - revs->bloom_filter_settings); +fill_bloom_keyvec_key (path, len, bloom_keyvec,0 , + revs->bloom_filter_settings); path_component_nr =1 ; p = path + len -1 ;while (p > path) {if (*p =='/' ) -fill_bloom_key (path, p - path, - &revs->bloom_keys[path_component_nr++], - revs->bloom_filter_settings); +fill_bloom_keyvec_key (path, p - path, bloom_keyvec, + path_component_nr++, + revs->bloom_filter_settings); p--; }
@@ -779,11 +782,8 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,return -1 ; } -for (j =0 ; result && j < revs->bloom_keys_nr; j++) { - result =bloom_filter_contains (filter, - &revs->bloom_keys[j], - revs->bloom_filter_settings); - } + result =bloom_filter_contains_vec (filter, revs->bloom_keyvecs[0 ], + revs->bloom_filter_settings);if (result) count_bloom_filter_maybe++;
@@ -823,7 +823,7 @@ static int rev_compare_tree(struct rev_info *revs,return REV_TREE_SAME ; } -if (revs->bloom_keys_nr && !nth_parent) { +if (revs->bloom_keyvecs_nr && !nth_parent) { bloom_ret =check_maybe_different_in_bloom_filter (revs, commit);if (bloom_ret ==0 )
@@ -850,7 +850,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,if (!t1)return 0 ; -if (!nth_parent && revs->bloom_keys_nr) { +if (!nth_parent && revs->bloom_keyvecs_nr) { bloom_ret =check_maybe_different_in_bloom_filter (revs, commit);if (!bloom_ret)return 1 ;
@@ -3230,10 +3230,10 @@ void release_revisions(struct rev_info *revs)line_log_free (revs);oidset_clear (&revs->missing_commits); -for (int i =0 ; i < revs->bloom_keys_nr; i++) -clear_bloom_key (&revs->bloom_keys[i]); -FREE_AND_NULL (revs->bloom_keys); - revs->bloom_keys_nr =0 ; +for (int i =0 ; i < revs->bloom_keyvecs_nr; i++) +destroy_bloom_keyvec (revs->bloom_keyvecs[i]); +FREE_AND_NULL (revs->bloom_keyvecs); + revs->bloom_keyvecs_nr =0 ; }static void add_child (struct rev_info *revs,struct commit *parent,struct commit *child)
revision.h +3 -3
@@ -62,7 +62,7 @@ struct repository;struct rev_info ;struct string_list ;struct saved_parents ; -struct bloom_key ; +struct bloom_keyvec ;struct bloom_filter_settings ;struct option ;struct parse_opt_ctx_t ;
@@ -360,8 +360,8 @@ struct rev_info {/* Commit graph bloom filter fields */ /* The bloom filter key(s) for the pathspec */ -struct bloom_key *bloom_keys; -int bloom_keys_nr; +struct bloom_keyvec **bloom_keyvecs; +int bloom_keyvecs_nr;/* * The bloom filter settings used to generate the key.
Signature · 1 line
2.50.0.108.g6ae0c543ae
Re: [PATCH v3 1/2] bloom: replace struct bloom_key * with struct bloom_keyvec
bloom.h struct bloom_key { · line 81
Quoted 13 lines · Lidong Yan
bloom.h +5
-0@@ -74,6 +74,11 @@ struct bloom_key {uint32_t *hashes; }; +struct bloom_keyvec { +size_t count; +struct bloom_key key[FLEX_ARRAY ]; +}; +
A short comment would help readers understand what the intent of this data structure is.
bloom.h void add_key_to_filter(const struct bloom_key *key, · line 109
Quoted 9 lines
bloom.h +2
-0int load_bloom_filter_from_graph (struct commit_graph *g,struct bloom_filter *filter,uint32_t graph_pos);@@ -100,6 +105,17 @@ void add_key_to_filter(const struct bloom_key *key,void init_bloom_filters (void );void deinit_bloom_filters (void ); +struct bloom_keyvec *create_bloom_keyvec (size_t count); +void destroy_bloom_keyvec (struct bloom_keyvec *vec);
These functions are named very unusually for us -- the first version of this patch series was following our coding guidelines, but this version here isn't anymore.
- The primary data structure that a subsystem 'S' deals with is called struct S. Functions that operate on struct S are named S_<verb>() and should generally receive a pointer to struct S as first parameter. E.g.
Second, the functions should probably be called *_new() and *_free() instead of create_*() and destroy_*().
bloom.h void add_key_to_filter(const struct bloom_key *key, · line 118
Quoted 8 lines
bloom.h +8
-0+static inline void fill_bloom_keyvec_key (const char *data,size_t len, +struct bloom_keyvec *vec,size_t nr, +const struct bloom_filter_settings *settings) +{ +assert (nr < vec->count); +fill_bloom_key (data, len, &vec->key[nr], settings); +} +
Similarly, this should probably be called bloom_keyvec_fill_key().
bloom.h int bloom_filter_contains(const struct bloom_filter *filter, · line 160
Quoted 12 lines
bloom.h +4
-0enum bloom_filter_computed {BLOOM_NOT_COMPUTED = (1 <<0 ),BLOOM_COMPUTED = (1 <<1 ),@@ -137,4 +153,8 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *v, +const struct bloom_filter_settings *settings); +#endif
This one looks alright though.
Quoted 8 lines
revision.c +0
-0@@ -779,11 +782,8 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,return -1 ; }
revision.c static int check_maybe_different_in_bloom_filter(struct rev_info *revs, · line 789
Quoted 10 lines
revision.c +2
-5-for (j =0 ; result && j < revs->bloom_keys_nr; j++) { - result =bloom_filter_contains (filter, - &revs->bloom_keys[j], - revs->bloom_filter_settings); - } + result =bloom_filter_contains_vec (filter, revs->bloom_keyvecs[0 ], + revs->bloom_filter_settings);if (result) count_bloom_filter_maybe++;
This conversion feels wrong to me. Why don't we end up iterating through revs->bloom_keyvecs_nr here? We do indeed change it back in the next patch to use a for loop.
revision.c void release_revisions(struct rev_info *revs) · line 3233
Quoted 9 lines
revision.c +1
-4@@ -3230,10 +3230,10 @@ void release_revisions(struct rev_info *revs)line_log_free (revs);oidset_clear (&revs->missing_commits); -for (int i =0 ; i < revs->bloom_keys_nr; i++) -clear_bloom_key (&revs->bloom_keys[i]); -FREE_AND_NULL (revs->bloom_keys); - revs->bloom_keys_nr =0 ; +for (int i =0 ; i < revs->bloom_keyvecs_nr; i++)
It's puzzling that the number of keys is declared as int. It's not an issue introduced by you, but can we maybe fix it while at it?
Patrick
Re: [PATCH v3 1/2] bloom: replace struct bloom_key * with struct bloom_keyvec
Quoted 10 lines · Patrick Steinhardt
Quoted 8 lines · Lidong Yan
bloom.h +0
-0@@ -74,6 +74,11 @@ struct bloom_key {uint32_t *hashes; };
Quoted 8 lines
bloom.h struct bloom_key { · line 81
Quoted 5 lines
bloom.h +5
-0+struct bloom_keyvec { +size_t count; +struct bloom_key key[FLEX_ARRAY ]; +}; +A short comment would help readers understand what the intent of this data structure is.
Understood, will add comment for struct bloom_keyvec in v4.
Quoted 15 lines
bloom.h void add_key_to_filter(const struct bloom_key *key, · line 109
Quoted 10 lines
bloom.h +2
-0int load_bloom_filter_from_graph (struct commit_graph *g,struct bloom_filter *filter,uint32_t graph_pos);@@ -100,6 +105,17 @@ void add_key_to_filter(const struct bloom_key *key,void init_bloom_filters (void );void deinit_bloom_filters (void ); +struct bloom_keyvec *create_bloom_keyvec (size_t count); +void destroy_bloom_keyvec (struct bloom_keyvec *vec);These functions are named very unusually for us -- the first version of this patch series was following our coding guidelines, but this version here isn't anymore.
Quoted 7 lines
- The primary data structure that a subsystem 'S' deals with is called
struct S. Functions that operate onstruct Sare namedS_<verb>()and should generally receive a pointer tostruct Sas first parameter. E.g.Second, the functions should probably be called
*_new()and*_free()instead ofcreate_*()anddestroy_*().
Though I think create and destroy doesn’t match the 'operate on struct S’ definition, I will rename these function to *_verb in v4.
Quoted 11 lines
bloom.h void add_key_to_filter(const struct bloom_key *key, · line 118
Quoted 9 lines
bloom.h +8
-0+static inline void fill_bloom_keyvec_key (const char *data,size_t len, +struct bloom_keyvec *vec,size_t nr, +const struct bloom_filter_settings *settings) +{ +assert (nr < vec->count); +fill_bloom_key (data, len, &vec->key[nr], settings); +} +Similarly, this should probably be called
bloom_keyvec_fill_key().
I initially wanted the new function to have a name similar to fill_bloom_key, but perhaps I should consider renaming it.
Quoted 32 lines
bloom.h int bloom_filter_contains(const struct bloom_filter *filter, · line 160
Quoted 13 lines
bloom.h +4
-0enum bloom_filter_computed {BLOOM_NOT_COMPUTED = (1 <<0 ),BLOOM_COMPUTED = (1 <<1 ),@@ -137,4 +153,8 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *v, +const struct bloom_filter_settings *settings); +#endif This one looks alright though.
Quoted 16 lines
revision.c +2
-5@@ -779,11 +782,8 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,return -1 ; } -for (j =0 ; result && j < revs->bloom_keys_nr; j++) { - result =bloom_filter_contains (filter, - &revs->bloom_keys[j], - revs->bloom_filter_settings); - } + result =bloom_filter_contains_vec (filter, revs->bloom_keyvecs[0 ], + revs->bloom_filter_settings);
Quoted 6 lines
revision.c static int check_maybe_different_in_bloom_filter(struct rev_info *revs, · line 789
Quoted 2 lines
revision.c +0
-0if (result) count_bloom_filter_maybe++;This conversion feels wrong to me. Why don't we end up iterating through
revs->bloom_keyvecs_nrhere? We do indeed change it back in the next patch to use a for loop.
My original intention was to include all the loop-related logic in [PATCH 2/2]. However, the lack of a loop here does make the code look error-prone. I will add the loop in v4.
Quoted 5 lines
Quoted 5 lines
revision.c +0
-0@@ -3230,10 +3230,10 @@ void release_revisions(struct rev_info *revs)line_log_free (revs);oidset_clear (&revs->missing_commits);
Quoted 8 lines
revision.c void release_revisions(struct rev_info *revs) · line 3233
Quoted 5 lines
revision.c +1
-4-for (int i =0 ; i < revs->bloom_keys_nr; i++) -clear_bloom_key (&revs->bloom_keys[i]); -FREE_AND_NULL (revs->bloom_keys); - revs->bloom_keys_nr =0 ; +for (int i =0 ; i < revs->bloom_keyvecs_nr; i++)It's puzzling that the number of keys is declared as
int. It's not an issue introduced by you, but can we maybe fix it while at it?
Yes, of course.
Thanks for your review,
Lidong
Re: [PATCH v3 1/2] bloom: replace struct bloom_key * with struct bloom_keyvec
In reply to Patrick SteinhardtQuoted 10 lines · Patrick Steinhardt
bloom.h void add_key_to_filter(const struct bloom_key *key, · line 118
Quoted 8 lines
bloom.h +8
-0+static inline void fill_bloom_keyvec_key (const char *data,size_t len, +struct bloom_keyvec *vec,size_t nr, +const struct bloom_filter_settings *settings) +{ +assert (nr < vec->count); +fill_bloom_key (data, len, &vec->key[nr], settings); +} +Similarly, this should probably be called
bloom_keyvec_fill_key().
If so, a preliminary clean-up patch in front of the series is in order, as the <bloom.h> header file, without these patches, already has the follwoing external API functions and structures declared, that do not follow your naming rules at all (I have removed the ones that begin with "bloom_" from the below):
int load_bloom_filter_from_graph()
uint32_t murmur3_seeded_v2();
void fill_bloom_key();
void clear_bloom_key(s);
void add_key_to_filter();
void init_bloom_filters(void);
void deinit_bloom_filters(void);
struct bloom_filter *get_or_compute_bloom_filter();
struct bloom_filter *get_bloom_filter();It is very dubious that murmur3_seeded_v2() is exposed (nobody would know it is for Bloom filter subsystem from that name); as far as I can tell, it is only needed for t/helper testing, and makes me wonder if we can come up with a better division between the production code and t/helper/ code around there.
Thanks.
Re: [PATCH v3 1/2] bloom: replace struct bloom_key * with struct bloom_keyvec
Quoted 7 lines · Junio C Hamano
It is very dubious that
murmur3_seeded_v2()is exposed (nobody would know it is for Bloom filter subsystem from that name); as far as I can tell, it is only needed for t/helper testing, and makes me wonder if we can come up with a better division between the production code and t/helper/ code around there.Thanks.
Maybe we can do something like this:
struct bloom_filter_settings settings;
struct bloom_key key;
uint32_t hash0;
settings->num_hashes = 1;
settings->hash_version = 2;
fill_bloom_key(argv[2], strlen(argv[2]), &key, &setting);
hash0 = key->hash[0];
clear_bloom_key(&key);
return hash0;In t/helper, so that we don’t need to export murmur3_seeded_v2().
PATCH v3 2/2 bloom: optimize multiple pathspec items in revision traversal
In reply to Lidong YanTo enable optimize multiple pathspec items in revision traversal, return 0 if all pathspec item is literal in forbid_bloom_filters(). Add code to initialize and check each pathspec item's bloom_keyvec.
Add new function release_revisions_bloom_keyvecs() to free all bloom keyvec owned by rev_info.
Add new test cases in t/t4216-log-bloom.sh to ensure
- consistent results between the optimization for multiple pathspec items using bloom filter and the case without bloom filter optimization.
- does not use bloom filter if any pathspec item is not literal.
--- revision.c | 126 ++++++++++++++++++++++++------------------- t/t4216-log-bloom.sh | 23 ++++---- 2 files changed, 85 insertions(+), 64 deletions(-)
revision.c +71 -55
@@ -675,16 +675,17 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ; -if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL )) -return 1 ; +for (size_t nr =0 ; nr < spec->nr; nr++) +if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +return 1 ;return 0 ; } +static void release_revisions_bloom_keyvecs (struct rev_info *revs); +static void prepare_to_use_bloom_filter (struct rev_info *revs) {struct pathspec_item *pi;
@@ -692,7 +693,7 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)char *path_alloc =NULL ;const char *path, *p;size_t len; -int path_component_nr =1 ; +int path_component_nr;if (!revs->commits)return ;
@@ -709,50 +710,53 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - pi = &revs->pruning.pathspec.items[0 ]; - -/* remove single trailing slash from path, if needed */ -if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { - path_alloc =xmemdupz (pi->match, pi->len -1 ); - path = path_alloc; - }else - path = pi->match; - - len =strlen (path); -if (!len) { - revs->bloom_filter_settings =NULL ; -free (path_alloc); -return ; - } - - p = path; -while (*p) { -/* -* At this point, the path is normalized to use Unix-style -* path separators. This is required due to how the -* changed-path Bloom filters store the paths. -*/ -if (*p =='/' ) - path_component_nr++; - p++; - } - - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - bloom_keyvec =create_bloom_keyvec (path_component_nr); - revs->bloom_keyvecs[0 ] = bloom_keyvec; + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { + pi = &revs->pruning.pathspec.items[i]; + path_component_nr =1 ; + +/* remove single trailing slash from path, if needed */ +if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { + path_alloc =xmemdupz (pi->match, pi->len -1 ); + path = path_alloc; + }else + path = pi->match; + + len =strlen (path); +if (!len) + goto fail; + + p = path; +while (*p) { +/* +* At this point, the path is normalized to use +* Unix-style path separators. This is required due to +* how the changed-path Bloom filters store the paths. +*/ +if (*p =='/' ) + path_component_nr++; + p++; + } -fill_bloom_keyvec_key (path, len, bloom_keyvec,0 , - revs->bloom_filter_settings); - path_component_nr =1 ; + bloom_keyvec =create_bloom_keyvec (path_component_nr); + revs->bloom_keyvecs[i] = bloom_keyvec; + +fill_bloom_keyvec_key (path, len, bloom_keyvec,0 , + revs->bloom_filter_settings); + path_component_nr =1 ; + + p = path + len -1 ; +while (p > path) { +if (*p =='/' ) +fill_bloom_keyvec_key (path, p - path, + bloom_keyvec, + path_component_nr++, + revs->bloom_filter_settings); + p--; + } - p = path + len -1 ; -while (p > path) { -if (*p =='/' ) -fill_bloom_keyvec_key (path, p - path, bloom_keyvec, - path_component_nr++, - revs->bloom_filter_settings); - p--; +FREE_AND_NULL (path_alloc); }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {
@@ -760,14 +764,19 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) bloom_filter_atexit_registered =1 ; } +return ; + +fail: + revs->bloom_filter_settings =NULL ;free (path_alloc); +release_revisions_bloom_keyvecs (revs); }static int check_maybe_different_in_bloom_filter (struct rev_info *revs,struct commit *commit) {struct bloom_filter *filter; -int result =1 , j; +int result =0 ;if (!revs->repo->objects->commit_graph)return -1 ;
@@ -782,8 +791,11 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,return -1 ; } - result =bloom_filter_contains_vec (filter, revs->bloom_keyvecs[0 ], - revs->bloom_filter_settings); +for (size_t nr =0 ; !result && nr < revs->bloom_keyvecs_nr; nr++) { + result =bloom_filter_contains_vec (filter, + revs->bloom_keyvecs[nr], + revs->bloom_filter_settings); + }if (result) count_bloom_filter_maybe++;
@@ -3201,6 +3213,14 @@ static void release_revisions_mailmap(struct string_list *mailmap)static void release_revisions_topo_walk_info (struct topo_walk_info *info); +static void release_revisions_bloom_keyvecs (struct rev_info *revs) +{ +for (size_t nr =0 ; nr < revs->bloom_keyvecs_nr; nr++) +destroy_bloom_keyvec (revs->bloom_keyvecs[nr]); +FREE_AND_NULL (revs->bloom_keyvecs); + revs->bloom_keyvecs_nr =0 ; +} +static void free_void_commit_list (void *list) {free_commit_list (list);
@@ -3229,11 +3249,7 @@ void release_revisions(struct rev_info *revs)clear_decoration (&revs->treesame, free);line_log_free (revs);oidset_clear (&revs->missing_commits); - -for (int i =0 ; i < revs->bloom_keyvecs_nr; i++) -destroy_bloom_keyvec (revs->bloom_keyvecs[i]); -FREE_AND_NULL (revs->bloom_keyvecs); - revs->bloom_keyvecs_nr =0 ; +release_revisions_bloom_keyvecs (revs); }static void add_child (struct rev_info *revs,struct commit *parent,struct commit *child)
t/t4216-log-bloom.sh +14 -9
@@ -66,8 +66,9 @@ sane_unset GIT_TRACE2_CONFIG_PARAMS setup () { rm -f "$TRASH_DIRECTORY/trace.perf" && - git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom && - GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom + eval git -c core.commitGraph=false log --pretty="format:%s" "$1" >log_wo_bloom && + eval "GIT_TRACE2_PERF=\"$TRASH_DIRECTORY/trace.perf\"" \ + git -c core.commitGraph=true log --pretty="format:%s" "$1" >log_w_bloom } test_bloom_filters_used () {
@@ -138,10 +139,6 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' ' test_bloom_filters_not_used "--walk-reflogs -- A" ' -test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" -' - test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' ' test_bloom_filters_not_used "-- ." '
@@ -151,9 +148,17 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used "-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with multiple literal paths uses Bloom filter' ' + test_bloom_filters_used "-- file4 A/file1" && + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" +' + +test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' + test_bloom_filters_not_used "-- file\*" && + test_bloom_filters_not_used "-- A/\* file4" && + test_bloom_filters_not_used "-- file4 A/\*" && + test_bloom_filters_not_used "-- * A/\*" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.50.0.108.g6ae0c543ae
PATCH v2 1/2 bloom: replace struct bloom_key * with struct bloom_keyvec
In reply to Lidong YanThe revision traversal limited by pathspec has optimization when the pathspec has only one element. To support optimization for multiple pathspec items, we need to modify the data structures in struct rev_info.
struct rev_info uses bloom_keys and bloom_nr to store the bloom keys corresponding to a single pathspec item. To allow struct rev_info to store bloom keys for multiple pathspec items, a new data structure struct bloom_keyvec is introduced. Each struct bloom_keyvec corresponds to a single pathspec item.
In struct rev_info, replace bloom_keys and bloom_nr with bloom_keyvecs and bloom_keyvec_nr. This commit still optimize one pathspec item, thus bloom_keyvec_nr can only be 0 or 1.
New *_bloom_keyvec functions are added to create and destroy a keyvec. bloom_filter_contains_vec() is added to check if all key in keyvec is contained in a bloom filter. fill_bloom_keyvec_key() is added to initialize a key in keyvec.
--- bloom.c | 31 +++++++++++++++++++++++++++++++ bloom.h | 20 ++++++++++++++++++++ revision.c | 36 ++++++++++++++++++------------------ revision.h | 6 +++--- 4 files changed, 72 insertions(+), 21 deletions(-)
bloom.c +31 -0
@@ -280,6 +280,25 @@ void deinit_bloom_filters(void)deep_clear_bloom_filter_slab (&bloom_filters, free_one_bloom_filter); } +struct bloom_keyvec *create_bloom_keyvec (size_t count) +{ +struct bloom_keyvec *vec; +size_t sz =sizeof (struct bloom_keyvec ); + sz += count *sizeof (struct bloom_key ); + vec = (struct bloom_keyvec *)xcalloc (1 , sz); + vec->count = count; +return vec; +} + +void destroy_bloom_keyvec (struct bloom_keyvec *vec) +{ +if (!vec) +return ; +for (size_t nr =0 ; nr < vec->count; nr++) +clear_bloom_key (&vec->key[nr]); +free (vec); +} + static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, const struct hashmap_entry *eptr, const struct hashmap_entry *entry_or_key,
@@ -540,3 +559,15 @@ int bloom_filter_contains(const struct bloom_filter *filter,return 1 ; } + +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *vec, +const struct bloom_filter_settings *settings) +{ +int ret =1 ; + +for (size_t nr =0 ; ret >0 && nr < vec->count; nr++) + ret =bloom_filter_contains (filter, &vec->key[nr], settings); + +return ret; +}
bloom.h +20 -0
@@ -74,6 +74,11 @@ struct bloom_key {uint32_t *hashes; }; +struct bloom_keyvec { +size_t count; +struct bloom_key key[FLEX_ARRAY ]; +}; +int load_bloom_filter_from_graph (struct commit_graph *g,struct bloom_filter *filter,uint32_t graph_pos);
@@ -100,6 +105,17 @@ void add_key_to_filter(const struct bloom_key *key,void init_bloom_filters (void );void deinit_bloom_filters (void ); +struct bloom_keyvec *create_bloom_keyvec (size_t count); +void destroy_bloom_keyvec (struct bloom_keyvec *vec); + +static inline void fill_bloom_keyvec_key (const char *data,size_t len, +struct bloom_keyvec *vec,size_t nr, +const struct bloom_filter_settings *settings) +{ +assert (nr < vec->count); +fill_bloom_key (data, len, &vec->key[nr], settings); +} +enum bloom_filter_computed {BLOOM_NOT_COMPUTED = (1 <<0 ),BLOOM_COMPUTED = (1 <<1 ),
@@ -137,4 +153,8 @@ int bloom_filter_contains(const struct bloom_filter *filter,const struct bloom_key *key, const struct bloom_filter_settings *settings); +int bloom_filter_contains_vec (const struct bloom_filter *filter, +const struct bloom_keyvec *v, +const struct bloom_filter_settings *settings); +#endif
revision.c +18 -18
@@ -688,6 +688,7 @@ static int forbid_bloom_filters(struct pathspec *spec)static void prepare_to_use_bloom_filter (struct rev_info *revs) {struct pathspec_item *pi; +struct bloom_keyvec *bloom_keyvec;char *path_alloc =NULL ;const char *path, *p;size_t len;
@@ -736,19 +737,21 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) p++; } - revs->bloom_keys_nr = path_component_nr; -ALLOC_ARRAY (revs->bloom_keys, revs->bloom_keys_nr); + revs->bloom_keyvecs_nr =1 ; +CALLOC_ARRAY (revs->bloom_keyvecs,1 ); + bloom_keyvec =create_bloom_keyvec (path_component_nr); + revs->bloom_keyvecs[0 ] = bloom_keyvec; -fill_bloom_key (path, len, &revs->bloom_keys[0 ], - revs->bloom_filter_settings); +fill_bloom_keyvec_key (path, len, bloom_keyvec,0 , + revs->bloom_filter_settings); path_component_nr =1 ; p = path + len -1 ;while (p > path) {if (*p =='/' ) -fill_bloom_key (path, p - path, - &revs->bloom_keys[path_component_nr++], - revs->bloom_filter_settings); +fill_bloom_keyvec_key (path, p - path, bloom_keyvec, + path_component_nr++, + revs->bloom_filter_settings); p--; }
@@ -779,11 +782,8 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,return -1 ; } -for (j =0 ; result && j < revs->bloom_keys_nr; j++) { - result =bloom_filter_contains (filter, - &revs->bloom_keys[j], - revs->bloom_filter_settings); - } + result =bloom_filter_contains_vec (filter, revs->bloom_keyvecs[0 ], + revs->bloom_filter_settings);if (result) count_bloom_filter_maybe++;
@@ -823,7 +823,7 @@ static int rev_compare_tree(struct rev_info *revs,return REV_TREE_SAME ; } -if (revs->bloom_keys_nr && !nth_parent) { +if (revs->bloom_keyvecs_nr && !nth_parent) { bloom_ret =check_maybe_different_in_bloom_filter (revs, commit);if (bloom_ret ==0 )
@@ -850,7 +850,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,if (!t1)return 0 ; -if (!nth_parent && revs->bloom_keys_nr) { +if (!nth_parent && revs->bloom_keyvecs_nr) { bloom_ret =check_maybe_different_in_bloom_filter (revs, commit);if (!bloom_ret)return 1 ;
@@ -3230,10 +3230,10 @@ void release_revisions(struct rev_info *revs)line_log_free (revs);oidset_clear (&revs->missing_commits); -for (int i =0 ; i < revs->bloom_keys_nr; i++) -clear_bloom_key (&revs->bloom_keys[i]); -FREE_AND_NULL (revs->bloom_keys); - revs->bloom_keys_nr =0 ; +for (int i =0 ; i < revs->bloom_keyvecs_nr; i++) +destroy_bloom_keyvec (revs->bloom_keyvecs[i]); +FREE_AND_NULL (revs->bloom_keyvecs); + revs->bloom_keyvecs_nr =0 ; }static void add_child (struct rev_info *revs,struct commit *parent,struct commit *child)
revision.h +3 -3
@@ -62,7 +62,7 @@ struct repository;struct rev_info ;struct string_list ;struct saved_parents ; -struct bloom_key ; +struct bloom_keyvec ;struct bloom_filter_settings ;struct option ;struct parse_opt_ctx_t ;
@@ -360,8 +360,8 @@ struct rev_info {/* Commit graph bloom filter fields */ /* The bloom filter key(s) for the pathspec */ -struct bloom_key *bloom_keys; -int bloom_keys_nr; +struct bloom_keyvec **bloom_keyvecs; +int bloom_keyvecs_nr;/* * The bloom filter settings used to generate the key.
Signature · 1 line
2.50.0.108.g6ae0c543ae
PATCH v2 2/2 bloom: optimize multiple pathspec items in revision traversal
In reply to Lidong YanRemove if (spec->nr > 1) to enable bloom filter given multiple pathspec items. Add for loop in prepare_to_use_bloom_filter() to initialize each pathspec item's struct bloom_keyvec. Add for loop in check_maybe_different_in_bloom_filter() to find if at least one bloom_keyvec is contained in bloom filter.
Add new function release_revisions_bloom_keyvecs() to free all bloom keyvec owned by rev_info.
Modify t/t4216 to ensure consistent results between the optimization for multiple pathspec items using bloom filters and the case without bloom filter optimization.
--- revision.c | 121 ++++++++++++++++++++++++------------------- t/t4216-log-bloom.sh | 10 ++-- 2 files changed, 73 insertions(+), 58 deletions(-)
revision.c +68 -53
@@ -675,8 +675,6 @@ static int forbid_bloom_filters(struct pathspec *spec) {if (spec->has_wildcard)return 1 ; -if (spec->nr >1 ) -return 1 ;if (spec->magic & ~PATHSPEC_LITERAL )return 1 ;if (spec->nr && (spec->items[0 ].magic & ~PATHSPEC_LITERAL ))
@@ -685,6 +683,8 @@ static int forbid_bloom_filters(struct pathspec *spec)return 0 ; } +static void release_revisions_bloom_keyvecs (struct rev_info *revs); +static void prepare_to_use_bloom_filter (struct rev_info *revs) {struct pathspec_item *pi;
@@ -692,7 +692,7 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)char *path_alloc =NULL ;const char *path, *p;size_t len; -int path_component_nr =1 ; +int path_component_nr;if (!revs->commits)return ;
@@ -709,50 +709,53 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)if (!revs->pruning.pathspec.nr)return ; - pi = &revs->pruning.pathspec.items[0 ]; - -/* remove single trailing slash from path, if needed */ -if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { - path_alloc =xmemdupz (pi->match, pi->len -1 ); - path = path_alloc; - }else - path = pi->match; - - len =strlen (path); -if (!len) { - revs->bloom_filter_settings =NULL ; -free (path_alloc); -return ; - } - - p = path; -while (*p) { -/* -* At this point, the path is normalized to use Unix-style -* path separators. This is required due to how the -* changed-path Bloom filters store the paths. -*/ -if (*p =='/' ) - path_component_nr++; - p++; - } - - revs->bloom_keyvecs_nr =1 ; -CALLOC_ARRAY (revs->bloom_keyvecs,1 ); - bloom_keyvec =create_bloom_keyvec (path_component_nr); - revs->bloom_keyvecs[0 ] = bloom_keyvec; + revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr; +CALLOC_ARRAY (revs->bloom_keyvecs, revs->bloom_keyvecs_nr); +for (int i =0 ; i < revs->pruning.pathspec.nr; i++) { + pi = &revs->pruning.pathspec.items[i]; + path_component_nr =1 ; + +/* remove single trailing slash from path, if needed */ +if (pi->len >0 && pi->match[pi->len -1 ] =='/' ) { + path_alloc =xmemdupz (pi->match, pi->len -1 ); + path = path_alloc; + }else + path = pi->match; + + len =strlen (path); +if (!len) + goto fail; + + p = path; +while (*p) { +/* +* At this point, the path is normalized to use +* Unix-style path separators. This is required due to +* how the changed-path Bloom filters store the paths. +*/ +if (*p =='/' ) + path_component_nr++; + p++; + } -fill_bloom_keyvec_key (path, len, bloom_keyvec,0 , - revs->bloom_filter_settings); - path_component_nr =1 ; + bloom_keyvec =create_bloom_keyvec (path_component_nr); + revs->bloom_keyvecs[i] = bloom_keyvec; + +fill_bloom_keyvec_key (path, len, bloom_keyvec,0 , + revs->bloom_filter_settings); + path_component_nr =1 ; + + p = path + len -1 ; +while (p > path) { +if (*p =='/' ) +fill_bloom_keyvec_key (path, p - path, + bloom_keyvec, + path_component_nr++, + revs->bloom_filter_settings); + p--; + } - p = path + len -1 ; -while (p > path) { -if (*p =='/' ) -fill_bloom_keyvec_key (path, p - path, bloom_keyvec, - path_component_nr++, - revs->bloom_filter_settings); - p--; +FREE_AND_NULL (path_alloc); }if (trace2_is_enabled () && !bloom_filter_atexit_registered) {
@@ -760,14 +763,19 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs) bloom_filter_atexit_registered =1 ; } +return ; + +fail: + revs->bloom_filter_settings =NULL ;free (path_alloc); +release_revisions_bloom_keyvecs (revs); }static int check_maybe_different_in_bloom_filter (struct rev_info *revs,struct commit *commit) {struct bloom_filter *filter; -int result =1 , j; +int result =0 ;if (!revs->repo->objects->commit_graph)return -1 ;
@@ -782,8 +790,11 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,return -1 ; } - result =bloom_filter_contains_vec (filter, revs->bloom_keyvecs[0 ], - revs->bloom_filter_settings); +for (size_t nr =0 ; !result && nr < revs->bloom_keyvecs_nr; nr++) { + result =bloom_filter_contains_vec (filter, + revs->bloom_keyvecs[nr], + revs->bloom_filter_settings); + }if (result) count_bloom_filter_maybe++;
@@ -3201,6 +3212,14 @@ static void release_revisions_mailmap(struct string_list *mailmap)static void release_revisions_topo_walk_info (struct topo_walk_info *info); +static void release_revisions_bloom_keyvecs (struct rev_info *revs) +{ +for (size_t nr =0 ; nr < revs->bloom_keyvecs_nr; nr++) +destroy_bloom_keyvec (revs->bloom_keyvecs[nr]); +FREE_AND_NULL (revs->bloom_keyvecs); + revs->bloom_keyvecs_nr =0 ; +} +static void free_void_commit_list (void *list) {free_commit_list (list);
@@ -3229,11 +3248,7 @@ void release_revisions(struct rev_info *revs)clear_decoration (&revs->treesame, free);line_log_free (revs);oidset_clear (&revs->missing_commits); - -for (int i =0 ; i < revs->bloom_keyvecs_nr; i++) -destroy_bloom_keyvec (revs->bloom_keyvecs[i]); -FREE_AND_NULL (revs->bloom_keyvecs); - revs->bloom_keyvecs_nr =0 ; +release_revisions_bloom_keyvecs (revs); }static void add_child (struct rev_info *revs,struct commit *parent,struct commit *child)
t/t4216-log-bloom.sh +5 -5
@@ -138,8 +138,8 @@ test_expect_success 'git log with --walk-reflogs does not use Bloom filters' ' test_bloom_filters_not_used "--walk-reflogs -- A" ' -test_expect_success 'git log -- multiple path specs does not use Bloom filters' ' - test_bloom_filters_not_used "-- file4 A/file1" +test_expect_success 'git log -- multiple path specs use Bloom filters' ' + test_bloom_filters_used "-- file4 A/file1" ' test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' '
@@ -151,9 +151,9 @@ test_expect_success 'git log with wildcard that resolves to a single path uses B test_bloom_filters_used "-- *renamed" ' -test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' ' - test_bloom_filters_not_used "-- *" && - test_bloom_filters_not_used "-- file*" +test_expect_success 'git log with wildcard that resolves to a multiple paths uses Bloom filters' ' + test_bloom_filters_used "-- *" && + test_bloom_filters_used "-- file*" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.50.0.108.g6ae0c543ae