{"thread":{"id":"66240","subject":"[PATCH v3 1/6] revision: move bloom keyvec precondition into function","startedAt":"2026-08-31T15:19:08Z","lastAt":"2026-09-10T07:04:48Z","messageCount":22,"participants":["Toon Claes","Junio C Hamano","Patrick Steinhardt"],"isPatch":true,"patchVersion":3,"patchTotal":6},"messages":[{"id":"551564","messageId":"20260831-toon-speed-up-last-modified-v3-1-2bbb864acf93@iotcl.com","threadId":"66240","inReplyTo":"20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com","subject":"[PATCH v3 1/6] revision: move bloom keyvec precondition into function","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-31T15:18:41Z","receivedAt":"2026-08-31T15:19:08Z","isPatch":true,"body":"There are currently two callsites calling\ncheck_maybe_different_in_bloom_filter(). They both check if\nrevs->bloom_keyvecs_nr is not zero before they call that function.\n\nMove bloom_keyvecs_nr precondition into\ncheck_maybe_different_in_bloom_filter() to simplify the code.\n\nNote that this changes `bloom_ret` to become -1 when there are no Bloom\nkey vectors, which results in `count_bloom_filter_false_positive` not\nbeing incremented. This is unobservable, as the Bloom statistics are\nonly reported when key vectors were set up.\n\nSigned-off-by: Toon Claes \n---\n revision.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 50dc8b1991..6a6a1b6fa0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -752,6 +752,9 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \tstruct bloom_filter *filter;\n \tint result = 0;\n \n+\tif (!revs->bloom_keyvecs_nr)\n+\t\treturn -1;\n+\n \tif (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)\n \t\treturn -1;\n \n@@ -806,7 +809,7 @@ static int rev_compare_tree(struct rev_info *revs,\n \t\t\treturn REV_TREE_SAME;\n \t}\n \n-\tif (revs->bloom_keyvecs_nr && !nth_parent) {\n+\tif (!nth_parent) {\n \t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n \n \t\tif (bloom_ret == 0)\n@@ -833,7 +836,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,\n \tif (!t1)\n \t\treturn 0;\n \n-\tif (!nth_parent && revs->bloom_keyvecs_nr) {\n+\tif (!nth_parent) {\n \t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n \t\tif (!bloom_ret)\n \t\t\treturn 1;\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551565","messageId":"20260831-toon-speed-up-last-modified-v3-2-2bbb864acf93@iotcl.com","threadId":"66240","inReplyTo":"20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com","subject":"[PATCH v3 2/6] revision: expose check for paths maybe changed in Bloom filter","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-31T15:18:42Z","receivedAt":"2026-08-31T15:19:10Z","isPatch":true,"body":"check_maybe_different_in_bloom_filter() looks up a commit's changed-path\nBloom filter and consults it to see whether the commit might have\nmodified any of the paths in the pathspec that `revs` was set up with.\nIn a follow-up commit we want to reuse this logic from another builtin.\n\nThat caller, however, has already looked up the commit's Bloom filter\nfor its own purposes, so having the function look it up again would mean\na redundant lookup.\n\nExtract the filter-consulting part into a new public function,\nrevs_maybe_changed_in_bloom(). This function takes an already looked-up\n`struct bloom_filter` instead of a commit.\nThe existing check_maybe_different_in_bloom_filter() becomes a thin\nwrapper that looks up the filter and delegates.\n\nExpose the new function via revision.h so other builtins can reuse the\nexact same filtering that `git log ` performs.\n\nThe existing function check_maybe_different_in_bloom_filter() returns a\ntristate value. This returns either:\n\n * `-1` : No Bloom filter was used.\n * `0` : The commit definitely did not change any of the paths.\n * `1` : The commit maybe changed one of the paths.\n\nThese return values are used to keep count of false-positives. But\nbecause the new function revs_maybe_changed_in_bloom() is not involved\nin counting statistics, it returns a boolean value telling whether the\ncommit definitely did not change any of the paths, or maybe changed some\nof them.\n\nSigned-off-by: Toon Claes \n---\n revision.c | 30 ++++++++++++++++++++----------\n revision.h | 12 ++++++++++++\n 2 files changed, 32 insertions(+), 10 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 6a6a1b6fa0..ed46b90b00 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -750,7 +750,6 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \t\t\t\t\t\t struct commit *commit)\n {\n \tstruct bloom_filter *filter;\n-\tint result = 0;\n \n \tif (!revs->bloom_keyvecs_nr)\n \t\treturn -1;\n@@ -765,18 +764,29 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \t\treturn -1;\n \t}\n \n-\tfor (size_t nr = 0; !result && nr < revs->bloom_keyvecs_nr; nr++) {\n-\t\tresult = bloom_filter_contains_vec(filter,\n-\t\t\t\t\t\t revs->bloom_keyvecs[nr],\n-\t\t\t\t\t\t revs->bloom_filter_settings);\n+\tif (revs_maybe_changed_in_bloom(revs, filter)) {\n+\t\tcount_bloom_filter_maybe++;\n+\t\treturn 1;\n \t}\n \n-\tif (result)\n-\t\tcount_bloom_filter_maybe++;\n-\telse\n-\t\tcount_bloom_filter_definitely_not++;\n+\tcount_bloom_filter_definitely_not++;\n+\n+\treturn 0;\n+}\n+\n+bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n+\t\t\t\t struct bloom_filter *filter)\n+{\n+\tif (!revs->bloom_keyvecs_nr || !filter)\n+\t\treturn true;\n+\n+\tfor (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)\n+\t\tif (bloom_filter_contains_vec(filter,\n+\t\t\t\t\t revs->bloom_keyvecs[nr],\n+\t\t\t\t\t revs->bloom_filter_settings))\n+\t\t\treturn true;\n \n-\treturn result;\n+\treturn false;\n }\n \n static int rev_compare_tree(struct rev_info *revs,\ndiff --git a/revision.h b/revision.h\nindex acf6d06b24..67778558e1 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -68,6 +68,7 @@ struct string_list;\n struct saved_parents;\n struct follow_pathspec_slab;\n struct bloom_keyvec;\n+struct bloom_filter;\n struct bloom_filter_settings;\n struct option;\n struct parse_opt_ctx_t;\n@@ -495,6 +496,17 @@ void reset_revision_walk(void);\n */\n int prepare_revision_walk(struct rev_info *revs);\n \n+/**\n+ * Consult a changed-path Bloom filter to determine if the commit to which the\n+ * filter belongs might have changed any of the paths in the `revs`.\n+ * prepare_revision_walk() needs to be called in advance to ensure\n+ * pathspec key vectors are set up.\n+ *\n+ * Returns false iff the commit definitely did not change any of the paths.\n+ */\n+bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n+\t\t\t\t struct bloom_filter *filter);\n+\n /* Drain the commits linked list into the priority queue. */\n void rev_info_commit_list_to_queue(struct rev_info *revs);\n /**\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551566","messageId":"20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com","threadId":"66240","inReplyTo":"20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com","subject":"[PATCH v3 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-31T15:18:40Z","receivedAt":"2026-08-31T15:19:11Z","isPatch":true,"body":"We have received a report[1] git-last-modified(1) is slow compared to\ngit-log(1) if you want to find the last commit for all entries in a\ndirectory. For example running the following command on ziglang/zig[2]:\n\n $ git last-modified -t --max-depth=0 $OID -- doc/langref/\n\nTurns out to find results about 2.5 times slower than:\n\n $ git log --name-status -c --format=commit%x00%H %P%x00\" \\\n --parents --no-renames -t -z $OID -- :(literal)doc/langref\n\nNow the latter needs some post-processing to come to the same results,\nthe total solution still is faster than integrating\ngit-last-modified(1).\n\nAfter some research we've discovered the Bloom filters aren't used\noptimally. But it turns out the code powering git-log(1) can fairly easy\nbe reused. We do this in a few steps:\n\n - Patch 1 & 2 prepare revision.[ch] to expose the helper to check if\n revs maybe changes in Bloom filter.\n - Patch 3 & 4 prepare a similar helper, but this one is needed when\n git-last-modified(1) is called with `--show-trees`.\n - Patch 5 uses these helpers in git-last-modified(1).\n - Patch 6 is a bonus change, which optimizes when working with wildcard\n pathspecs.\n\nBelow are benchmarks on the ziglang/zig repository for the\n`doc/langref/` directory (with commit-graphs written using\n`--changed-paths`):\n\n Benchmark 1: master: last-modified -z -t\n Time (mean ± σ): 61.9 ms ± 1.8 ms [User: 57.1 ms, System: 4.0 ms]\n Range (min … max): 58.5 ms … 68.9 ms 150 runs\n\n Benchmark 2: HEAD: last-modified -z -t\n Time (mean ± σ): 31.8 ms ± 1.3 ms [User: 27.1 ms, System: 4.2 ms]\n Range (min … max): 29.7 ms … 35.6 ms 150 runs\n\n Benchmark 3: git log -t\n Time (mean ± σ): 22.1 ms ± 1.2 ms [User: 16.7 ms, System: 5.0 ms]\n Range (min … max): 20.1 ms … 26.6 ms 150 runs\n\n Summary\n git log -t ran\n 1.44 ± 0.10 times faster than HEAD: last-modified -z -t\n 2.80 ± 0.18 times faster than master: last-modified -z -t\n\nComparing HEAD to master, there is about 1.95x speedup on running `git\nlast-modified -z -t. `git log -t` is still slightly faster though.\n\nBut without `-t` the speedup is even bigger:\n\n Benchmark 1: master: last-modified -z\n Time (mean ± σ): 60.7 ms ± 4.5 ms [User: 56.5 ms, System: 3.8 ms]\n Range (min … max): 57.5 ms … 96.2 ms 150 runs\n\n Benchmark 2: HEAD: last-modified -z\n Time (mean ± σ): 16.2 ms ± 1.4 ms [User: 13.3 ms, System: 2.7 ms]\n Range (min … max): 13.9 ms … 20.4 ms 212 runs\n\n Benchmark 3: git log (no -t)\n Time (mean ± σ): 22.0 ms ± 3.7 ms [User: 16.8 ms, System: 4.9 ms]\n Range (min … max): 18.7 ms … 37.6 ms 150 runs\n\n Summary\n HEAD: last-modified -z ran\n 1.35 ± 0.25 times faster than git log (no -t)\n 3.74 ± 0.42 times faster than master: last-modified -z\n\nThis makes sense because without `-t` we can use the Bloom filter more\noptimally.\n\nSimilar timings are seen across a few other repositories (like GitLab's\nmonolith gitlab-org/gitlab).\n\n[1]: https://lore.kernel.org/git/17f356ff-7bfb-47f5-b714-62a95cc8b821@codeberg.org/\n[2]: https://codeberg.org/ziglang/zig\n\n---\nChanges in v3:\n- Add trace2 \"bloom_queries\" and use it in test to verify top-level\n wildcard behavior.\n- Link to v2: https://patch.msgid.link/20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com\n\nChanges in v2:\n- Make the public helper revs_maybe_changed_in_bloom() return a bool\n instead of a tristate.\n- Keep the bloom_keyvecs_nr precondition before get_bloom_filter() and\n return early from the key vector loop.\n- Add commits 3 & 4 to add helper used with `--show-trees`.\n- Use Bloom filter correctly with `--show-trees` and add test to prove.\n- Rerun benchmarks to compare results with and without `--show-trees`.\n- Link to v1: https://patch.msgid.link/20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com\n\n---\nToon Claes (6):\n revision: move bloom keyvec precondition into function\n revision: expose check for paths maybe changed in Bloom filter\n bloom: add helper to check if any key in a vector is present\n revision: add Bloom check that includes parent directories\n last-modified: check pathspec against Bloom filter first\n last-modified: keep per-path Bloom filters for wildcard pathspecs\n\n bloom.c | 12 +++++++++++\n bloom.h | 11 ++++++++++\n builtin/last-modified.c | 28 ++++++++++++++++++++++++++\n revision.c | 52 +++++++++++++++++++++++++++++++++++++-----------\n revision.h | 20 +++++++++++++++++++\n t/t8020-last-modified.sh | 47 +++++++++++++++++++++++++++++++++++++++++++\n 6 files changed, 158 insertions(+), 12 deletions(-)\n\nRange-diff versus v2:\n\n1: a98bbaad50 = 1: ac58e4a3cd revision: move bloom keyvec precondition into function\n2: ebf4f65fab = 2: 43375b505e revision: expose check for paths maybe changed in Bloom filter\n3: 7a3c14fe87 = 3: 41e3a19fde bloom: add helper to check if any key in a vector is present\n4: 145c95a2fa = 4: a648612927 revision: add Bloom check that includes parent directories\n5: 9dc5a0be79 = 5: 0e8721fe75 last-modified: check pathspec against Bloom filter first\n6: 83036c2fe4 ! 6: e7997e0a9b last-modified: keep per-path Bloom filters for wildcard pathspecs\n @@ Commit message\n Restore `bloom_filter_settings` after prepare_revision_walk() so the\n per-path check keeps working for wildcard pathspecs.\n \n + This change isn't having any effect on the output, but only has an\n + impact on performance. Add a \"bloom_queries\" trace2 counter that records\n + how often the per-path Bloom check runs, and a test that asserts the\n + count increments as appropriate for a top-level wildcard pathspec.\n +\n Signed-off-by: Toon Claes \n \n ## builtin/last-modified.c ##\n +@@\n + #include \"quote.h\"\n + #include \"repository.h\"\n + #include \"revision.h\"\n ++#include \"trace2.h\"\n + \n + /* Remember to update object flag allocation in object.h */\n + #define PARENT1 (1u<<16) /* used instead of SEEN */\n +@@ builtin/last-modified.c: struct last_modified {\n + \n + \t/* 'scratch' to avoid allocating a bitmap every process_parent() */\n + \tstruct bitmap *scratch;\n ++\n ++\tunsigned int count_bloom_filter_queries;\n + };\n + \n + static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)\n +@@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm,\n + \tif (!filter)\n + \t\treturn true;\n + \n ++\tlm->count_bloom_filter_queries++;\n ++\n + \t/*\n + \t * With --show-trees we also track the tree entries containing the\n + \t * paths, so a change to any of those parent directories matters too.\n @@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)\n \n \tprepare_revision_walk(&lm->rev);\n @@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)\n \tmax_count = lm->rev.max_count;\n \n \tinit_active_paths_for_commit(&lm->active_paths);\n +@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)\n + \tif (hashmap_get_size(&lm->paths))\n + \t\tBUG(\"paths remaining beyond boundary in last-modified\");\n + \n ++\ttrace2_data_intmax(\"last-modified\", lm->rev.repo, \"bloom_queries\",\n ++\t\t\t lm->count_bloom_filter_queries);\n ++\n + \tclear_prio_queue(¬_queue);\n + \tclear_prio_queue(&queue);\n + \tclear_active_paths_for_commit(&lm->active_paths);\n +\n + ## t/t8020-last-modified.sh ##\n +@@ t/t8020-last-modified.sh: test_expect_success 'last-modified with Bloom filters and --show-trees' '\n + \t)\n + '\n + \n ++test_expect_success 'last-modified with Bloom filters and top-level wildcard' '\n ++\ttest_when_finished rm -rf wildcard &&\n ++\tgit init wildcard &&\n ++\t(\n ++\t\tcd wildcard &&\n ++\t\ttest_commit base-c a.c &&\n ++\t\ttest_commit base-h a.h &&\n ++\t\ttest_commit touch-c a.c &&\n ++\t\tmkdir d &&\n ++\t\ttest_commit sub-c d/b.c &&\n ++\n ++\t\tgit commit-graph write --reachable --changed-paths &&\n ++\t\tGIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n ++\t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n ++\t\t\t-- \"*.c\" >expect &&\n ++\t\ttest_grep \"data .* bloom_queries:0$\" off.perf &&\n ++\n ++\t\tGIT_TRACE2_PERF=\"$(pwd)/on.perf\" \\\n ++\t\t\tgit -c core.commitGraph=true last-modified -r HEAD \\\n ++\t\t\t-- \"*.c\" >actual &&\n ++\t\ttest_grep \"data .* bloom_queries:2$\" on.perf &&\n ++\n ++\t\ttest_cmp expect actual\n ++\t)\n ++'\n ++\n + test_expect_success 'cannot run last-modified on two commits' '\n + \ttest_must_fail git last-modified HEAD HEAD~1 2>err &&\n + \ttest_grep \"last-modified can only operate on one commit at a time\" err\n\n\n---\nbase-commit: c73e85354c275c9d409b26445089bc16940fc527\nchange-id: 20260716-toon-speed-up-last-modified-b04ea1f21831\n\n"},{"id":"551567","messageId":"20260831-toon-speed-up-last-modified-v3-3-2bbb864acf93@iotcl.com","threadId":"66240","inReplyTo":"20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com","subject":"[PATCH v3 3/6] bloom: add helper to check if any key in a vector is present","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-31T15:18:43Z","receivedAt":"2026-08-31T15:19:16Z","isPatch":true,"body":"The changed-path Bloom filter of a commit stores a key for every changed\npath together with each of its leading directories. To query if a path\nwas changed, bloom_keyvec_new() fills a key vector the same way: a key\nfor the given path and one for each of its leading directories. For\nexample, for \"a/b/c\" the vector holds keys for \"a/b/c\", \"a/b\" and \"a\".\n\nA Bloom filter can only ever prove absence. When a key is not in the\nfilter, the path it was made for definitely did not change. When it is\nin the filter, the path may have changed, as the key can be a false\npositive.\n\nbloom_filter_contains_vec() looks up all keys of a vector and reports\nwhether all of them are present. That answers: Is this path maybe\nchanged by this commit?\n\nA caller that also cares about the directories containing the path asks\na different question: Is this path, or any directory leading up to it,\nmaybe changed by this commit?\n\nConsider the Bloom filter of a commit that changed \"a/b/d\". It holds\nkeys for \"a/b/d\", \"a/b\" and \"a\", so looking up the vector of \"a/b/c\"\nwith bloom_filter_contains_vec() reports that nothing changed, even\nthough \"a/b\" and \"a\" did.\n\nAdd bloom_filter_contains_any_vec(), which reports whether any key in\nthe vector is present. It returns 0 only when none of the keys are in\nthe filter, which means the path and all directories leading up to it\ndefinitely did not change.\n\nThere are no callers yet, one is added in a subsequent commit.\n\nSigned-off-by: Toon Claes \n---\n bloom.c | 12 ++++++++++++\n bloom.h | 11 +++++++++++\n 2 files changed, 23 insertions(+)\n\ndiff --git a/bloom.c b/bloom.c\nindex caf22f9831..b96534e6e3 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -607,6 +607,18 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,\n \treturn ret;\n }\n \n+int bloom_filter_contains_any_vec(const struct bloom_filter *filter,\n+\t\t\t\t const struct bloom_keyvec *vec,\n+\t\t\t\t const struct bloom_filter_settings *settings)\n+{\n+\tint ret = 0;\n+\n+\tfor (size_t nr = 0; !ret && nr < vec->count; nr++)\n+\t\tret = bloom_filter_contains(filter, &vec->key[nr], settings);\n+\n+\treturn ret;\n+}\n+\n uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,\n \t\t\t\t int version)\n {\ndiff --git a/bloom.h b/bloom.h\nindex 92ab2100d3..f508db23ad 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -164,6 +164,17 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,\n \t\t\t const struct bloom_keyvec *v,\n \t\t\t const struct bloom_filter_settings *settings);\n \n+/*\n+ * bloom_filter_contains_any_vec - Check if any key in a key vector is in the\n+ * Bloom filter.\n+ *\n+ * Returns 1 if **any** key in the vector is present in the filter, 0 if none\n+ * of them are.\n+ */\n+int bloom_filter_contains_any_vec(const struct bloom_filter *filter,\n+\t\t\t\t const struct bloom_keyvec *v,\n+\t\t\t\t const struct bloom_filter_settings *settings);\n+\n uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,\n \t\t\t\t int version);\n \n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551568","messageId":"20260831-toon-speed-up-last-modified-v3-4-2bbb864acf93@iotcl.com","threadId":"66240","inReplyTo":"20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com","subject":"[PATCH v3 4/6] revision: add Bloom check that includes parent directories","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-31T15:18:44Z","receivedAt":"2026-08-31T15:19:17Z","isPatch":true,"body":"revs_maybe_changed_in_bloom() reports whether a commit may have changed\nany of the paths in the pathspec. It uses bloom_filter_contains_vec(),\nwhich requires all keys of a path's key vector to be present, so it only\nanswers for the paths themselves.\n\nA caller may track more than those paths. git-last-modified(1) with\n--show-trees reports the last modifying commit for the tree entries\ncontaining the paths as well, up to the root. For a pathspec \"a/b/c/\"\nthat means it reports \"a\" and \"a/b\" next to \"a/b/c\" and its entries, and\nthose can each resolve to a different commit. A commit that only changed\n\"a/top\" is the answer for \"a\", even though it touched nothing under\n\"a/b\".\n\nSuch a caller needs to know whether the path, or any of the directories\nleading up to it, may have changed. Add\nrevs_maybe_changed_in_bloom_with_parents(), which asks that question by\nusing bloom_filter_contains_any_vec() instead. A key vector holds a key\nfor the path and one for each of its leading directories, so looking up\nany of them answers it.\n\nThere are no callers yet, one is added in a subsequent commit.\n\nSigned-off-by: Toon Claes \n---\n revision.c | 15 +++++++++++++++\n revision.h | 8 ++++++++\n 2 files changed, 23 insertions(+)\n\ndiff --git a/revision.c b/revision.c\nindex ed46b90b00..a560146b4d 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -789,6 +789,21 @@ bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n \treturn false;\n }\n \n+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,\n+\t\t\t\t\t struct bloom_filter *filter)\n+{\n+\tif (!revs->bloom_keyvecs_nr || !filter)\n+\t\treturn true;\n+\n+\tfor (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)\n+\t\tif (bloom_filter_contains_any_vec(filter,\n+\t\t\t\t\t\t revs->bloom_keyvecs[nr],\n+\t\t\t\t\t\t revs->bloom_filter_settings))\n+\t\t\treturn true;\n+\n+\treturn false;\n+}\n+\n static int rev_compare_tree(struct rev_info *revs,\n \t\t\t struct commit *parent, struct commit *commit, int nth_parent)\n {\ndiff --git a/revision.h b/revision.h\nindex 67778558e1..192001ff79 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -507,6 +507,14 @@ int prepare_revision_walk(struct rev_info *revs);\n bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n \t\t\t\t struct bloom_filter *filter);\n \n+/**\n+ * Same as revs_maybe_changed_in_bloom(), but a change to any of the directories\n+ * leading up to a path counts as well. Callers that track the tree entries\n+ * containing the paths, and not just the paths themselves, need this.\n+ */\n+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,\n+\t\t\t\t\t struct bloom_filter *filter);\n+\n /* Drain the commits linked list into the priority queue. */\n void rev_info_commit_list_to_queue(struct rev_info *revs);\n /**\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551569","messageId":"20260831-toon-speed-up-last-modified-v3-5-2bbb864acf93@iotcl.com","threadId":"66240","inReplyTo":"20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com","subject":"[PATCH v3 5/6] last-modified: check pathspec against Bloom filter first","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-31T15:18:45Z","receivedAt":"2026-08-31T15:19:23Z","isPatch":true,"body":"When git-last-modified(1) starts, it builds a list of all the paths\nmatching the pathspec it needs to find the last modifying commit for.\nFor example, every file and subdirectory listed by:\n\n $ git last-modified -t --max-depth=0 -- src/\n\nAs it resolves a commit for each path during the revision walk, it drops\nthat path from the list.\n\nTo avoid diffing trees for every commit, Bloom filters are used when\navailable. For each remaining path, the commit's Bloom filter is checked\nto see whether the commit changed that path. The Bloom filter says\neither \"no\" or \"maybe\", and only in the latter case is the diff\ncalculated.\n\ngit-log(1) does this differently. It does not expand the pathspec but\nchecks the Bloom filter against the pathspec itself. This way, commits\nnot touching any path matching the pathspec can be discarded as a whole.\n\nApply this same check to git-last-modified(1). In a previous commit the\nfunction revs_maybe_changed_in_bloom(), used by git-log(1), was made\npublic. Use this as a pre-filter in git-last-modified(1). After this\npre-filter, paths are still checked one-by-one to only find those which\ndon't have a \"last commit\" yet.\n\nWith `--show-trees` the list holds more than the paths matching the\npathspec. It also holds each parent tree entry, up to the root. Each of\nthose can resolve to a different commit. Thus for the pathspec \"a/b/c\",\nthe list will also hold \"a\" and \"a/b\".\n\nWhen a commit touches \"a/other\", that commit could be the last commit\nfor \"a\", but revs_maybe_changed_in_bloom() would discard it, because it\ndoesn't match the full pathspec.\n\nInstead, when `--show-trees` is given, use\nrevs_maybe_changed_in_bloom_with_parents(), which indicates the commit\nmaybe changed any of the paths leading up to the path in the pathspec.\n\nSigned-off-by: Toon Claes \n---\n builtin/last-modified.c | 12 ++++++++++++\n t/t8020-last-modified.sh | 21 +++++++++++++++++++++\n 2 files changed, 33 insertions(+)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 3846244dfc..8ab7944314 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -272,6 +272,18 @@ static bool maybe_changed_path(struct last_modified *lm,\n \tif (!filter)\n \t\treturn true;\n \n+\t/*\n+\t * With --show-trees we also track the tree entries containing the\n+\t * paths, so a change to any of those parent directories matters too.\n+\t */\n+\tif (lm->show_trees) {\n+\t\tif (!revs_maybe_changed_in_bloom_with_parents(&lm->rev, filter))\n+\t\t\treturn false;\n+\t} else {\n+\t\tif (!revs_maybe_changed_in_bloom(&lm->rev, filter))\n+\t\t\treturn false;\n+\t}\n+\n \thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n \t\tif (active && !bitmap_get(active, ent->diff_idx))\n \t\t\tcontinue;\ndiff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\nindex 9dba4b9d90..df73c7d0d0 100755\n--- a/t/t8020-last-modified.sh\n+++ b/t/t8020-last-modified.sh\n@@ -269,6 +269,27 @@ test_expect_success 'last-modified merge undoes changes' '\n \tEOF\n '\n \n+test_expect_success 'last-modified with Bloom filters and --show-trees' '\n+\ttest_when_finished rm -rf bloom &&\n+\tgit init bloom &&\n+\t(\n+\t\tcd bloom &&\n+\t\tmkdir d &&\n+\t\ttest_commit base-a d/a &&\n+\t\ttest_commit base-b d/b &&\n+\t\ttest_commit touch-a d/a &&\n+\t\ttest_commit touch-b d/b &&\n+\n+\t\tgit commit-graph write --reachable --changed-paths &&\n+\t\tgit -c core.commitGraph=false last-modified -t HEAD -- d/a \\\n+\t\t\t>expect &&\n+\t\tgit -c core.commitGraph=true last-modified -t HEAD -- d/a \\\n+\t\t\t>actual &&\n+\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n test_expect_success 'cannot run last-modified on two commits' '\n \ttest_must_fail git last-modified HEAD HEAD~1 2>err &&\n \ttest_grep \"last-modified can only operate on one commit at a time\" err\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551570","messageId":"20260831-toon-speed-up-last-modified-v3-6-2bbb864acf93@iotcl.com","threadId":"66240","inReplyTo":"20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com","subject":"[PATCH v3 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-31T15:18:46Z","receivedAt":"2026-08-31T15:19:25Z","isPatch":true,"body":"The last-modified builtin expands the pathspec to a set of literal paths\nand builds a Bloom key for each. During the walk it looks those keys up\nin the commit's filter to decide whether the commit is worth diffing.\nThese lookups need `bloom_filter_settings` for the key hashing.\n\nprepare_revision_walk() runs prepare_to_use_bloom_filter() to build the\npathspec key vectors. For a pathspec that cannot be turned into a Bloom\nkey, such as a top-level wildcard like \"*.c\", that function gives up and\nclears `bloom_filter_settings`.\n\nRestore `bloom_filter_settings` after prepare_revision_walk() so the\nper-path check keeps working for wildcard pathspecs.\n\nThis change isn't having any effect on the output, but only has an\nimpact on performance. Add a \"bloom_queries\" trace2 counter that records\nhow often the per-path Bloom check runs, and a test that asserts the\ncount increments as appropriate for a top-level wildcard pathspec.\n\nSigned-off-by: Toon Claes \n---\n builtin/last-modified.c | 16 ++++++++++++++++\n t/t8020-last-modified.sh | 26 ++++++++++++++++++++++++++\n 2 files changed, 42 insertions(+)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 8ab7944314..bedccb3ace 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -18,6 +18,7 @@\n #include \"quote.h\"\n #include \"repository.h\"\n #include \"revision.h\"\n+#include \"trace2.h\"\n \n /* Remember to update object flag allocation in object.h */\n #define PARENT1 (1u<<16) /* used instead of SEEN */\n@@ -63,6 +64,8 @@ struct last_modified {\n \n \t/* 'scratch' to avoid allocating a bitmap every process_parent() */\n \tstruct bitmap *scratch;\n+\n+\tunsigned int count_bloom_filter_queries;\n };\n \n static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)\n@@ -272,6 +275,8 @@ static bool maybe_changed_path(struct last_modified *lm,\n \tif (!filter)\n \t\treturn true;\n \n+\tlm->count_bloom_filter_queries++;\n+\n \t/*\n \t * With --show-trees we also track the tree entries containing the\n \t * paths, so a change to any of those parent directories matters too.\n@@ -370,6 +375,14 @@ static int last_modified_run(struct last_modified *lm)\n \n \tprepare_revision_walk(&lm->rev);\n \n+\t/*\n+\t * prepare_revision_walk() clears bloom_filter_settings for pathspecs\n+\t * without a Bloom key. Restore it so the per-path check keeps working.\n+\t */\n+\tif (!lm->rev.bloom_filter_settings)\n+\t\tlm->rev.bloom_filter_settings =\n+\t\t\tget_bloom_filter_settings(lm->rev.repo);\n+\n \tmax_count = lm->rev.max_count;\n \n \tinit_active_paths_for_commit(&lm->active_paths);\n@@ -479,6 +492,9 @@ static int last_modified_run(struct last_modified *lm)\n \tif (hashmap_get_size(&lm->paths))\n \t\tBUG(\"paths remaining beyond boundary in last-modified\");\n \n+\ttrace2_data_intmax(\"last-modified\", lm->rev.repo, \"bloom_queries\",\n+\t\t\t lm->count_bloom_filter_queries);\n+\n \tclear_prio_queue(¬_queue);\n \tclear_prio_queue(&queue);\n \tclear_active_paths_for_commit(&lm->active_paths);\ndiff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\nindex df73c7d0d0..75b18ee83b 100755\n--- a/t/t8020-last-modified.sh\n+++ b/t/t8020-last-modified.sh\n@@ -290,6 +290,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '\n \t)\n '\n \n+test_expect_success 'last-modified with Bloom filters and top-level wildcard' '\n+\ttest_when_finished rm -rf wildcard &&\n+\tgit init wildcard &&\n+\t(\n+\t\tcd wildcard &&\n+\t\ttest_commit base-c a.c &&\n+\t\ttest_commit base-h a.h &&\n+\t\ttest_commit touch-c a.c &&\n+\t\tmkdir d &&\n+\t\ttest_commit sub-c d/b.c &&\n+\n+\t\tgit commit-graph write --reachable --changed-paths &&\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n+\t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n+\t\t\t-- \"*.c\" >expect &&\n+\t\ttest_grep \"data .* bloom_queries:0$\" off.perf &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/on.perf\" \\\n+\t\t\tgit -c core.commitGraph=true last-modified -r HEAD \\\n+\t\t\t-- \"*.c\" >actual &&\n+\t\ttest_grep \"data .* bloom_queries:2$\" on.perf &&\n+\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n test_expect_success 'cannot run last-modified on two commits' '\n \ttest_must_fail git last-modified HEAD HEAD~1 2>err &&\n \ttest_grep \"last-modified can only operate on one commit at a time\" err\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551607","messageId":"xmqqmru2ugxn.fsf@gitster.g","threadId":"66240","inReplyTo":"20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com","subject":"Re: [PATCH v3 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-08-31T21:19:00Z","receivedAt":"2026-08-31T21:19:03Z","isPatch":true,"body":"Toon Claes writes:\n\n> Similar timings are seen across a few other repositories (like GitLab's\n> monolith gitlab-org/gitlab).\n>\n> [1]: https://lore.kernel.org/git/17f356ff-7bfb-47f5-b714-62a95cc8b821@codeberg.org/\n> [2]: https://codeberg.org/ziglang/zig\n>\n> ---\n> Changes in v3:\n> - Add trace2 \"bloom_queries\" and use it in test to verify top-level\n> wildcard behavior.\n> - Link to v2: https://patch.msgid.link/20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com\n\nMerged to 'seen', pushed the result out, and saw this:\n\n https://github.com/git/git/actions/runs/33429987759/job/99612809093#step:10:1391\n\nIt seems that it is reproducible locally with the variable settings\nstolen from ci/run-build-and-tests.sh, i.e.,\n\n $ bash\n sh-5.3$ export OPENSSL_SHA1_UNSAFE=YesPlease\n sh-5.3$ export GIT_TEST_SPLIT_INDEX=yes\n sh-5.3$ export GIT_TEST_FULL_IN_PACK_ARRAY=true\n sh-5.3$ export GIT_TEST_OE_SIZE=10\n sh-5.3$ export GIT_TEST_OE_DELTA_SIZE=5\n sh-5.3$ export GIT_TEST_COMMIT_GRAPH=1\n sh-5.3$ export GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1\n sh-5.3$ export GIT_TEST_MULTI_PACK_INDEX=1\n sh-5.3$ export GIT_TEST_MULTI_PACK_INDEX_WRITE_INCREMENTAL=1\n sh-5.3$ export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master\n sh-5.3$ export GIT_TEST_NO_WRITE_REV_INDEX=1\n sh-5.3$ export GIT_TEST_CHECKOUT_WORKERS=2\n sh-5.3$ export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1\n sh-5.3$ make T='t8020*' test\n\nand it does reproduce when the topic is tested standalone (I've kept\nthe base that I have used to queue the previous iteration,\n41365c2a9b The 4th batch for Git 2.56).\n\nEjected out of 'seen' for now.\n"},{"id":"551616","messageId":"xmqq8q5lvc1i.fsf@gitster.g","threadId":"66240","inReplyTo":"20260831-toon-speed-up-last-modified-v3-6-2bbb864acf93@iotcl.com","subject":"Re: [PATCH v3 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-09-01T04:19:21Z","receivedAt":"2026-09-01T04:19:24Z","isPatch":true,"body":"Toon Claes writes:\n\n> diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\n> index df73c7d0d0..75b18ee83b 100755\n> --- a/t/t8020-last-modified.sh\n> +++ b/t/t8020-last-modified.sh\n> @@ -290,6 +290,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '\n> \t)\n> '\n> \n> +test_expect_success 'last-modified with Bloom filters and top-level wildcard' '\n> ...\n> +\t\tGIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n> +\t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n> +\t\t\t-- \"*.c\" >expect &&\n> +\t\ttest_grep \"data .* bloom_queries:0$\" off.perf &&\n\nAh, OK. With GIT_TEST_COMMIT_GRAPH=1 exported from the test harness\nenvironment, 'git -c core.commitGraph=false' would not be effective\nhere. You would need to do something like:\n\n\t\tGIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n\t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n\t\t\t-- \"*.c\" >expect &&\n\n> +\t\tGIT_TRACE2_PERF=\"$(pwd)/on.perf\" \\\n> +\t\t\tgit -c core.commitGraph=true last-modified -r HEAD \\\n> +\t\t\t-- \"*.c\" >actual &&\n\nAnd in the case where GIT_TEST_COMMIT_GRAPH=0 comes from the\nenvironment, you might want to be explicit about setting the\nvariable here as well.\n"},{"id":"551632","messageId":"87mru1wcyi.fsf@emacs.iotcl.com","threadId":"66240","inReplyTo":"xmqq8q5lvc1i.fsf@gitster.g","subject":"Re: [PATCH v3 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-09-01T09:14:13Z","receivedAt":"2026-09-01T09:14:33Z","isPatch":true,"body":"Junio C Hamano writes:\n\n> Toon Claes writes:\n>\n>> diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\n>> index df73c7d0d0..75b18ee83b 100755\n>> --- a/t/t8020-last-modified.sh\n>> +++ b/t/t8020-last-modified.sh\n>> @@ -290,6 +290,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '\n>> \t)\n>> '\n>> \n>> +test_expect_success 'last-modified with Bloom filters and top-level wildcard' '\n>> ...\n>> +\t\tGIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n>> +\t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n>> +\t\t\t-- \"*.c\" >expect &&\n>> +\t\ttest_grep \"data .* bloom_queries:0$\" off.perf &&\n>\n> Ah, OK. With GIT_TEST_COMMIT_GRAPH=1 exported from the test harness\n> environment, 'git -c core.commitGraph=false' would not be effective\n> here. You would need to do something like:\n>\n> \t\tGIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n> \t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n> \t\t\t-- \"*.c\" >expect &&\n>\n>> +\t\tGIT_TRACE2_PERF=\"$(pwd)/on.perf\" \\\n>> +\t\t\tgit -c core.commitGraph=true last-modified -r HEAD \\\n>> +\t\t\t-- \"*.c\" >actual &&\n>\n> And in the case where GIT_TEST_COMMIT_GRAPH=0 comes from the\n> environment, you might want to be explicit about setting the\n> variable here as well.\n\nThanks for this suggestion. Yeah, I didn't notice it makes CI fail.\n\nBut a little bit of a followup question, I noticed I also should be\nsetting these in [PATCH 5/6], but test don't fail if not set\nappropriately.\n\nI just sent out version 4, but to make it really waterproof, test case\n'last-modified with Bloom filters and --show-trees' also should use\ntrace2 counters. Although I wasn't convinced it's worth it?\n\n-- \nLaters,\nToon\n"},{"id":"551634","messageId":"20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com","threadId":"66240","inReplyTo":"20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com","subject":"[PATCH v4 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-09-01T09:10:20Z","receivedAt":"2026-09-01T09:29:29Z","isPatch":true,"body":"We have received a report[1] git-last-modified(1) is slow compared to\ngit-log(1) if you want to find the last commit for all entries in a\ndirectory. For example running the following command on ziglang/zig[2]:\n\n $ git last-modified -t --max-depth=0 $OID -- doc/langref/\n\nTurns out to find results about 2.5 times slower than:\n\n $ git log --name-status -c --format=commit%x00%H %P%x00\" \\\n --parents --no-renames -t -z $OID -- :(literal)doc/langref\n\nNow the latter needs some post-processing to come to the same results,\nthe total solution still is faster than integrating\ngit-last-modified(1).\n\nAfter some research we've discovered the Bloom filters aren't used\noptimally. But it turns out the code powering git-log(1) can fairly easy\nbe reused. We do this in a few steps:\n\n - Patch 1 & 2 prepare revision.[ch] to expose the helper to check if\n revs maybe changes in Bloom filter.\n - Patch 3 & 4 prepare a similar helper, but this one is needed when\n git-last-modified(1) is called with `--show-trees`.\n - Patch 5 uses these helpers in git-last-modified(1).\n - Patch 6 is a bonus change, which optimizes when working with wildcard\n pathspecs.\n\nBelow are benchmarks on the ziglang/zig repository for the\n`doc/langref/` directory (with commit-graphs written using\n`--changed-paths`):\n\n Benchmark 1: master: last-modified -z -t\n Time (mean ± σ): 61.9 ms ± 1.8 ms [User: 57.1 ms, System: 4.0 ms]\n Range (min … max): 58.5 ms … 68.9 ms 150 runs\n\n Benchmark 2: HEAD: last-modified -z -t\n Time (mean ± σ): 31.8 ms ± 1.3 ms [User: 27.1 ms, System: 4.2 ms]\n Range (min … max): 29.7 ms … 35.6 ms 150 runs\n\n Benchmark 3: git log -t\n Time (mean ± σ): 22.1 ms ± 1.2 ms [User: 16.7 ms, System: 5.0 ms]\n Range (min … max): 20.1 ms … 26.6 ms 150 runs\n\n Summary\n git log -t ran\n 1.44 ± 0.10 times faster than HEAD: last-modified -z -t\n 2.80 ± 0.18 times faster than master: last-modified -z -t\n\nComparing HEAD to master, there is about 1.95x speedup on running `git\nlast-modified -z -t. `git log -t` is still slightly faster though.\n\nBut without `-t` the speedup is even bigger:\n\n Benchmark 1: master: last-modified -z\n Time (mean ± σ): 60.7 ms ± 4.5 ms [User: 56.5 ms, System: 3.8 ms]\n Range (min … max): 57.5 ms … 96.2 ms 150 runs\n\n Benchmark 2: HEAD: last-modified -z\n Time (mean ± σ): 16.2 ms ± 1.4 ms [User: 13.3 ms, System: 2.7 ms]\n Range (min … max): 13.9 ms … 20.4 ms 212 runs\n\n Benchmark 3: git log (no -t)\n Time (mean ± σ): 22.0 ms ± 3.7 ms [User: 16.8 ms, System: 4.9 ms]\n Range (min … max): 18.7 ms … 37.6 ms 150 runs\n\n Summary\n HEAD: last-modified -z ran\n 1.35 ± 0.25 times faster than git log (no -t)\n 3.74 ± 0.42 times faster than master: last-modified -z\n\nThis makes sense because without `-t` we can use the Bloom filter more\noptimally.\n\nSimilar timings are seen across a few other repositories (like GitLab's\nmonolith gitlab-org/gitlab).\n\n[1]: https://lore.kernel.org/git/17f356ff-7bfb-47f5-b714-62a95cc8b821@codeberg.org/\n[2]: https://codeberg.org/ziglang/zig\n\n---\nChanges in v4:\n- Override GIT_TEST_COMMIT_GRAPH when passing `-c core.commitGraph=` in\n t8020 tests.\n- Link to v3: https://patch.msgid.link/20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com\n\nChanges in v3:\n- Add trace2 \"bloom_queries\" and use it in test to verify top-level\n wildcard behavior.\n- Link to v2: https://patch.msgid.link/20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com\n\nChanges in v2:\n- Make the public helper revs_maybe_changed_in_bloom() return a bool\n instead of a tristate.\n- Keep the bloom_keyvecs_nr precondition before get_bloom_filter() and\n return early from the key vector loop.\n- Add commits 3 & 4 to add helper used with `--show-trees`.\n- Use Bloom filter correctly with `--show-trees` and add test to prove.\n- Rerun benchmarks to compare results with and without `--show-trees`.\n- Link to v1: https://patch.msgid.link/20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com\n\n---\nToon Claes (6):\n revision: move bloom keyvec precondition into function\n revision: expose check for paths maybe changed in Bloom filter\n bloom: add helper to check if any key in a vector is present\n revision: add Bloom check that includes parent directories\n last-modified: check pathspec against Bloom filter first\n last-modified: keep per-path Bloom filters for wildcard pathspecs\n\n bloom.c | 12 +++++++++++\n bloom.h | 11 ++++++++++\n builtin/last-modified.c | 28 ++++++++++++++++++++++++++\n revision.c | 52 +++++++++++++++++++++++++++++++++++++-----------\n revision.h | 20 +++++++++++++++++++\n t/t8020-last-modified.sh | 49 +++++++++++++++++++++++++++++++++++++++++++++\n 6 files changed, 160 insertions(+), 12 deletions(-)\n\nRange-diff versus v3:\n\n1: 645c5d1ddf = 1: dbb1ad8e96 revision: move bloom keyvec precondition into function\n2: 3fa70e300d = 2: 6f0d62fe6c revision: expose check for paths maybe changed in Bloom filter\n3: d30e3fea71 = 3: 1c09e9ecba bloom: add helper to check if any key in a vector is present\n4: 7b5cc70022 = 4: 7c7792e057 revision: add Bloom check that includes parent directories\n5: 5cb67a54b1 ! 5: ac5a6bd427 last-modified: check pathspec against Bloom filter first\n @@ t/t8020-last-modified.sh: test_expect_success 'last-modified merge undoes change\n +\t\ttest_commit touch-b d/b &&\n +\n +\t\tgit commit-graph write --reachable --changed-paths &&\n -+\t\tgit -c core.commitGraph=false last-modified -t HEAD -- d/a \\\n -+\t\t\t>expect &&\n -+\t\tgit -c core.commitGraph=true last-modified -t HEAD -- d/a \\\n -+\t\t\t>actual &&\n ++\t\tGIT_TEST_COMMIT_GRAPH=0 \\\n ++\t\t\tgit -c core.commitGraph=false last-modified -t HEAD \\\n ++\t\t\t-- d/a >expect &&\n ++\t\tGIT_TEST_COMMIT_GRAPH=1 \\\n ++\t\t\tgit -c core.commitGraph=true last-modified -t HEAD \\\n ++\t\t\t-- d/a >actual &&\n +\n +\t\ttest_cmp expect actual\n +\t)\n6: c94f744a0f ! 6: 3524a202e7 last-modified: keep per-path Bloom filters for wildcard pathspecs\n @@ t/t8020-last-modified.sh: test_expect_success 'last-modified with Bloom filters\n +\t\ttest_commit sub-c d/b.c &&\n +\n +\t\tgit commit-graph write --reachable --changed-paths &&\n -+\t\tGIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n ++\t\tGIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n +\t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n +\t\t\t-- \"*.c\" >expect &&\n +\t\ttest_grep \"data .* bloom_queries:0$\" off.perf &&\n +\n -+\t\tGIT_TRACE2_PERF=\"$(pwd)/on.perf\" \\\n ++\t\tGIT_TEST_COMMIT_GRAPH=1 GIT_TRACE2_PERF=\"$(pwd)/on.perf\" \\\n +\t\t\tgit -c core.commitGraph=true last-modified -r HEAD \\\n +\t\t\t-- \"*.c\" >actual &&\n +\t\ttest_grep \"data .* bloom_queries:2$\" on.perf &&\n\n\n---\nbase-commit: c73e85354c275c9d409b26445089bc16940fc527\nchange-id: 20260716-toon-speed-up-last-modified-b04ea1f21831\n\n"},{"id":"551635","messageId":"20260901-toon-speed-up-last-modified-v4-1-a09949800404@iotcl.com","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com","subject":"[PATCH v4 1/6] revision: move bloom keyvec precondition into function","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-09-01T09:10:21Z","receivedAt":"2026-09-01T09:29:30Z","isPatch":true,"body":"There are currently two callsites calling\ncheck_maybe_different_in_bloom_filter(). They both check if\nrevs->bloom_keyvecs_nr is not zero before they call that function.\n\nMove bloom_keyvecs_nr precondition into\ncheck_maybe_different_in_bloom_filter() to simplify the code.\n\nNote that this changes `bloom_ret` to become -1 when there are no Bloom\nkey vectors, which results in `count_bloom_filter_false_positive` not\nbeing incremented. This is unobservable, as the Bloom statistics are\nonly reported when key vectors were set up.\n\nSigned-off-by: Toon Claes \n---\n revision.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 50dc8b1991..6a6a1b6fa0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -752,6 +752,9 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \tstruct bloom_filter *filter;\n \tint result = 0;\n \n+\tif (!revs->bloom_keyvecs_nr)\n+\t\treturn -1;\n+\n \tif (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)\n \t\treturn -1;\n \n@@ -806,7 +809,7 @@ static int rev_compare_tree(struct rev_info *revs,\n \t\t\treturn REV_TREE_SAME;\n \t}\n \n-\tif (revs->bloom_keyvecs_nr && !nth_parent) {\n+\tif (!nth_parent) {\n \t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n \n \t\tif (bloom_ret == 0)\n@@ -833,7 +836,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,\n \tif (!t1)\n \t\treturn 0;\n \n-\tif (!nth_parent && revs->bloom_keyvecs_nr) {\n+\tif (!nth_parent) {\n \t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n \t\tif (!bloom_ret)\n \t\t\treturn 1;\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551636","messageId":"20260901-toon-speed-up-last-modified-v4-2-a09949800404@iotcl.com","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com","subject":"[PATCH v4 2/6] revision: expose check for paths maybe changed in Bloom filter","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-09-01T09:10:22Z","receivedAt":"2026-09-01T09:29:36Z","isPatch":true,"body":"check_maybe_different_in_bloom_filter() looks up a commit's changed-path\nBloom filter and consults it to see whether the commit might have\nmodified any of the paths in the pathspec that `revs` was set up with.\nIn a follow-up commit we want to reuse this logic from another builtin.\n\nThat caller, however, has already looked up the commit's Bloom filter\nfor its own purposes, so having the function look it up again would mean\na redundant lookup.\n\nExtract the filter-consulting part into a new public function,\nrevs_maybe_changed_in_bloom(). This function takes an already looked-up\n`struct bloom_filter` instead of a commit.\nThe existing check_maybe_different_in_bloom_filter() becomes a thin\nwrapper that looks up the filter and delegates.\n\nExpose the new function via revision.h so other builtins can reuse the\nexact same filtering that `git log ` performs.\n\nThe existing function check_maybe_different_in_bloom_filter() returns a\ntristate value. This returns either:\n\n * `-1` : No Bloom filter was used.\n * `0` : The commit definitely did not change any of the paths.\n * `1` : The commit maybe changed one of the paths.\n\nThese return values are used to keep count of false-positives. But\nbecause the new function revs_maybe_changed_in_bloom() is not involved\nin counting statistics, it returns a boolean value telling whether the\ncommit definitely did not change any of the paths, or maybe changed some\nof them.\n\nSigned-off-by: Toon Claes \n---\n revision.c | 30 ++++++++++++++++++++----------\n revision.h | 12 ++++++++++++\n 2 files changed, 32 insertions(+), 10 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 6a6a1b6fa0..ed46b90b00 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -750,7 +750,6 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \t\t\t\t\t\t struct commit *commit)\n {\n \tstruct bloom_filter *filter;\n-\tint result = 0;\n \n \tif (!revs->bloom_keyvecs_nr)\n \t\treturn -1;\n@@ -765,18 +764,29 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \t\treturn -1;\n \t}\n \n-\tfor (size_t nr = 0; !result && nr < revs->bloom_keyvecs_nr; nr++) {\n-\t\tresult = bloom_filter_contains_vec(filter,\n-\t\t\t\t\t\t revs->bloom_keyvecs[nr],\n-\t\t\t\t\t\t revs->bloom_filter_settings);\n+\tif (revs_maybe_changed_in_bloom(revs, filter)) {\n+\t\tcount_bloom_filter_maybe++;\n+\t\treturn 1;\n \t}\n \n-\tif (result)\n-\t\tcount_bloom_filter_maybe++;\n-\telse\n-\t\tcount_bloom_filter_definitely_not++;\n+\tcount_bloom_filter_definitely_not++;\n+\n+\treturn 0;\n+}\n+\n+bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n+\t\t\t\t struct bloom_filter *filter)\n+{\n+\tif (!revs->bloom_keyvecs_nr || !filter)\n+\t\treturn true;\n+\n+\tfor (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)\n+\t\tif (bloom_filter_contains_vec(filter,\n+\t\t\t\t\t revs->bloom_keyvecs[nr],\n+\t\t\t\t\t revs->bloom_filter_settings))\n+\t\t\treturn true;\n \n-\treturn result;\n+\treturn false;\n }\n \n static int rev_compare_tree(struct rev_info *revs,\ndiff --git a/revision.h b/revision.h\nindex acf6d06b24..67778558e1 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -68,6 +68,7 @@ struct string_list;\n struct saved_parents;\n struct follow_pathspec_slab;\n struct bloom_keyvec;\n+struct bloom_filter;\n struct bloom_filter_settings;\n struct option;\n struct parse_opt_ctx_t;\n@@ -495,6 +496,17 @@ void reset_revision_walk(void);\n */\n int prepare_revision_walk(struct rev_info *revs);\n \n+/**\n+ * Consult a changed-path Bloom filter to determine if the commit to which the\n+ * filter belongs might have changed any of the paths in the `revs`.\n+ * prepare_revision_walk() needs to be called in advance to ensure\n+ * pathspec key vectors are set up.\n+ *\n+ * Returns false iff the commit definitely did not change any of the paths.\n+ */\n+bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n+\t\t\t\t struct bloom_filter *filter);\n+\n /* Drain the commits linked list into the priority queue. */\n void rev_info_commit_list_to_queue(struct rev_info *revs);\n /**\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551637","messageId":"20260901-toon-speed-up-last-modified-v4-3-a09949800404@iotcl.com","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com","subject":"[PATCH v4 3/6] bloom: add helper to check if any key in a vector is present","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-09-01T09:10:23Z","receivedAt":"2026-09-01T09:29:40Z","isPatch":true,"body":"The changed-path Bloom filter of a commit stores a key for every changed\npath together with each of its leading directories. To query if a path\nwas changed, bloom_keyvec_new() fills a key vector the same way: a key\nfor the given path and one for each of its leading directories. For\nexample, for \"a/b/c\" the vector holds keys for \"a/b/c\", \"a/b\" and \"a\".\n\nA Bloom filter can only ever prove absence. When a key is not in the\nfilter, the path it was made for definitely did not change. When it is\nin the filter, the path may have changed, as the key can be a false\npositive.\n\nbloom_filter_contains_vec() looks up all keys of a vector and reports\nwhether all of them are present. That answers: Is this path maybe\nchanged by this commit?\n\nA caller that also cares about the directories containing the path asks\na different question: Is this path, or any directory leading up to it,\nmaybe changed by this commit?\n\nConsider the Bloom filter of a commit that changed \"a/b/d\". It holds\nkeys for \"a/b/d\", \"a/b\" and \"a\", so looking up the vector of \"a/b/c\"\nwith bloom_filter_contains_vec() reports that nothing changed, even\nthough \"a/b\" and \"a\" did.\n\nAdd bloom_filter_contains_any_vec(), which reports whether any key in\nthe vector is present. It returns 0 only when none of the keys are in\nthe filter, which means the path and all directories leading up to it\ndefinitely did not change.\n\nThere are no callers yet, one is added in a subsequent commit.\n\nSigned-off-by: Toon Claes \n---\n bloom.c | 12 ++++++++++++\n bloom.h | 11 +++++++++++\n 2 files changed, 23 insertions(+)\n\ndiff --git a/bloom.c b/bloom.c\nindex caf22f9831..b96534e6e3 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -607,6 +607,18 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,\n \treturn ret;\n }\n \n+int bloom_filter_contains_any_vec(const struct bloom_filter *filter,\n+\t\t\t\t const struct bloom_keyvec *vec,\n+\t\t\t\t const struct bloom_filter_settings *settings)\n+{\n+\tint ret = 0;\n+\n+\tfor (size_t nr = 0; !ret && nr < vec->count; nr++)\n+\t\tret = bloom_filter_contains(filter, &vec->key[nr], settings);\n+\n+\treturn ret;\n+}\n+\n uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,\n \t\t\t\t int version)\n {\ndiff --git a/bloom.h b/bloom.h\nindex 92ab2100d3..f508db23ad 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -164,6 +164,17 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,\n \t\t\t const struct bloom_keyvec *v,\n \t\t\t const struct bloom_filter_settings *settings);\n \n+/*\n+ * bloom_filter_contains_any_vec - Check if any key in a key vector is in the\n+ * Bloom filter.\n+ *\n+ * Returns 1 if **any** key in the vector is present in the filter, 0 if none\n+ * of them are.\n+ */\n+int bloom_filter_contains_any_vec(const struct bloom_filter *filter,\n+\t\t\t\t const struct bloom_keyvec *v,\n+\t\t\t\t const struct bloom_filter_settings *settings);\n+\n uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,\n \t\t\t\t int version);\n \n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551638","messageId":"20260901-toon-speed-up-last-modified-v4-4-a09949800404@iotcl.com","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com","subject":"[PATCH v4 4/6] revision: add Bloom check that includes parent directories","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-09-01T09:10:24Z","receivedAt":"2026-09-01T09:29:43Z","isPatch":true,"body":"revs_maybe_changed_in_bloom() reports whether a commit may have changed\nany of the paths in the pathspec. It uses bloom_filter_contains_vec(),\nwhich requires all keys of a path's key vector to be present, so it only\nanswers for the paths themselves.\n\nA caller may track more than those paths. git-last-modified(1) with\n--show-trees reports the last modifying commit for the tree entries\ncontaining the paths as well, up to the root. For a pathspec \"a/b/c/\"\nthat means it reports \"a\" and \"a/b\" next to \"a/b/c\" and its entries, and\nthose can each resolve to a different commit. A commit that only changed\n\"a/top\" is the answer for \"a\", even though it touched nothing under\n\"a/b\".\n\nSuch a caller needs to know whether the path, or any of the directories\nleading up to it, may have changed. Add\nrevs_maybe_changed_in_bloom_with_parents(), which asks that question by\nusing bloom_filter_contains_any_vec() instead. A key vector holds a key\nfor the path and one for each of its leading directories, so looking up\nany of them answers it.\n\nThere are no callers yet, one is added in a subsequent commit.\n\nSigned-off-by: Toon Claes \n---\n revision.c | 15 +++++++++++++++\n revision.h | 8 ++++++++\n 2 files changed, 23 insertions(+)\n\ndiff --git a/revision.c b/revision.c\nindex ed46b90b00..a560146b4d 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -789,6 +789,21 @@ bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n \treturn false;\n }\n \n+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,\n+\t\t\t\t\t struct bloom_filter *filter)\n+{\n+\tif (!revs->bloom_keyvecs_nr || !filter)\n+\t\treturn true;\n+\n+\tfor (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)\n+\t\tif (bloom_filter_contains_any_vec(filter,\n+\t\t\t\t\t\t revs->bloom_keyvecs[nr],\n+\t\t\t\t\t\t revs->bloom_filter_settings))\n+\t\t\treturn true;\n+\n+\treturn false;\n+}\n+\n static int rev_compare_tree(struct rev_info *revs,\n \t\t\t struct commit *parent, struct commit *commit, int nth_parent)\n {\ndiff --git a/revision.h b/revision.h\nindex 67778558e1..192001ff79 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -507,6 +507,14 @@ int prepare_revision_walk(struct rev_info *revs);\n bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n \t\t\t\t struct bloom_filter *filter);\n \n+/**\n+ * Same as revs_maybe_changed_in_bloom(), but a change to any of the directories\n+ * leading up to a path counts as well. Callers that track the tree entries\n+ * containing the paths, and not just the paths themselves, need this.\n+ */\n+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,\n+\t\t\t\t\t struct bloom_filter *filter);\n+\n /* Drain the commits linked list into the priority queue. */\n void rev_info_commit_list_to_queue(struct rev_info *revs);\n /**\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551639","messageId":"20260901-toon-speed-up-last-modified-v4-5-a09949800404@iotcl.com","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com","subject":"[PATCH v4 5/6] last-modified: check pathspec against Bloom filter first","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-09-01T09:10:25Z","receivedAt":"2026-09-01T09:29:46Z","isPatch":true,"body":"When git-last-modified(1) starts, it builds a list of all the paths\nmatching the pathspec it needs to find the last modifying commit for.\nFor example, every file and subdirectory listed by:\n\n $ git last-modified -t --max-depth=0 -- src/\n\nAs it resolves a commit for each path during the revision walk, it drops\nthat path from the list.\n\nTo avoid diffing trees for every commit, Bloom filters are used when\navailable. For each remaining path, the commit's Bloom filter is checked\nto see whether the commit changed that path. The Bloom filter says\neither \"no\" or \"maybe\", and only in the latter case is the diff\ncalculated.\n\ngit-log(1) does this differently. It does not expand the pathspec but\nchecks the Bloom filter against the pathspec itself. This way, commits\nnot touching any path matching the pathspec can be discarded as a whole.\n\nApply this same check to git-last-modified(1). In a previous commit the\nfunction revs_maybe_changed_in_bloom(), used by git-log(1), was made\npublic. Use this as a pre-filter in git-last-modified(1). After this\npre-filter, paths are still checked one-by-one to only find those which\ndon't have a \"last commit\" yet.\n\nWith `--show-trees` the list holds more than the paths matching the\npathspec. It also holds each parent tree entry, up to the root. Each of\nthose can resolve to a different commit. Thus for the pathspec \"a/b/c\",\nthe list will also hold \"a\" and \"a/b\".\n\nWhen a commit touches \"a/other\", that commit could be the last commit\nfor \"a\", but revs_maybe_changed_in_bloom() would discard it, because it\ndoesn't match the full pathspec.\n\nInstead, when `--show-trees` is given, use\nrevs_maybe_changed_in_bloom_with_parents(), which indicates the commit\nmaybe changed any of the paths leading up to the path in the pathspec.\n\nSigned-off-by: Toon Claes \n---\n builtin/last-modified.c | 12 ++++++++++++\n t/t8020-last-modified.sh | 23 +++++++++++++++++++++++\n 2 files changed, 35 insertions(+)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 3846244dfc..8ab7944314 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -272,6 +272,18 @@ static bool maybe_changed_path(struct last_modified *lm,\n \tif (!filter)\n \t\treturn true;\n \n+\t/*\n+\t * With --show-trees we also track the tree entries containing the\n+\t * paths, so a change to any of those parent directories matters too.\n+\t */\n+\tif (lm->show_trees) {\n+\t\tif (!revs_maybe_changed_in_bloom_with_parents(&lm->rev, filter))\n+\t\t\treturn false;\n+\t} else {\n+\t\tif (!revs_maybe_changed_in_bloom(&lm->rev, filter))\n+\t\t\treturn false;\n+\t}\n+\n \thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n \t\tif (active && !bitmap_get(active, ent->diff_idx))\n \t\t\tcontinue;\ndiff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\nindex 9dba4b9d90..e75437c18e 100755\n--- a/t/t8020-last-modified.sh\n+++ b/t/t8020-last-modified.sh\n@@ -269,6 +269,29 @@ test_expect_success 'last-modified merge undoes changes' '\n \tEOF\n '\n \n+test_expect_success 'last-modified with Bloom filters and --show-trees' '\n+\ttest_when_finished rm -rf bloom &&\n+\tgit init bloom &&\n+\t(\n+\t\tcd bloom &&\n+\t\tmkdir d &&\n+\t\ttest_commit base-a d/a &&\n+\t\ttest_commit base-b d/b &&\n+\t\ttest_commit touch-a d/a &&\n+\t\ttest_commit touch-b d/b &&\n+\n+\t\tgit commit-graph write --reachable --changed-paths &&\n+\t\tGIT_TEST_COMMIT_GRAPH=0 \\\n+\t\t\tgit -c core.commitGraph=false last-modified -t HEAD \\\n+\t\t\t-- d/a >expect &&\n+\t\tGIT_TEST_COMMIT_GRAPH=1 \\\n+\t\t\tgit -c core.commitGraph=true last-modified -t HEAD \\\n+\t\t\t-- d/a >actual &&\n+\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n test_expect_success 'cannot run last-modified on two commits' '\n \ttest_must_fail git last-modified HEAD HEAD~1 2>err &&\n \ttest_grep \"last-modified can only operate on one commit at a time\" err\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551640","messageId":"20260901-toon-speed-up-last-modified-v4-6-a09949800404@iotcl.com","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com","subject":"[PATCH v4 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-09-01T09:10:26Z","receivedAt":"2026-09-01T09:29:48Z","isPatch":true,"body":"The last-modified builtin expands the pathspec to a set of literal paths\nand builds a Bloom key for each. During the walk it looks those keys up\nin the commit's filter to decide whether the commit is worth diffing.\nThese lookups need `bloom_filter_settings` for the key hashing.\n\nprepare_revision_walk() runs prepare_to_use_bloom_filter() to build the\npathspec key vectors. For a pathspec that cannot be turned into a Bloom\nkey, such as a top-level wildcard like \"*.c\", that function gives up and\nclears `bloom_filter_settings`.\n\nRestore `bloom_filter_settings` after prepare_revision_walk() so the\nper-path check keeps working for wildcard pathspecs.\n\nThis change isn't having any effect on the output, but only has an\nimpact on performance. Add a \"bloom_queries\" trace2 counter that records\nhow often the per-path Bloom check runs, and a test that asserts the\ncount increments as appropriate for a top-level wildcard pathspec.\n\nSigned-off-by: Toon Claes \n---\n builtin/last-modified.c | 16 ++++++++++++++++\n t/t8020-last-modified.sh | 26 ++++++++++++++++++++++++++\n 2 files changed, 42 insertions(+)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 8ab7944314..bedccb3ace 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -18,6 +18,7 @@\n #include \"quote.h\"\n #include \"repository.h\"\n #include \"revision.h\"\n+#include \"trace2.h\"\n \n /* Remember to update object flag allocation in object.h */\n #define PARENT1 (1u<<16) /* used instead of SEEN */\n@@ -63,6 +64,8 @@ struct last_modified {\n \n \t/* 'scratch' to avoid allocating a bitmap every process_parent() */\n \tstruct bitmap *scratch;\n+\n+\tunsigned int count_bloom_filter_queries;\n };\n \n static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)\n@@ -272,6 +275,8 @@ static bool maybe_changed_path(struct last_modified *lm,\n \tif (!filter)\n \t\treturn true;\n \n+\tlm->count_bloom_filter_queries++;\n+\n \t/*\n \t * With --show-trees we also track the tree entries containing the\n \t * paths, so a change to any of those parent directories matters too.\n@@ -370,6 +375,14 @@ static int last_modified_run(struct last_modified *lm)\n \n \tprepare_revision_walk(&lm->rev);\n \n+\t/*\n+\t * prepare_revision_walk() clears bloom_filter_settings for pathspecs\n+\t * without a Bloom key. Restore it so the per-path check keeps working.\n+\t */\n+\tif (!lm->rev.bloom_filter_settings)\n+\t\tlm->rev.bloom_filter_settings =\n+\t\t\tget_bloom_filter_settings(lm->rev.repo);\n+\n \tmax_count = lm->rev.max_count;\n \n \tinit_active_paths_for_commit(&lm->active_paths);\n@@ -479,6 +492,9 @@ static int last_modified_run(struct last_modified *lm)\n \tif (hashmap_get_size(&lm->paths))\n \t\tBUG(\"paths remaining beyond boundary in last-modified\");\n \n+\ttrace2_data_intmax(\"last-modified\", lm->rev.repo, \"bloom_queries\",\n+\t\t\t lm->count_bloom_filter_queries);\n+\n \tclear_prio_queue(¬_queue);\n \tclear_prio_queue(&queue);\n \tclear_active_paths_for_commit(&lm->active_paths);\ndiff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\nindex e75437c18e..5be1d0f948 100755\n--- a/t/t8020-last-modified.sh\n+++ b/t/t8020-last-modified.sh\n@@ -292,6 +292,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '\n \t)\n '\n \n+test_expect_success 'last-modified with Bloom filters and top-level wildcard' '\n+\ttest_when_finished rm -rf wildcard &&\n+\tgit init wildcard &&\n+\t(\n+\t\tcd wildcard &&\n+\t\ttest_commit base-c a.c &&\n+\t\ttest_commit base-h a.h &&\n+\t\ttest_commit touch-c a.c &&\n+\t\tmkdir d &&\n+\t\ttest_commit sub-c d/b.c &&\n+\n+\t\tgit commit-graph write --reachable --changed-paths &&\n+\t\tGIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n+\t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n+\t\t\t-- \"*.c\" >expect &&\n+\t\ttest_grep \"data .* bloom_queries:0$\" off.perf &&\n+\n+\t\tGIT_TEST_COMMIT_GRAPH=1 GIT_TRACE2_PERF=\"$(pwd)/on.perf\" \\\n+\t\t\tgit -c core.commitGraph=true last-modified -r HEAD \\\n+\t\t\t-- \"*.c\" >actual &&\n+\t\ttest_grep \"data .* bloom_queries:2$\" on.perf &&\n+\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n test_expect_success 'cannot run last-modified on two commits' '\n \ttest_must_fail git last-modified HEAD HEAD~1 2>err &&\n \ttest_grep \"last-modified can only operate on one commit at a time\" err\n\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"551668","messageId":"xmqqv78pt75k.fsf@gitster.g","threadId":"66240","inReplyTo":"87mru1wcyi.fsf@emacs.iotcl.com","subject":"Re: [PATCH v3 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-09-01T13:47:51Z","receivedAt":"2026-09-01T13:47:54Z","isPatch":true,"body":"Toon Claes writes:\n\n> Junio C Hamano writes:\n>\n>> Toon Claes writes:\n>>\n>>> diff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\n>>> index df73c7d0d0..75b18ee83b 100755\n>>> --- a/t/t8020-last-modified.sh\n>>> +++ b/t/t8020-last-modified.sh\n>>> @@ -290,6 +290,32 @@ test_expect_success 'last-modified with Bloom filters and --show-trees' '\n>>> \t)\n>>> '\n>>> \n>>> +test_expect_success 'last-modified with Bloom filters and top-level wildcard' '\n>>> ...\n>>> +\t\tGIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n>>> +\t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n>>> +\t\t\t-- \"*.c\" >expect &&\n>>> +\t\ttest_grep \"data .* bloom_queries:0$\" off.perf &&\n>>\n>> Ah, OK. With GIT_TEST_COMMIT_GRAPH=1 exported from the test harness\n>> environment, 'git -c core.commitGraph=false' would not be effective\n>> here. You would need to do something like:\n>>\n>> \t\tGIT_TEST_COMMIT_GRAPH=0 GIT_TRACE2_PERF=\"$(pwd)/off.perf\" \\\n>> \t\t\tgit -c core.commitGraph=false last-modified -r HEAD \\\n>> \t\t\t-- \"*.c\" >expect &&\n>>\n>>> +\t\tGIT_TRACE2_PERF=\"$(pwd)/on.perf\" \\\n>>> +\t\t\tgit -c core.commitGraph=true last-modified -r HEAD \\\n>>> +\t\t\t-- \"*.c\" >actual &&\n>>\n>> And in the case where GIT_TEST_COMMIT_GRAPH=0 comes from the\n>> environment, you might want to be explicit about setting the\n>> variable here as well.\n>\n> Thanks for this suggestion. Yeah, I didn't notice it makes CI fail.\n>\n> But a little bit of a followup question, I noticed I also should be\n> setting these in [PATCH 5/6], but test don't fail if not set\n> appropriately.\n\nYeah, I noticed it when I queued the two fixup commits near the tip\nof 'seen'. I wrote it off as the test *not* checking everything.\nIf the test is about what the command does and not about how the\ncommand exactly does its thing, you may not notice the difference\nas long as two code paths both produce the right results.\n\nSo some tightening of tests might be needed, if we care.\n"},{"id":"552414","messageId":"aqJWX0INerT8F687@pks.im","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-3-a09949800404@iotcl.com","subject":"Re: [PATCH v4 3/6] bloom: add helper to check if any key in a vector is present","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-09-10T07:03:59Z","receivedAt":"2026-09-10T07:04:12Z","isPatch":true,"body":"On Tue, Sep 01, 2026 at 11:10:23AM +0200, Toon Claes wrote:\n> diff --git a/bloom.c b/bloom.c\n> index caf22f9831..b96534e6e3 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -607,6 +607,18 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,\n> \treturn ret;\n> }\n> \n> +int bloom_filter_contains_any_vec(const struct bloom_filter *filter,\n> +\t\t\t\t const struct bloom_keyvec *vec,\n> +\t\t\t\t const struct bloom_filter_settings *settings)\n> +{\n> +\tint ret = 0;\n> +\n> +\tfor (size_t nr = 0; !ret && nr < vec->count; nr++)\n> +\t\tret = bloom_filter_contains(filter, &vec->key[nr], settings);\n> +\n> +\treturn ret;\n> +}\n\n`bloom_filter_contains()` may also return -1 in case `filter->len == 0`,\nand we'd bubble up that code. But here...\n\n> diff --git a/bloom.h b/bloom.h\n> index 92ab2100d3..f508db23ad 100644\n> --- a/bloom.h\n> +++ b/bloom.h\n> @@ -164,6 +164,17 @@ int bloom_filter_contains_vec(const struct bloom_filter *filter,\n> \t\t\t const struct bloom_keyvec *v,\n> \t\t\t const struct bloom_filter_settings *settings);\n> \n> +/*\n> + * bloom_filter_contains_any_vec - Check if any key in a key vector is in the\n> + * Bloom filter.\n> + *\n> + * Returns 1 if **any** key in the vector is present in the filter, 0 if none\n> + * of them are.\n> + */\n> +int bloom_filter_contains_any_vec(const struct bloom_filter *filter,\n> +\t\t\t\t const struct bloom_keyvec *v,\n> +\t\t\t\t const struct bloom_filter_settings *settings);\n\n... you only document that it may return 0 or 1. We should either\nproperly document this or munge the returned value to be 0 or 1, only.\nAnd if so, we could probably adapt this function to have a boolean\nreturn value.\n\nPatrick\n"},{"id":"552415","messageId":"aqJWasW9IKXhjfd7@pks.im","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-4-a09949800404@iotcl.com","subject":"Re: [PATCH v4 4/6] revision: add Bloom check that includes parent directories","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-09-10T07:04:10Z","receivedAt":"2026-09-10T07:04:15Z","isPatch":true,"body":"On Tue, Sep 01, 2026 at 11:10:24AM +0200, Toon Claes wrote:\n> diff --git a/revision.c b/revision.c\n> index ed46b90b00..a560146b4d 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -789,6 +789,21 @@ bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n> \treturn false;\n> }\n> \n> +bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,\n> +\t\t\t\t\t struct bloom_filter *filter)\n\nIn \"revision.c\", \"parents\" would immediately read as \"commit parent\" to\nme. Would `revs_maybe_changed_in_bloom_with_leading_dirs()` be a better\nname to clarify that this is about directories, only?\n\n> +{\n> +\tif (!revs->bloom_keyvecs_nr || !filter)\n> +\t\treturn true;\n> +\n> +\tfor (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)\n> +\t\tif (bloom_filter_contains_any_vec(filter,\n> +\t\t\t\t\t\t revs->bloom_keyvecs[nr],\n> +\t\t\t\t\t\t revs->bloom_filter_settings))\n> +\t\t\treturn true;\n> +\n> +\treturn false;\n> +}\n> +\n> static int rev_compare_tree(struct rev_info *revs,\n> \t\t\t struct commit *parent, struct commit *commit, int nth_parent)\n> {\n> diff --git a/revision.h b/revision.h\n> index 67778558e1..192001ff79 100644\n> --- a/revision.h\n> +++ b/revision.h\n> @@ -507,6 +507,14 @@ int prepare_revision_walk(struct rev_info *revs);\n> bool revs_maybe_changed_in_bloom(struct rev_info *revs,\n> \t\t\t\t struct bloom_filter *filter);\n> \n> +/**\n> + * Same as revs_maybe_changed_in_bloom(), but a change to any of the directories\n> + * leading up to a path counts as well. Callers that track the tree entries\n> + * containing the paths, and not just the paths themselves, need this.\n> + */\n\nThis comment also talks about leading directories, not parent\ndirectories.\n\n> +bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,\n> +\t\t\t\t\t struct bloom_filter *filter);\n> +\n\nPatrick\n"},{"id":"552416","messageId":"aqJWb1kq81A8AJWI@pks.im","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-5-a09949800404@iotcl.com","subject":"Re: [PATCH v4 5/6] last-modified: check pathspec against Bloom filter first","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-09-10T07:04:15Z","receivedAt":"2026-09-10T07:04:22Z","isPatch":true,"body":"On Tue, Sep 01, 2026 at 11:10:25AM +0200, Toon Claes wrote:\n> When git-last-modified(1) starts, it builds a list of all the paths\n> matching the pathspec it needs to find the last modifying commit for.\n> For example, every file and subdirectory listed by:\n> \n> $ git last-modified -t --max-depth=0 -- src/\n> \n> As it resolves a commit for each path during the revision walk, it drops\n> that path from the list.\n> \n> To avoid diffing trees for every commit, Bloom filters are used when\n> available. For each remaining path, the commit's Bloom filter is checked\n> to see whether the commit changed that path. The Bloom filter says\n> either \"no\" or \"maybe\", and only in the latter case is the diff\n> calculated.\n> \n> git-log(1) does this differently. It does not expand the pathspec but\n> checks the Bloom filter against the pathspec itself. This way, commits\n> not touching any path matching the pathspec can be discarded as a whole.\n> \n> Apply this same check to git-last-modified(1). In a previous commit the\n> function revs_maybe_changed_in_bloom(), used by git-log(1), was made\n> public. Use this as a pre-filter in git-last-modified(1). After this\n> pre-filter, paths are still checked one-by-one to only find those which\n> don't have a \"last commit\" yet.\n\nSo in theory, we _might_ now do some of the checks multiple times. But\nthe expectation is that the number of pathspecs is typically much lower\nthan the number of expanded paths to check against, so in most cases it\nshould be faster to do this pre-filtering?\n\nIt'll probably be possible to craft edge cases where the new logic is\nslower because we now do more work in the matching case. But overall I\nthink this is a sensible tradeoff. After all, we use the same tradeoff\nin git-log(1).\n\n> With `--show-trees` the list holds more than the paths matching the\n> pathspec. It also holds each parent tree entry, up to the root. Each of\n> those can resolve to a different commit. Thus for the pathspec \"a/b/c\",\n> the list will also hold \"a\" and \"a/b\".\n> \n> When a commit touches \"a/other\", that commit could be the last commit\n> for \"a\", but revs_maybe_changed_in_bloom() would discard it, because it\n> doesn't match the full pathspec.\n> \n> Instead, when `--show-trees` is given, use\n> revs_maybe_changed_in_bloom_with_parents(), which indicates the commit\n> maybe changed any of the paths leading up to the path in the pathspec.\n\nYou explain what we do and why it's safe, which is good. But what's\nmissing is the \"why\". As far as I understand the reason is performance,\nbut if so I'd have expected a benchmark demonstrating the benefit.\n\nPatrick\n"},{"id":"552417","messageId":"aqJWihcFmX7tPio5@pks.im","threadId":"66240","inReplyTo":"20260901-toon-speed-up-last-modified-v4-6-a09949800404@iotcl.com","subject":"Re: [PATCH v4 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-09-10T07:04:42Z","receivedAt":"2026-09-10T07:04:48Z","isPatch":true,"body":"On Tue, Sep 01, 2026 at 11:10:26AM +0200, Toon Claes wrote:\n> diff --git a/builtin/last-modified.c b/builtin/last-modified.c\n> index 8ab7944314..bedccb3ace 100644\n> --- a/builtin/last-modified.c\n> +++ b/builtin/last-modified.c\n> @@ -370,6 +375,14 @@ static int last_modified_run(struct last_modified *lm)\n> \n> \tprepare_revision_walk(&lm->rev);\n> \n> +\t/*\n> +\t * prepare_revision_walk() clears bloom_filter_settings for pathspecs\n> +\t * without a Bloom key. Restore it so the per-path check keeps working.\n> +\t */\n> +\tif (!lm->rev.bloom_filter_settings)\n> +\t\tlm->rev.bloom_filter_settings =\n> +\t\t\tget_bloom_filter_settings(lm->rev.repo);\n> +\n> \tmax_count = lm->rev.max_count;\n> \n> \tinit_active_paths_for_commit(&lm->active_paths);\n\nSo the revision subsystem is unhappy, but we basically force the bloom\nfilter settings in there anyway? That feels a bit fragile to me. Is\nthere a reason why the revision machinery itself specifically needs to\nhave the bloom filters populated, or do we basically just have to set up\nthe bloom filters so that we can access them ourselves?\n\nIf the latter, can't we instead store the bloom filter settings in\n`struct last_modified` instead of forcing them into the revision\nmachinery? Something like the below patch on top of tihs, which still\npasses all of our tests.\n\nThere might be good reasons though why we can't do it this way.\n\nPatrick\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex bedccb3ace..dabd0b7c34 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -58,6 +58,8 @@ struct last_modified {\n \tbool nul_termination;\n \tint max_depth;\n \n+\tstruct bloom_filter_settings *bloom_filter_settings;\n+\n \tconst char **all_paths;\n \tsize_t all_paths_nr;\n \tstruct active_paths_for_commit active_paths;\n@@ -117,9 +119,9 @@ static void add_path_from_diff(struct diff_queue_struct *q,\n \n \t\tFLEX_ALLOC_STR(ent, path, path);\n \t\toidcpy(&ent->oid, &p->two->oid);\n-\t\tif (lm->rev.bloom_filter_settings)\n+\t\tif (lm->bloom_filter_settings)\n \t\t\tbloom_key_fill(&ent->key, path, strlen(path),\n-\t\t\t\t lm->rev.bloom_filter_settings);\n+\t\t\t\t lm->bloom_filter_settings);\n \t\thashmap_entry_init(&ent->hashent, strhash(ent->path));\n \t\thashmap_add(&lm->paths, &ent->hashent);\n \t}\n@@ -265,7 +267,7 @@ static bool maybe_changed_path(struct last_modified *lm,\n \tstruct last_modified_entry *ent;\n \tstruct hashmap_iter iter;\n \n-\tif (!lm->rev.bloom_filter_settings)\n+\tif (!lm->bloom_filter_settings)\n \t\treturn true;\n \n \tif (commit_graph_generation(origin) == GENERATION_NUMBER_INFINITY)\n@@ -294,7 +296,7 @@ static bool maybe_changed_path(struct last_modified *lm,\n \t\t\tcontinue;\n \n \t\tif (bloom_filter_contains(filter, &ent->key,\n-\t\t\t\t\t lm->rev.bloom_filter_settings))\n+\t\t\t\t\t lm->bloom_filter_settings))\n \t\t\treturn true;\n \t}\n \treturn false;\n@@ -375,14 +377,6 @@ static int last_modified_run(struct last_modified *lm)\n \n \tprepare_revision_walk(&lm->rev);\n \n-\t/*\n-\t * prepare_revision_walk() clears bloom_filter_settings for pathspecs\n-\t * without a Bloom key. Restore it so the per-path check keeps working.\n-\t */\n-\tif (!lm->rev.bloom_filter_settings)\n-\t\tlm->rev.bloom_filter_settings =\n-\t\t\tget_bloom_filter_settings(lm->rev.repo);\n-\n \tmax_count = lm->rev.max_count;\n \n \tinit_active_paths_for_commit(&lm->active_paths);\n@@ -530,7 +524,7 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,\n \t\treturn argc;\n \t}\n \n-\tlm->rev.bloom_filter_settings = get_bloom_filter_settings(lm->rev.repo);\n+\tlm->bloom_filter_settings = get_bloom_filter_settings(lm->rev.repo);\n \n \tif (populate_paths_from_revs(lm) < 0)\n \t\treturn -1;\n"}]}