Re: [PATCH v4 4/4] bloom: optimize multiple pathspec items in revision traversal
- From
Derrick Stolee <stolee@gmail.com>
- Date
- Jul 7, 2025, 11:43 UTC
- Message-ID
- <ea144a72-0975-4ac9-b2e4-ae0f7fcb6837@gmail.com>
- In-Reply-To
- <20250704111437.2660251-5-502024330056@smail.nju.edu.cn>
On 7/4/2025 7:14 AM, Lidong Yan wrote:
Show 12 quoted lines
> 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 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.
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).
Show 23 quoted lines
> Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
> ---
> revision.c | 118 ++++++++++++++++++++++++-------------------
> t/t4216-log-bloom.sh | 23 +++++----
> 2 files changed, 79 insertions(+), 62 deletions(-)
>
> diff --git a/revision.c b/revision.c
> index 7cbb49617d..9a77c0d0bc 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -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;This is a good check: if any is non-literal, then we can't use bloom filters.
Show 11 quoted lines
> +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?
Show 42 quoted lines
> 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;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.
Show 53 quoted lines
> + 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);...
> -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.
Show 22 quoted lines
> 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/\*" > '
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