Skip to contentSkip to conversation

bloom: enable bloom filter with wildcard pathspec in revision traversal

PATCH Superseded Lidong Yan 3 participants 16 messages Aug 7, 2025 – Aug 11, 2025

lore
Share & tools
lore

Lidong Yan

author
#0 lore raw

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
index 18f300d455..ef8c0b6eca 100644
@@ -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
index 639868ac56..d8200e4dcb 100755
@@ -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)
#1 lore raw

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
index 18f300d455..ef8c0b6eca 100644
@@ -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
index 639868ac56..d8200e4dcb 100755
@@ -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.

author
#2 lore raw
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
index 18f300d455..ef8c0b6eca 100644
@@ -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 .gitattributes

You 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

#3 lore raw
In reply to Patrick Steinhardt
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
index 18f300d455..ef8c0b6eca 100644
@@ -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.

author
#4 lore raw
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

author
#5 lore raw

PATCH v2 1/1 bloom: enable bloom filter with wildcard pathspec in revision traversal

In reply to 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 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
index 18f300d455..2a5b98390e 100644
@@ -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
index 639868ac56..1064990de3 100755
@@ -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)
#6 lore raw
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
index 2a5b98390e..2a92bdda84 100644
@@ -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);
author
#7 lore raw
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 the

Leading "/" 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
index 2a5b98390e..2a92bdda84 100644
@@ -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

author
#8 lore raw

PATCH v3 1/1 bloom: enable bloom filter with wildcard pathspec in revision traversal

In reply to Junio C Hamano

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 in
convert_pathspec_to_bloom_keyvec()]

---
 revision.c           | 37 +++++++++++++++++++++++++++----------
 t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----
 2 files changed, 54 insertions(+), 14 deletions(-)
revision.c +27 -10
index 18f300d455..386c52aba1 100644
@@ -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
index 639868ac56..1064990de3 100755
@@ -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
author
#9 lore raw

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 in
convert_pathspec_to_bloom_keyvec()]

---
 revision.c           | 45 +++++++++++++++++++++++++++-----------------
 t/t4216-log-bloom.sh | 31 ++++++++++++++++++++++++++----
 2 files changed, 55 insertions(+), 21 deletions(-)
revision.c +28 -17
index 18f300d455..79372fd483 100644
@@ -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
index 639868ac56..1064990de3 100755
@@ -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)
author
#10 lore raw
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 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 in
convert_pathspec_to_bloom_keyvec()]

---
revision.c | 45 +++++++++++++++++++++++++++-----------------
t/t4216-log-bloom.sh | 31 ++++++++++++++++++++++++++----

2 files changed, 55 insertions(+), 21 deletions(-)
revision.c +27 -10
index 18f300d455..79372fd483 100644
@@ -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

author
#11 lore raw

PATCH v5 1/1 bloom: enable bloom filter with wildcard pathspec in revision traversal

In reply to 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 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 in
convert_pathspec_to_bloom_keyvec()]

---
 revision.c           | 42 +++++++++++++++++++++++++++++-------------
 t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----
 2 files changed, 56 insertions(+), 17 deletions(-)
revision.c +29 -13
index 18f300d455..7449064def 100644
@@ -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
index 639868ac56..1064990de3 100755
@@ -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)
#12 lore raw
Quoted 4 lines · Lidong Yan

[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]

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.

author
#13 lore raw
Quoted 8 lines · Junio C Hamano
Quoted 4 lines · Lidong Yan

[jc: avoid allocating zero length path in
convert_pathspec_to_bloom_keyvec()]

Quoted 8 lines

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.

I see — when someone makes additions to another person’s commit, they’ll also modify the log message in the process.

Thanks,
Lidong

#14 lore raw
In reply to Lidong Yan
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".

author
#15 lore raw
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