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 18, 2026, 21:22 UTC
Message-ID
<alvulw2fk67duo8n@com-79390>
In-Reply-To
<20260718083757.GD22588@coredump.intra.peff.net>
On Sat, Jul 18, 2026 at 04:37:57AM -0400, Jeff King wrote:
Show 14 quoted lines
> > 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.
>
> Hmm, interesting. I am surprised to learn that "-t" includes "d" when
> the pathspec asked for "d/a". I thought it was mostly about showing
> "d/a" when we recurse to find "d/a/b". But I guess it does not make a
> distinction between the two (probably because it is just telling the
> diff code to show trees, and it does not further apply the pathspec to
> the output).
>
> Does this mean there is also a bug in "git log"? I guess not, because it
> is purely pruning based on the pathspec, and only shows "d/" for those
> commits.
Right.
Show 18 quoted lines
> > 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;
>
> Hmph. That makes this optimization all but useless, because the intended
> use case of last-modified is almost always going to use "-t" to be able
> to mark the interior trees. And most callers are not going to care about
> seeing "d" here; their purpose was to find out about the things _inside_
> "d".
>
> Would we consider removing "d" from the output for this case? Presumably
> by double-checking the pathspecs again in add_path_from_diff(). That
> gives less surprising output (to me, anyway) and would enable this
> optimization. And the command is still marked as experimental, and I
> think this is exactly the kind of corner case that is meant to cover.

I think that we could feasibly get rid of "d" in the output in this particular case within last-modified. As you note, the command is marked EXPERIMENTAL for a reason, after all ;-).

If we wanted to do that, it should be straightforward to do. I think the following (untested) patch would be sufficient:

--- 8< ---
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index adc7cd8c74..0f0c1d1d17 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -103,7 +103,7 @@ struct last_modified_callback_data {
 };

 static void add_path_from_diff(struct diff_queue_struct *q,
-			       struct diff_options *opt UNUSED, void *data)
+			       struct diff_options *opt, void *data)
 {
 	struct last_modified *lm = data;

@@ -112,6 +112,11 @@ static void add_path_from_diff(struct diff_queue_struct *q,
 		struct last_modified_entry *ent;
 		const char *path = p->two->path;

+		if (!match_pathspec(opt->repo->index, &opt->pathspec, path,
+				    strlen(path), 0, NULL,
+				    S_ISDIR(p->two->mode)))
+			continue;
+
 		FLEX_ALLOC_STR(ent, path, path);
 		oidcpy(&ent->oid, &p->two->oid);
 		if (lm->rev.bloom_filter_settings)
--- >8 ---

If, on the other hand, we wanted to retain "d" in the output (which I am
inclined to suggest is a bad idea), we could keep a list of paths which
are not covered by the given pathspec.

If you had such a list, you could check only active entries within that
list, removing them as they are resolved. That makes a Bloom query miss
O(U*H) (where U is the uncovered subset of all paths, and H is the
number of hash functions in our Bloom key, which in our case is 7) as
opposed to O(P*H), where P is the number of active paths.

Of course, as U approaches P, the advantage disappears and so too do
the benefits of Toon's optimization.

If you wanted to go that route, you could do something like the
following (lightly tested):

--- 8< ---
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index adc7cd8c74..e69c7a44b6 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -11,6 +11,7 @@
 #include "ewah/ewok.h"
 #include "hashmap.h"
 #include "hex.h"
+#include "list.h"
 #include "object-name.h"
 #include "object.h"
 #include "parse-options.h"
@@ -25,9 +26,11 @@

 struct last_modified_entry {
 	struct hashmap_entry hashent;
+	struct list_head uncovered;
 	struct object_id oid;
 	struct bloom_key key;
 	size_t diff_idx;
+	bool covered_by_pathspec;
 	const char path[FLEX_ARRAY];
 };

@@ -52,6 +55,7 @@ define_commit_slab(active_paths_for_commit, struct bitmap *);

 struct last_modified {
 	struct hashmap paths;
+	struct list_head uncovered_paths;
 	struct rev_info rev;
 	bool show_trees;
 	bool nul_termination;
@@ -103,7 +107,7 @@ struct last_modified_callback_data {
 };

 static void add_path_from_diff(struct diff_queue_struct *q,
-			       struct diff_options *opt UNUSED, void *data)
+			       struct diff_options *opt, void *data)
 {
 	struct last_modified *lm = data;

@@ -114,6 +118,16 @@ static void add_path_from_diff(struct diff_queue_struct *q,

 		FLEX_ALLOC_STR(ent, path, path);
 		oidcpy(&ent->oid, &p->two->oid);
+
+		if (match_pathspec(opt->repo->index, &opt->pathspec, path,
+				   strlen(path), 0, NULL,
+				   S_ISDIR(p->two->mode))) {
+			ent->covered_by_pathspec = true;
+		} else {
+			list_add_tail(&ent->uncovered, &lm->uncovered_paths);
+			ent->covered_by_pathspec = false;
+		}
+
 		if (lm->rev.bloom_filter_settings)
 			bloom_key_fill(&ent->key, path, strlen(path),
 				       lm->rev.bloom_filter_settings);
@@ -202,6 +216,8 @@ static void mark_path(const char *path, const struct object_id *oid,
 	last_modified_emit(data->lm, path, data->commit);

 	hashmap_remove(&data->lm->paths, &ent->hashent, path);
+	if (!ent->covered_by_pathspec)
+		list_del(&ent->uncovered);
 	bloom_key_clear(&ent->key);
 	free(ent);
 }
@@ -272,8 +288,22 @@ static bool maybe_changed_path(struct last_modified *lm,
 	if (!filter)
 		return true;

-	if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)
+	if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0) {
+		struct list_head *pos;
+
+		list_for_each(pos, &lm->uncovered_paths) {
+			ent = list_entry(pos, struct last_modified_entry,
+					 uncovered);
+			if (active && !bitmap_get(active, ent->diff_idx))
+				continue;
+
+			if (bloom_filter_contains(filter, &ent->key,
+						  lm->rev.bloom_filter_settings))
+				return true;
+		}
+
 		return false;
+	}

 	hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
 		if (active && !bitmap_get(active, ent->diff_idx))
@@ -490,6 +520,7 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,
 	struct last_modified_entry *ent;

 	hashmap_init(&lm->paths, last_modified_entry_hashcmp, NULL, 0);
+	INIT_LIST_HEAD(&lm->uncovered_paths);

 	repo_init_revisions(r, &lm->rev, prefix);
 	lm->rev.def = "HEAD";
--- >8 ---

On my machine, in a synthetic repository containing 10,000 commits with
5,001 covered paths and 1 uncovered path, Toon's original patch runs in
~450ms. With the above patch, the timing drops to ~227ms, whereas it
drops further to ~190ms when omitting the uncovered path entirely.

So I'm inclined to suggest that we take advantage of the command's
EXPERIMENTAL nature and avoid printing the uncovered path entirely.

Thanks,
Taylor
Previous: Jeff KingNext: Jeff King
Message 12 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.