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