Taylor Blau [off-list ref] writes:

On Thu, Oct 16, 2025 at 10:39:25AM +0200, Toon Claes wrote:

quoted

[...]

To avoid computing many first-parent diffs, add another trick on top of
this and check if all paths active in 'c' are DEFINITELY NOT in c's
Bloom filter. Since the commit-graph only stores first-parent diffs in
the Bloom filters, we can only apply this trick to first-parent diffs.

OK, up to this point this is the same as the commit message that I wrote
with Stolee back in 2020.

quoted

Comparing the performance of this new algorithm shows about a 2.6x
improvement on git.git:

    Benchmark 1: master
      Time (mean ± σ):      3.077 s ±  0.055 s    [User: 3.017 s, System: 0.051 s]
      Range (min … max):    2.947 s …  3.127 s    10 runs

    Benchmark 2: HEAD
      Time (mean ± σ):      1.181 s ±  0.010 s    [User: 1.139 s, System: 0.038 s]
      Range (min … max):    1.169 s …  1.194 s    10 runs

    Summary
      HEAD ran
        2.60 ± 0.05 times faster than master

But when comparing a more extreme example of
`git last-modified -- COPYING t`, the difference is a lot bigger:

    Benchmark 1: master
      Time (mean ± σ):      4.372 s ±  0.057 s    [User: 4.286 s, System: 0.062 s]
      Range (min … max):    4.308 s …  4.509 s    10 runs

    Benchmark 2: HEAD
      Time (mean ± σ):     826.3 ms ±  22.3 ms    [User: 784.1 ms, System: 39.2 ms]
      Range (min … max):   810.6 ms … 881.2 ms    10 runs

    Summary
      HEAD ran
        5.29 ± 0.16 times faster than master

These benchmarks are different than the ones that I provided, which is
good, since we should be measuring modern Git, not dragging forward
stale benchmarks ;-).

I imagine that you are just doing a straight last-modified run here in
both instances. In the original patch, I timed this both with and
without changed-path Bloom filters, which helped illustrate their impact
on the changes here.

I'd suggest including those benchmarks as well, and potentially running
them on linux.git, or another comparably larger open-source repository.
git.git is large enough to show some interesting behavior, but I always
have found it useful to compare the results against a larger repository
as well.

Sure.

quoted

As an added benefit, this implementation gives more correct results. For
example implementation in 'master' gives:

    $ git log --max-count=1 --format=%H -- pkt-line.h
    15df15fe07ef66b51302bb77e393f3c5502629de

    $ git last-modified -- pkt-line.h
    15df15fe07ef66b51302bb77e393f3c5502629de	pkt-line.h

    $ git last-modified | grep pkt-line.h
    5b49c1af03e600c286f63d9d9c9fb01403230b9f	pkt-line.h

With the changes in this patch the results of git-last-modified(1)
always match those of `git log --max-count=1`.

One thing to note though, the results might be outputted in a different
order than before. This is not considerd to be an issue because nowhere
is documented the order is guaranteed.

Based-on-patches-by: Taylor Blau [off-list ref]

Stolee and I wrote these patches together many years ago, so he should
be credited here as well. Since this patch appears to be substantially
based on the original work, I think it is appropriate to include my
S-o-b once the patch is ready.

I'm very grateful you (GitHub) have written and shared these patches, so
I'm happy to give proper attribution.

Sorry for this oopsie. Right before I sent this patch, I had a version
that removed the oideq() condition. In the final diff I noticed and I
decided to undo that, but didn't check my tests again. Thanks for the
patch, because I know I had that at one point as well.

But this makes me wonder, is there even any value in keeping `oid` on
`struct last_modified_entry`? I'll have a deeper look into this.

quoted

+/* Remember to update object flag allocation in object.h */
+#define PARENT1 (1u<<16) /* used instead of SEEN */
+#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */
+
 struct last_modified_entry {
 	struct hashmap_entry hashent;
 	struct object_id oid;
 	struct bloom_key key;
+	size_t diff_idx;
 	const char path[FLEX_ARRAY];
 };

@@ -37,13 +43,35 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,
 	return strcmp(ent1->path, path ? path : ent2->path);
 }

+/*
+ * Hold a bitmap for each commit we're working with. Each bit represents a path
+ * in `lm->all_paths`. Active bit means the path still needs to be dealt with.
+ */
+define_commit_slab(commit_bitmaps, struct bitmap *);
+

Nice, I am glad to see that we are using a bitmap here rather than the
hacky 'char *' that we had originally written. I seem to remember that
there was a tiny slow-down when using bitmaps, but can't find the
discussion anymore. (It wasn't in the internal PR that I originally
opened, and I no longer can read messages that far back in history.)

It might be worth benchmarking here to see if using a 'char *' is
faster. Of course, that's 8x worse in terms of memory usage, but not a
huge deal given both the magnitude and typical number of directory
elements (you'd need 1024^2 entries in a single tree to occupy even a
single MiB of heap).

Okay, I can give it a try.

Regardless of how you handle the above, I think that the commit slab
name here is a little generic. I guess it's OK since this is only
visible within this compilation unit, but perhaps something like
"active_paths_bitmap" would be more descriptive.

I struggled a lot naming this thing, so I'm open to suggestions.

Likewise, I wonder if we should have elemtype here be just 'struct
bitmap'. Unfortunately I don't think the EWAH code has a function like:

    void bitmap_init(struct bitmap *);

and only has ones that allocate for us. So we may consider adding one,
or creating a dummy bitmap and copying its contents, or otherwise.

quoted

 struct last_modified {
 	struct hashmap paths;
 	struct rev_info rev;
 	bool recursive;
 	bool show_trees;
+
+	const char **all_paths;
+	size_t all_paths_nr;

I wonder if all_paths should be a strvec here? I think that this code
was all written when the type was called argv_array (hilariously, that
change took place towards the end of July, 2020, and the --go-faster
code where this patch came from was written just a couple of weeks
earlier.)

Ahha, that might be a good idea. This might allow us to get rid of the
hashmap, which stops us from storing the paths twice. Not sure what the
impact on the performance would be, because the hashmap now is valuable
for path_idx() lookups.

quoted

@@ -196,7 +226,36 @@ static void last_modified_diff(struct diff_queue_struct *q,
 	}
 }

-static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)
+static size_t path_idx(struct last_modified *lm, char *path)
+{
+	struct last_modified_entry *ent;
+	ent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,
+					  struct last_modified_entry, hashent);
+
+	return ent ? ent->diff_idx : -1;
+}
+
+static void pass_to_parent(struct last_modified *lm,
+			   struct bitmap *c,
+			   struct bitmap *p,
+			   size_t pos)
+{
+	struct last_modified_entry *ent;
+	struct hashmap_iter iter;
+
+	bitmap_unset(c, pos);
+
+	hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
+		if (ent->diff_idx == pos) {
+			bitmap_set(p, pos);
+			break;
+		}
+	}
+}

This one I'm not quite following. The original implementation does
something like:

    c->active[i] = 0;
    c->nr--;
    p->active[i] = 1;
    p->nr++;

, where 'i' is an index into the all_paths array. It looks like you are
effectively doing the first part of that with the bitmap_unset() call,
but I'm confused why you're iterating over paths here.

The caller in process_parents() is iterating over all entries that are
treesame to the parent, bit by bit. So I think you can just bitmap_set()
in the parent directly here, but let me know if I am missing something.

It is an attempt from my side to optimize things further. I was thinking
a path could have been associated by another commit already. But now
you've brought this up, I don't think this no more.

A bit can only be set in two places:

* Initially when a commit is added from lm->rev.commits. We can only
  have one commit in there, because we count `num_interesting` in
  populate_paths_from_revs() and abort if it's more than 1.

* Here in pass_to_parent(). A commit only passes a bit to one parent.

So I'll remove the extra guard in the next version.

quoted

@@ -220,42 +282,197 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)
 	return false;
 }

+static void process_parent(struct last_modified *lm,
+			   struct prio_queue *queue,
+			   struct commit *c, struct bitmap *active_c,
+			   struct commit *parent, int parent_i)
+{
+	size_t i;
+	struct bitmap *active_p;
+
+	repo_parse_commit(lm->rev.repo, parent);
+	active_p = get_bitmap(lm, parent);
+
+	/*
+	 * The first time entering this function for this commit (i.e. first parent)
+	 * see if Bloom filters will tell us it's worth to do the diff.
+	 */
+	if (parent_i || maybe_changed_path(lm, c, active_c)) {
+		diff_tree_oid(&parent->object.oid,
+			      &c->object.oid, "", &lm->rev.diffopt);
+		diffcore_std(&lm->rev.diffopt);
+	}
+
+	/*
+	 * Otherwise, test each path for TREESAME-ness against the parent. If

This "otherwise" is referencing a piece of the patch that doesn't appear
to be here directly, which is how we handle the special case of having
nothing in the diff queue, meaning we are treesame at the root.

True, I shall drop the "otherwise" and rephrase further if needed.

In the GitHub version of this patch, we pass all active paths to the
parent, assign the PARENT1 flag if it doesn't already have it, and put
it in the queue as well.

In your version, we'd skip past the next for-loop, and do the same
pass-to-parent dance below, along with inserting the parent into the
prio queue.

This is the "shortcut" I'm mentioning in my cover letter. In my testing
it seemed it didn't provide any performance gains to keep it. I consider
less code better code, so I left it out.

So I think that this is all functionally equivalent, but I had to work
through a little bit of the details here, mostly since I haven't looked
at or thought about this code in many years ;-).

quoted

 static int last_modified_run(struct last_modified *lm)
 {
+	int max_count, queue_popped = 0;
+	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+	struct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };
+	struct commit_list *list;
 	struct last_modified_callback_data data = { .lm = lm };

 	lm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;
 	lm->rev.diffopt.format_callback = last_modified_diff;
 	lm->rev.diffopt.format_callback_data = &data;
+	lm->rev.no_walk = 1;

This one is new relative to the original patch. Why set no_walk here?

This comes from
https://github.com/ttaylorr/git/commit/e8ea49705873d28f64b815bd00d14bdf6d48ca4d

Well, it basically squashes various commits together. There are various
commits doing different things here. I don't think it's valuable for
anyone to see the full history of the iterations at GitHub, that's why I
squashed it in.

Would you consider it better to not set `no_walk`?

quoted

 	prepare_revision_walk(&lm->rev);

-	while (hashmap_get_size(&lm->paths)) {
-		data.commit = get_revision(&lm->rev);
-		if (!data.commit)
-			BUG("paths remaining beyond boundary in last-modified");
+	max_count = lm->rev.max_count;
+
+	init_commit_bitmaps(&lm->commit_bitmaps);
+	lm->scratch = bitmap_word_alloc(lm->all_paths_nr);
+
+	/*
+	 * lm->rev.commits holds the set of boundary commits for our walk.
+	 *
+	 * Loop through each such commit, and place it in the appropriate queue.
+	 */
+	for (list = lm->rev.commits; list; list = list->next) {

Hmm. In the original patch, we look at rev.pending, not rev.commits. The
rest of the patch looks good to me and looks like a faithful
representation of the original patch from GitHub's fork. Thanks for
working on this and making the new last-modified builtin faster ;-).

Euh, interesting. I'll look into it.

Thanks for the support!

-- 
Cheers,
Toon