[PATCH v3 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits
From: Toon Claes <hidden>
Date: 2026-08-31 15:19:11
We have received a report[1] git-last-modified(1) is slow compared to
git-log(1) if you want to find the last commit for all entries in a
directory. For example running the following command on ziglang/zig[2]:
$ git last-modified -t --max-depth=0 $OID -- doc/langref/
Turns out to find results about 2.5 times slower than:
$ git log --name-status -c --format=commit%x00%H %P%x00" \
--parents --no-renames -t -z $OID -- :(literal)doc/langref
Now the latter needs some post-processing to come to the same results,
the total solution still is faster than integrating
git-last-modified(1).
After some research we've discovered the Bloom filters aren't used
optimally. But it turns out the code powering git-log(1) can fairly easy
be reused. We do this in a few steps:
- Patch 1 & 2 prepare revision.[ch] to expose the helper to check if
revs maybe changes in Bloom filter.
- Patch 3 & 4 prepare a similar helper, but this one is needed when
git-last-modified(1) is called with `--show-trees`.
- Patch 5 uses these helpers in git-last-modified(1).
- Patch 6 is a bonus change, which optimizes when working with wildcard
pathspecs.
Below are benchmarks on the ziglang/zig repository for the
`doc/langref/` directory (with commit-graphs written using
`--changed-paths`):
Benchmark 1: master: last-modified -z -t
Time (mean ± σ): 61.9 ms ± 1.8 ms [User: 57.1 ms, System: 4.0 ms]
Range (min … max): 58.5 ms … 68.9 ms 150 runs
Benchmark 2: HEAD: last-modified -z -t
Time (mean ± σ): 31.8 ms ± 1.3 ms [User: 27.1 ms, System: 4.2 ms]
Range (min … max): 29.7 ms … 35.6 ms 150 runs
Benchmark 3: git log -t
Time (mean ± σ): 22.1 ms ± 1.2 ms [User: 16.7 ms, System: 5.0 ms]
Range (min … max): 20.1 ms … 26.6 ms 150 runs
Summary
git log -t ran
1.44 ± 0.10 times faster than HEAD: last-modified -z -t
2.80 ± 0.18 times faster than master: last-modified -z -t
Comparing HEAD to master, there is about 1.95x speedup on running `git
last-modified -z -t. `git log -t` is still slightly faster though.
But without `-t` the speedup is even bigger:
Benchmark 1: master: last-modified -z
Time (mean ± σ): 60.7 ms ± 4.5 ms [User: 56.5 ms, System: 3.8 ms]
Range (min … max): 57.5 ms … 96.2 ms 150 runs
Benchmark 2: HEAD: last-modified -z
Time (mean ± σ): 16.2 ms ± 1.4 ms [User: 13.3 ms, System: 2.7 ms]
Range (min … max): 13.9 ms … 20.4 ms 212 runs
Benchmark 3: git log (no -t)
Time (mean ± σ): 22.0 ms ± 3.7 ms [User: 16.8 ms, System: 4.9 ms]
Range (min … max): 18.7 ms … 37.6 ms 150 runs
Summary
HEAD: last-modified -z ran
1.35 ± 0.25 times faster than git log (no -t)
3.74 ± 0.42 times faster than master: last-modified -z
This makes sense because without `-t` we can use the Bloom filter more
optimally.
Similar timings are seen across a few other repositories (like GitLab's
monolith gitlab-org/gitlab).
[1]: https://lore.kernel.org/git/17f356ff-7bfb-47f5-b714-62a95cc8b821@codeberg.org/ (local)
[2]: https://codeberg.org/ziglang/zig
---
Changes in v3:
- Add trace2 "bloom_queries" and use it in test to verify top-level
wildcard behavior.
- Link to v2: https://patch.msgid.link/20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com
Changes in v2:
- Make the public helper revs_maybe_changed_in_bloom() return a bool
instead of a tristate.
- Keep the bloom_keyvecs_nr precondition before get_bloom_filter() and
return early from the key vector loop.
- Add commits 3 & 4 to add helper used with `--show-trees`.
- Use Bloom filter correctly with `--show-trees` and add test to prove.
- Rerun benchmarks to compare results with and without `--show-trees`.
- Link to v1: https://patch.msgid.link/20260717-toon-speed-up-last-modified-v1-0-410418f18614@iotcl.com
---
Toon Claes (6):
revision: move bloom keyvec precondition into function
revision: expose check for paths maybe changed in Bloom filter
bloom: add helper to check if any key in a vector is present
revision: add Bloom check that includes parent directories
last-modified: check pathspec against Bloom filter first
last-modified: keep per-path Bloom filters for wildcard pathspecs
bloom.c | 12 +++++++++++
bloom.h | 11 ++++++++++
builtin/last-modified.c | 28 ++++++++++++++++++++++++++
revision.c | 52 +++++++++++++++++++++++++++++++++++++-----------
revision.h | 20 +++++++++++++++++++
t/t8020-last-modified.sh | 47 +++++++++++++++++++++++++++++++++++++++++++
6 files changed, 158 insertions(+), 12 deletions(-)
Range-diff versus v2:
1: a98bbaad50 = 1: ac58e4a3cd revision: move bloom keyvec precondition into function
2: ebf4f65fab = 2: 43375b505e revision: expose check for paths maybe changed in Bloom filter
3: 7a3c14fe87 = 3: 41e3a19fde bloom: add helper to check if any key in a vector is present
4: 145c95a2fa = 4: a648612927 revision: add Bloom check that includes parent directories
5: 9dc5a0be79 = 5: 0e8721fe75 last-modified: check pathspec against Bloom filter first
6: 83036c2fe4 ! 6: e7997e0a9b last-modified: keep per-path Bloom filters for wildcard pathspecs
@@ Commit message
Restore `bloom_filter_settings` after prepare_revision_walk() so the
per-path check keeps working for wildcard pathspecs.
+ This change isn't having any effect on the output, but only has an
+ impact on performance. Add a "bloom_queries" trace2 counter that records
+ how often the per-path Bloom check runs, and a test that asserts the
+ count increments as appropriate for a top-level wildcard pathspec.
+
Signed-off-by: Toon Claes [off-list ref]
## builtin/last-modified.c ##
+@@
+ #include "quote.h"
+ #include "repository.h"
+ #include "revision.h"
++#include "trace2.h"
+
+ /* Remember to update object flag allocation in object.h */
+ #define PARENT1 (1u<<16) /* used instead of SEEN */
+@@ builtin/last-modified.c: struct last_modified {
+
+ /* 'scratch' to avoid allocating a bitmap every process_parent() */
+ struct bitmap *scratch;
++
++ unsigned int count_bloom_filter_queries;
+ };
+
+ static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)
+@@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm,
+ if (!filter)
+ return true;
+
++ lm->count_bloom_filter_queries++;
++
+ /*
+ * With --show-trees we also track the tree entries containing the
+ * paths, so a change to any of those parent directories matters too.
@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)
prepare_revision_walk(&lm->rev);
@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)
max_count = lm->rev.max_count;
init_active_paths_for_commit(&lm->active_paths);
+@@ builtin/last-modified.c: static int last_modified_run(struct last_modified *lm)
+ if (hashmap_get_size(&lm->paths))
+ BUG("paths remaining beyond boundary in last-modified");
+
++ trace2_data_intmax("last-modified", lm->rev.repo, "bloom_queries",
++ lm->count_bloom_filter_queries);
++
+ clear_prio_queue(¬_queue);
+ clear_prio_queue(&queue);
+ clear_active_paths_for_commit(&lm->active_paths);
+
+ ## t/t8020-last-modified.sh ##
+@@ t/t8020-last-modified.sh: test_expect_success 'last-modified with Bloom filters and --show-trees' '
+ )
+ '
+
++test_expect_success 'last-modified with Bloom filters and top-level wildcard' '
++ test_when_finished rm -rf wildcard &&
++ git init wildcard &&
++ (
++ cd wildcard &&
++ test_commit base-c a.c &&
++ test_commit base-h a.h &&
++ test_commit touch-c a.c &&
++ mkdir d &&
++ test_commit sub-c d/b.c &&
++
++ git commit-graph write --reachable --changed-paths &&
++ GIT_TRACE2_PERF="$(pwd)/off.perf" \
++ git -c core.commitGraph=false last-modified -r HEAD \
++ -- "*.c" >expect &&
++ test_grep "data .* bloom_queries:0$" off.perf &&
++
++ GIT_TRACE2_PERF="$(pwd)/on.perf" \
++ git -c core.commitGraph=true last-modified -r HEAD \
++ -- "*.c" >actual &&
++ test_grep "data .* bloom_queries:2$" on.perf &&
++
++ test_cmp expect actual
++ )
++'
++
+ test_expect_success 'cannot run last-modified on two commits' '
+ test_must_fail git last-modified HEAD HEAD~1 2>err &&
+ test_grep "last-modified can only operate on one commit at a time" err
---
base-commit: c73e85354c275c9d409b26445089bc16940fc527
change-id: 20260716-toon-speed-up-last-modified-b04ea1f21831