git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

Previous: Toon ClaesNext: Jeff King
Message 10 of 30 in “last-modified: use the pathspec's Bloom key to pre-filter commits”
  1. 0/4 last-modified: use the pathspec's Bloom key to pre-filter commitsToon Claes, Jul 17, 2026
  2. 1/4 revision: move bloom keyvec precondition into functionToon Claes, Jul 17, 2026
  3. Jeff KingJul 18, 2026
  4. Toon ClaesAug 5, 2026
  5. Jeff KingAug 5, 2026
  6. 2/4 revision: expose check for paths maybe changed in Bloom filterToon Claes, Jul 17, 2026
  7. Junio C HamanoJul 17, 2026
  8. Taylor BlauJul 17, 2026
  9. 3/4 last-modified: check pathspec against Bloom filter firstToon Claes, Jul 17, 2026
  10. Taylor BlauJul 17, 2026
  11. Jeff KingJul 18, 2026
  12. Taylor BlauJul 18, 2026
  13. Jeff KingJul 20, 2026
  14. 4/4 last-modified: keep per-path Bloom filters for wildcard pathspecsToon Claes, Jul 17, 2026
  15. Toon ClaesJul 17, 2026
  16. Jeff KingJul 18, 2026
  17. Junio C HamanoAug 4, 2026
  18. Taylor BlauAug 5, 2026
  19. Junio C HamanoAug 5, 2026
  20. Jeff KingAug 5, 2026
  21. Taylor BlauJul 17, 2026
  22. Toon ClaesJul 17, 2026
  23. 0/6 last-modified: use the pathspec's Bloom key to pre-filter commitsToon Claes, Aug 7, 2026
  24. 1/6 revision: move bloom keyvec precondition into functionToon Claes, Aug 7, 2026
  25. 2/6 revision: expose check for paths maybe changed in Bloom filterToon Claes, Aug 7, 2026
  26. 3/6 bloom: add helper to check if any key in a vector is presentToon Claes, Aug 7, 2026
  27. 4/6 revision: add Bloom check that includes parent directoriesToon Claes, Aug 7, 2026
  28. 5/6 last-modified: check pathspec against Bloom filter firstToon Claes, Aug 7, 2026
  29. 6/6 last-modified: keep per-path Bloom filters for wildcard pathspecsToon Claes, Aug 7, 2026
  30. Junio C HamanoAug 8, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.