bloom: enable bloom filter with wildcard pathspec in revision traversal
PATCH 1/1 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. Enable Bloom filter even if a pathspec item contains wildcard characters by filter only the non-wildcard part of the pathspec item. Also Enable Bloom filter if magic signature is not "exclude" or "icase".
With this optimization, we get some improvements for pathspec with wildcard and magic signature. First, in the Git repository we see these modest results:
git log -100 -- "t/*"
Benchmark 1: new
Time (mean ± σ): 20.7 ms ± 0.5 ms Range (min … max): 19.8 ms … 21.8 ms
Benchmark 2: old
Time (mean ± σ): 25.4 ms ± 0.6 ms Range (min … max): 24.1 ms … 26.8 ms
git log -100 -- ":(top)t"
Benchmark 1: new
Time (mean ± σ): 15.3 ms ± 0.3 ms Range (min … max): 14.5 ms … 16.1 ms
Benchmark 2: old
Time (mean ± σ): 19.5 ms ± 0.5 ms Range (min … max): 18.7 ms … 20.7 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 ± σ): 10.1 ms ± 0.7 ms
Range (min … max): 8.7 ms … 11.5 ms
Benchmark 2: old
Time (mean ± σ): 26.1 ms ± 0.7 ms Range (min … max): 24.6 ms … 27.4 ms
git log -100 -- ":(top)libc"
Benchmark 1: new
Time (mean ± σ): 11.0 ms ± 0.8 ms
Range (min … max): 9.6 ms … 13.9 ms
Benchmark 2: old
Time (mean ± σ): 20.7 ms ± 0.8 ms Range (min … max): 18.8 ms … 21.8 ms
--- revision.c | 26 ++++++++++++++++++++------ t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++---- 2 files changed, 47 insertions(+), 10 deletions(-)
revision.c +20 -6
@@ -671,12 +671,13 @@ 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 ) +int forbid_mask = +PATHSPEC_EXCLUDE |PATHSPEC_ICASE ; + +if (spec->magic & forbid_mask)return 1 ;for (size_t nr =0 ; nr < spec->nr; nr++) -if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +if (spec->items[nr].magic & forbid_mask)return 1 ;return 0 ;
@@ -693,9 +694,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,size_t len;int res =0 ; + len = pi->nowildcard_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--; +else 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--; + } + +if (len != pi->len) { + path_alloc =xmemdupz (pi->match, len); path = path_alloc; }else path = pi->match;
t/t4216-log-bloom.sh +27 -4
@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' ' test_bloom_filters_used "-- file*" ' -test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' ' + test_bloom_filters_used "-- A/\* file4" && + test_bloom_filters_used "-- file4 A/\*" && + test_bloom_filters_used "-- * A/\*" +' + +test_expect_success 'git log with path only contains wildcard part 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_bloom_filters_not_used "-- file\* A/\*" && + test_bloom_filters_not_used "-- file\* *" && + test_bloom_filters_not_used "-- \*" +' + +test_expect_success 'git log with path contains various magic signatures' ' + cd A && + test_bloom_filters_used "-- \:\(top\)B" && + cd .. && + + test_bloom_filters_used "-- \:\(glob\)A/\*\*/C" && + test_bloom_filters_not_used "-- \:\(icase\)FILE4" && + test_bloom_filters_not_used "-- \:\(exclude\)A/B/C" && + + cat >.gitattributes <<-EOF && + A/file1 text + A/B/file2 -text + EOF + test_bloom_filters_used "-- \:\(attr\:text\)A" && + rm .gitattributes ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.39.5 (Apple Git-154)
On Thu, Aug 07, 2025 at 01:12:43PM +0800, Lidong Yan wrote:
In the subject it should be s/enable bloom/enable Bloom.
Quoted 7 lines
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.
Let's add a paragraph here, as we now switch into the "what is being done mode".
Quoted 2 lines
Enable Bloom filter even if a pathspec item contains wildcard characters by filter only the non-wildcard part of the pathspec item.
s/by filter/by filtering/
Quoted 2 lines
Also Enable Bloom filter if magic signature is not "exclude" or "icase".
This explains what is done, but not why this is safe to do.
Quoted 2 lines
With this optimization, we get some improvements for pathspec with wildcard and magic signature. First, in the Git repository we see these
"for pathspecs with wildcards or magic signatures".
revision.c static void trace2_bloom_filter_statistics_atexit(void) · line 674
Quoted 12 lines
revision.c +1
-3@@ -671,12 +671,13 @@ 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 ) + int forbid_mask =
The mask should be unsigned.
revision.c static void trace2_bloom_filter_statistics_atexit(void) · line 675
Quoted 1 line
revision.c +1
-0+PATHSPEC_EXCLUDE |PATHSPEC_ICASE ;
I think instead of a forbid-mask we should use an allow-mask. Otherwise it can happen quite easily that we add new magic that isn't compatible with Bloom filters but forget to update this part here. I'd rather be slow but correct than fast but incorrect.
Quoted 23 lines
revision.c +10
-3+if (spec->magic & forbid_mask)return 1 ;for (size_t nr =0 ; nr < spec->nr; nr++) -if (spec->items[nr].magic & ~PATHSPEC_LITERAL ) +if (spec->items[nr].magic & forbid_mask)return 1 ;return 0 ;@@ -693,9 +694,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,size_t len;int res =0 ; + len = pi->nowildcard_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--; +else 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
revision.c static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out, · line 715
Quoted 10 lines
revision.c +7
-0+*/ +while (len >0 && pi->match[len -1 ] !='/' ) + len--; + } + +if (len != pi->len) { + path_alloc =xmemdupz (pi->match, len); path = path_alloc; }else path = pi->match;
Okay, this matches what I've expected: if we have a wildcard we cannot match on the component that contains the wildcard itself. But what we _can_ do is to match on all the components leading to that wildcard component.
One thing I did wonder though: what happens if the first component contains the wildcard? We cannot really make any use of the Bloom filter in that case as the path we match against becomes empty. I expect that we'll handle this just fine. But is it still more performant than not even trying Bloom filters in the first place?
Quoted 27 lines
t/t4216-log-bloom.sh +14
-4@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' ' test_bloom_filters_used "-- file*" ' -test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' ' + test_bloom_filters_used "-- A/\* file4" && + test_bloom_filters_used "-- file4 A/\*" && + test_bloom_filters_used "-- * A/\*" +' + +test_expect_success 'git log with path only contains wildcard part 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_bloom_filters_not_used "-- file\* A/\*" && + test_bloom_filters_not_used "-- file\* *" && + test_bloom_filters_not_used "-- \*" +' + +test_expect_success 'git log with path contains various magic signatures' ' + cd A &&
t/t4216-log-bloom.sh test_expect_success 'git log with multiple literal paths uses Bloom filter' ' · line 181
Quoted 10 lines
t/t4216-log-bloom.sh +10
-0+ test_bloom_filters_used "-- \:\(top\)B" && + cd .. && + + test_bloom_filters_used "-- \:\(glob\)A/\*\*/C" && + test_bloom_filters_not_used "-- \:\(icase\)FILE4" && + test_bloom_filters_not_used "-- \:\(exclude\)A/B/C" && + + cat >.gitattributes <<-EOF && + A/file1 text + A/B/file2 -text
We typically indent the heredoc text to the same level as the command.
t/t4216-log-bloom.sh test_expect_success 'git log with multiple literal paths uses Bloom filter' ' · line 184
Quoted 3 lines
t/t4216-log-bloom.sh +3
-0+ EOF + test_bloom_filters_used "-- \:\(attr\:text\)A" && + rm .gitattributes
You can use `test_when_finished" instead to clean up after yourself even in case the test fails.
Quoted 19 lines · Patrick Steinhardt
On Thu, Aug 07, 2025 at 01:12:43PM +0800, Lidong Yan wrote:
In the subject it should be s/enable bloom/enable Bloom.
Quoted 7 lines
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.
Let's add a paragraph here, as we now switch into the "what is being done mode".
Quoted 2 lines
Enable Bloom filter even if a pathspec item contains wildcard characters by filter only the non-wildcard part of the pathspec item.
Quoted 6 lines
s/by filter/by filtering/
Quoted 2 lines
With this optimization, we get some improvements for pathspec with wildcard and magic signature. First, in the Git repository we see these
"for pathspecs with wildcards or magic signatures".
Will fix all the grammatical errors in next version.
Quoted 4 lines
Quoted 2 lines
Also Enable Bloom filter if magic signature is not "exclude" or "icase".
This explains what is done, but not why this is safe to do.
I forgot to mention this — I’ll make sure to include it in the next commit message.
Quoted 16 lines
revision.c static void trace2_bloom_filter_statistics_atexit(void) · line 674
Quoted 13 lines
revision.c +1
-3@@ -671,12 +671,13 @@ 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 ) + int forbid_mask =The mask should be
unsigned.
Quoted 6 lines
revision.c static void trace2_bloom_filter_statistics_atexit(void) · line 675
Quoted 1 line
revision.c +1
-0+PATHSPEC_EXCLUDE |PATHSPEC_ICASE ;I think instead of a forbid-mask we should use an allow-mask. Otherwise it can happen quite easily that we add new magic that isn't compatible with Bloom filters but forget to update this part here. I'd rather be slow but correct than fast but incorrect.
Interesting and reasonable point — will fix.
Quoted 6 lines
One thing I did wonder though: what happens if the first component contains the wildcard? We cannot really make any use of the Bloom filter in that case as the path we match against becomes empty. I expect that we'll handle this just fine. But is it still more performant than not even trying Bloom filters in the first place?
If the first component contains the wildcard, convert_pathspec_to_bloom_keyvec() failed and returns -1, which lead to prepare_to_use_bloom_filter() cleanup (free and NULLing) all bloom filter related field. So the performant would be as same as bloom filter is not even tried.
I actually find a bug in my code and I will add test and fix it, the code should be
if (len != pi->len) while (len > 0 && pi->match[len - 1]) len—; if (len > 0 && pi->match[len - 1] == ‘/‘) len—;
Quoted 1 line
We typically indent the heredoc text to the same level as the command.
Got it, will fix.
Quoted 7 lines
revision.c static void trace2_bloom_filter_statistics_atexit(void) · line 678
Quoted 4 lines
revision.c +3
-0+EOF + test_bloom_filters_used "-- \:\(attr\:text\)A" && + rm .gitattributesYou can use `test_when_finished" instead to clean up after yourself even in case the test fails.
I see — I never knew how to deal with the issue where one failing test case causes all subsequent tests to fail.
Thanks,
Lidong
Quoted 12 lines · Patrick Steinhardt
On Thu, Aug 07, 2025 at 01:12:43PM +0800, Lidong Yan wrote:
In the subject it should be s/enable bloom/enable Bloom.
Quoted 7 lines
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.
Quoted 2 lines
Let's add a paragraph here, as we now switch into the "what is being done mode".
I agree, a paragraph break is very welcome here. I was confused when I read this first that you are suggesting to add a new paragraph with unspecified contents.
Quoted 4 lines
Quoted 2 lines
Also Enable Bloom filter if magic signature is not "exclude" or "icase".
This explains what is done, but not why this is safe to do.
And for that, the enumeration needs to be done inclusively, e.g. "we know :(literal) is OK because we can do X; we know :(glob) is OK because we can do Y".
The numbers are impressive ;-)
Quoted 15 lines
revision.c static void trace2_bloom_filter_statistics_atexit(void) · line 674
Quoted 12 lines
revision.c +1
-3@@ -671,12 +671,13 @@ 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 ) + int forbid_mask =The mask should be
unsigned.
Quoted 6 lines
revision.c static void trace2_bloom_filter_statistics_atexit(void) · line 675
Quoted 1 line
revision.c +1
-0+PATHSPEC_EXCLUDE |PATHSPEC_ICASE ;I think instead of a forbid-mask we should use an allow-mask. Otherwise it can happen quite easily that we add new magic that isn't compatible with Bloom filters but forget to update this part here. I'd rather be slow but correct than fast but incorrect.
Good suggestion. From the use of &-, it is obvious it is a mask, but "allow-mask" is not clear among what kind of things some are allowed, so how about calling it:
unsigned allowed_magic;
Thanks.
Quoted 2 lines · Junio C Hamano
The numbers are impressive ;-)
The bad news is that the Git versions I tested are 2.39 and 2.51, and I used git commit-graph write --split to build the commit graph, which resulted in a large value for filter_not_present in trace.perf.
The good news is that after rebuilding the commit-graph, I repeated the experiment on HEAD and HEAD~1, and the results on HEAD were still better. Anyway, I will update the experimental results in the next patch.
Thanks,
Lidong
PATCH v2 1/1 bloom: enable bloom filter with wildcard pathspec in revision traversal
In reply to Lidong YanWhen 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
--- revision.c | 30 ++++++++++++++++++++++++------ t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++---- 2 files changed, 51 insertions(+), 10 deletions(-)
revision.c +24 -6
@@ -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 ;
@@ -693,9 +698,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,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 != pi->len) { + path_alloc =xmemdupz (pi->match, len); path = path_alloc; }else path = pi->match;
t/t4216-log-bloom.sh +27 -4
@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' ' test_bloom_filters_used "-- file*" ' -test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' ' + test_bloom_filters_used "-- A/\* file4" && + test_bloom_filters_used "-- A/file\*" && + test_bloom_filters_used "-- * A/\*" +' + +test_expect_success 'git log with path only contains wildcard part 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_bloom_filters_not_used "-- file\* A/\*" && + test_bloom_filters_not_used "-- file\* *" && + test_bloom_filters_not_used "-- \*" +' + +test_expect_success 'git log with path contains various magic signatures' ' + cd A && + test_bloom_filters_used "-- \:\(top\)B" && + cd .. && + + test_bloom_filters_used "-- \:\(glob\)A/\*\*/C" && + test_bloom_filters_not_used "-- \:\(icase\)FILE4" && + test_bloom_filters_not_used "-- \:\(exclude\)A/B/C" && + + test_when_finished "rm -f .gitattributes" && + cat >.gitattributes <<-EOF && + A/file1 text + A/B/file2 -text + EOF + test_bloom_filters_used "-- \:\(attr\:text\)A" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.39.5 (Apple Git-154)
Quoted 8 lines · Lidong Yan
static int
forbid_bloom_filters(struct pathspec *spec){(quoted diff) +3
-3- if (spec->has_wildcard) - return 1; - if (spec->magic & ~PATHSPEC_LITERAL) + unsigned int allowed_magic = + PATHSPEC_FROMTOP | + PATHSPEC_MAXDEPTH |
Review
Quoted 10 lines
(quoted diff) +6
-1+ 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;
Quite straight-forward and easy to see that this is a simple enhancement of the existing code. Good.
Review static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out, · line 705
Quoted 9 lines
(quoted diff) +5
-0@@ -693,9 +698,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out, 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
Leading "/" makes it look as if the pathspec element can begin with a slash, but it can not, can it?
Review static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out, · line 709
Quoted 4 lines
(quoted diff) +4
-0+ * bloom filter + */ + while (len > 0 && pi->match[len - 1] != '/') + len--;
In a tree that has both "builtin/" directory and "builtin.h" file, what pathspec_element do we get here when we run
$ git log "builtin*"
We need to be able to catch commits that touch anything in "builtin/" and also anything at the top-level that begins with "builtin", like "builtin.h" and other things that might have existed ever in the history. I think len goes down to 0 and that is the correct behaviour.
The code does deal with the case where len is reduced down to zero, but a bit poorly. It would allocate a zero-length string, then realize it frees it, and returns -1. As it must know how long the resulting path is before it allocated, and by definition len is pi->len if it did not have to allocate, it should be able to take the "goto cleanup" code path before it even attempts to allocate, and it should not have to do strlen(). But the current code is not incorrect.
Quoted 5 lines
(quoted diff) +2
-2+ } /* 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] == '/')
Review static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,
Quoted 10 lines
(quoted diff) +6
-0+ len--; + + if (len != pi->len) { + path_alloc = xmemdupz(pi->match, len); path = path_alloc; } else path = pi->match; +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' ' + test_bloom_filters_used "-- A/\* file4" &&
We'd ask the Bloom filter: skip commits that you know that can never be touching either "A/(anything)" or "file4".
Review
Quoted 1 line
(quoted diff) +1
-0+ test_bloom_filters_used "-- A/file\*" &&
We'd ask the Bloom filter: skip commits that you know that can never be touching either "A/".
Review
Quoted 1 line
(quoted diff) +1
-0+ test_bloom_filters_used "-- * A/\*"
What do we ask? The second one says that a commit that might touch "A/(something)" is worth investigating, but what about the first one?
Ahhh, that one is not quoted, so the shell expands to existing files (which presumably do not have any wildcard characters). OK. If the lone * were quoted, we shouldn't be using the Bloom filter.
Review
Quoted 4 lines
+'
(quoted diff) +2
-0+ +test_expect_success 'git log with path only contains wildcard part does not use Bloom filter' ' test_bloom_filters_not_used "-- file\*" &&
OK, this is exactly the case I wondered about in the above wrt "builtin*" and I agree with the expectation of this test.
Review
Quoted 4 lines
(quoted diff) +1
-3- test_bloom_filters_not_used "-- A/\* file4" && - test_bloom_filters_not_used "-- file4 A/\*" && - test_bloom_filters_not_used "-- * A/\*" + test_bloom_filters_not_used "-- file\* A/\*" &&
This one I understand. The first one reduces len down to 0 in the wildcard stripping loop, and makes us say "a commit that might touch any path is worth investigating", which amounts to the same thing as not using the Bloom filter at all.
Review
Quoted 1 line
(quoted diff) +1
-0+ test_bloom_filters_not_used "-- file\* *" &&
Ditto. Even if the unquoted * may expand to many concrete paths, "file\*" that can match any path that begins with "file" that ever have existed in the history would not help skipping any commit.
Review
Quoted 1 line
(quoted diff) +1
-0+ test_bloom_filters_not_used "-- \*"
Ditto.
Quoted 8 lines
+'
(quoted diff) +7
-0+ +test_expect_success 'git log with path contains various magic signatures' ' + cd A && + test_bloom_filters_used "-- \:\(top\)B" && + cd .. && + + test_bloom_filters_used "-- \:\(glob\)A/\*\*/C" &&
Review
Quoted 10 lines
(quoted diff) +9
-0+ test_bloom_filters_not_used "-- \:\(icase\)FILE4" && + test_bloom_filters_not_used "-- \:\(exclude\)A/B/C" && + + test_when_finished "rm -f .gitattributes" && + cat >.gitattributes <<-EOF && + A/file1 text + A/B/file2 -text + EOF + test_bloom_filters_used "-- \:\(attr\:text\)A" '
OK. Good to see negative test cases here, which we sometimes forget to test when showing off our shiny new toy.
Taking what I suggested above, here is a possible improvement.
revision.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-)
revision.c +8 -10
@@ -696,14 +696,14 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,char *path_alloc =NULL ;const char *path;size_t len; -int res =0 ; +int res =-1 ;/* be pessimistic */ 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 +* 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--;
@@ -712,19 +712,17 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,if (len >0 && pi->match[len -1 ] =='/' ) len--; +if (!len) + goto cleanup; +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); + res =0 ; cleanup:free (path_alloc);
Quoted 5 lines · Junio C Hamano
Quoted 5 lines
revision.c +0
-0@@ -693,9 +698,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,size_t len;int res =0 ;
Quoted 8 lines
Review static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out, · line 705
Quoted 5 lines
(quoted diff) +5
-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 theLeading "/" makes it look as if the pathspec element can begin with a slash, but it can not, can it?
Yes, seems like if we pass a absolute path "/path/to/repository/dir/file”, git will automatically move "/path/to/repository” (in setup.c abspath_part_inside_repo()) So I should remove leading slash in my comment.
Quoted 50 lines
Taking what I suggested above, here is a possible improvement.
revision.c| 18 ++++++++----------1 file changed, 8 insertions(+), 10 deletions(-)revision.c +8
-10@@ -696,14 +696,14 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,char *path_alloc =NULL ;const char *path;size_t len; -int res =0 ; +int res =-1 ;/* be pessimistic */ 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 +* 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--;@@ -712,19 +712,17 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,if (len >0 && pi->match[len -1 ] =='/' ) len--; +if (!len) + goto cleanup; +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); + res =0 ;
Quoted 2 lines
cleanup:
free(path_alloc);
Thanks, I will apply this and add your signed-off. Lidong
PATCH v3 1/1 bloom: enable bloom filter with wildcard pathspec in revision traversal
In reply to Junio C HamanoWhen 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
[jc: avoid allocating zero length path inconvert_pathspec_to_bloom_keyvec()]
--- revision.c | 37 +++++++++++++++++++++++++++---------- t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++---- 2 files changed, 54 insertions(+), 14 deletions(-)
revision.c +27 -10
@@ -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 ;
@@ -693,19 +698,31 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,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 ); - path = path_alloc; - }else - path = pi->match; +if (len >0 && pi->match[len -1 ] =='/' ) + len--; - len =strlen (path);if (!len) { res =-1 ; goto cleanup; } +if (len != pi->len) { + path_alloc =xmemdupz (pi->match, len); + path = path_alloc; + }else + path = pi->match; + *out =bloom_keyvec_new (path, len, settings); cleanup:
t/t4216-log-bloom.sh +27 -4
@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' ' test_bloom_filters_used "-- file*" ' -test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' ' + test_bloom_filters_used "-- A/\* file4" && + test_bloom_filters_used "-- A/file\*" && + test_bloom_filters_used "-- * A/\*" +' + +test_expect_success 'git log with path only contains wildcard part 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_bloom_filters_not_used "-- file\* A/\*" && + test_bloom_filters_not_used "-- file\* *" && + test_bloom_filters_not_used "-- \*" +' + +test_expect_success 'git log with path contains various magic signatures' ' + cd A && + test_bloom_filters_used "-- \:\(top\)B" && + cd .. && + + test_bloom_filters_used "-- \:\(glob\)A/\*\*/C" && + test_bloom_filters_not_used "-- \:\(icase\)FILE4" && + test_bloom_filters_not_used "-- \:\(exclude\)A/B/C" && + + test_when_finished "rm -f .gitattributes" && + cat >.gitattributes <<-EOF && + A/file1 text + A/B/file2 -text + EOF + test_bloom_filters_used "-- \:\(attr\:text\)A" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.51.0.rc0.49.gea0dd4b6b4.dirty
PATCH v4 1/1 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
[jc: avoid allocating zero length path inconvert_pathspec_to_bloom_keyvec()]
--- revision.c | 45 +++++++++++++++++++++++++++----------------- t/t4216-log-bloom.sh | 31 ++++++++++++++++++++++++++---- 2 files changed, 55 insertions(+), 21 deletions(-)
revision.c +28 -17
@@ -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 ; }static void prepare_to_use_bloom_filter (struct rev_info *revs)
t/t4216-log-bloom.sh +27 -4
@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' ' test_bloom_filters_used "-- file*" ' -test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' ' + test_bloom_filters_used "-- A/\* file4" && + test_bloom_filters_used "-- A/file\*" && + test_bloom_filters_used "-- * A/\*" +' + +test_expect_success 'git log with path only contains wildcard part 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_bloom_filters_not_used "-- file\* A/\*" && + test_bloom_filters_not_used "-- file\* *" && + test_bloom_filters_not_used "-- \*" +' + +test_expect_success 'git log with path contains various magic signatures' ' + cd A && + test_bloom_filters_used "-- \:\(top\)B" && + cd .. && + + test_bloom_filters_used "-- \:\(glob\)A/\*\*/C" && + test_bloom_filters_not_used "-- \:\(icase\)FILE4" && + test_bloom_filters_not_used "-- \:\(exclude\)A/B/C" && + + test_when_finished "rm -f .gitattributes" && + cat >.gitattributes <<-EOF && + A/file1 text + A/B/file2 -text + EOF + test_bloom_filters_used "-- \:\(attr\:text\)A" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.39.5 (Apple Git-154)
Quoted 138 lines · Lidong Yan
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 msBenchmark 2: old
Time (mean ± σ): 23.4 ms ± 0.5 ms Range (min … max): 22.5 ms … 24.7 msgit log -100 -- ":(top)t"
Benchmark 1: new
Time (mean ± σ): 16.2 ms ± 0.4 ms Range (min … max): 15.3 ms … 17.2 msBenchmark 2: old
Time (mean ± σ): 18.6 ms ± 0.5 ms Range (min … max): 17.6 ms … 20.4 msBut 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 msBenchmark 2: old
Time (mean ± σ): 26.7 ms ± 0.5 ms Range (min … max): 25.4 ms … 27.8 msgit log -100 -- ":(top)libc"
Benchmark 1: new
Time (mean ± σ): 15.6 ms ± 0.6 ms Range (min … max): 14.4 ms … 17.7 msBenchmark 2: old
Time (mean ± σ): 19.6 ms ± 0.5 ms Range (min … max): 18.6 ms … 20.6 msSigned-off-by Lidong Yan <[email protected]>[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]Signed-off-by Junio C Hamano <[email protected]>---
revision.c| 45 +++++++++++++++++++++++++++-----------------t/t4216-log-bloom.sh| 31 ++++++++++++++++++++++++++----2 files changed, 55 insertions(+), 21 deletions(-)revision.c +27
-10@@ -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 ;
revision.c static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out, · line 725
Quoted 10 lines
revision.c +1
-7- goto cleanup; - } - *out =bloom_keyvec_new (path, len, settings); - -cleanup: -free (path_alloc); -return res; +return 0 ; }
I realized that I shouldn’t delete free(path_alloc) part in the patch. I wonder if Junio could help remove that part from the patch.
Thanks,
Lidong
PATCH v5 1/1 bloom: enable bloom filter with wildcard pathspec in revision traversal
In reply to Lidong YanWhen 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
[jc: avoid allocating zero length path inconvert_pathspec_to_bloom_keyvec()]
--- revision.c | 42 +++++++++++++++++++++++++++++------------- t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++---- 2 files changed, 56 insertions(+), 17 deletions(-)
revision.c +29 -13
@@ -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,23 +696,34 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,char *path_alloc =NULL ;const char *path;size_t len; -int res =0 ; +int res =-1 ; + 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) + goto cleanup; + +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); + res =0 ; cleanup:free (path_alloc);return res;
t/t4216-log-bloom.sh +27 -4
@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' ' test_bloom_filters_used "-- file*" ' -test_expect_success 'git log with path contains a wildcard does not use Bloom filter' ' +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' ' + test_bloom_filters_used "-- A/\* file4" && + test_bloom_filters_used "-- A/file\*" && + test_bloom_filters_used "-- * A/\*" +' + +test_expect_success 'git log with path only contains wildcard part 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_bloom_filters_not_used "-- file\* A/\*" && + test_bloom_filters_not_used "-- file\* *" && + test_bloom_filters_not_used "-- \*" +' + +test_expect_success 'git log with path contains various magic signatures' ' + cd A && + test_bloom_filters_used "-- \:\(top\)B" && + cd .. && + + test_bloom_filters_used "-- \:\(glob\)A/\*\*/C" && + test_bloom_filters_not_used "-- \:\(icase\)FILE4" && + test_bloom_filters_not_used "-- \:\(exclude\)A/B/C" && + + test_when_finished "rm -f .gitattributes" && + cat >.gitattributes <<-EOF && + A/file1 text + A/B/file2 -text + EOF + test_bloom_filters_used "-- \:\(attr\:text\)A" ' test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
Signature · 1 line
2.39.5 (Apple Git-154)
Quoted 4 lines · Lidong Yan
Signed-off-by Lidong Yan <[email protected]>[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]Signed-off-by Junio C Hamano <[email protected]>
Instead just do
here. [who: comment] followed by a sign-off from that person is done by the person who is signing off the tweak, not by the original author.
No need to resend; I'll fix it up locally.
Thanks.
Quoted 8 lines · Junio C Hamano
Quoted 4 lines · Lidong Yan
Signed-off-by Lidong Yan <[email protected]>[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]Signed-off-by Junio C Hamano <[email protected]>
Quoted 8 lines
Instead just do
Helped-by Junio C Hamano <[email protected]>Signed-off-by Lidong Yan <[email protected]>here. [who: comment] followed by a sign-off from that person is done by the person who is signing off the tweak, not by the original author.
I see — when someone makes additions to another person’s commit, they’ll also modify the log message in the process.
Thanks,
Lidong
Quoted 2 lines · Lidong Yan
[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]
This is different from what I did, though.
revision.c static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out, · line 707
Quoted 11 lines
revision.c +7
-0@@ -693,19 +698,31 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,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 +*/
A missing full-stop.
Quoted 17 lines
revision.c +5
-6+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 ); - path = path_alloc; - }else - path = pi->match; +if (len >0 && pi->match[len -1 ] =='/' ) + len--; - len =strlen (path);if (!len) { res =-1 ; goto cleanup; }
revision.c static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out, · line 728
Quoted 10 lines
revision.c +6
-0+if (len != pi->len) { + path_alloc =xmemdupz (pi->match, len); + path = path_alloc; + }else + path = pi->match; + *out =bloom_keyvec_new (path, len, settings); cleanup:
Two comments.
* For a function that finds an error condition in the middle and jumps to the "cleanup:" label at the end, it is more future-proof to start pessimistic (i.e. initialize 'res' to error(-1)) and flip 'res' to success(0) at the very end when everything went well. It would simplify the change necessary when we need to add _more_ early error return code paths to the function in the future.
But this flip from "assume success" to "assume failure" is something that should be not be done as part of this patch; perhaps doing it a separate preliminary clean-up patch is a better way to do so.
* I think the change from v3 (this one) to v4 makes the function worse; we found that it is a good practice to have a single place to release any resources we temporarily acquired and arrange exception handling code to just jump there during the course of this project.
The current implementation may happen to have only one such early return (i.e. "len has become 0; we realize that we cannot use the Bloom filter"), but adding a new early return in the future would be easier if you kept the original arrangement. The new early return condition may have to be computed after we have acquired resources we need to release, so it may need more than a simple "return -1".
Quoted 7 lines · Junio C Hamano
Quoted 2 lines · Lidong Yan
[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]This is different from what I did, though.
Sorry, I don’t fully understand what you mean — should I remove this line or rewrite it?
Quoted 5 lines
Quoted 5 lines
revision.c +0
-0@@ -693,19 +698,31 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,size_t len;int res =0 ;
Quoted 9 lines
revision.c static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out, · line 707
Quoted 7 lines
revision.c +7
-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 +*/ A missing full-stop.
Will fix.
Quoted 39 lines
Quoted 27 lines
revision.c +11
-6+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 ); - path = path_alloc; - }else - path = pi->match; +if (len >0 && pi->match[len -1 ] =='/' ) + len--; - len =strlen (path);if (!len) { res =-1 ; goto cleanup; } +if (len != pi->len) { + path_alloc =xmemdupz (pi->match, len); + path = path_alloc; + }else + path = pi->match; + *out =bloom_keyvec_new (path, len, settings);Quoted 1 line
cleanup:
Two comments.
* For a function that finds an error condition in the middle and jumps to the "cleanup:" label at the end, it is more future-proof to start pessimistic (i.e. initialize 'res' to error(-1)) and flip 'res' to success(0) at the very end when everything went well. It would simplify the change necessary when we need to add _more_ early error return code paths to the function in the future.
Quoted 4 lines
But this flip from "assume success" to "assume failure" is something that should be not be done as part of this patch; perhaps doing it a separate preliminary clean-up patch is a better way to do so.
Ah, I’ve always thought that ret = -1; goto cleanup; was a kind of the everybody-should-use pattern. So when I saw you write int ret = -1; first, I was a bit puzzled. Now I understand what you mean, and I’ll add a cleanup patch.
Quoted 7 lines
* I think the change from v3 (this one) to v4 makes the function worse; we found that it is a good practice to have a single place to release any resources we temporarily acquired and arrange exception handling code to just jump there during the course of this project.
Quoted 7 lines
The current implementation may happen to have only one such early return (i.e. "len has become 0; we realize that we cannot use the Bloom filter"), but adding a new early return in the future would be easier if you kept the original arrangement. The new early return condition may have to be computed after we have acquired resources we need to release, so it may need more than a simple "return -1”.
Understand. I was thinking about less code is better. I will add the cleanup part back.
Thanks,
Lidong