* Re: git-last-modified(1) slower than git-log(1)?
2026-07-14 18:33 git-last-modified(1) slower than git-log(1)? Gusted
@ 2026-07-16 4:28 ` Jeff King
2026-07-16 11:42 ` Toon Claes
2026-07-16 9:26 ` Toon Claes
1 sibling, 1 reply; 4+ messages in thread
From: Jeff King @ 2026-07-16 4:28 UTC (permalink / raw)
To: Gusted; +Cc: git, Toon Claes, Taylor Blau
On Tue, Jul 14, 2026 at 08:33:59PM +0200, Gusted wrote:
> The repository I'm currently using to evaluate the performance is
> https://codeberg.org/ziglang/zig
>
> Reproduction steps:
> 1. `git clone https://codeberg.org/ziglang/zig $(mktemp -d)`
> 2. cd to tmp directory.
> 3. `git commit-graph write --changed-paths`. As git-last-modified(1)
> makes good use of the bloom filters.
> 4. `hyperfine 'git last-modified -z -t --max-depth=0
> 80d06578ac66bce3aa0a21e9610cdb782b9a0593 -- doc/langref/' 'git log
> --name-status -c "--format=commit%x00%H %P%x00" --parents --no-renames
> -t -z 80d06578ac66bce3aa0a21e9610cdb782b9a0593 -- ":(literal)doc/langref"'`
Thanks for this concrete reproduction. I can see the same problem here.
Interestingly, if we turn off changed-paths, we get very different
results.
Without a commit graph at all, last-modified wins (this is using the zig
repo and the commands above):
- log: 150ms
- last-modified: 79ms
But with a graph and no changed-paths, they're about equal:
- log: 61ms
- last-modified: 61ms
And then with changed-paths, the log command gets much faster but
last-modified gets slower!
- log: 20ms
- last-modified: 64ms
I think there's a tradeoff in the way that last-modified uses the bloom
filters. It makes a key for every path we're interested in, and then for
each commit, we check each key to say "is this in the commit's filter?".
So if you have a subdirectory with a non-trivial number of entries (like
doc/langref here which has 290), but most commits don't touch that path
at all (only 120 out of ~39k in this case), we'll spend a lot of time
checking each key against each filter. We save ourselves opening the
trees, but at the cost of 290*39k filter comparisons).
Whereas in the git-log case, we make a filter key out of the single
pathspec we're given, and then check each commit against that. So we
only do a single filter check for each commit to narrow it down to those
120 that matter (modulo a few filter false positives).
But I don't see any reason that last-modified couldn't _also_ do that:
pre-filter the commits with a commit matching the original pathspec, and
discard most commits with a single filter check.
The hacky patch below does this, and brings my last-modified runtime
down to 16ms (a 4x improvement, and just a bit faster than git-log).
It tries to reuse the logic from revision.c, so it's doing the exact
same filtering that git-log would do. I think there are other ways to do
it. E.g., we could make our own "root" bloom key that contains all of
the paths and pre-filter with that. But it seemed to be a little slower
when I tried it (~24ms). I'd guess that the problem is that because the
bloom filter is probabilistic, if you shove too many items into a single
key you'll end getting more and more false positives. So putting all 290
entries into one key is too much, and we are better off just considering
the shared prefix.
Anyway, here's the patch. Toon, I'm not planning to take it further
immediately, but you may be interested in poking at it. It probably
needs at least:
- some light refactoring of revision.c
- tests? We don't seem to cover last-modified with changed-paths at
all, and just rely on the test-vars CI job which sets
GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS. It did pass for me with that
flag, so surely I didn't introduce any bugs. :)
- more timing exploration; e.g., might it make things worse if
doc/langref were touched in 99% of the commits? Probably not, but it
might be nice to check timings against a few repo shapes and request
depths.
- Not all pathspecs can support bloom filters (e.g., "*.c" would not).
So in theory:
git last-modified HEAD -- "*.c"
could work, but wouldn't be optimized. I don't think it _does_ work
now, because last-modified's max-depth logic complains. So it might
be a non-issue.
But I think it is solvable if we really wanted. Rather than
traversing looking for "*.c", we actually expand the pathspec in the
tip commit to a set of literal paths, and then as we traverse we
look for those paths. So we could collect all of "*.c" and then
add bloom keys for the shared prefixes. I think this does get tricky
in the general case, though. If you have "a/b/c" and "a/b/d",
looking for "a/b" is reasonable. But what if you also have "a/e"?
Should you just have a key for "a/", or both "a/b" and "a/e"?
There are some tradeoffs between how often uninteresting things in
"a/" will give us a false positive, versus the cost of checking
extra keys.
So maybe an interesting area, but given that in practice most people
will feed a single pathspec to last-modified, it's a lot easier to
just use that.
- I know that last-modified was derived from GitHub's blame-tree
implementation (which I originally wrote, but stopped paying
attention to well before it learned about changed-path filters). I
don't know if the problem was solved separately there, but it would
be worth checking. +cc Taylor
-Peff
---
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index 5478182f2e..c07169258f 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -254,6 +254,29 @@ static void pass_to_parent(struct bitmap *c,
bitmap_set(p, pos);
}
+/*
+ * revision.c already has this functionality, but it is not public
+ * and it looks up the filter itself. But probably some refactoring
+ * could make it available at the right level?
+ */
+static bool filter_contains_keyvec(const struct bloom_filter *filter,
+ struct rev_info *rev)
+{
+ /*
+ * If we have no keys, we must pessimistically assume a match.
+ */
+ if (!rev->bloom_keyvecs_nr)
+ return true;
+
+ for (int i = 0; i < rev->bloom_keyvecs_nr; i++) {
+ if (bloom_filter_contains_vec(filter,
+ rev->bloom_keyvecs[i],
+ rev->bloom_filter_settings))
+ return true;
+ }
+ return false;
+}
+
static bool maybe_changed_path(struct last_modified *lm,
struct commit *origin,
struct bitmap *active)
@@ -272,6 +295,9 @@ static bool maybe_changed_path(struct last_modified *lm,
if (!filter)
return true;
+ if (!filter_contains_keyvec(filter, &lm->rev))
+ return false;
+
hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
if (active && !bitmap_get(active, ent->diff_idx))
continue;
@@ -499,7 +525,22 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,
return argc;
}
- lm->rev.bloom_filter_settings = get_bloom_filter_settings(lm->rev.repo);
+ /*
+ * Load the bloom settings, but also convert our pathspec into
+ * bloom_keyvecs that can be used later. This helper should
+ * probably be factored out, but we don't want to do it ourselves.
+ * There is logic about which pathspecs are allowed or not that
+ * we would not want to duplicate.
+ */
+ prepare_to_use_bloom_filter(&lm->rev);
+
+ /*
+ * Even if our initial pathspecs forbid using bloom filters, we'd still
+ * use them for the literal paths we expand below in
+ * populate_paths_from_revs().
+ */
+ if (!lm->rev.bloom_filter_settings)
+ lm->rev.bloom_filter_settings = get_bloom_filter_settings(lm->rev.repo);
if (populate_paths_from_revs(lm) < 0)
return -1;
diff --git a/revision.c b/revision.c
index 137a86d33b..f5b36ea2cc 100644
--- a/revision.c
+++ b/revision.c
@@ -705,7 +705,7 @@ static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,
return res;
}
-static void prepare_to_use_bloom_filter(struct rev_info *revs)
+void prepare_to_use_bloom_filter(struct rev_info *revs)
{
if (!revs->commits)
return;
diff --git a/revision.h b/revision.h
index 569b3fa1cb..1f761b85d0 100644
--- a/revision.h
+++ b/revision.h
@@ -576,4 +576,6 @@ int rewrite_parents(struct rev_info *revs,
*/
struct commit_list *get_saved_parents(struct rev_info *revs, const struct commit *commit);
+void prepare_to_use_bloom_filter(struct rev_info *revs);
+
#endif
^ permalink raw reply related [flat|nested] 4+ messages in thread* Re: git-last-modified(1) slower than git-log(1)?
2026-07-14 18:33 git-last-modified(1) slower than git-log(1)? Gusted
2026-07-16 4:28 ` Jeff King
@ 2026-07-16 9:26 ` Toon Claes
1 sibling, 0 replies; 4+ messages in thread
From: Toon Claes @ 2026-07-16 9:26 UTC (permalink / raw)
To: Gusted, git, Jeff King
Gusted <gusted@codeberg.org> writes:
> Hi,
>
> I'm working at switching Forgejo's implementation of getting the last
> modified commits in a directory to git-last-modified(1). I'd expected
> equal or better performance than the current implementation, but have
> not yet been able to get this and I'm a bit puzzled as to why.
>
> The current implementation of Forgejo (inherited from Gitea) works
> roughly like this:
> 1. Run `git log --name-status -c --format=commit%x00%H %P%x00" --parents
> --no-renames -t -z $OID -- :(literal)some/path`, the output of this is
> quite complex and possible outputs more information than necessary.
> 2. The output of this is piped to some code to a parser and reconstructs
> what commit ID last modified each file in the directory.
> 3. Via `git cat-file --batch` get each unique commits information.
>
> With git-last-modified(1) (-z --show-trees --max-depth=0) this replaces
> step 1-2, but is slower. I've isolated the degraded performance to the
> fact that git-last-changed(1) takes more time to finish. So from my
> perspective it does not seem worth it to replace the current
> implementation with git-last-modified(1), and I would like to know if
> I'm missing something here or if git-last-modified(1) possibly could see
> a speedup?
>
> The repository I'm currently using to evaluate the performance is
> https://codeberg.org/ziglang/zig
>
> Reproduction steps:
> 1. `git clone https://codeberg.org/ziglang/zig $(mktemp -d)`
> 2. cd to tmp directory.
> 3. `git commit-graph write --changed-paths`. As git-last-modified(1)
> makes good use of the bloom filters.
> 4. `hyperfine 'git last-modified -z -t --max-depth=0
> 80d06578ac66bce3aa0a21e9610cdb782b9a0593 -- doc/langref/' 'git log
> --name-status -c "--format=commit%x00%H %P%x00" --parents --no-renames
> -t -z 80d06578ac66bce3aa0a21e9610cdb782b9a0593 -- ":(literal)doc/langref"'`
>
> With as output:
> Benchmark 1: git last-modified -z -t --max-depth=0
> 80d06578ac66bce3aa0a21e9610cdb782b9a0593 -- doc/langref/
> Time (mean ± σ): 66.5 ms ± 0.6 ms [User: 60.6 ms, System: 5.2 ms]
> Range (min … max): 65.3 ms … 67.7 ms 44 runs
>
> Benchmark 2: git log --name-status -c "--format=commit%x00%H %P%x00"
> --parents --no-renames -t -z 80d06578ac66bce3aa0a21e9610cdb782b9a0593 --
> ":(literal)doc/langref"
> Time (mean ± σ): 26.2 ms ± 1.0 ms [User: 17.3 ms, System: 8.4 ms]
> Range (min … max): 24.3 ms … 30.1 ms 110 runs
>
> Summary
> git log --name-status -c "--format=commit%x00%H %P%x00" --parents
> --no-renames -t -z 80d06578ac66bce3aa0a21e9610cdb782b9a0593 --
> ":(literal)doc/langref" ran
> 2.54 ± 0.10 times faster than git last-modified -z -t --max-depth=0
> 80d06578ac66bce3aa0a21e9610cdb782b9a0593 -- doc/langref/
Hi Gusted,
Thanks for reaching out.
You're actually not the first to notice this, and I've been aware of
this.
The thing is, you're testing the difference on a single file. For us at
GitLab, it wasn't very useful to optimize that use-case, because usually
we want to see the last commit for a bunch of files at once.
So the use-case for git-last-modified(1) for us has been to replace
(pseudo code):
$ FILES=$(git ls-tree $COMMIT $PATH)
$ foreach $FILE in $FILES; do git log -1 $COMMIT -- $FILE; end
GitLab is batching files 25 at once, and in my benchmarking, it was
shown git-last-modified(1) is faster:
$ git last-modified $COMMIT -- <files
(I did this benchmarking in our Gitaly component to have a real-world
experience and you can visit the results at:
https://gitlab.com/gitlab-org/gitaly/-/merge_requests/7999#note_2850505479
)
So we left the door open for future improvement, although I never have
gotten to it. At some point I was trying to chase down when git-log(1)
was doing differently, but I never figured it out.
But this email challenged me already. And with some help of AI, I
managed to work on some improvements. You can expect a patch series
soon.
(Right before sending out this mail I noticed Peff sent out some changes
as well. I'll coordinate how to combine.)
--
Cheers,
Toon
^ permalink raw reply [flat|nested] 4+ messages in thread