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

[Toon Claes <toon@iotcl.com>]

Jeff King <peff@peff.net> writes:

> 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.

As I mentioned, I was aware of that issue, but never felt the need (and
didn't have the deep Bloom filter knowledge) to fix it.

> 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).

Oh, that's very useful of you to explain this. Thank you.

> 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).

Funny, I was toying around with my AI agent, and they came with a
similar solution, but I'm working on a cleaner solution.

> 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

Agreed.

>   - 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. :)

Fair of you calling that out. Thanks for checking.

>   - 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.

Maybe, I tried a few things.

On gitlab-org/gitlab (our Rails monolith), there seems to be a noticable
improvement when running for `app/`:

    Benchmark 1: old
      Time (mean ± σ):     435.5 ms ±   9.8 ms    [User: 369.5 ms, System: 64.4 ms]
      Range (min … max):   425.3 ms … 450.9 ms    5 runs
     
    Benchmark 2: new
      Time (mean ± σ):     278.5 ms ±  32.3 ms    [User: 208.0 ms, System: 69.3 ms]
      Range (min … max):   246.2 ms … 314.8 ms    5 runs
     
    Summary
      new ran
        1.56 ± 0.18 times faster than old

The app/ directory is touched by roughly 35% of the commits.

In gitlab-org/gitaly, I ran a benchmark on `internal/`, which is touched
in about 58% of the commits:

    Benchmark 1: old
      Time (mean ± σ):      13.2 ms ±   1.3 ms    [User: 10.4 ms, System: 2.5 ms]
      Range (min … max):    11.3 ms …  14.8 ms    10 runs
     
    Benchmark 2: new
      Time (mean ± σ):       9.9 ms ±   0.4 ms    [User: 7.3 ms, System: 2.4 ms]
      Range (min … max):     9.6 ms …  10.8 ms    10 runs
     
    Summary
      new ran
        1.33 ± 0.14 times faster than old

(although Gitaly a lot less commits, ~23k commits vs ~530k in our Rails
monolith)

And also --recursive it's faster:

    Benchmark 1: old
      Time (mean ± σ):     204.6 ms ±   4.4 ms    [User: 193.2 ms, System: 10.5 ms]
      Range (min … max):   199.9 ms … 213.2 ms    10 runs
     
    Benchmark 2: new
      Time (mean ± σ):     181.5 ms ±   2.7 ms    [User: 170.9 ms, System: 9.7 ms]
      Range (min … max):   177.0 ms … 187.1 ms    10 runs
     
    Summary
      new ran
        1.13 ± 0.03 times faster than old

Personally I'm not too worried any use-case would be at least equally
fast.

>   - 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.

Yeah, I rather not deal with that right now.

>   - 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?

I assume you're talking about check_maybe_different_in_bloom_filter()?

I was working on a fix to simply make it public and call it, but that's
a very valid point you're making. I'll change my plans.

> + */
> +static bool filter_contains_keyvec(const struct bloom_filter *filter,
> +				   struct rev_info *rev)
> +{
> ... [snip]

-- 
Cheers,
Toon