{"thread":{"id":"63922","subject":"[PATCH] bloom: enable bloom filter with wildcard pathspec in revision traversal","startedAt":"2025-08-07T05:13:17Z","lastAt":"2025-08-11T16:08:17Z","messageCount":16,"participants":["Lidong Yan","Patrick Steinhardt","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"523702","messageId":"20250807051243.96884-1-yldhome2d2@gmail.com","threadId":"63922","inReplyTo":null,"subject":"[PATCH] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-07T05:12:43Z","receivedAt":"2025-08-07T05:13:17Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"When traversing commits, a pathspec item can be used to limit the\ntraversal to commits that modify the specified paths. And the\ncommit-graph includes a Bloom filter to exclude commits that definitely\ndid not modify a given pathspec item. During commit traversal, the\nBloom filter can significantly improve performance. However, it is\ndisabled if the specified pathspec item contains wildcard characters\nor magic signatures. Enable Bloom filter even if a pathspec item\ncontains wildcard characters by filter only the non-wildcard part of\nthe pathspec item. Also Enable Bloom filter if magic signature is not\n\"exclude\" or \"icase\".\n\nWith this optimization, we get some improvements for pathspec with\nwildcard and magic signature. First, in the Git repository we see these\nmodest results:\n\ngit log -100 -- \"t/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      20.7 ms ±   0.5 ms\n  Range (min … max):    19.8 ms …  21.8 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      25.4 ms ±   0.6 ms\n  Range (min … max):    24.1 ms …  26.8 ms\n\ngit log -100 -- \":(top)t\"\n\nBenchmark 1: new\n  Time (mean ± σ):      15.3 ms ±   0.3 ms\n  Range (min … max):    14.5 ms …  16.1 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      19.5 ms ±   0.5 ms\n  Range (min … max):    18.7 ms …  20.7 ms\n\nBut in a larger repo, such as the LLVM project repo below, we get even\nbetter results:\n\ngit log -100 -- \"libc/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      10.1 ms ±   0.7 ms\n  Range (min … max):     8.7 ms …  11.5 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      26.1 ms ±   0.7 ms\n  Range (min … max):    24.6 ms …  27.4 ms\n\ngit log -100 -- \":(top)libc\"\n\nBenchmark 1: new\n  Time (mean ± σ):      11.0 ms ±   0.8 ms\n  Range (min … max):     9.6 ms …  13.9 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      20.7 ms ±   0.8 ms\n  Range (min … max):    18.8 ms …  21.8 ms\n\nSigned-off-by: Lidong Yan <yldhome2d2@gmail.com>\n---\n revision.c           | 26 ++++++++++++++++++++------\n t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----\n 2 files changed, 47 insertions(+), 10 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 18f300d455..ef8c0b6eca 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -671,12 +671,13 @@ static void trace2_bloom_filter_statistics_atexit(void)\n \n static int forbid_bloom_filters(struct pathspec *spec)\n {\n-\tif (spec->has_wildcard)\n-\t\treturn 1;\n-\tif (spec->magic & ~PATHSPEC_LITERAL)\n+\tint forbid_mask =\n+\t\tPATHSPEC_EXCLUDE | PATHSPEC_ICASE;\n+\n+\tif (spec->magic & forbid_mask)\n \t\treturn 1;\n \tfor (size_t nr = 0; nr < spec->nr; nr++)\n-\t\tif (spec->items[nr].magic & ~PATHSPEC_LITERAL)\n+\t\tif (spec->items[nr].magic & forbid_mask)\n \t\t\treturn 1;\n \n \treturn 0;\n@@ -693,9 +694,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n \tsize_t len;\n \tint res = 0;\n \n+\tlen = pi->nowildcard_len;\n \t/* remove single trailing slash from path, if needed */\n-\tif (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n-\t\tpath_alloc = xmemdupz(pi->match, pi->len - 1);\n+\tif (len > 0 && pi->match[len - 1] == '/')\n+\t\tlen--;\n+\telse if (len != pi->len) {\n+\t\t/*\n+\t\t * for path like \"/dir/file*\", nowildcard part would be\n+\t\t * \"/dir/file\", but only \"/dir\" should be used for the\n+\t\t * bloom filter\n+\t\t */\n+\t\twhile (len > 0 && pi->match[len - 1] != '/')\n+\t\t\tlen--;\n+\t}\n+\n+\tif (len != pi->len) {\n+\t\tpath_alloc = xmemdupz(pi->match, len);\n \t\tpath = path_alloc;\n \t} else\n \t\tpath = pi->match;\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 639868ac56..d8200e4dcb 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' '\n \ttest_bloom_filters_used \"-- file*\"\n '\n \n-test_expect_success 'git log with path contains a wildcard does not use Bloom filter' '\n+test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' '\n+\ttest_bloom_filters_used \"-- A/\\* file4\" &&\n+\ttest_bloom_filters_used \"-- file4 A/\\*\" &&\n+\ttest_bloom_filters_used \"-- * A/\\*\"\n+'\n+\n+test_expect_success 'git log with path only contains wildcard part does not use Bloom filter' '\n \ttest_bloom_filters_not_used \"-- file\\*\" &&\n-\ttest_bloom_filters_not_used \"-- A/\\* file4\" &&\n-\ttest_bloom_filters_not_used \"-- file4 A/\\*\" &&\n-\ttest_bloom_filters_not_used \"-- * A/\\*\"\n+\ttest_bloom_filters_not_used \"-- file\\* A/\\*\" &&\n+\ttest_bloom_filters_not_used \"-- file\\* *\" &&\n+\ttest_bloom_filters_not_used \"-- \\*\"\n+'\n+\n+test_expect_success 'git log with path contains various magic signatures' '\n+\tcd A &&\n+\ttest_bloom_filters_used \"-- \\:\\(top\\)B\" &&\n+\tcd .. &&\n+\n+\ttest_bloom_filters_used \"-- \\:\\(glob\\)A/\\*\\*/C\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(icase\\)FILE4\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(exclude\\)A/B/C\" &&\n+\n+\tcat >.gitattributes <<-EOF &&\n+\t\tA/file1 text\n+\t\tA/B/file2 -text\n+\tEOF\n+\ttest_bloom_filters_used \"-- \\:\\(attr\\:text\\)A\" &&\n+\trm .gitattributes\n '\n \n test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '\n-- \n2.39.5 (Apple Git-154)\n\n"},{"id":"523709","messageId":"aJRMaYfMd3PlRtoz@pks.im","threadId":"63922","inReplyTo":"20250807051243.96884-1-yldhome2d2@gmail.com","subject":"Re: [PATCH] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-08-07T06:49:13Z","receivedAt":"2025-08-07T06:49:20Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Aug 07, 2025 at 01:12:43PM +0800, Lidong Yan wrote:\n\nIn the subject it should be s/enable bloom/enable Bloom.\n\n> When traversing commits, a pathspec item can be used to limit the\n> traversal to commits that modify the specified paths. And the\n> commit-graph includes a Bloom filter to exclude commits that definitely\n> did not modify a given pathspec item. During commit traversal, the\n> Bloom filter can significantly improve performance. However, it is\n> disabled if the specified pathspec item contains wildcard characters\n> or magic signatures.\n\nLet's add a paragraph here, as we now switch into the \"what is being\ndone mode\".\n\n> Enable Bloom filter even if a pathspec item contains wildcard\n> characters by filter only the non-wildcard part of the pathspec item.\n\ns/by filter/by filtering/\n\n> Also Enable Bloom filter if magic signature is not \"exclude\" or\n> \"icase\".\n\nThis explains what is done, but not why this is safe to do.\n\n> With this optimization, we get some improvements for pathspec with\n> wildcard and magic signature. First, in the Git repository we see these\n\n\"for pathspecs with wildcards or magic signatures\".\n\n> diff --git a/revision.c b/revision.c\n> index 18f300d455..ef8c0b6eca 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -671,12 +671,13 @@ static void trace2_bloom_filter_statistics_atexit(void)\n>  \n>  static int forbid_bloom_filters(struct pathspec *spec)\n>  {\n> -\tif (spec->has_wildcard)\n> -\t\treturn 1;\n> -\tif (spec->magic & ~PATHSPEC_LITERAL)\n> +\tint forbid_mask =\n\nThe mask should be `unsigned`.\n\n> +\t\tPATHSPEC_EXCLUDE | PATHSPEC_ICASE;\n\nI think instead of a forbid-mask we should use an allow-mask. Otherwise\nit can happen quite easily that we add new magic that isn't compatible\nwith Bloom filters but forget to update this part here. I'd rather be\nslow but correct than fast but incorrect.\n\n> +\tif (spec->magic & forbid_mask)\n>  \t\treturn 1;\n>  \tfor (size_t nr = 0; nr < spec->nr; nr++)\n> -\t\tif (spec->items[nr].magic & ~PATHSPEC_LITERAL)\n> +\t\tif (spec->items[nr].magic & forbid_mask)\n>  \t\t\treturn 1;\n>  \n>  \treturn 0;\n> @@ -693,9 +694,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n>  \tsize_t len;\n>  \tint res = 0;\n>  \n> +\tlen = pi->nowildcard_len;\n>  \t/* remove single trailing slash from path, if needed */\n> -\tif (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n> -\t\tpath_alloc = xmemdupz(pi->match, pi->len - 1);\n> +\tif (len > 0 && pi->match[len - 1] == '/')\n> +\t\tlen--;\n> +\telse if (len != pi->len) {\n> +\t\t/*\n> +\t\t * for path like \"/dir/file*\", nowildcard part would be\n> +\t\t * \"/dir/file\", but only \"/dir\" should be used for the\n> +\t\t * bloom filter\n> +\t\t */\n> +\t\twhile (len > 0 && pi->match[len - 1] != '/')\n> +\t\t\tlen--;\n> +\t}\n> +\n> +\tif (len != pi->len) {\n> +\t\tpath_alloc = xmemdupz(pi->match, len);\n>  \t\tpath = path_alloc;\n>  \t} else\n>  \t\tpath = pi->match;\n\nOkay, this matches what I've expected: if we have a wildcard we cannot\nmatch on the component that contains the wildcard itself. But what we\n_can_ do is to match on all the components leading to that wildcard\ncomponent.\n\nOne thing I did wonder though: what happens if the first component\ncontains the wildcard? We cannot really make any use of the Bloom filter\nin that case as the path we match against becomes empty. I expect that\nwe'll handle this just fine. But is it still more performant than not\neven trying Bloom filters in the first place?\n\n> diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\n> index 639868ac56..d8200e4dcb 100755\n> --- a/t/t4216-log-bloom.sh\n> +++ b/t/t4216-log-bloom.sh\n> @@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' '\n>  \ttest_bloom_filters_used \"-- file*\"\n>  '\n>  \n> -test_expect_success 'git log with path contains a wildcard does not use Bloom filter' '\n> +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' '\n> +\ttest_bloom_filters_used \"-- A/\\* file4\" &&\n> +\ttest_bloom_filters_used \"-- file4 A/\\*\" &&\n> +\ttest_bloom_filters_used \"-- * A/\\*\"\n> +'\n> +\n> +test_expect_success 'git log with path only contains wildcard part does not use Bloom filter' '\n>  \ttest_bloom_filters_not_used \"-- file\\*\" &&\n> -\ttest_bloom_filters_not_used \"-- A/\\* file4\" &&\n> -\ttest_bloom_filters_not_used \"-- file4 A/\\*\" &&\n> -\ttest_bloom_filters_not_used \"-- * A/\\*\"\n> +\ttest_bloom_filters_not_used \"-- file\\* A/\\*\" &&\n> +\ttest_bloom_filters_not_used \"-- file\\* *\" &&\n> +\ttest_bloom_filters_not_used \"-- \\*\"\n> +'\n> +\n> +test_expect_success 'git log with path contains various magic signatures' '\n> +\tcd A &&\n> +\ttest_bloom_filters_used \"-- \\:\\(top\\)B\" &&\n> +\tcd .. &&\n> +\n> +\ttest_bloom_filters_used \"-- \\:\\(glob\\)A/\\*\\*/C\" &&\n> +\ttest_bloom_filters_not_used \"-- \\:\\(icase\\)FILE4\" &&\n> +\ttest_bloom_filters_not_used \"-- \\:\\(exclude\\)A/B/C\" &&\n> +\n> +\tcat >.gitattributes <<-EOF &&\n> +\t\tA/file1 text\n> +\t\tA/B/file2 -text\n\nWe typically indent the heredoc text to the same level as the command.\n\n> +\tEOF\n> +\ttest_bloom_filters_used \"-- \\:\\(attr\\:text\\)A\" &&\n> +\trm .gitattributes\n\nYou can use `test_when_finished\" instead to clean up after yourself even\nin case the test fails.\n"},{"id":"523741","messageId":"4B24EAB9-6D52-4D97-A3D8-FF72A12701C7@gmail.com","threadId":"63922","inReplyTo":"aJRMaYfMd3PlRtoz@pks.im","subject":"Re: [PATCH] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-07T08:59:42Z","receivedAt":"2025-08-07T09:00:02Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"Patrick Steinhardt <ps@pks.im> wrote:\n> \n> On Thu, Aug 07, 2025 at 01:12:43PM +0800, Lidong Yan wrote:\n> \n> In the subject it should be s/enable bloom/enable Bloom.\n> \n>> When traversing commits, a pathspec item can be used to limit the\n>> traversal to commits that modify the specified paths. And the\n>> commit-graph includes a Bloom filter to exclude commits that definitely\n>> did not modify a given pathspec item. During commit traversal, the\n>> Bloom filter can significantly improve performance. However, it is\n>> disabled if the specified pathspec item contains wildcard characters\n>> or magic signatures.\n> \n> Let's add a paragraph here, as we now switch into the \"what is being\n> done mode\".\n> \n>> Enable Bloom filter even if a pathspec item contains wildcard\n>> characters by filter only the non-wildcard part of the pathspec item.\n> \n> s/by filter/by filtering/\n> \n>> With this optimization, we get some improvements for pathspec with\n>> wildcard and magic signature. First, in the Git repository we see these\n> \n> \"for pathspecs with wildcards or magic signatures\".\n\nWill fix all the grammatical errors in next version.\n\n\n>> Also Enable Bloom filter if magic signature is not \"exclude\" or\n>> \"icase\".\n> \n> This explains what is done, but not why this is safe to do.\n\nI forgot to mention this — I’ll make sure to include it in the next commit message. \n\n> \n>> diff --git a/revision.c b/revision.c\n>> index 18f300d455..ef8c0b6eca 100644\n>> --- a/revision.c\n>> +++ b/revision.c\n>> @@ -671,12 +671,13 @@ static void trace2_bloom_filter_statistics_atexit(void)\n>> \n>> static int forbid_bloom_filters(struct pathspec *spec)\n>> {\n>> - if (spec->has_wildcard)\n>> - return 1;\n>> - if (spec->magic & ~PATHSPEC_LITERAL)\n>> + int forbid_mask =\n> \n> The mask should be `unsigned`.\n> \n>> + PATHSPEC_EXCLUDE | PATHSPEC_ICASE;\n> \n> I think instead of a forbid-mask we should use an allow-mask. Otherwise\n> it can happen quite easily that we add new magic that isn't compatible\n> with Bloom filters but forget to update this part here. I'd rather be\n> slow but correct than fast but incorrect.\n\nInteresting and reasonable point — will fix.\n\n> \n> One thing I did wonder though: what happens if the first component\n> contains the wildcard? We cannot really make any use of the Bloom filter\n> in that case as the path we match against becomes empty. I expect that\n> we'll handle this just fine. But is it still more performant than not\n> even trying Bloom filters in the first place?\n\nIf the first component contains the wildcard, convert_pathspec_to_bloom_keyvec()\nfailed and returns -1, which lead to prepare_to_use_bloom_filter() cleanup (free and NULLing)\nall bloom filter related field. So the performant would be as same as bloom filter is\nnot even tried.\n\nI actually find a bug in my code and I will add test and fix it, the code should be\n\n\tif (len != pi->len)\n\t\twhile (len > 0 && pi->match[len - 1])\n\t\t\tlen—;\n\tif (len > 0 && pi->match[len - 1] == ‘/‘)\n\t\tlen—;\n\n> We typically indent the heredoc text to the same level as the command.\n\nGot it, will fix.\n\n> \n>> + EOF\n>> + test_bloom_filters_used \"-- \\:\\(attr\\:text\\)A\" &&\n>> + rm .gitattributes\n> \n> You can use `test_when_finished\" instead to clean up after yourself even\n> in case the test fails.\n\nI see — I never knew how to deal with the issue where one failing test case\ncauses all subsequent tests to fail.\n\nThanks,\nLidong\n\n"},{"id":"523761","messageId":"xmqqa54brtve.fsf@gitster.g","threadId":"63922","inReplyTo":"aJRMaYfMd3PlRtoz@pks.im","subject":"Re: [PATCH] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-07T16:15:01Z","receivedAt":"2025-08-07T16:15:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> On Thu, Aug 07, 2025 at 01:12:43PM +0800, Lidong Yan wrote:\n>\n> In the subject it should be s/enable bloom/enable Bloom.\n>\n>> When traversing commits, a pathspec item can be used to limit the\n>> traversal to commits that modify the specified paths. And the\n>> commit-graph includes a Bloom filter to exclude commits that definitely\n>> did not modify a given pathspec item. During commit traversal, the\n>> Bloom filter can significantly improve performance. However, it is\n>> disabled if the specified pathspec item contains wildcard characters\n>> or magic signatures.\n>\n> Let's add a paragraph here, as we now switch into the \"what is being\n> done mode\".\n\nI agree, a paragraph break is very welcome here.  I was confused\nwhen I read this first that you are suggesting to add a new\nparagraph with unspecified contents.\n\n>> Also Enable Bloom filter if magic signature is not \"exclude\" or\n>> \"icase\".\n>\n> This explains what is done, but not why this is safe to do.\n\nAnd for that, the enumeration needs to be done inclusively, e.g. \"we\nknow :(literal) is OK because we can do X; we know :(glob) is OK\nbecause we can do Y\".\n\nThe numbers are impressive ;-)\n\n>> diff --git a/revision.c b/revision.c\n>> index 18f300d455..ef8c0b6eca 100644\n>> --- a/revision.c\n>> +++ b/revision.c\n>> @@ -671,12 +671,13 @@ static void trace2_bloom_filter_statistics_atexit(void)\n>>  \n>>  static int forbid_bloom_filters(struct pathspec *spec)\n>>  {\n>> -\tif (spec->has_wildcard)\n>> -\t\treturn 1;\n>> -\tif (spec->magic & ~PATHSPEC_LITERAL)\n>> +\tint forbid_mask =\n>\n> The mask should be `unsigned`.\n>\n>> +\t\tPATHSPEC_EXCLUDE | PATHSPEC_ICASE;\n>\n> I think instead of a forbid-mask we should use an allow-mask. Otherwise\n> it can happen quite easily that we add new magic that isn't compatible\n> with Bloom filters but forget to update this part here. I'd rather be\n> slow but correct than fast but incorrect.\n\nGood suggestion.  From the use of &-, it is obvious it is a mask, but\n\"allow-mask\" is not clear among what kind of things some are\nallowed, so how about calling it:\n\n    unsigned allowed_magic;\n\nThanks.\n"},{"id":"523801","messageId":"1369D2B0-9B41-40F4-ADE1-B109F0B7B56C@gmail.com","threadId":"63922","inReplyTo":"xmqqa54brtve.fsf@gitster.g","subject":"Re: [PATCH] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-08T06:40:42Z","receivedAt":"2025-08-08T06:41:00Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n> \n> The numbers are impressive ;-)\n\nThe bad news is that the Git versions I tested are 2.39 and 2.51, and I used\ngit commit-graph write --split to build the commit graph, which resulted in a\nlarge value for filter_not_present in trace.perf.\n\nThe good news is that after rebuilding the commit-graph, I repeated the experiment\non HEAD and HEAD~1, and the results on HEAD were still better. Anyway, I will\nupdate the experimental results in the next patch.\n\nThanks,\nLidong"},{"id":"523802","messageId":"20250808065834.22743-1-yldhome2d2@gmail.com","threadId":"63922","inReplyTo":"20250807051243.96884-1-yldhome2d2@gmail.com","subject":"[PATCH v2] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-08T06:58:34Z","receivedAt":"2025-08-08T06:58:54Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"When traversing commits, a pathspec item can be used to limit the\ntraversal to commits that modify the specified paths. And the\ncommit-graph includes a Bloom filter to exclude commits that definitely\ndid not modify a given pathspec item. During commit traversal, the\nBloom filter can significantly improve performance. However, it is\ndisabled if the specified pathspec item contains wildcard characters\nor magic signatures.\n\nFor performance reason, enable Bloom filter even if a pathspec item\ncontains wildcard characters by filtering only the non-wildcard part of\nthe pathspec item.\n\nThe function of pathspec magic signature is generally to narrow down\nthe path specified by the pathspecs. So, enable Bloom filter when\nthe magic signature is \"top\", \"glob\", \"attr\", \"--depth\" or \"literal\".\n\"exclude\" is used to select paths other than the specified path, rather\nthan serving as a filtering function, so it cannot be used together with\nthe Bloom filter. Since Bloom filter is not case insensitive even in\ncase insensitive system (e.g. MacOS), it cannot be used together with\n\"icase\" magic.\n\nWith this optimization, we get some improvements for pathspecs with\nwildcards or magic signatures. First, in the Git repository we see these\nmodest results:\n\ngit log -100 -- \"t/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      20.4 ms ±   0.6 ms\n  Range (min … max):    19.3 ms …  24.4 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      23.4 ms ±   0.5 ms\n  Range (min … max):    22.5 ms …  24.7 ms\n\ngit log -100 -- \":(top)t\"\n\nBenchmark 1: new\n  Time (mean ± σ):      16.2 ms ±   0.4 ms\n  Range (min … max):    15.3 ms …  17.2 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      18.6 ms ±   0.5 ms\n  Range (min … max):    17.6 ms …  20.4 ms\n\nBut in a larger repo, such as the LLVM project repo below, we get even\nbetter results:\n\ngit log -100 -- \"libc/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      16.0 ms ±   0.6 ms\n  Range (min … max):    14.7 ms …  17.8 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      26.7 ms ±   0.5 ms\n  Range (min … max):    25.4 ms …  27.8 ms\n\ngit log -100 -- \":(top)libc\"\n\nBenchmark 1: new\n  Time (mean ± σ):      15.6 ms ±   0.6 ms\n  Range (min … max):    14.4 ms …  17.7 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      19.6 ms ±   0.5 ms\n  Range (min … max):    18.6 ms …  20.6 ms\n\nSigned-off-by: Lidong Yan <yldhome2d2@gmail.com>\n---\n revision.c           | 30 ++++++++++++++++++++++++------\n t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----\n 2 files changed, 51 insertions(+), 10 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 18f300d455..2a5b98390e 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -671,12 +671,17 @@ static void trace2_bloom_filter_statistics_atexit(void)\n \n static int forbid_bloom_filters(struct pathspec *spec)\n {\n-\tif (spec->has_wildcard)\n-\t\treturn 1;\n-\tif (spec->magic & ~PATHSPEC_LITERAL)\n+\tunsigned int allowed_magic =\n+\t\tPATHSPEC_FROMTOP |\n+\t\tPATHSPEC_MAXDEPTH |\n+\t\tPATHSPEC_LITERAL |\n+\t\tPATHSPEC_GLOB |\n+\t\tPATHSPEC_ATTR;\n+\n+\tif (spec->magic & ~allowed_magic)\n \t\treturn 1;\n \tfor (size_t nr = 0; nr < spec->nr; nr++)\n-\t\tif (spec->items[nr].magic & ~PATHSPEC_LITERAL)\n+\t\tif (spec->items[nr].magic & ~allowed_magic)\n \t\t\treturn 1;\n \n \treturn 0;\n@@ -693,9 +698,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n \tsize_t len;\n \tint res = 0;\n \n+\tlen = pi->nowildcard_len;\n+\tif (len != pi->len) {\n+\t\t/*\n+\t\t * for path like \"/dir/file*\", nowildcard part would be\n+\t\t * \"/dir/file\", but only \"/dir\" should be used for the\n+\t\t * bloom filter\n+\t\t */\n+\t\twhile (len > 0 && pi->match[len - 1] != '/')\n+\t\t\tlen--;\n+\t}\n \t/* remove single trailing slash from path, if needed */\n-\tif (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n-\t\tpath_alloc = xmemdupz(pi->match, pi->len - 1);\n+\tif (len > 0 && pi->match[len - 1] == '/')\n+\t\tlen--;\n+\n+\tif (len != pi->len) {\n+\t\tpath_alloc = xmemdupz(pi->match, len);\n \t\tpath = path_alloc;\n \t} else\n \t\tpath = pi->match;\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 639868ac56..1064990de3 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' '\n \ttest_bloom_filters_used \"-- file*\"\n '\n \n-test_expect_success 'git log with path contains a wildcard does not use Bloom filter' '\n+test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' '\n+\ttest_bloom_filters_used \"-- A/\\* file4\" &&\n+\ttest_bloom_filters_used \"-- A/file\\*\" &&\n+\ttest_bloom_filters_used \"-- * A/\\*\"\n+'\n+\n+test_expect_success 'git log with path only contains wildcard part does not use Bloom filter' '\n \ttest_bloom_filters_not_used \"-- file\\*\" &&\n-\ttest_bloom_filters_not_used \"-- A/\\* file4\" &&\n-\ttest_bloom_filters_not_used \"-- file4 A/\\*\" &&\n-\ttest_bloom_filters_not_used \"-- * A/\\*\"\n+\ttest_bloom_filters_not_used \"-- file\\* A/\\*\" &&\n+\ttest_bloom_filters_not_used \"-- file\\* *\" &&\n+\ttest_bloom_filters_not_used \"-- \\*\"\n+'\n+\n+test_expect_success 'git log with path contains various magic signatures' '\n+\tcd A &&\n+\ttest_bloom_filters_used \"-- \\:\\(top\\)B\" &&\n+\tcd .. &&\n+\n+\ttest_bloom_filters_used \"-- \\:\\(glob\\)A/\\*\\*/C\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(icase\\)FILE4\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(exclude\\)A/B/C\" &&\n+\n+\ttest_when_finished \"rm -f .gitattributes\" &&\n+\tcat >.gitattributes <<-EOF &&\n+\tA/file1 text\n+\tA/B/file2 -text\n+\tEOF\n+\ttest_bloom_filters_used \"-- \\:\\(attr\\:text\\)A\"\n '\n \n test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '\n-- \n2.39.5 (Apple Git-154)\n\n"},{"id":"523828","messageId":"xmqqsei1izhs.fsf@gitster.g","threadId":"63922","inReplyTo":"20250808065834.22743-1-yldhome2d2@gmail.com","subject":"Re: [PATCH v2] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-08T15:50:39Z","receivedAt":"2025-08-08T15:50:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lidong Yan <yldhome2d2@gmail.com> writes:\n\n>  static int forbid_bloom_filters(struct pathspec *spec)\n>  {\n> -\tif (spec->has_wildcard)\n> -\t\treturn 1;\n> -\tif (spec->magic & ~PATHSPEC_LITERAL)\n> +\tunsigned int allowed_magic =\n> +\t\tPATHSPEC_FROMTOP |\n> +\t\tPATHSPEC_MAXDEPTH |\n> +\t\tPATHSPEC_LITERAL |\n> +\t\tPATHSPEC_GLOB |\n> +\t\tPATHSPEC_ATTR;\n> +\n> +\tif (spec->magic & ~allowed_magic)\n>  \t\treturn 1;\n>  \tfor (size_t nr = 0; nr < spec->nr; nr++)\n> -\t\tif (spec->items[nr].magic & ~PATHSPEC_LITERAL)\n> +\t\tif (spec->items[nr].magic & ~allowed_magic)\n>  \t\t\treturn 1;\n\nQuite straight-forward and easy to see that this is a simple\nenhancement of the existing code.  Good.\n\n> @@ -693,9 +698,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n>  \tsize_t len;\n>  \tint res = 0;\n>  \n> +\tlen = pi->nowildcard_len;\n> +\tif (len != pi->len) {\n> +\t\t/*\n> +\t\t * for path like \"/dir/file*\", nowildcard part would be\n> +\t\t * \"/dir/file\", but only \"/dir\" should be used for the\n\nLeading \"/\" makes it look as if the pathspec element can begin with\na slash, but it can not, can it?\n\n> +\t\t * bloom filter\n> +\t\t */\n> +\t\twhile (len > 0 && pi->match[len - 1] != '/')\n> +\t\t\tlen--;\n\nIn a tree that has both \"builtin/\" directory and \"builtin.h\" file,\nwhat pathspec_element do we get here when we run\n\n\t$ git log \"builtin*\"\n\nWe need to be able to catch commits that touch anything in\n\"builtin/\" and also anything at the top-level that begins with\n\"builtin\", like \"builtin.h\" and other things that might have existed\never in the history.  I think len goes down to 0 and that is the\ncorrect behaviour.\n\nThe code does deal with the case where len is reduced down to zero,\nbut a bit poorly.  It would allocate a zero-length string, then\nrealize it frees it, and returns -1.  As it must know how long the\nresulting path is before it allocated, and by definition len is\npi->len if it did not have to allocate, it should be able to take\nthe \"goto cleanup\" code path before it even attempts to allocate,\nand it should not have to do strlen().  But the current code is not\nincorrect.\n\n> +\t}\n>  \t/* remove single trailing slash from path, if needed */\n> -\tif (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n> -\t\tpath_alloc = xmemdupz(pi->match, pi->len - 1);\n> +\tif (len > 0 && pi->match[len - 1] == '/')\n> +\t\tlen--;\n> +\n> +\tif (len != pi->len) {\n> +\t\tpath_alloc = xmemdupz(pi->match, len);\n>  \t\tpath = path_alloc;\n>  \t} else\n>  \t\tpath = pi->match;\n\n> +test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' '\n> +\ttest_bloom_filters_used \"-- A/\\* file4\" &&\n\nWe'd ask the Bloom filter: skip commits that you know that can never\nbe touching either \"A/(anything)\" or \"file4\".\n\n> +\ttest_bloom_filters_used \"-- A/file\\*\" &&\n\nWe'd ask the Bloom filter: skip commits that you know that can never\nbe touching either \"A/\".\n\n> +\ttest_bloom_filters_used \"-- * A/\\*\"\n\nWhat do we ask?  The second one says that a commit that might touch\n\"A/(something)\" is worth investigating, but what about the first\none?  \n\nAhhh, that one is not quoted, so the shell expands to existing files\n(which presumably do not have any wildcard characters).  OK.  If the\nlone * were quoted, we shouldn't be using the Bloom filter.\n\n> +'\n> +\n> +test_expect_success 'git log with path only contains wildcard part does not use Bloom filter' '\n>  \ttest_bloom_filters_not_used \"-- file\\*\" &&\n\nOK, this is exactly the case I wondered about in the above wrt \"builtin*\"\nand I agree with the expectation of this test.\n\n> -\ttest_bloom_filters_not_used \"-- A/\\* file4\" &&\n> -\ttest_bloom_filters_not_used \"-- file4 A/\\*\" &&\n> -\ttest_bloom_filters_not_used \"-- * A/\\*\"\n> +\ttest_bloom_filters_not_used \"-- file\\* A/\\*\" &&\n\nThis one I understand.  The first one reduces len down to 0 in the\nwildcard stripping loop, and makes us say \"a commit that might touch\nany path is worth investigating\", which amounts to the same thing as\nnot using the Bloom filter at all.\n\n> +\ttest_bloom_filters_not_used \"-- file\\* *\" &&\n\nDitto.  Even if the unquoted * may expand to many concrete paths,\n\"file\\*\" that can match any path that begins with \"file\" that ever\nhave existed in the history would not help skipping any commit.\n\n> +\ttest_bloom_filters_not_used \"-- \\*\"\n\nDitto.\n\n> +'\n> +\n> +test_expect_success 'git log with path contains various magic signatures' '\n> +\tcd A &&\n> +\ttest_bloom_filters_used \"-- \\:\\(top\\)B\" &&\n> +\tcd .. &&\n> +\n> +\ttest_bloom_filters_used \"-- \\:\\(glob\\)A/\\*\\*/C\" &&\n> +\ttest_bloom_filters_not_used \"-- \\:\\(icase\\)FILE4\" &&\n> +\ttest_bloom_filters_not_used \"-- \\:\\(exclude\\)A/B/C\" &&\n> +\n> +\ttest_when_finished \"rm -f .gitattributes\" &&\n> +\tcat >.gitattributes <<-EOF &&\n> +\tA/file1 text\n> +\tA/B/file2 -text\n> +\tEOF\n> +\ttest_bloom_filters_used \"-- \\:\\(attr\\:text\\)A\"\n>  '\n\nOK.  Good to see negative test cases here, which we sometimes forget\nto test when showing off our shiny new toy.\n\nTaking what I suggested above, here is a possible improvement.\n\n revision.c | 18 ++++++++----------\n 1 file changed, 8 insertions(+), 10 deletions(-)\n\ndiff --git i/revision.c w/revision.c\nindex 2a5b98390e..2a92bdda84 100644\n--- i/revision.c\n+++ w/revision.c\n@@ -696,14 +696,14 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n \tchar *path_alloc = NULL;\n \tconst char *path;\n \tsize_t len;\n-\tint res = 0;\n+\tint res = -1; /* be pessimistic */\n \n \tlen = pi->nowildcard_len;\n \tif (len != pi->len) {\n \t\t/*\n-\t\t * for path like \"/dir/file*\", nowildcard part would be\n-\t\t * \"/dir/file\", but only \"/dir\" should be used for the\n-\t\t * bloom filter\n+\t\t * for path like \"dir/file*\", nowildcard part would be\n+\t\t * \"dir/file\", but only \"dir\" should be used for the\n+\t\t * bloom filter.\n \t\t */\n \t\twhile (len > 0 && pi->match[len - 1] != '/')\n \t\t\tlen--;\n@@ -712,19 +712,17 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n \tif (len > 0 && pi->match[len - 1] == '/')\n \t\tlen--;\n \n+\tif (!len)\n+\t\tgoto cleanup;\n+\n \tif (len != pi->len) {\n \t\tpath_alloc = xmemdupz(pi->match, len);\n \t\tpath = path_alloc;\n \t} else\n \t\tpath = pi->match;\n \n-\tlen = strlen(path);\n-\tif (!len) {\n-\t\tres = -1;\n-\t\tgoto cleanup;\n-\t}\n-\n \t*out = bloom_keyvec_new(path, len, settings);\n+\tres = 0;\n \n cleanup:\n \tfree(path_alloc);\n"},{"id":"523861","messageId":"B2F0FE14-AA88-490D-989C-3D93BF972DCF@gmail.com","threadId":"63922","inReplyTo":"xmqqsei1izhs.fsf@gitster.g","subject":"Re: [PATCH v2] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-09T02:06:06Z","receivedAt":"2025-08-09T02:06:20Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n> \n>> @@ -693,9 +698,22 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n>> size_t len;\n>> int res = 0;\n>> \n>> + len = pi->nowildcard_len;\n>> + if (len != pi->len) {\n>> + /*\n>> + * for path like \"/dir/file*\", nowildcard part would be\n>> + * \"/dir/file\", but only \"/dir\" should be used for the\n> \n> Leading \"/\" makes it look as if the pathspec element can begin with\n> a slash, but it can not, can it?\n\nYes, seems like if we pass a absolute path \"/path/to/repository/dir/file”, git\nwill automatically move \"/path/to/repository” (in setup.c abspath_part_inside_repo())\nSo I should remove leading slash in my comment.\n\n> Taking what I suggested above, here is a possible improvement.\n> \n> revision.c | 18 ++++++++----------\n> 1 file changed, 8 insertions(+), 10 deletions(-)\n> \n> diff --git i/revision.c w/revision.c\n> index 2a5b98390e..2a92bdda84 100644\n> --- i/revision.c\n> +++ w/revision.c\n> @@ -696,14 +696,14 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n> char *path_alloc = NULL;\n> const char *path;\n> size_t len;\n> - int res = 0;\n> + int res = -1; /* be pessimistic */\n> \n> len = pi->nowildcard_len;\n> if (len != pi->len) {\n> /*\n> - * for path like \"/dir/file*\", nowildcard part would be\n> - * \"/dir/file\", but only \"/dir\" should be used for the\n> - * bloom filter\n> + * for path like \"dir/file*\", nowildcard part would be\n> + * \"dir/file\", but only \"dir\" should be used for the\n> + * bloom filter.\n> */\n> while (len > 0 && pi->match[len - 1] != '/')\n> len--;\n> @@ -712,19 +712,17 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n> if (len > 0 && pi->match[len - 1] == '/')\n> len--;\n> \n> + if (!len)\n> + goto cleanup;\n> +\n> if (len != pi->len) {\n> path_alloc = xmemdupz(pi->match, len);\n> path = path_alloc;\n> } else\n> path = pi->match;\n> \n> - len = strlen(path);\n> - if (!len) {\n> - res = -1;\n> - goto cleanup;\n> - }\n> -\n> *out = bloom_keyvec_new(path, len, settings);\n> + res = 0;\n> \n> cleanup:\n> free(path_alloc);\n\nThanks, I will apply this and add your signed-off.\nLidong"},{"id":"523862","messageId":"20250809021642.22195-1-yldhome2d2@gmail.com","threadId":"63922","inReplyTo":"xmqqsei1izhs.fsf@gitster.g","subject":"[PATCH v3] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-09T02:16:42Z","receivedAt":"2025-08-09T02:18:02Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"When traversing commits, a pathspec item can be used to limit the\ntraversal to commits that modify the specified paths. And the\ncommit-graph includes a Bloom filter to exclude commits that definitely\ndid not modify a given pathspec item. During commit traversal, the\nBloom filter can significantly improve performance. However, it is\ndisabled if the specified pathspec item contains wildcard characters\nor magic signatures.\n\nFor performance reason, enable Bloom filter even if a pathspec item\ncontains wildcard characters by filtering only the non-wildcard part of\nthe pathspec item.\n\nThe function of pathspec magic signature is generally to narrow down\nthe path specified by the pathspecs. So, enable Bloom filter when\nthe magic signature is \"top\", \"glob\", \"attr\", \"--depth\" or \"literal\".\n\"exclude\" is used to select paths other than the specified path, rather\nthan serving as a filtering function, so it cannot be used together with\nthe Bloom filter. Since Bloom filter is not case insensitive even in\ncase insensitive system (e.g. MacOS), it cannot be used together with\n\"icase\" magic.\n\nWith this optimization, we get some improvements for pathspecs with\nwildcards or magic signatures. First, in the Git repository we see these\nmodest results:\n\ngit log -100 -- \"t/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      20.4 ms ±   0.6 ms\n  Range (min … max):    19.3 ms …  24.4 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      23.4 ms ±   0.5 ms\n  Range (min … max):    22.5 ms …  24.7 ms\n\ngit log -100 -- \":(top)t\"\n\nBenchmark 1: new\n  Time (mean ± σ):      16.2 ms ±   0.4 ms\n  Range (min … max):    15.3 ms …  17.2 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      18.6 ms ±   0.5 ms\n  Range (min … max):    17.6 ms …  20.4 ms\n\nBut in a larger repo, such as the LLVM project repo below, we get even\nbetter results:\n\ngit log -100 -- \"libc/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      16.0 ms ±   0.6 ms\n  Range (min … max):    14.7 ms …  17.8 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      26.7 ms ±   0.5 ms\n  Range (min … max):    25.4 ms …  27.8 ms\n\ngit log -100 -- \":(top)libc\"\n\nBenchmark 1: new\n  Time (mean ± σ):      15.6 ms ±   0.6 ms\n  Range (min … max):    14.4 ms …  17.7 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      19.6 ms ±   0.5 ms\n  Range (min … max):    18.6 ms …  20.6 ms\n\nSigned-off-by: Lidong Yan <yldhome2d2@gmail.com>\n[jc: avoid allocating zero length path in\nconvert_pathspec_to_bloom_keyvec()]\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n revision.c           | 37 +++++++++++++++++++++++++++----------\n t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----\n 2 files changed, 54 insertions(+), 14 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 18f300d455..386c52aba1 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -671,12 +671,17 @@ static void trace2_bloom_filter_statistics_atexit(void)\n \n static int forbid_bloom_filters(struct pathspec *spec)\n {\n-\tif (spec->has_wildcard)\n-\t\treturn 1;\n-\tif (spec->magic & ~PATHSPEC_LITERAL)\n+\tunsigned int allowed_magic =\n+\t\tPATHSPEC_FROMTOP |\n+\t\tPATHSPEC_MAXDEPTH |\n+\t\tPATHSPEC_LITERAL |\n+\t\tPATHSPEC_GLOB |\n+\t\tPATHSPEC_ATTR;\n+\n+\tif (spec->magic & ~allowed_magic)\n \t\treturn 1;\n \tfor (size_t nr = 0; nr < spec->nr; nr++)\n-\t\tif (spec->items[nr].magic & ~PATHSPEC_LITERAL)\n+\t\tif (spec->items[nr].magic & ~allowed_magic)\n \t\t\treturn 1;\n \n \treturn 0;\n@@ -693,19 +698,31 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n \tsize_t len;\n \tint res = 0;\n \n+\tlen = pi->nowildcard_len;\n+\tif (len != pi->len) {\n+\t\t/*\n+\t\t * for path like \"dir/file*\", nowildcard part would be\n+\t\t * \"dir/file\", but only \"dir\" should be used for the\n+\t\t * bloom filter\n+\t\t */\n+\t\twhile (len > 0 && pi->match[len - 1] != '/')\n+\t\t\tlen--;\n+\t}\n \t/* remove single trailing slash from path, if needed */\n-\tif (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n-\t\tpath_alloc = xmemdupz(pi->match, pi->len - 1);\n-\t\tpath = path_alloc;\n-\t} else\n-\t\tpath = pi->match;\n+\tif (len > 0 && pi->match[len - 1] == '/')\n+\t\tlen--;\n \n-\tlen = strlen(path);\n \tif (!len) {\n \t\tres = -1;\n \t\tgoto cleanup;\n \t}\n \n+\tif (len != pi->len) {\n+\t\tpath_alloc = xmemdupz(pi->match, len);\n+\t\tpath = path_alloc;\n+\t} else\n+\t\tpath = pi->match;\n+\n \t*out = bloom_keyvec_new(path, len, settings);\n \n cleanup:\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 639868ac56..1064990de3 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' '\n \ttest_bloom_filters_used \"-- file*\"\n '\n \n-test_expect_success 'git log with path contains a wildcard does not use Bloom filter' '\n+test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' '\n+\ttest_bloom_filters_used \"-- A/\\* file4\" &&\n+\ttest_bloom_filters_used \"-- A/file\\*\" &&\n+\ttest_bloom_filters_used \"-- * A/\\*\"\n+'\n+\n+test_expect_success 'git log with path only contains wildcard part does not use Bloom filter' '\n \ttest_bloom_filters_not_used \"-- file\\*\" &&\n-\ttest_bloom_filters_not_used \"-- A/\\* file4\" &&\n-\ttest_bloom_filters_not_used \"-- file4 A/\\*\" &&\n-\ttest_bloom_filters_not_used \"-- * A/\\*\"\n+\ttest_bloom_filters_not_used \"-- file\\* A/\\*\" &&\n+\ttest_bloom_filters_not_used \"-- file\\* *\" &&\n+\ttest_bloom_filters_not_used \"-- \\*\"\n+'\n+\n+test_expect_success 'git log with path contains various magic signatures' '\n+\tcd A &&\n+\ttest_bloom_filters_used \"-- \\:\\(top\\)B\" &&\n+\tcd .. &&\n+\n+\ttest_bloom_filters_used \"-- \\:\\(glob\\)A/\\*\\*/C\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(icase\\)FILE4\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(exclude\\)A/B/C\" &&\n+\n+\ttest_when_finished \"rm -f .gitattributes\" &&\n+\tcat >.gitattributes <<-EOF &&\n+\tA/file1 text\n+\tA/B/file2 -text\n+\tEOF\n+\ttest_bloom_filters_used \"-- \\:\\(attr\\:text\\)A\"\n '\n \n test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '\n-- \n2.51.0.rc0.49.gea0dd4b6b4.dirty\n\n"},{"id":"523864","messageId":"20250809042236.72695-1-yldhome2d2@gmail.com","threadId":"63922","inReplyTo":"20250809021642.22195-1-yldhome2d2@gmail.com","subject":"[PATCH v4] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-09T04:22:36Z","receivedAt":"2025-08-09T04:23:00Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"When traversing commits, a pathspec item can be used to limit the\ntraversal to commits that modify the specified paths. And the\ncommit-graph includes a Bloom filter to exclude commits that definitely\ndid not modify a given pathspec item. During commit traversal, the\nBloom filter can significantly improve performance. However, it is\ndisabled if the specified pathspec item contains wildcard characters\nor magic signatures.\n\nFor performance reason, enable Bloom filter even if a pathspec item\ncontains wildcard characters by filtering only the non-wildcard part of\nthe pathspec item.\n\nThe function of pathspec magic signature is generally to narrow down\nthe path specified by the pathspecs. So, enable Bloom filter when\nthe magic signature is \"top\", \"glob\", \"attr\", \"--depth\" or \"literal\".\n\"exclude\" is used to select paths other than the specified path, rather\nthan serving as a filtering function, so it cannot be used together with\nthe Bloom filter. Since Bloom filter is not case insensitive even in\ncase insensitive system (e.g. MacOS), it cannot be used together with\n\"icase\" magic.\n\nWith this optimization, we get some improvements for pathspecs with\nwildcards or magic signatures. First, in the Git repository we see these\nmodest results:\n\ngit log -100 -- \"t/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      20.4 ms ±   0.6 ms\n  Range (min … max):    19.3 ms …  24.4 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      23.4 ms ±   0.5 ms\n  Range (min … max):    22.5 ms …  24.7 ms\n\ngit log -100 -- \":(top)t\"\n\nBenchmark 1: new\n  Time (mean ± σ):      16.2 ms ±   0.4 ms\n  Range (min … max):    15.3 ms …  17.2 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      18.6 ms ±   0.5 ms\n  Range (min … max):    17.6 ms …  20.4 ms\n\nBut in a larger repo, such as the LLVM project repo below, we get even\nbetter results:\n\ngit log -100 -- \"libc/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      16.0 ms ±   0.6 ms\n  Range (min … max):    14.7 ms …  17.8 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      26.7 ms ±   0.5 ms\n  Range (min … max):    25.4 ms …  27.8 ms\n\ngit log -100 -- \":(top)libc\"\n\nBenchmark 1: new\n  Time (mean ± σ):      15.6 ms ±   0.6 ms\n  Range (min … max):    14.4 ms …  17.7 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      19.6 ms ±   0.5 ms\n  Range (min … max):    18.6 ms …  20.6 ms\n\nSigned-off-by: Lidong Yan <yldhome2d2@gmail.com>\n[jc: avoid allocating zero length path in\nconvert_pathspec_to_bloom_keyvec()]\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n revision.c           | 45 +++++++++++++++++++++++++++-----------------\n t/t4216-log-bloom.sh | 31 ++++++++++++++++++++++++++----\n 2 files changed, 55 insertions(+), 21 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 18f300d455..79372fd483 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -671,12 +671,17 @@ static void trace2_bloom_filter_statistics_atexit(void)\n \n static int forbid_bloom_filters(struct pathspec *spec)\n {\n-\tif (spec->has_wildcard)\n-\t\treturn 1;\n-\tif (spec->magic & ~PATHSPEC_LITERAL)\n+\tunsigned int allowed_magic =\n+\t\tPATHSPEC_FROMTOP |\n+\t\tPATHSPEC_MAXDEPTH |\n+\t\tPATHSPEC_LITERAL |\n+\t\tPATHSPEC_GLOB |\n+\t\tPATHSPEC_ATTR;\n+\n+\tif (spec->magic & ~allowed_magic)\n \t\treturn 1;\n \tfor (size_t nr = 0; nr < spec->nr; nr++)\n-\t\tif (spec->items[nr].magic & ~PATHSPEC_LITERAL)\n+\t\tif (spec->items[nr].magic & ~allowed_magic)\n \t\t\treturn 1;\n \n \treturn 0;\n@@ -691,26 +696,32 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n \tchar *path_alloc = NULL;\n \tconst char *path;\n \tsize_t len;\n-\tint res = 0;\n \n+\tlen = pi->nowildcard_len;\n+\tif (len != pi->len) {\n+\t\t/*\n+\t\t * for path like \"dir/file*\", nowildcard part would be\n+\t\t * \"dir/file\", but only \"dir\" should be used for the\n+\t\t * bloom filter\n+\t\t */\n+\t\twhile (len > 0 && pi->match[len - 1] != '/')\n+\t\t\tlen--;\n+\t}\n \t/* remove single trailing slash from path, if needed */\n-\tif (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n-\t\tpath_alloc = xmemdupz(pi->match, pi->len - 1);\n+\tif (len > 0 && pi->match[len - 1] == '/')\n+\t\tlen--;\n+\n+\tif (!len)\n+\t\treturn -1;\n+\n+\tif (len != pi->len) {\n+\t\tpath_alloc = xmemdupz(pi->match, len);\n \t\tpath = path_alloc;\n \t} else\n \t\tpath = pi->match;\n \n-\tlen = strlen(path);\n-\tif (!len) {\n-\t\tres = -1;\n-\t\tgoto cleanup;\n-\t}\n-\n \t*out = bloom_keyvec_new(path, len, settings);\n-\n-cleanup:\n-\tfree(path_alloc);\n-\treturn res;\n+\treturn 0;\n }\n \n static void prepare_to_use_bloom_filter(struct rev_info *revs)\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 639868ac56..1064990de3 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' '\n \ttest_bloom_filters_used \"-- file*\"\n '\n \n-test_expect_success 'git log with path contains a wildcard does not use Bloom filter' '\n+test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' '\n+\ttest_bloom_filters_used \"-- A/\\* file4\" &&\n+\ttest_bloom_filters_used \"-- A/file\\*\" &&\n+\ttest_bloom_filters_used \"-- * A/\\*\"\n+'\n+\n+test_expect_success 'git log with path only contains wildcard part does not use Bloom filter' '\n \ttest_bloom_filters_not_used \"-- file\\*\" &&\n-\ttest_bloom_filters_not_used \"-- A/\\* file4\" &&\n-\ttest_bloom_filters_not_used \"-- file4 A/\\*\" &&\n-\ttest_bloom_filters_not_used \"-- * A/\\*\"\n+\ttest_bloom_filters_not_used \"-- file\\* A/\\*\" &&\n+\ttest_bloom_filters_not_used \"-- file\\* *\" &&\n+\ttest_bloom_filters_not_used \"-- \\*\"\n+'\n+\n+test_expect_success 'git log with path contains various magic signatures' '\n+\tcd A &&\n+\ttest_bloom_filters_used \"-- \\:\\(top\\)B\" &&\n+\tcd .. &&\n+\n+\ttest_bloom_filters_used \"-- \\:\\(glob\\)A/\\*\\*/C\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(icase\\)FILE4\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(exclude\\)A/B/C\" &&\n+\n+\ttest_when_finished \"rm -f .gitattributes\" &&\n+\tcat >.gitattributes <<-EOF &&\n+\tA/file1 text\n+\tA/B/file2 -text\n+\tEOF\n+\ttest_bloom_filters_used \"-- \\:\\(attr\\:text\\)A\"\n '\n \n test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '\n-- \n2.39.5 (Apple Git-154)\n\n"},{"id":"523865","messageId":"4CA97F18-6B0D-4CD9-AE3A-6232A8E775FC@gmail.com","threadId":"63922","inReplyTo":"20250809042236.72695-1-yldhome2d2@gmail.com","subject":"Re: [PATCH v4] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-09T07:40:20Z","receivedAt":"2025-08-09T07:40:37Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"Lidong Yan <yldhome2d2@gmail.com> writes:\n> \n> When traversing commits, a pathspec item can be used to limit the\n> traversal to commits that modify the specified paths. And the\n> commit-graph includes a Bloom filter to exclude commits that definitely\n> did not modify a given pathspec item. During commit traversal, the\n> Bloom filter can significantly improve performance. However, it is\n> disabled if the specified pathspec item contains wildcard characters\n> or magic signatures.\n> \n> For performance reason, enable Bloom filter even if a pathspec item\n> contains wildcard characters by filtering only the non-wildcard part of\n> the pathspec item.\n> \n> The function of pathspec magic signature is generally to narrow down\n> the path specified by the pathspecs. So, enable Bloom filter when\n> the magic signature is \"top\", \"glob\", \"attr\", \"--depth\" or \"literal\".\n> \"exclude\" is used to select paths other than the specified path, rather\n> than serving as a filtering function, so it cannot be used together with\n> the Bloom filter. Since Bloom filter is not case insensitive even in\n> case insensitive system (e.g. MacOS), it cannot be used together with\n> \"icase\" magic.\n> \n> With this optimization, we get some improvements for pathspecs with\n> wildcards or magic signatures. First, in the Git repository we see these\n> modest results:\n> \n> git log -100 -- \"t/*\"\n> \n> Benchmark 1: new\n>  Time (mean ± σ):      20.4 ms ±   0.6 ms\n>  Range (min … max):    19.3 ms …  24.4 ms\n> \n> Benchmark 2: old\n>  Time (mean ± σ):      23.4 ms ±   0.5 ms\n>  Range (min … max):    22.5 ms …  24.7 ms\n> \n> git log -100 -- \":(top)t\"\n> \n> Benchmark 1: new\n>  Time (mean ± σ):      16.2 ms ±   0.4 ms\n>  Range (min … max):    15.3 ms …  17.2 ms\n> \n> Benchmark 2: old\n>  Time (mean ± σ):      18.6 ms ±   0.5 ms\n>  Range (min … max):    17.6 ms …  20.4 ms\n> \n> But in a larger repo, such as the LLVM project repo below, we get even\n> better results:\n> \n> git log -100 -- \"libc/*\"\n> \n> Benchmark 1: new\n>  Time (mean ± σ):      16.0 ms ±   0.6 ms\n>  Range (min … max):    14.7 ms …  17.8 ms\n> \n> Benchmark 2: old\n>  Time (mean ± σ):      26.7 ms ±   0.5 ms\n>  Range (min … max):    25.4 ms …  27.8 ms\n> \n> git log -100 -- \":(top)libc\"\n> \n> Benchmark 1: new\n>  Time (mean ± σ):      15.6 ms ±   0.6 ms\n>  Range (min … max):    14.4 ms …  17.7 ms\n> \n> Benchmark 2: old\n>  Time (mean ± σ):      19.6 ms ±   0.5 ms\n>  Range (min … max):    18.6 ms …  20.6 ms\n> \n> Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>\n> [jc: avoid allocating zero length path in\n> convert_pathspec_to_bloom_keyvec()]\n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n> ---\n> revision.c           | 45 +++++++++++++++++++++++++++-----------------\n> t/t4216-log-bloom.sh | 31 ++++++++++++++++++++++++++----\n> 2 files changed, 55 insertions(+), 21 deletions(-)\n> \n> diff --git a/revision.c b/revision.c\n> index 18f300d455..79372fd483 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -671,12 +671,17 @@ static void trace2_bloom_filter_statistics_atexit(void)\n> \n> static int forbid_bloom_filters(struct pathspec *spec)\n> {\n> - if (spec->has_wildcard)\n> - return 1;\n> - if (spec->magic & ~PATHSPEC_LITERAL)\n> + unsigned int allowed_magic =\n> + PATHSPEC_FROMTOP |\n> + PATHSPEC_MAXDEPTH |\n> + PATHSPEC_LITERAL |\n> + PATHSPEC_GLOB |\n> + PATHSPEC_ATTR;\n> +\n> + if (spec->magic & ~allowed_magic)\n> return 1;\n> for (size_t nr = 0; nr < spec->nr; nr++)\n> - if (spec->items[nr].magic & ~PATHSPEC_LITERAL)\n> + if (spec->items[nr].magic & ~allowed_magic)\n> return 1;\n> \n> return 0;\n> @@ -691,26 +696,32 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n> char *path_alloc = NULL;\n> const char *path;\n> size_t len;\n> - int res = 0;\n> \n> + len = pi->nowildcard_len;\n> + if (len != pi->len) {\n> + /*\n> + * for path like \"dir/file*\", nowildcard part would be\n> + * \"dir/file\", but only \"dir\" should be used for the\n> + * bloom filter\n> + */\n> + while (len > 0 && pi->match[len - 1] != '/')\n> + len--;\n> + }\n> /* remove single trailing slash from path, if needed */\n> - if (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n> - path_alloc = xmemdupz(pi->match, pi->len - 1);\n> + if (len > 0 && pi->match[len - 1] == '/')\n> + len--;\n> +\n> + if (!len)\n> + return -1;\n> +\n> + if (len != pi->len) {\n> + path_alloc = xmemdupz(pi->match, len);\n> path = path_alloc;\n> } else\n> path = pi->match;\n> \n> - len = strlen(path);\n> - if (!len) {\n> - res = -1;\n> - goto cleanup;\n> - }\n> -\n> *out = bloom_keyvec_new(path, len, settings);\n> -\n> -cleanup:\n> - free(path_alloc);\n> - return res;\n> + return 0;\n> }\n\nI realized that I shouldn’t delete free(path_alloc) part in the patch. I wonder if\nJunio could help remove that part from the patch.\n\nThanks,\nLidong"},{"id":"523875","messageId":"xmqqpld45a0h.fsf@gitster.g","threadId":"63922","inReplyTo":"20250809021642.22195-1-yldhome2d2@gmail.com","subject":"Re: [PATCH v3] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-09T23:51:42Z","receivedAt":"2025-08-09T23:51:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lidong Yan <yldhome2d2@gmail.com> writes:\n\n> [jc: avoid allocating zero length path in\n> convert_pathspec_to_bloom_keyvec()]\n\nThis is different from what I did, though.\n\n> @@ -693,19 +698,31 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n>  \tsize_t len;\n>  \tint res = 0;\n>  \n> +\tlen = pi->nowildcard_len;\n> +\tif (len != pi->len) {\n> +\t\t/*\n> +\t\t * for path like \"dir/file*\", nowildcard part would be\n> +\t\t * \"dir/file\", but only \"dir\" should be used for the\n> +\t\t * bloom filter\n> +\t\t */\n\nA missing full-stop.\n\n> +\t\twhile (len > 0 && pi->match[len - 1] != '/')\n> +\t\t\tlen--;\n> +\t}\n>  \t/* remove single trailing slash from path, if needed */\n> -\tif (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n> -\t\tpath_alloc = xmemdupz(pi->match, pi->len - 1);\n> -\t\tpath = path_alloc;\n> -\t} else\n> -\t\tpath = pi->match;\n> +\tif (len > 0 && pi->match[len - 1] == '/')\n> +\t\tlen--;\n>  \n> -\tlen = strlen(path);\n>  \tif (!len) {\n>  \t\tres = -1;\n>  \t\tgoto cleanup;\n>  \t}\n>  \n> +\tif (len != pi->len) {\n> +\t\tpath_alloc = xmemdupz(pi->match, len);\n> +\t\tpath = path_alloc;\n> +\t} else\n> +\t\tpath = pi->match;\n> +\n>  \t*out = bloom_keyvec_new(path, len, settings);\n>  \n>  cleanup:\n\nTwo comments.\n\n * For a function that finds an error condition in the middle and\n   jumps to the \"cleanup:\" label at the end, it is more future-proof\n   to start pessimistic (i.e. initialize 'res' to error(-1)) and\n   flip 'res' to success(0) at the very end when everything went\n   well.  It would simplify the change necessary when we need to add\n   _more_ early error return code paths to the function in the\n   future.\n\n   But this flip from \"assume success\" to \"assume failure\" is\n   something that should be not be done as part of this patch;\n   perhaps doing it a separate preliminary clean-up patch is a\n   better way to do so.\n\n * I think the change from v3 (this one) to v4 makes the function\n   worse; we found that it is a good practice to have a single place\n   to release any resources we temporarily acquired and arrange\n   exception handling code to just jump there during the course of\n   this project.\n\n   The current implementation may happen to have only one such early\n   return (i.e. \"len has become 0; we realize that we cannot use the\n   Bloom filter\"), but adding a new early return in the future would\n   be easier if you kept the original arrangement.  The new early\n   return condition may have to be computed after we have acquired\n   resources we need to release, so it may need more than a simple\n   \"return -1\".\n"},{"id":"523882","messageId":"3C87ACC0-DFC0-4941-9611-1325911A92BE@gmail.com","threadId":"63922","inReplyTo":"xmqqpld45a0h.fsf@gitster.g","subject":"Re: [PATCH v3] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-10T01:57:15Z","receivedAt":"2025-08-10T01:57:32Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n> \n> Lidong Yan <yldhome2d2@gmail.com> writes:\n> \n>> [jc: avoid allocating zero length path in\n>> convert_pathspec_to_bloom_keyvec()]\n> \n> This is different from what I did, though.\n\nSorry, I don’t fully understand what you mean — should I remove\nthis line or rewrite it?\n\n> \n>> @@ -693,19 +698,31 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n>> size_t len;\n>> int res = 0;\n>> \n>> + len = pi->nowildcard_len;\n>> + if (len != pi->len) {\n>> + /*\n>> + * for path like \"dir/file*\", nowildcard part would be\n>> + * \"dir/file\", but only \"dir\" should be used for the\n>> + * bloom filter\n>> + */\n> \n> A missing full-stop.\n\nWill fix.\n\n> \n>> + while (len > 0 && pi->match[len - 1] != '/')\n>> + len--;\n>> + }\n>> /* remove single trailing slash from path, if needed */\n>> - if (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n>> - path_alloc = xmemdupz(pi->match, pi->len - 1);\n>> - path = path_alloc;\n>> - } else\n>> - path = pi->match;\n>> + if (len > 0 && pi->match[len - 1] == '/')\n>> + len--;\n>> \n>> - len = strlen(path);\n>> if (!len) {\n>> res = -1;\n>> goto cleanup;\n>> }\n>> \n>> + if (len != pi->len) {\n>> + path_alloc = xmemdupz(pi->match, len);\n>> + path = path_alloc;\n>> + } else\n>> + path = pi->match;\n>> +\n>> *out = bloom_keyvec_new(path, len, settings);\n>> \n>> cleanup:\n> \n> Two comments.\n> \n> * For a function that finds an error condition in the middle and\n>   jumps to the \"cleanup:\" label at the end, it is more future-proof\n>   to start pessimistic (i.e. initialize 'res' to error(-1)) and\n>   flip 'res' to success(0) at the very end when everything went\n>   well.  It would simplify the change necessary when we need to add\n>   _more_ early error return code paths to the function in the\n>   future.\n> \n>   But this flip from \"assume success\" to \"assume failure\" is\n>   something that should be not be done as part of this patch;\n>   perhaps doing it a separate preliminary clean-up patch is a\n>   better way to do so.\n\nAh, I’ve always thought that `ret = -1; goto cleanup;` was a kind of the\neverybody-should-use pattern. So when I saw you write `int ret = -1;` first,\nI was a bit puzzled. Now I understand what you mean, and I’ll add a\ncleanup patch.\n\n> \n> * I think the change from v3 (this one) to v4 makes the function\n>   worse; we found that it is a good practice to have a single place\n>   to release any resources we temporarily acquired and arrange\n>   exception handling code to just jump there during the course of\n>   this project.\n> \n>   The current implementation may happen to have only one such early\n>   return (i.e. \"len has become 0; we realize that we cannot use the\n>   Bloom filter\"), but adding a new early return in the future would\n>   be easier if you kept the original arrangement.  The new early\n>   return condition may have to be computed after we have acquired\n>   resources we need to release, so it may need more than a simple\n>   \"return -1”.\n\nUnderstand. I was thinking about less code is better. I will add the cleanup\npart back.\n\nThanks,\nLidong"},{"id":"523908","messageId":"20250811060137.75135-1-yldhome2d2@gmail.com","threadId":"63922","inReplyTo":"20250809042236.72695-1-yldhome2d2@gmail.com","subject":"[PATCH v5] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-11T06:01:37Z","receivedAt":"2025-08-11T06:01:45Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"When traversing commits, a pathspec item can be used to limit the\ntraversal to commits that modify the specified paths. And the\ncommit-graph includes a Bloom filter to exclude commits that definitely\ndid not modify a given pathspec item. During commit traversal, the\nBloom filter can significantly improve performance. However, it is\ndisabled if the specified pathspec item contains wildcard characters\nor magic signatures.\n\nFor performance reason, enable Bloom filter even if a pathspec item\ncontains wildcard characters by filtering only the non-wildcard part of\nthe pathspec item.\n\nThe function of pathspec magic signature is generally to narrow down\nthe path specified by the pathspecs. So, enable Bloom filter when\nthe magic signature is \"top\", \"glob\", \"attr\", \"--depth\" or \"literal\".\n\"exclude\" is used to select paths other than the specified path, rather\nthan serving as a filtering function, so it cannot be used together with\nthe Bloom filter. Since Bloom filter is not case insensitive even in\ncase insensitive system (e.g. MacOS), it cannot be used together with\n\"icase\" magic.\n\nWith this optimization, we get some improvements for pathspecs with\nwildcards or magic signatures. First, in the Git repository we see these\nmodest results:\n\ngit log -100 -- \"t/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      20.4 ms ±   0.6 ms\n  Range (min … max):    19.3 ms …  24.4 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      23.4 ms ±   0.5 ms\n  Range (min … max):    22.5 ms …  24.7 ms\n\ngit log -100 -- \":(top)t\"\n\nBenchmark 1: new\n  Time (mean ± σ):      16.2 ms ±   0.4 ms\n  Range (min … max):    15.3 ms …  17.2 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      18.6 ms ±   0.5 ms\n  Range (min … max):    17.6 ms …  20.4 ms\n\nBut in a larger repo, such as the LLVM project repo below, we get even\nbetter results:\n\ngit log -100 -- \"libc/*\"\n\nBenchmark 1: new\n  Time (mean ± σ):      16.0 ms ±   0.6 ms\n  Range (min … max):    14.7 ms …  17.8 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      26.7 ms ±   0.5 ms\n  Range (min … max):    25.4 ms …  27.8 ms\n\ngit log -100 -- \":(top)libc\"\n\nBenchmark 1: new\n  Time (mean ± σ):      15.6 ms ±   0.6 ms\n  Range (min … max):    14.4 ms …  17.7 ms\n\nBenchmark 2: old\n  Time (mean ± σ):      19.6 ms ±   0.5 ms\n  Range (min … max):    18.6 ms …  20.6 ms\n\nSigned-off-by: Lidong Yan <yldhome2d2@gmail.com>\n[jc: avoid allocating zero length path in\nconvert_pathspec_to_bloom_keyvec()]\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n revision.c           | 42 +++++++++++++++++++++++++++++-------------\n t/t4216-log-bloom.sh | 31 +++++++++++++++++++++++++++----\n 2 files changed, 56 insertions(+), 17 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 18f300d455..7449064def 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -671,12 +671,17 @@ static void trace2_bloom_filter_statistics_atexit(void)\n \n static int forbid_bloom_filters(struct pathspec *spec)\n {\n-\tif (spec->has_wildcard)\n-\t\treturn 1;\n-\tif (spec->magic & ~PATHSPEC_LITERAL)\n+\tunsigned int allowed_magic =\n+\t\tPATHSPEC_FROMTOP |\n+\t\tPATHSPEC_MAXDEPTH |\n+\t\tPATHSPEC_LITERAL |\n+\t\tPATHSPEC_GLOB |\n+\t\tPATHSPEC_ATTR;\n+\n+\tif (spec->magic & ~allowed_magic)\n \t\treturn 1;\n \tfor (size_t nr = 0; nr < spec->nr; nr++)\n-\t\tif (spec->items[nr].magic & ~PATHSPEC_LITERAL)\n+\t\tif (spec->items[nr].magic & ~allowed_magic)\n \t\t\treturn 1;\n \n \treturn 0;\n@@ -691,23 +696,34 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,\n \tchar *path_alloc = NULL;\n \tconst char *path;\n \tsize_t len;\n-\tint res = 0;\n+\tint res = -1;\n \n+\tlen = pi->nowildcard_len;\n+\tif (len != pi->len) {\n+\t\t/*\n+\t\t * for path like \"dir/file*\", nowildcard part would be\n+\t\t * \"dir/file\", but only \"dir\" should be used for the\n+\t\t * bloom filter.\n+\t\t */\n+\t\twhile (len > 0 && pi->match[len - 1] != '/')\n+\t\t\tlen--;\n+\t}\n \t/* remove single trailing slash from path, if needed */\n-\tif (pi->len > 0 && pi->match[pi->len - 1] == '/') {\n-\t\tpath_alloc = xmemdupz(pi->match, pi->len - 1);\n+\tif (len > 0 && pi->match[len - 1] == '/')\n+\t\tlen--;\n+\n+\tif (!len)\n+\t\tgoto cleanup;\n+\n+\tif (len != pi->len) {\n+\t\tpath_alloc = xmemdupz(pi->match, len);\n \t\tpath = path_alloc;\n \t} else\n \t\tpath = pi->match;\n \n-\tlen = strlen(path);\n-\tif (!len) {\n-\t\tres = -1;\n-\t\tgoto cleanup;\n-\t}\n-\n \t*out = bloom_keyvec_new(path, len, settings);\n \n+\tres = 0;\n cleanup:\n \tfree(path_alloc);\n \treturn res;\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 639868ac56..1064990de3 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -154,11 +154,34 @@ test_expect_success 'git log with multiple literal paths uses Bloom filter' '\n \ttest_bloom_filters_used \"-- file*\"\n '\n \n-test_expect_success 'git log with path contains a wildcard does not use Bloom filter' '\n+test_expect_success 'git log with paths all contain non-wildcard part uses Bloom filter' '\n+\ttest_bloom_filters_used \"-- A/\\* file4\" &&\n+\ttest_bloom_filters_used \"-- A/file\\*\" &&\n+\ttest_bloom_filters_used \"-- * A/\\*\"\n+'\n+\n+test_expect_success 'git log with path only contains wildcard part does not use Bloom filter' '\n \ttest_bloom_filters_not_used \"-- file\\*\" &&\n-\ttest_bloom_filters_not_used \"-- A/\\* file4\" &&\n-\ttest_bloom_filters_not_used \"-- file4 A/\\*\" &&\n-\ttest_bloom_filters_not_used \"-- * A/\\*\"\n+\ttest_bloom_filters_not_used \"-- file\\* A/\\*\" &&\n+\ttest_bloom_filters_not_used \"-- file\\* *\" &&\n+\ttest_bloom_filters_not_used \"-- \\*\"\n+'\n+\n+test_expect_success 'git log with path contains various magic signatures' '\n+\tcd A &&\n+\ttest_bloom_filters_used \"-- \\:\\(top\\)B\" &&\n+\tcd .. &&\n+\n+\ttest_bloom_filters_used \"-- \\:\\(glob\\)A/\\*\\*/C\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(icase\\)FILE4\" &&\n+\ttest_bloom_filters_not_used \"-- \\:\\(exclude\\)A/B/C\" &&\n+\n+\ttest_when_finished \"rm -f .gitattributes\" &&\n+\tcat >.gitattributes <<-EOF &&\n+\tA/file1 text\n+\tA/B/file2 -text\n+\tEOF\n+\ttest_bloom_filters_used \"-- \\:\\(attr\\:text\\)A\"\n '\n \n test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '\n-- \n2.39.5 (Apple Git-154)\n\n"},{"id":"523954","messageId":"xmqqy0rp3l8s.fsf@gitster.g","threadId":"63922","inReplyTo":"20250811060137.75135-1-yldhome2d2@gmail.com","subject":"Re: [PATCH v5] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-11T15:56:35Z","receivedAt":"2025-08-11T15:56:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lidong Yan <yldhome2d2@gmail.com> writes:\n\n> Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>\n> [jc: avoid allocating zero length path in\n> convert_pathspec_to_bloom_keyvec()]\n> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n\nInstead just do\n\n        Helped-by: Junio C Hamano <gitster@pobox.com>\n        Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>\n\nhere.  [who: comment] followed by a sign-off from that person is\ndone by the person who is signing off the tweak, not by the original\nauthor.\n\nNo need to resend; I'll fix it up locally.\n\nThanks.\n"},{"id":"523957","messageId":"B5A8897E-3D20-487D-9774-444463F81DA4@gmail.com","threadId":"63922","inReplyTo":"xmqqy0rp3l8s.fsf@gitster.g","subject":"Re: [PATCH v5] bloom: enable bloom filter with wildcard pathspec in revision traversal","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-08-11T16:08:03Z","receivedAt":"2025-08-11T16:08:17Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n> \n> Lidong Yan <yldhome2d2@gmail.com> writes:\n> \n>> Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>\n>> [jc: avoid allocating zero length path in\n>> convert_pathspec_to_bloom_keyvec()]\n>> Signed-off-by: Junio C Hamano <gitster@pobox.com>\n> \n> Instead just do\n> \n>        Helped-by: Junio C Hamano <gitster@pobox.com>\n>        Signed-off-by: Lidong Yan <yldhome2d2@gmail.com>\n> \n> here.  [who: comment] followed by a sign-off from that person is\n> done by the person who is signing off the tweak, not by the original\n> author.\n\nI see — when someone makes additions to another person’s\ncommit, they’ll also modify the log message in the process.\n\nThanks,\nLidong\n\n"}]}