Re: git-last-modified(1) slower than git-log(1)?

> 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

>   - 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)
> +{
> ... [snip]