From: Toon Claes Date: Tue, 01 Sep 2026 09:10:20 GMT Subject: [PATCH v4 0/6] last-modified: use the pathspec's Bloom key to pre-filter commits Message-ID: <20260901-toon-speed-up-last-modified-v4-0-a09949800404@iotcl.com> In-Reply-To: <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com> 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/ [2]: https://codeberg.org/ziglang/zig --- Changes in v4: - Override GIT_TEST_COMMIT_GRAPH when passing `-c core.commitGraph=` in t8020 tests. - Link to v3: https://patch.msgid.link/20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@iotcl.com 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 | 49 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 160 insertions(+), 12 deletions(-) Range-diff versus v3: 1: 645c5d1ddf = 1: dbb1ad8e96 revision: move bloom keyvec precondition into function 2: 3fa70e300d = 2: 6f0d62fe6c revision: expose check for paths maybe changed in Bloom filter 3: d30e3fea71 = 3: 1c09e9ecba bloom: add helper to check if any key in a vector is present 4: 7b5cc70022 = 4: 7c7792e057 revision: add Bloom check that includes parent directories 5: 5cb67a54b1 ! 5: ac5a6bd427 last-modified: check pathspec against Bloom filter first @@ t/t8020-last-modified.sh: test_expect_success 'last-modified merge undoes change + test_commit touch-b d/b && + + git commit-graph write --reachable --changed-paths && -+ git -c core.commitGraph=false last-modified -t HEAD -- d/a \ -+ >expect && -+ git -c core.commitGraph=true last-modified -t HEAD -- d/a \ -+ >actual && ++ GIT_TEST_COMMIT_GRAPH=0 \ ++ git -c core.commitGraph=false last-modified -t HEAD \ ++ -- d/a >expect && ++ GIT_TEST_COMMIT_GRAPH=1 \ ++ git -c core.commitGraph=true last-modified -t HEAD \ ++ -- d/a >actual && + + test_cmp expect actual + ) 6: c94f744a0f ! 6: 3524a202e7 last-modified: keep per-path Bloom filters for wildcard pathspecs @@ t/t8020-last-modified.sh: test_expect_success 'last-modified with Bloom filters + test_commit sub-c d/b.c && + + git commit-graph write --reachable --changed-paths && -+ GIT_TRACE2_PERF="$(pwd)/off.perf" \ ++ GIT_TEST_COMMIT_GRAPH=0 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_TEST_COMMIT_GRAPH=1 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 && --- base-commit: c73e85354c275c9d409b26445089bc16940fc527 change-id: 20260716-toon-speed-up-last-modified-b04ea1f21831