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

On Tue, Jul 14, 2026 at 08:33:59PM +0200, Gusted wrote:

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

---