{"thread":{"id":"66029","subject":"[PATCH 0/4] last-modified: use the pathspec's Bloom key to pre-filter commits","startedAt":"2026-07-17T15:47:08Z","lastAt":"2026-08-08T17:08:01Z","messageCount":30,"participants":["Toon Claes","Junio C Hamano","Taylor Blau","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"548535","messageId":"20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com","threadId":"66029","inReplyTo":null,"subject":"[PATCH 0/4] last-modified: use the pathspec's Bloom key to pre-filter commits","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-07-17T15:46:58Z","receivedAt":"2026-07-17T15:47:08Z","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 moves a condition around so it becomes deduplicated and\n   eventually can be reused by git-last-modified(1).\n - Patch 2 exposes a helper from revision.c publicly. The function is\n   split out so the Bloom filter wouldn't be looked up twice from\n   git-last-modified(1).\n - Patch 3 uses this new helper in git-last-modified(1).\n - Patch 4 is bonus change, which optimizes when working with wildcard\n   pathspecs.\n\nBelow are benchmark on the ziglang/zig repository for the `doc/langref/`\ndirectory (with commit-graphs writting using `--changed-paths`):\n\n    Benchmark 1: master last-modified\n      Time (mean ± σ):      52.6 ms ±   4.0 ms    [User: 49.2 ms, System: 3.0 ms]\n      Range (min … max):    48.2 ms …  73.8 ms    62 runs\n\n    Benchmark 2: HEAD last-modified\n      Time (mean ± σ):      14.3 ms ±   1.8 ms    [User: 12.0 ms, System: 2.1 ms]\n      Range (min … max):    10.5 ms …  18.9 ms    182 runs\n\n    Benchmark 3: git log\n      Time (mean ± σ):      17.4 ms ±   1.4 ms    [User: 13.5 ms, System: 3.7 ms]\n      Range (min … max):    15.0 ms …  26.1 ms    185 runs\n\n    Summary\n      HEAD last-modified ran\n        1.22 ± 0.18 times faster than git log\n        3.66 ± 0.55 times faster than master last-modified\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---\nToon Claes (4):\n      revision: move bloom keyvec precondition into function\n      revision: expose check for paths maybe changed in Bloom filter\n      last-modified: check pathspec against Bloom filter first\n      last-modified: keep per-path Bloom filters for wildcard pathspecs\n\n builtin/last-modified.c | 11 +++++++++++\n revision.c              | 32 +++++++++++++++++++++++---------\n revision.h              | 17 +++++++++++++++++\n 3 files changed, 51 insertions(+), 9 deletions(-)\n\n\n\n---\nbase-commit: 55526a18268bbc1ddaf8a6b7850c33d984eac9e9\nchange-id: 20260716-toon-speed-up-last-modified-b04ea1f21831\n\n"},{"id":"548536","messageId":"20260717-toon-speed-up-last-modified-v1-1-410418f18614@iotcl.com","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com","subject":"[PATCH 1/4] revision: move bloom keyvec precondition into function","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-07-17T15:46:59Z","receivedAt":"2026-07-17T15:47:11Z","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 <toon@iotcl.com>\n---\n revision.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 137a86d33b..f3c9407a66 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -750,6 +750,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@@ -804,7 +807,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@@ -831,7 +834,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.53.0.1323.g189a785ab5\n\n"},{"id":"548537","messageId":"20260717-toon-speed-up-last-modified-v1-2-410418f18614@iotcl.com","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com","subject":"[PATCH 2/4] revision: expose check for paths maybe changed in Bloom filter","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-07-17T15:47:00Z","receivedAt":"2026-07-17T15:47:19Z","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 <pathspec>` performs.\n\nSigned-off-by: Toon Claes <toon@iotcl.com>\n---\n revision.c | 31 +++++++++++++++++++++----------\n revision.h | 17 +++++++++++++++++\n 2 files changed, 38 insertions(+), 10 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex f3c9407a66..040b30b5ee 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -748,26 +748,20 @@ 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+\tint result;\n \n \tif (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)\n \t\treturn -1;\n \n \tfilter = get_bloom_filter(revs->repo, commit);\n-\n \tif (!filter) {\n \t\tcount_bloom_filter_not_present++;\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-\t}\n+\tresult = revs_maybe_changed_in_bloom(revs, filter);\n+\tif (result < 0)\n+\t\treturn result;\n \n \tif (result)\n \t\tcount_bloom_filter_maybe++;\n@@ -777,6 +771,23 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \treturn result;\n }\n \n+int revs_maybe_changed_in_bloom(struct rev_info *revs,\n+\t\t\t\tstruct bloom_filter *filter)\n+{\n+\tint result = 0;\n+\n+\tif (!revs->bloom_keyvecs_nr)\n+\t\treturn -1;\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+\t}\n+\n+\treturn result;\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 569b3fa1cb..7569c210cc 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@@ -493,6 +494,22 @@ void reset_revision_walk(void);\n  */\n int prepare_revision_walk(struct rev_info *revs);\n \n+/**\n+ * Take in a changed-path Bloom filter that belongs to a commit, and consult it\n+ * to see if it might have modified any of the paths in the `revs`.\n+ * The caller should look up `filter`, probably with get_bloom_filter().\n+ * prepare_revision_walk() needs to be called in advance to ensure\n+ * pathspec key vectors are set up.\n+ *\n+ * Returns -1 if no sensible answer could be given because of missing\n+ * preconditions (no pathspec key vectors).\n+ * Returns 0 if the commit definitely did not change any of the paths and 1 if\n+ * the commit maybe has changed one of them, although that might be a\n+ * false-positive.\n+ */\n+int revs_maybe_changed_in_bloom(struct rev_info *revs,\n+\t\t\t\tstruct 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.53.0.1323.g189a785ab5\n\n"},{"id":"548538","messageId":"20260717-toon-speed-up-last-modified-v1-3-410418f18614@iotcl.com","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com","subject":"[PATCH 3/4] last-modified: check pathspec against Bloom filter first","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-07-17T15:47:01Z","receivedAt":"2026-07-17T15:47:29Z","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\nSigned-off-by: Toon Claes <toon@iotcl.com>\n---\n builtin/last-modified.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 5478182f2e..e8ee610404 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -272,6 +272,9 @@ static bool maybe_changed_path(struct last_modified *lm,\n \tif (!filter)\n \t\treturn true;\n \n+\tif (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)\n+\t\treturn false;\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;\n\n-- \n2.53.0.1323.g189a785ab5\n\n"},{"id":"548539","messageId":"20260717-toon-speed-up-last-modified-v1-4-410418f18614@iotcl.com","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com","subject":"[PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-07-17T15:47:02Z","receivedAt":"2026-07-17T15:47:33Z","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\nSigned-off-by: Toon Claes <toon@iotcl.com>\n---\n builtin/last-modified.c | 8 ++++++++\n 1 file changed, 8 insertions(+)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex e8ee610404..adc7cd8c74 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -360,6 +360,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\n-- \n2.53.0.1323.g189a785ab5\n\n"},{"id":"548558","messageId":"87cxwl1lb4.fsf@emacs.iotcl.com","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com","subject":"Re: [PATCH 0/4] last-modified: use the pathspec's Bloom key to pre-filter commits","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-07-17T19:13:35Z","receivedAt":"2026-07-17T19:13:45Z","isPatch":true,"body":"Toon Claes <toon@iotcl.com> writes:\n\n>  - Patch 3 uses this new helper in git-last-modified(1).\n>  - Patch 4 is bonus change, which optimizes when working with wildcard\n>    pathspecs.\n\nI just realize I forgot to add Helped-by or Based-on-patches-by trailers\nfor Peff. I'm happy to add them on reroll.\n\n-- \nCheers,\nToon\n"},{"id":"548559","messageId":"87a4rp1l65.fsf@emacs.iotcl.com","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-4-410418f18614@iotcl.com","subject":"Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-07-17T19:16:34Z","receivedAt":"2026-07-17T19:16:45Z","isPatch":true,"body":"Toon Claes <toon@iotcl.com> writes:\n\n> The last-modified builtin expands the pathspec to a set of literal paths\n> and builds a Bloom key for each. During the walk it looks those keys up\n> in the commit's filter to decide whether the commit is worth diffing.\n> These lookups need `bloom_filter_settings` for the key hashing.\n>\n> prepare_revision_walk() runs prepare_to_use_bloom_filter() to build the\n> pathspec key vectors. For a pathspec that cannot be turned into a Bloom\n> key, such as a top-level wildcard like \"*.c\", that function gives up and\n> clears `bloom_filter_settings`.\n>\n> Restore `bloom_filter_settings` after prepare_revision_walk() so the\n> per-path check keeps working for wildcard pathspecs.\n>\n> Signed-off-by: Toon Claes <toon@iotcl.com>\n> ---\n>  builtin/last-modified.c | 8 ++++++++\n>  1 file changed, 8 insertions(+)\n>\n> diff --git a/builtin/last-modified.c b/builtin/last-modified.c\n> index e8ee610404..adc7cd8c74 100644\n> --- a/builtin/last-modified.c\n> +++ b/builtin/last-modified.c\n> @@ -360,6 +360,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\n@Peff, as far I could tell:\n\n* This change was not needed to be able to use the Bloom filters with\n  the pathspec.\n\n* Only restoring bloom_filter_settings was needed. In your patch you're\n  calling prepare_to_use_bloom_filter(), but that is being called by\n  prepare_revision_walk(). Thus the restoring of the filter settings\n  I've added after that function.\n\n>  \tmax_count = lm->rev.max_count;\n>  \n>  \tinit_active_paths_for_commit(&lm->active_paths);\n>\n> -- \n> 2.53.0.1323.g189a785ab5\n>\n\n-- \nCheers,\nToon\n"},{"id":"548560","messageId":"xmqqwlut1gzc.fsf@gitster.g","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-2-410418f18614@iotcl.com","subject":"Re: [PATCH 2/4] revision: expose check for paths maybe changed in Bloom filter","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-07-17T20:47:03Z","receivedAt":"2026-07-17T20:47:06Z","isPatch":true,"body":"Toon Claes <toon@iotcl.com> writes:\n\n> @@ -748,26 +748,20 @@ 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> +\tint result;\n>  \n>  \tif (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)\n>  \t\treturn -1;\n>  \n>  \tfilter = get_bloom_filter(revs->repo, commit);\n> -\n>  \tif (!filter) {\n>  \t\tcount_bloom_filter_not_present++;\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> -\t}\n> +\tresult = revs_maybe_changed_in_bloom(revs, filter);\n> +\tif (result < 0)\n> +\t\treturn result;\n>  \n>  \tif (result)\n>  \t\tcount_bloom_filter_maybe++;\n\nDoesn't this change skew the stats?\n\nIn today's code, revs->bloom_keyvecs_nr == 0 results in an early\nreturn, without touching count_bloom_filter_not_present.  In the\nupdated code, we would not notice revs->bloom_keyvecs_nr being zero\nand call get_bloom_filter() first.  If that yields NULL, we increment\n_not_present variable.\n\nAlso an error return -1 from bloom_filter_contains_vec() breaks the\nloop in today's code, increments count_bloom_filter_maybe (even\nthough the result is -1, not positive) and returns.  In updated\ncode, an error return would return from this function but neither\n_maybe nor _definitely_not is incremented.\n\nIt could be that these two are intended \"while at it we fix it too\"\nimprovements, but then they deserve to be mentioned in the proposed\nlog message.  Personally, I think the first one that increments the\n_not_present statistics when keyvecs is empty a bug, though.\n\n> @@ -777,6 +771,23 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n>  \treturn result;\n>  }\n>  \n> +int revs_maybe_changed_in_bloom(struct rev_info *revs,\n> +\t\t\t\tstruct bloom_filter *filter)\n> +{\n> +\tint result = 0;\n> +\n> +\tif (!revs->bloom_keyvecs_nr)\n> +\t\treturn -1;\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> +\t}\n> +\n> +\treturn result;\n> +}\n\nThis is inherited from the original, but I think it would be easier\nto follow if it were written like this:\n\n\tfor (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++) {\n\t\tif ((result = bloom_filter_contains_vec(filter,\n\t\t\t\t\trevs->bloom_keyvecs[nr],\n\t\t\t\t\trevs->bloom_filter_settings)))\n\t\t\treturn result;\n\t}\n\treturn 0;\n"},{"id":"548563","messageId":"alq1Q55ezuN9ZI9j@com-79390","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-3-410418f18614@iotcl.com","subject":"Re: [PATCH 3/4] last-modified: check pathspec against Bloom filter first","fromName":"Taylor Blau","fromEmail":"ttaylorr@openai.com","sentAt":"2026-07-17T23:05:39Z","receivedAt":"2026-07-17T23:05:43Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 05:47:01PM +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>\n> Signed-off-by: Toon Claes <toon@iotcl.com>\n\n> ---\n>  builtin/last-modified.c | 3 +++\n>  1 file changed, 3 insertions(+)\n>\n> diff --git a/builtin/last-modified.c b/builtin/last-modified.c\n> index 5478182f2e..e8ee610404 100644\n> --- a/builtin/last-modified.c\n> +++ b/builtin/last-modified.c\n> @@ -272,6 +272,9 @@ static bool maybe_changed_path(struct last_modified *lm,\n>  \tif (!filter)\n>  \t\treturn true;\n>\n> +\tif (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)\n\nNit: please prefer 'if (!foo())' over 'if (foo() == 0)'.\n\n> +\t\treturn false;\n> +\n\nI don't think this is safe with '--show-trees'. The original pathspec\ndoes not cover every entry in 'lm->paths', since the function\n'populate_paths_from_revs()' also adds ancestor tree entries.\n\nThis can be reproduced by adding the following to t8020:\n\n    test_expect_success 'Bloom filter with --show-trees' '\n        mkdir d &&\n\n        test_commit base-a d/a &&\n        test_commit base-b d/b &&\n        test_commit touch-a d/a &&\n        test_commit touch-b d/b &&\n\n        git commit-graph write --reachable --changed-paths &&\n        git -c core.commitGraph=false last-modified -t HEAD -- d/a \\\n            >expect &&\n        git -c core.commitGraph=true last-modified -t HEAD -- d/a \\\n            >actual &&\n\n        test_cmp expect actual\n    '\n\nWithout the graph, 'd' is attributed to 'touch-b' and 'd/a' to 'touch-a'.\nWith the graph, both are attributed to 'touch-a'. The filter for\n'touch-b' lacks 'd/a', so the new prefilter skips its diff even though 'd'\nchanged.\n\nI think that the conditional is otherwise correct, if guarded when we\nknow that 'lm->show_trees' is false, like so:\n\n    if (!lm->show_trees &&\n        !revs_maybe_changed_in_bloom(&lm->rev, filter))\n            return false;\n\nThe cover benchmark uses the same --show-trees plus narrow-pathspec\nshape, so I think its output should be checked before interpreting the\nspeedup.\n\nThanks,\nTaylor\n"},{"id":"548564","messageId":"alq4QN6CtQMz_pU8@com-79390","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-4-410418f18614@iotcl.com","subject":"Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Taylor Blau","fromEmail":"ttaylorr@openai.com","sentAt":"2026-07-17T23:18:24Z","receivedAt":"2026-07-17T23:18:28Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 05:47:02PM +0200, Toon Claes wrote:\n> Restore `bloom_filter_settings` after prepare_revision_walk() so the\n> per-path check keeps working for wildcard pathspecs.\n\nCould we add a test which actually exercises this?\n\nt8020 never writes a commit-graph with --changed-paths, so these new\nBloom paths remain dormant. The existing \"last-modified subdir with\nwildcard non-recursive\" case passes a/* unquoted, so the shell expands\nit into literal pathspecs before last-modified sees it.\n\nWriting a changed-path commit-graph and using a genuinely quoted\ntop-level wildcard, e.g.:\n\n    check_last_modified -r \"*\"\n\n, would cover the zero-prefix wildcard case here. -r is necessary\nsince the default max-depth rejects a true wildcard pathspec.\n\n(To be clear, I don't think that there is a correctness issue here,\nbut I do think we have a gap in test coverage in this patch.)\n\nThanks,\nTaylor\n\n"},{"id":"548565","messageId":"alq6E2oFH6JyYAay@com-79390","threadId":"66029","inReplyTo":"xmqqwlut1gzc.fsf@gitster.g","subject":"Re: [PATCH 2/4] revision: expose check for paths maybe changed in Bloom filter","fromName":"Taylor Blau","fromEmail":"ttaylorr@openai.com","sentAt":"2026-07-17T23:26:11Z","receivedAt":"2026-07-17T23:26:14Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 01:47:03PM -0700, Junio C Hamano wrote:\n> >  \tif (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)\n> >  \t\treturn -1;\n> >\n> >  \tfilter = get_bloom_filter(revs->repo, commit);\n> > -\n\n(This is an extreme nit-pick, but can we please try and avoid stray\nchanges like this? This one is not a huge deal, but it does make the\npatch more difficult to read than necessary.)\n\n> >  \tif (!filter) {\n> >  \t\tcount_bloom_filter_not_present++;\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> > -\t}\n> > +\tresult = revs_maybe_changed_in_bloom(revs, filter);\n> > +\tif (result < 0)\n> > +\t\treturn result;\n> >\n> >  \tif (result)\n> >  \t\tcount_bloom_filter_maybe++;\n>\n> Doesn't this change skew the stats?\n\nI believe so.\n\nI had the same thinking, which is that without any key vectors, there is\nno Bloom query to perform or account for, so that guard should stay\nahead of the generation and filter lookups.\n\n> It could be that these two are intended \"while at it we fix it too\"\n> improvements, but then they deserve to be mentioned in the proposed\n> log message.  Personally, I think the first one that increments the\n> _not_present statistics when keyvecs is empty a bug, though.\n\nIt seems separable. It may be worth fixing, but I would mention it\nexplicitly in the commit message.\n\nThanks,\nTaylor\n"},{"id":"548569","messageId":"20260718075700.GB22588@coredump.intra.peff.net","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-1-410418f18614@iotcl.com","subject":"Re: [PATCH 1/4] revision: move bloom keyvec precondition into function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-18T07:57:00Z","receivedAt":"2026-07-18T07:57:01Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 05:46:59PM +0200, Toon Claes wrote:\n\n> There are currently two callsites calling\n> check_maybe_different_in_bloom_filter(). They both check if\n> revs->bloom_keyvecs_nr is not zero before they call that function.\n> \n> Move bloom_keyvecs_nr precondition into\n> check_maybe_different_in_bloom_filter() to simplify the code.\n\nMakes sense, but...\n\n> Note that this changes `bloom_ret` to become -1 when there are no Bloom\n> key vectors, which results in `count_bloom_filter_false_positive` not\n> being incremented. This is unobservable, as the Bloom statistics are\n> only reported when key vectors were set up.\n\nThis \"-1\" return is kind of subtle. The function is really a tristate\nreturning one of:\n\n  0: no, it's definitely not in the filter\n  1: yes, it's (probably) in the filter\n  -1: we could not even check the filter\n\nBut nobody ever cares about the difference between \"1\" and \"-1\", because\nthe probabilistic data structure means \"we could not check\" must err on\nthe side of \"it might be in the filter\". But that leads to code like:\n\n  if (!bloom_ret)\n\nthat _looks_ wrong at first glance (as in \"oops, we are not catching -1\nand accidentally treating it the same as 1\"). But it's is actually\ncorrect for the reason above.\n\nThe \"return -1\" you are adding here is not the first (we'd do a similar\nthing if the commit was not found in the graph file). So it is not\nreally adding to the confusion.\n\nBut as we prepare to make this function public, should we consider\nchanging that tristate to a boolean, like:\n\n  false: no, the path is definitely not touched by this commit\n  true: the path could be touched by this commit\n\nIt's a minor point, but I think this makes the interface much more\nobvious.\n\n-Peff\n"},{"id":"548572","messageId":"20260718081407.GC22588@coredump.intra.peff.net","threadId":"66029","inReplyTo":"87a4rp1l65.fsf@emacs.iotcl.com","subject":"Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-18T08:14:07Z","receivedAt":"2026-07-18T08:14:08Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 09:16:34PM +0200, Toon Claes wrote:\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> \n> @Peff, as far I could tell:\n> \n> * This change was not needed to be able to use the Bloom filters with\n>   the pathspec.\n\nAh, right. In my earlier attempt I came at it from the bottom up: I\nfound the bloom_keyvec, saw how it was populated, and then worked my way\nback to prepare_to_use_bloom_filter() without going further.\n\nBut it is much nicer if we can rely on prepare_revision_walk() here, as\nwe don't need to make an additional function public.\n\n> * Only restoring bloom_filter_settings was needed. In your patch you're\n>   calling prepare_to_use_bloom_filter(), but that is being called by\n>   prepare_revision_walk(). Thus the restoring of the filter settings\n>   I've added after that function.\n\nHmm, OK. The \"clearing\" done by prepare_revision_walk() is kind of\nweird. The bloom settings are a const pointer, not a resource we own, so\nthere is really no need to clear them.\n\nBut accepting for a moment that we do clear them, is this maybe an\nindication that we are abusing rev_info.bloom_filter_settings? It is\nreally an internal implementation detail that revision.c uses for its\nown bloom filters. Wouldn't it be cleaner for last-modified to keep its\nown, like this:\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex fe012b0c2e..5e176bbeed 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -61,6 +61,8 @@ struct last_modified {\n \tsize_t all_paths_nr;\n \tstruct active_paths_for_commit active_paths;\n \n+\tstruct bloom_filter_settings *bloom_filter_settings;\n+\n \t/* 'scratch' to avoid allocating a bitmap every process_parent() */\n \tstruct bitmap *scratch;\n };\n@@ -114,9 +116,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@@ -262,7 +264,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@@ -277,7 +279,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@@ -502,7 +504,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\nIt's mostly academic, as both of the pointers (if not NULL) would always\npoint to the same setting that ultimately come from the repository\nobject. But it feels cleaner for them to keep their own pointers,\nbecause that pointer may also signal \"do we have usable bloom filters\".\nWe are a little lucky in dodging a bug here: last-modified uses the\npointer for that purpose, but if revision.c did so also, they'd\nconflict.\n\n  Side note: this is really a repository property, so it would be nice\n  if we could just do:\n\n    repo_bloom_filter_contains(filter, &ent->key);\n\n  without managing the settings pointer ourselves at all. But the cost\n  to fetch it from the graph linked list is not totally trivial, so we'd\n  probably end up having to cache it somewhere. I don't know if that's\n  worth it (plus last-modified would still have to keep a boolean\n  somewhere to decide whether it is using bloom filters or not).\n\n-Peff\n"},{"id":"548574","messageId":"20260718083757.GD22588@coredump.intra.peff.net","threadId":"66029","inReplyTo":"alq1Q55ezuN9ZI9j@com-79390","subject":"Re: [PATCH 3/4] last-modified: check pathspec against Bloom filter first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-18T08:37:57Z","receivedAt":"2026-07-18T08:37:58Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 06:05:39PM -0500, Taylor Blau wrote:\n\n> > diff --git a/builtin/last-modified.c b/builtin/last-modified.c\n> > index 5478182f2e..e8ee610404 100644\n> > --- a/builtin/last-modified.c\n> > +++ b/builtin/last-modified.c\n> > @@ -272,6 +272,9 @@ static bool maybe_changed_path(struct last_modified *lm,\n> >  \tif (!filter)\n> >  \t\treturn true;\n> >\n> > +\tif (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)\n> \n> Nit: please prefer 'if (!foo())' over 'if (foo() == 0)'.\n\nYeah, though there is some subtlety here because of the tristate return\nI described elsewhere in the thread. I think if we switch to a boolean\nreturn then a straight \"!\" becomes even more desirable.\n\n> I don't think this is safe with '--show-trees'. The original pathspec\n> does not cover every entry in 'lm->paths', since the function\n> 'populate_paths_from_revs()' also adds ancestor tree entries.\n\nHmm, interesting. I am surprised to learn that \"-t\" includes \"d\" when\nthe pathspec asked for \"d/a\". I thought it was mostly about showing\n\"d/a\" when we recurse to find \"d/a/b\". But I guess it does not make a\ndistinction between the two (probably because it is just telling the\ndiff code to show trees, and it does not further apply the pathspec to\nthe output).\n\nDoes this mean there is also a bug in \"git log\"? I guess not, because it\nis purely pruning based on the pathspec, and only shows \"d/\" for those\ncommits.\n\n>         git -c core.commitGraph=false last-modified -t HEAD -- d/a \\\n>             >expect &&\n>         git -c core.commitGraph=true last-modified -t HEAD -- d/a \\\n>             >actual &&\n\nA minor side note: the documentation claims \"-t\" has no effect without\n\"-r\", but it clearly is not true (it tells us to show \"d\", even when we\nare not recursing).\n\n> I think that the conditional is otherwise correct, if guarded when we\n> know that 'lm->show_trees' is false, like so:\n> \n>     if (!lm->show_trees &&\n>         !revs_maybe_changed_in_bloom(&lm->rev, filter))\n>             return false;\n\nHmph. That makes this optimization all but useless, because the intended\nuse case of last-modified is almost always going to use \"-t\" to be able\nto mark the interior trees. And most callers are not going to care about\nseeing \"d\" here; their purpose was to find out about the things _inside_\n\"d\".\n\nWould we consider removing \"d\" from the output for this case? Presumably\nby double-checking the pathspecs again in add_path_from_diff(). That\ngives less surprising output (to me, anyway) and would enable this\noptimization. And the command is still marked as experimental, and I\nthink this is exactly the kind of corner case that is meant to cover.\n\n-Peff\n"},{"id":"548597","messageId":"alvulw2fk67duo8n@com-79390","threadId":"66029","inReplyTo":"20260718083757.GD22588@coredump.intra.peff.net","subject":"Re: [PATCH 3/4] last-modified: check pathspec against Bloom filter first","fromName":"Taylor Blau","fromEmail":"ttaylorr@openai.com","sentAt":"2026-07-18T21:22:31Z","receivedAt":"2026-07-18T21:22:36Z","isPatch":true,"body":"On Sat, Jul 18, 2026 at 04:37:57AM -0400, Jeff King wrote:\n> > I don't think this is safe with '--show-trees'. The original pathspec\n> > does not cover every entry in 'lm->paths', since the function\n> > 'populate_paths_from_revs()' also adds ancestor tree entries.\n>\n> Hmm, interesting. I am surprised to learn that \"-t\" includes \"d\" when\n> the pathspec asked for \"d/a\". I thought it was mostly about showing\n> \"d/a\" when we recurse to find \"d/a/b\". But I guess it does not make a\n> distinction between the two (probably because it is just telling the\n> diff code to show trees, and it does not further apply the pathspec to\n> the output).\n>\n> Does this mean there is also a bug in \"git log\"? I guess not, because it\n> is purely pruning based on the pathspec, and only shows \"d/\" for those\n> commits.\n\nRight.\n\n> > I think that the conditional is otherwise correct, if guarded when we\n> > know that 'lm->show_trees' is false, like so:\n> >\n> >     if (!lm->show_trees &&\n> >         !revs_maybe_changed_in_bloom(&lm->rev, filter))\n> >             return false;\n>\n> Hmph. That makes this optimization all but useless, because the intended\n> use case of last-modified is almost always going to use \"-t\" to be able\n> to mark the interior trees. And most callers are not going to care about\n> seeing \"d\" here; their purpose was to find out about the things _inside_\n> \"d\".\n>\n> Would we consider removing \"d\" from the output for this case? Presumably\n> by double-checking the pathspecs again in add_path_from_diff(). That\n> gives less surprising output (to me, anyway) and would enable this\n> optimization. And the command is still marked as experimental, and I\n> think this is exactly the kind of corner case that is meant to cover.\n\nI think that we could feasibly get rid of \"d\" in the output in this\nparticular case within last-modified. As you note, the command is marked\nEXPERIMENTAL for a reason, after all ;-).\n\nIf we wanted to do that, it should be straightforward to do. I think the\nfollowing (untested) patch would be sufficient:\n\n--- 8< ---\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex adc7cd8c74..0f0c1d1d17 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -103,7 +103,7 @@ struct last_modified_callback_data {\n };\n\n static void add_path_from_diff(struct diff_queue_struct *q,\n-\t\t\t       struct diff_options *opt UNUSED, void *data)\n+\t\t\t       struct diff_options *opt, void *data)\n {\n \tstruct last_modified *lm = data;\n\n@@ -112,6 +112,11 @@ static void add_path_from_diff(struct diff_queue_struct *q,\n \t\tstruct last_modified_entry *ent;\n \t\tconst char *path = p->two->path;\n\n+\t\tif (!match_pathspec(opt->repo->index, &opt->pathspec, path,\n+\t\t\t\t    strlen(path), 0, NULL,\n+\t\t\t\t    S_ISDIR(p->two->mode)))\n+\t\t\tcontinue;\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--- >8 ---\n\nIf, on the other hand, we wanted to retain \"d\" in the output (which I am\ninclined to suggest is a bad idea), we could keep a list of paths which\nare not covered by the given pathspec.\n\nIf you had such a list, you could check only active entries within that\nlist, removing them as they are resolved. That makes a Bloom query miss\nO(U*H) (where U is the uncovered subset of all paths, and H is the\nnumber of hash functions in our Bloom key, which in our case is 7) as\nopposed to O(P*H), where P is the number of active paths.\n\nOf course, as U approaches P, the advantage disappears and so too do\nthe benefits of Toon's optimization.\n\nIf you wanted to go that route, you could do something like the\nfollowing (lightly tested):\n\n--- 8< ---\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex adc7cd8c74..e69c7a44b6 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -11,6 +11,7 @@\n #include \"ewah/ewok.h\"\n #include \"hashmap.h\"\n #include \"hex.h\"\n+#include \"list.h\"\n #include \"object-name.h\"\n #include \"object.h\"\n #include \"parse-options.h\"\n@@ -25,9 +26,11 @@\n\n struct last_modified_entry {\n \tstruct hashmap_entry hashent;\n+\tstruct list_head uncovered;\n \tstruct object_id oid;\n \tstruct bloom_key key;\n \tsize_t diff_idx;\n+\tbool covered_by_pathspec;\n \tconst char path[FLEX_ARRAY];\n };\n\n@@ -52,6 +55,7 @@ define_commit_slab(active_paths_for_commit, struct bitmap *);\n\n struct last_modified {\n \tstruct hashmap paths;\n+\tstruct list_head uncovered_paths;\n \tstruct rev_info rev;\n \tbool show_trees;\n \tbool nul_termination;\n@@ -103,7 +107,7 @@ struct last_modified_callback_data {\n };\n\n static void add_path_from_diff(struct diff_queue_struct *q,\n-\t\t\t       struct diff_options *opt UNUSED, void *data)\n+\t\t\t       struct diff_options *opt, void *data)\n {\n \tstruct last_modified *lm = data;\n\n@@ -114,6 +118,16 @@ 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+\n+\t\tif (match_pathspec(opt->repo->index, &opt->pathspec, path,\n+\t\t\t\t   strlen(path), 0, NULL,\n+\t\t\t\t   S_ISDIR(p->two->mode))) {\n+\t\t\tent->covered_by_pathspec = true;\n+\t\t} else {\n+\t\t\tlist_add_tail(&ent->uncovered, &lm->uncovered_paths);\n+\t\t\tent->covered_by_pathspec = false;\n+\t\t}\n+\n \t\tif (lm->rev.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@@ -202,6 +216,8 @@ static void mark_path(const char *path, const struct object_id *oid,\n \tlast_modified_emit(data->lm, path, data->commit);\n\n \thashmap_remove(&data->lm->paths, &ent->hashent, path);\n+\tif (!ent->covered_by_pathspec)\n+\t\tlist_del(&ent->uncovered);\n \tbloom_key_clear(&ent->key);\n \tfree(ent);\n }\n@@ -272,8 +288,22 @@ static bool maybe_changed_path(struct last_modified *lm,\n \tif (!filter)\n \t\treturn true;\n\n-\tif (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)\n+\tif (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0) {\n+\t\tstruct list_head *pos;\n+\n+\t\tlist_for_each(pos, &lm->uncovered_paths) {\n+\t\t\tent = list_entry(pos, struct last_modified_entry,\n+\t\t\t\t\t uncovered);\n+\t\t\tif (active && !bitmap_get(active, ent->diff_idx))\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (bloom_filter_contains(filter, &ent->key,\n+\t\t\t\t\t\t  lm->rev.bloom_filter_settings))\n+\t\t\t\treturn true;\n+\t\t}\n+\n \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@@ -490,6 +520,7 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,\n \tstruct last_modified_entry *ent;\n\n \thashmap_init(&lm->paths, last_modified_entry_hashcmp, NULL, 0);\n+\tINIT_LIST_HEAD(&lm->uncovered_paths);\n\n \trepo_init_revisions(r, &lm->rev, prefix);\n \tlm->rev.def = \"HEAD\";\n--- >8 ---\n\nOn my machine, in a synthetic repository containing 10,000 commits with\n5,001 covered paths and 1 uncovered path, Toon's original patch runs in\n~450ms. With the above patch, the timing drops to ~227ms, whereas it\ndrops further to ~190ms when omitting the uncovered path entirely.\n\nSo I'm inclined to suggest that we take advantage of the command's\nEXPERIMENTAL nature and avoid printing the uncovered path entirely.\n\nThanks,\nTaylor\n"},{"id":"548664","messageId":"20260720094218.GA681989@coredump.intra.peff.net","threadId":"66029","inReplyTo":"alvulw2fk67duo8n@com-79390","subject":"Re: [PATCH 3/4] last-modified: check pathspec against Bloom filter first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-20T09:42:18Z","receivedAt":"2026-07-20T09:42:27Z","isPatch":true,"body":"On Sat, Jul 18, 2026 at 04:22:31PM -0500, Taylor Blau wrote:\n\n> I think that we could feasibly get rid of \"d\" in the output in this\n> particular case within last-modified. As you note, the command is marked\n> EXPERIMENTAL for a reason, after all ;-).\n> \n> If we wanted to do that, it should be straightforward to do. I think the\n> following (untested) patch would be sufficient:\n> \n> --- 8< ---\n> diff --git a/builtin/last-modified.c b/builtin/last-modified.c\n> index adc7cd8c74..0f0c1d1d17 100644\n> --- a/builtin/last-modified.c\n> +++ b/builtin/last-modified.c\n> @@ -103,7 +103,7 @@ struct last_modified_callback_data {\n>  };\n> \n>  static void add_path_from_diff(struct diff_queue_struct *q,\n> -\t\t\t       struct diff_options *opt UNUSED, void *data)\n> +\t\t\t       struct diff_options *opt, void *data)\n>  {\n>  \tstruct last_modified *lm = data;\n> \n> @@ -112,6 +112,11 @@ static void add_path_from_diff(struct diff_queue_struct *q,\n>  \t\tstruct last_modified_entry *ent;\n>  \t\tconst char *path = p->two->path;\n> \n> +\t\tif (!match_pathspec(opt->repo->index, &opt->pathspec, path,\n> +\t\t\t\t    strlen(path), 0, NULL,\n> +\t\t\t\t    S_ISDIR(p->two->mode)))\n> +\t\t\tcontinue;\n> +\n\nYeah, that was exactly what I was thinking, but I wasn't sure if\nmatch_pathspec() was the right tool. I mean, obviously it sounds like it\nshould be from the name, but I don't think it is actually what is used\nin tree-diffs! There we have tree-walk.c:do_match() which does some\nmagic. And match_pathspec() is used more for dir.c callers.\n\nI guess the two are supposed to be equivalent, or else we'd have weird\ndiscrepancies between commands. So maybe just a weird existing oddity\nthat we don't need to worry about here.\n\nThere is one other interesting corner case here. If I do this in\ngit.git, for example:\n\n  git last-modified -t Documentation/technical/\n\nit shows an entry for Documentation/, which we both find weird. And the\npatch above would remove that. But it also shows an entry for\nDocumentation/technical/, which _is_ within the pathspec and would still\nbe shown after the patch above. That's OK for the optimization we're\ntalking about (it would be part of the filter key), but I do find it\nstill a little funny. The invocation above, at least as we used to use\nit as blame-tree at GitHub, is really about asking for the entries\ninside that directory, not the directory itself.\n\nPerhaps not worth worrying too much about, though. The caller can easily\nignore the extra entry.\n\n> If, on the other hand, we wanted to retain \"d\" in the output (which I am\n> inclined to suggest is a bad idea), we could keep a list of paths which\n> are not covered by the given pathspec.\n\nYeah, your analysis here makes sense, but I agree that it is not worth\nretaining \"d\". Besides reducing our ability to optimize, it is IMHO just\nplain confusing to have in the output.\n\n-Peff\n"},{"id":"549629","messageId":"xmqqzez1sf3m.fsf@gitster.g","threadId":"66029","inReplyTo":"20260718081407.GC22588@coredump.intra.peff.net","subject":"Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-08-04T22:19:57Z","receivedAt":"2026-08-04T22:20:01Z","isPatch":true,"body":"Jeff King <peff@peff.net> writes:\n\n> On Fri, Jul 17, 2026 at 09:16:34PM +0200, Toon Claes wrote:\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>> \n>> @Peff, as far I could tell:\n>> \n>> * This change was not needed to be able to use the Bloom filters with\n>>   the pathspec.\n>\n> Ah, right. In my earlier attempt I came at it from the bottom up: I\n> found the bloom_keyvec, saw how it was populated, and then worked my way\n> back to prepare_to_use_bloom_filter() without going further.\n>\n> But it is much nicer if we can rely on prepare_revision_walk() here, as\n> we don't need to make an additional function public.\n> ...\n> It's mostly academic, as both of the pointers (if not NULL) would always\n> point to the same setting that ultimately come from the repository\n> object. But it feels cleaner for them to keep their own pointers,\n> because that pointer may also signal \"do we have usable bloom filters\".\n> We are a little lucky in dodging a bug here: last-modified uses the\n> pointer for that purpose, but if revision.c did so also, they'd\n> conflict.\n>\n>   Side note: this is really a repository property, so it would be nice\n>   if we could just do:\n>\n>     repo_bloom_filter_contains(filter, &ent->key);\n>\n>   without managing the settings pointer ourselves at all. But the cost\n>   to fetch it from the graph linked list is not totally trivial, so we'd\n>   probably end up having to cache it somewhere. I don't know if that's\n>   worth it (plus last-modified would still have to keep a boolean\n>   somewhere to decide whether it is using bloom filters or not).\n\nSo what happened to this discussion?  Are we happy with the set of\npatches in v1 after all, or are we still thinking it over?\n\nThanks.\n"},{"id":"549631","messageId":"anKHP7G1uE78e2x0@com-79390","threadId":"66029","inReplyTo":"xmqqzez1sf3m.fsf@gitster.g","subject":"Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Taylor Blau","fromEmail":"ttaylorr@openai.com","sentAt":"2026-08-05T00:43:43Z","receivedAt":"2026-08-05T00:43:53Z","isPatch":true,"body":"On Tue, Aug 04, 2026 at 03:19:57PM -0700, Junio C Hamano wrote:\n> So what happened to this discussion?  Are we happy with the set of\n> patches in v1 after all, or are we still thinking it over?\n\nI don't have a strong sense of this particular discussion, since this\nsub-thread involves only Peff and Toon. But in general, I think that my\ncomment[1] here needs to be resolved before we start merging this down.\n\nThanks,\nTaylor\n\n[1]: https://lore.kernel.org/git/alq1Q55ezuN9ZI9j@com-79390/\n"},{"id":"549632","messageId":"20260805011835.GA954960@coredump.intra.peff.net","threadId":"66029","inReplyTo":"xmqqzez1sf3m.fsf@gitster.g","subject":"Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-08-05T01:18:35Z","receivedAt":"2026-08-05T01:25:19Z","isPatch":true,"body":"On Tue, Aug 04, 2026 at 03:19:57PM -0700, Junio C Hamano wrote:\n\n> > It's mostly academic, as both of the pointers (if not NULL) would always\n> > point to the same setting that ultimately come from the repository\n> > object. But it feels cleaner for them to keep their own pointers,\n> > because that pointer may also signal \"do we have usable bloom filters\".\n> > We are a little lucky in dodging a bug here: last-modified uses the\n> > pointer for that purpose, but if revision.c did so also, they'd\n> > conflict.\n> >\n> >   Side note: this is really a repository property, so it would be nice\n> >   if we could just do:\n> >\n> >     repo_bloom_filter_contains(filter, &ent->key);\n> >\n> >   without managing the settings pointer ourselves at all. But the cost\n> >   to fetch it from the graph linked list is not totally trivial, so we'd\n> >   probably end up having to cache it somewhere. I don't know if that's\n> >   worth it (plus last-modified would still have to keep a boolean\n> >   somewhere to decide whether it is using bloom filters or not).\n> \n> So what happened to this discussion?  Are we happy with the set of\n> patches in v1 after all, or are we still thinking it over?\n\nThe bit quoted above is mostly quibbling about some refactoring, and I'd\nbe OK with or without my suggestion. But the \"--show-trees\" issue that\nTaylor raised should be dealt with before moving the topic forward. I\nthink the next step is probably a re-roll from Toon with a preparatory\npatch cleaning up the --show-trees output.\n\n-Peff\n"},{"id":"549728","messageId":"xmqqqzkcsgjd.fsf@gitster.g","threadId":"66029","inReplyTo":"anKHP7G1uE78e2x0@com-79390","subject":"Re: [PATCH 4/4] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-08-05T16:01:10Z","receivedAt":"2026-08-05T16:01:16Z","isPatch":true,"body":"Taylor Blau <ttaylorr@openai.com> writes:\n\n> On Tue, Aug 04, 2026 at 03:19:57PM -0700, Junio C Hamano wrote:\n>> So what happened to this discussion?  Are we happy with the set of\n>> patches in v1 after all, or are we still thinking it over?\n>\n> I don't have a strong sense of this particular discussion, since this\n> sub-thread involves only Peff and Toon. But in general, I think that my\n> comment[1] here needs to be resolved before we start merging this down.\n>\n> Thanks,\n> Taylor\n>\n> [1]: https://lore.kernel.org/git/alq1Q55ezuN9ZI9j@com-79390/\n\nThanks.  Yes, the --show-trees issue looks a lot more relevant.\n\n"},{"id":"549769","messageId":"87wlu44bv3.fsf@emacs.iotcl.com","threadId":"66029","inReplyTo":"20260718075700.GB22588@coredump.intra.peff.net","subject":"Re: [PATCH 1/4] revision: move bloom keyvec precondition into function","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-05T19:16:00Z","receivedAt":"2026-08-05T19:16:18Z","isPatch":true,"body":"Jeff King <peff@peff.net> writes:\n\n> On Fri, Jul 17, 2026 at 05:46:59PM +0200, Toon Claes wrote:\n>\n>> There are currently two callsites calling\n>> check_maybe_different_in_bloom_filter(). They both check if\n>> revs->bloom_keyvecs_nr is not zero before they call that function.\n>> \n>> Move bloom_keyvecs_nr precondition into\n>> check_maybe_different_in_bloom_filter() to simplify the code.\n>\n> Makes sense, but...\n>\n>> Note that this changes `bloom_ret` to become -1 when there are no Bloom\n>> key vectors, which results in `count_bloom_filter_false_positive` not\n>> being incremented. This is unobservable, as the Bloom statistics are\n>> only reported when key vectors were set up.\n>\n> This \"-1\" return is kind of subtle. The function is really a tristate\n> returning one of:\n>\n>   0: no, it's definitely not in the filter\n>   1: yes, it's (probably) in the filter\n>   -1: we could not even check the filter\n>\n> But nobody ever cares about the difference between \"1\" and \"-1\", because\n> the probabilistic data structure means \"we could not check\" must err on\n> the side of \"it might be in the filter\".\n\nThat's not entirely true. The `count_bloom_filter_false_positive`\ndepends on knowing whether the filter said \"maybe\" or if no filter was\nused at all.\n\n> But that leads to code like:\n>\n>   if (!bloom_ret)\n>\n> that _looks_ wrong at first glance (as in \"oops, we are not catching -1\n> and accidentally treating it the same as 1\"). But it's is actually\n> correct for the reason above.\n>\n> The \"return -1\" you are adding here is not the first (we'd do a similar\n> thing if the commit was not found in the graph file). So it is not\n> really adding to the confusion.\n>\n> But as we prepare to make this function public, should we consider\n> changing that tristate to a boolean, like:\n>\n>   false: no, the path is definitely not touched by this commit\n>   true: the path could be touched by this commit\n>\n> It's a minor point, but I think this makes the interface much more\n> obvious.\n\nThat said, the public function might have a boolean interface, while\nthe private wrapper still uses the tristate. I'll address in the next\nversion.\n\n\n-- \nCheers,\nToon\n"},{"id":"549777","messageId":"20260805203255.GA1010713@coredump.intra.peff.net","threadId":"66029","inReplyTo":"87wlu44bv3.fsf@emacs.iotcl.com","subject":"Re: [PATCH 1/4] revision: move bloom keyvec precondition into function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-08-05T20:32:55Z","receivedAt":"2026-08-05T20:32:58Z","isPatch":true,"body":"On Wed, Aug 05, 2026 at 09:16:00PM +0200, Toon Claes wrote:\n\n> > But nobody ever cares about the difference between \"1\" and \"-1\", because\n> > the probabilistic data structure means \"we could not check\" must err on\n> > the side of \"it might be in the filter\".\n> \n> That's not entirely true. The `count_bloom_filter_false_positive`\n> depends on knowing whether the filter said \"maybe\" or if no filter was\n> used at all.\n\nAh, yeah, you're right. I saw the \"== 0\" comparison there, but didn't\nnotice that we later checked it against \"== 1\".\n\n> That said, the public function might have a boolean interface, while\n> the private wrapper still uses the tristate. I'll address in the next\n> version.\n\nYeah, I'd be OK with that. Or leaving it as-is, given that there is a\ncaller who cares. It might be less subtle if we used symbolic constants,\nbut that could be done separately (later or never if nobody cares\nenough).\n\n-Peff\n"},{"id":"550038","messageId":"20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com","threadId":"66029","inReplyTo":"20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com","subject":"[PATCH v2 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-07T18:26:46Z","receivedAt":"2026-08-07T18:27:15Z","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 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  | 20 +++++++++++++++++++\n revision.c               | 52 +++++++++++++++++++++++++++++++++++++-----------\n revision.h               | 20 +++++++++++++++++++\n t/t8020-last-modified.sh | 21 +++++++++++++++++++\n 6 files changed, 124 insertions(+), 12 deletions(-)\n\nRange-diff versus v1:\n\n1:  dd152b3fd5 = 1:  961bf0c547 revision: move bloom keyvec precondition into function\n2:  0e80ca2500 ! 2:  8d8eaea04f revision: expose check for paths maybe changed in Bloom filter\n    @@ Commit message\n         Expose the new function via revision.h so other builtins can reuse the\n         exact same filtering that `git log <pathspec>` performs.\n     \n    +    The existing function check_maybe_different_in_bloom_filter() returns a\n    +    tristate 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    +\n    +    These return values are used to keep count of false-positives. But\n    +    because the new function revs_maybe_changed_in_bloom() is not involved\n    +    in counting statistics, it returns a boolean value telling whether the\n    +    commit definitely did not change any of the paths, or maybe changed some\n    +    of them.\n    +\n         Signed-off-by: Toon Claes <toon@iotcl.com>\n     \n      ## revision.c ##\n    @@ revision.c: static int check_maybe_different_in_bloom_filter(struct rev_info *re\n      {\n      \tstruct bloom_filter *filter;\n     -\tint result = 0;\n    --\n    --\tif (!revs->bloom_keyvecs_nr)\n    --\t\treturn -1;\n    -+\tint result;\n      \n    - \tif (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)\n    + \tif (!revs->bloom_keyvecs_nr)\n      \t\treturn -1;\n    - \n    - \tfilter = get_bloom_filter(revs->repo, commit);\n    --\n    - \tif (!filter) {\n    - \t\tcount_bloom_filter_not_present++;\n    +@@ revision.c: static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n      \t\treturn -1;\n      \t}\n      \n    @@ revision.c: static int check_maybe_different_in_bloom_filter(struct rev_info *re\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    --\t}\n    -+\tresult = revs_maybe_changed_in_bloom(revs, filter);\n    -+\tif (result < 0)\n    -+\t\treturn result;\n    - \n    - \tif (result)\n    - \t\tcount_bloom_filter_maybe++;\n    -@@ revision.c: static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n    - \treturn result;\n    - }\n    ++\tif (revs_maybe_changed_in_bloom(revs, filter)) {\n    ++\t\tcount_bloom_filter_maybe++;\n    ++\t\treturn 1;\n    + \t}\n      \n    -+int revs_maybe_changed_in_bloom(struct rev_info *revs,\n    -+\t\t\t\tstruct bloom_filter *filter)\n    -+{\n    -+\tint result = 0;\n    -+\n    -+\tif (!revs->bloom_keyvecs_nr)\n    -+\t\treturn -1;\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    -+\t}\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 result;\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,\n    - \t\t\t    struct commit *parent, struct commit *commit, int nth_parent)\n    - {\n     \n      ## revision.h ##\n     @@ revision.h: struct string_list;\n    @@ revision.h: void reset_revision_walk(void);\n      int prepare_revision_walk(struct rev_info *revs);\n      \n     +/**\n    -+ * Take in a changed-path Bloom filter that belongs to a commit, and consult it\n    -+ * to see if it might have modified any of the paths in the `revs`.\n    -+ * The caller should look up `filter`, probably with get_bloom_filter().\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 -1 if no sensible answer could be given because of missing\n    -+ * preconditions (no pathspec key vectors).\n    -+ * Returns 0 if the commit definitely did not change any of the paths and 1 if\n    -+ * the commit maybe has changed one of them, although that might be a\n    -+ * false-positive.\n    ++ * Returns false iff the commit definitely did not change any of the paths.\n     + */\n    -+int revs_maybe_changed_in_bloom(struct rev_info *revs,\n    -+\t\t\t\tstruct bloom_filter *filter);\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-:  ---------- > 3:  a2d2c47cd5 bloom: add helper to check if any key in a vector is present\n-:  ---------- > 4:  b33ef3dfd1 revision: add Bloom check that includes parent directories\n3:  378403d38d ! 5:  f1f194d66d last-modified: check pathspec against Bloom filter first\n    @@ Commit message\n         pre-filter, paths are still checked one-by-one to only find those which\n         don't have a \"last commit\" yet.\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    +\n         Signed-off-by: Toon Claes <toon@iotcl.com>\n     \n      ## builtin/last-modified.c ##\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n      \tif (!filter)\n      \t\treturn true;\n      \n    -+\tif (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)\n    -+\t\treturn false;\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;\n    +\n    + ## t/t8020-last-modified.sh ##\n    +@@ t/t8020-last-modified.sh: 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\n4:  24884916d4 = 6:  f313142134 last-modified: keep per-path Bloom filters for wildcard pathspecs\n\n\n---\nbase-commit: 2c78326f810173a4f3aefd8021f1e07575412481\nchange-id: 20260716-toon-speed-up-last-modified-b04ea1f21831\n\n"},{"id":"550039","messageId":"20260807-toon-speed-up-last-modified-v2-1-7d87bbdeaf9b@iotcl.com","threadId":"66029","inReplyTo":"20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com","subject":"[PATCH v2 1/6] revision: move bloom keyvec precondition into function","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-07T18:26:47Z","receivedAt":"2026-08-07T18:27:18Z","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 <toon@iotcl.com>\n---\n revision.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 526bcf3fb5..5b53902c05 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":"550040","messageId":"20260807-toon-speed-up-last-modified-v2-2-7d87bbdeaf9b@iotcl.com","threadId":"66029","inReplyTo":"20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com","subject":"[PATCH v2 2/6] revision: expose check for paths maybe changed in Bloom filter","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-07T18:26:48Z","receivedAt":"2026-08-07T18:27:24Z","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 <pathspec>` 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 <toon@iotcl.com>\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 5b53902c05..78dcb40d9f 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":"550041","messageId":"20260807-toon-speed-up-last-modified-v2-3-7d87bbdeaf9b@iotcl.com","threadId":"66029","inReplyTo":"20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com","subject":"[PATCH v2 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-07T18:26:49Z","receivedAt":"2026-08-07T18:27:27Z","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 <toon@iotcl.com>\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":"550042","messageId":"20260807-toon-speed-up-last-modified-v2-4-7d87bbdeaf9b@iotcl.com","threadId":"66029","inReplyTo":"20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com","subject":"[PATCH v2 4/6] revision: add Bloom check that includes parent directories","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-07T18:26:50Z","receivedAt":"2026-08-07T18:27:31Z","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 <toon@iotcl.com>\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 78dcb40d9f..3195c0cab1 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":"550043","messageId":"20260807-toon-speed-up-last-modified-v2-5-7d87bbdeaf9b@iotcl.com","threadId":"66029","inReplyTo":"20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com","subject":"[PATCH v2 5/6] last-modified: check pathspec against Bloom filter first","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-07T18:26:51Z","receivedAt":"2026-08-07T18:27:34Z","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 <toon@iotcl.com>\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 5478182f2e..5678731a04 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":"550044","messageId":"20260807-toon-speed-up-last-modified-v2-6-7d87bbdeaf9b@iotcl.com","threadId":"66029","inReplyTo":"20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com","subject":"[PATCH v2 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2026-08-07T18:26:52Z","receivedAt":"2026-08-07T18:27:36Z","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\nSigned-off-by: Toon Claes <toon@iotcl.com>\n---\n builtin/last-modified.c | 8 ++++++++\n 1 file changed, 8 insertions(+)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 5678731a04..35d9dccd9b 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -369,6 +369,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\n-- \n2.55.0.679.g6767b8d81c\n\n"},{"id":"550102","messageId":"xmqqtsp4a6c2.fsf@gitster.g","threadId":"66029","inReplyTo":"20260807-toon-speed-up-last-modified-v2-6-7d87bbdeaf9b@iotcl.com","subject":"Re: [PATCH v2 6/6] last-modified: keep per-path Bloom filters for wildcard pathspecs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-08-08T17:07:57Z","receivedAt":"2026-08-08T17:08:01Z","isPatch":true,"body":"Toon Claes <toon@iotcl.com> writes:\n\n> The last-modified builtin expands the pathspec to a set of literal paths\n> and builds a Bloom key for each. During the walk it looks those keys up\n> in the commit's filter to decide whether the commit is worth diffing.\n> These lookups need `bloom_filter_settings` for the key hashing.\n>\n> prepare_revision_walk() runs prepare_to_use_bloom_filter() to build the\n> pathspec key vectors. For a pathspec that cannot be turned into a Bloom\n> key, such as a top-level wildcard like \"*.c\", that function gives up and\n> clears `bloom_filter_settings`.\n>\n> Restore `bloom_filter_settings` after prepare_revision_walk() so the\n> per-path check keeps working for wildcard pathspecs.\n\nShould a new test or two cover a case where a pathspec with a\ntop-level wildcard is supplied, and ensure that this restoration\nkicks in?\n\nThe machinery should work correctly with or without Bloom filters.\nWithout trace instrumentation, such a test might not exhibit any\nbehavior difference even when the filter is not restored.\nHowever, the failure scenario is specific enough to make a good\ntest case.\n\nThanks.\n"}]}