Re: [PATCH 3/4] last-modified: check pathspec against Bloom filter first
- From
Taylor Blau <ttaylorr@openai.com>
- Date
- Jul 17, 2026, 23:05 UTC
- Message-ID
- <alq1Q55ezuN9ZI9j@com-79390>
- In-Reply-To
- <20260717-toon-speed-up-last-modified-v1-3-410418f18614@iotcl.com>
On Fri, Jul 17, 2026 at 05:47:01PM +0200, Toon Claes wrote:
Show 26 quoted lines
> When git-last-modified(1) starts, it builds a list of all the paths > matching the pathspec it needs to find the last modifying commit for. > For example, every file and subdirectory listed by: > > $ git last-modified -t --max-depth=0 -- src/ > > As it resolves a commit for each path during the revision walk, it drops > that path from the list. > > To avoid diffing trees for every commit, Bloom filters are used when > available. For each remaining path, the commit's Bloom filter is checked > to see whether the commit changed that path. The Bloom filter says > either "no" or "maybe", and only in the latter case is the diff > calculated. > > git-log(1) does this differently. It does not expand the pathspec but > checks the Bloom filter against the pathspec itself. This way, commits > not touching any path matching the pathspec can be discarded as a whole. > > Apply this same check to git-last-modified(1). In a previous commit the > function revs_maybe_changed_in_bloom(), used by git-log(1), was made > public. Use this as a pre-filter in git-last-modified(1). After this > pre-filter, paths are still checked one-by-one to only find those which > don't have a "last commit" yet. > > Signed-off-by: Toon Claes <toon@iotcl.com>
Show 13 quoted lines
> --- > builtin/last-modified.c | 3 +++ > 1 file changed, 3 insertions(+) > > diff --git a/builtin/last-modified.c b/builtin/last-modified.c > index 5478182f2e..e8ee610404 100644 > --- a/builtin/last-modified.c > +++ b/builtin/last-modified.c > @@ -272,6 +272,9 @@ static bool maybe_changed_path(struct last_modified *lm, > if (!filter) > return true; > > + if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)
Nit: please prefer 'if (!foo())' over 'if (foo() == 0)'.
> + return false; > +
I don't think this is safe with '--show-trees'. The original pathspec does not cover every entry in 'lm->paths', since the function 'populate_paths_from_revs()' also adds ancestor tree entries.
This can be reproduced by adding the following to t8020:
test_expect_success 'Bloom filter with --show-trees' '
mkdir d && test_commit base-a d/a &&
test_commit base-b d/b &&
test_commit touch-a d/a &&
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 && test_cmp expect actual
'Without the graph, 'd' is attributed to 'touch-b' and 'd/a' to 'touch-a'. With the graph, both are attributed to 'touch-a'. The filter for 'touch-b' lacks 'd/a', so the new prefilter skips its diff even though 'd' changed.
I think that the conditional is otherwise correct, if guarded when we know that 'lm->show_trees' is false, like so:
if (!lm->show_trees &&
!revs_maybe_changed_in_bloom(&lm->rev, filter))
return false;The cover benchmark uses the same --show-trees plus narrow-pathspec shape, so I think its output should be checked before interpreting the speedup.
Thanks, Taylor