Re: [PATCH v4] bloom: enable bloom filter with wildcard pathspec in revision traversal

> 
> When traversing commits, a pathspec item can be used to limit the
> traversal to commits that modify the specified paths. And the
> commit-graph includes a Bloom filter to exclude commits that definitely
> did not modify a given pathspec item. During commit traversal, the
> Bloom filter can significantly improve performance. However, it is
> disabled if the specified pathspec item contains wildcard characters
> or magic signatures.
> 
> For performance reason, enable Bloom filter even if a pathspec item
> contains wildcard characters by filtering only the non-wildcard part of
> the pathspec item.
> 
> The function of pathspec magic signature is generally to narrow down
> the path specified by the pathspecs. So, enable Bloom filter when
> the magic signature is "top", "glob", "attr", "--depth" or "literal".
> "exclude" is used to select paths other than the specified path, rather
> than serving as a filtering function, so it cannot be used together with
> the Bloom filter. Since Bloom filter is not case insensitive even in
> case insensitive system (e.g. MacOS), it cannot be used together with
> "icase" magic.
> 
> With this optimization, we get some improvements for pathspecs with
> wildcards or magic signatures. First, in the Git repository we see these
> modest results:
> 
> git log -100 -- "t/*"
> 
> Benchmark 1: new
>  Time (mean ± σ):      20.4 ms ±   0.6 ms
>  Range (min … max):    19.3 ms …  24.4 ms
> 
> Benchmark 2: old
>  Time (mean ± σ):      23.4 ms ±   0.5 ms
>  Range (min … max):    22.5 ms …  24.7 ms
> 
> git log -100 -- ":(top)t"
> 
> Benchmark 1: new
>  Time (mean ± σ):      16.2 ms ±   0.4 ms
>  Range (min … max):    15.3 ms …  17.2 ms
> 
> Benchmark 2: old
>  Time (mean ± σ):      18.6 ms ±   0.5 ms
>  Range (min … max):    17.6 ms …  20.4 ms
> 
> But in a larger repo, such as the LLVM project repo below, we get even
> better results:
> 
> git log -100 -- "libc/*"
> 
> Benchmark 1: new
>  Time (mean ± σ):      16.0 ms ±   0.6 ms
>  Range (min … max):    14.7 ms …  17.8 ms
> 
> Benchmark 2: old
>  Time (mean ± σ):      26.7 ms ±   0.5 ms
>  Range (min … max):    25.4 ms …  27.8 ms
> 
> git log -100 -- ":(top)libc"
> 
> Benchmark 1: new
>  Time (mean ± σ):      15.6 ms ±   0.6 ms
>  Range (min … max):    14.4 ms …  17.7 ms
> 
> Benchmark 2: old
>  Time (mean ± σ):      19.6 ms ±   0.5 ms
>  Range (min … max):    18.6 ms …  20.6 ms
> 
> Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>
> [jc: avoid allocating zero length path in
> convert_pathspec_to_bloom_keyvec()]
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---
> revision.c           | 45 +++++++++++++++++++++++++++-----------------
> t/t4216-log-bloom.sh | 31 ++++++++++++++++++++++++++----
> 2 files changed, 55 insertions(+), 21 deletions(-)
> 
> diff --git a/revision.c b/revision.c
> index 18f300d455..79372fd483 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -671,12 +671,17 @@ static void trace2_bloom_filter_statistics_atexit(void)
> 
> static int forbid_bloom_filters(struct pathspec *spec)
> {
> - if (spec->has_wildcard)
> - return 1;
> - if (spec->magic & ~PATHSPEC_LITERAL)
> + unsigned int allowed_magic =
> + PATHSPEC_FROMTOP |
> + PATHSPEC_MAXDEPTH |
> + PATHSPEC_LITERAL |
> + PATHSPEC_GLOB |
> + PATHSPEC_ATTR;
> +
> + if (spec->magic & ~allowed_magic)
> return 1;
> for (size_t nr = 0; nr < spec->nr; nr++)
> - if (spec->items[nr].magic & ~PATHSPEC_LITERAL)
> + if (spec->items[nr].magic & ~allowed_magic)
> return 1;
> 
> return 0;
> @@ -691,26 +696,32 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,
> char *path_alloc = NULL;
> const char *path;
> size_t len;
> - int res = 0;
> 
> + len = pi->nowildcard_len;
> + if (len != pi->len) {
> + /*
> + * for path like "dir/file*", nowildcard part would be
> + * "dir/file", but only "dir" should be used for the
> + * bloom filter
> + */
> + while (len > 0 && pi->match[len - 1] != '/')
> + len--;
> + }
> /* 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);
> + if (len > 0 && pi->match[len - 1] == '/')
> + len--;
> +
> + if (!len)
> + return -1;
> +
> + if (len != pi->len) {
> + path_alloc = xmemdupz(pi->match, len);
> 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;
> + return 0;
> }