Re: [PATCH v2] last-modified: implement faster algorithm

[Taylor Blau <me@ttaylorr.com>]

On Tue, Oct 21, 2025 at 10:52:11AM -0700, Junio C Hamano wrote:
> > +		struct diff_filepair *fp = diff_queued_diff.queue[i];
> > +		size_t k = path_idx(lm, fp->two->path);
> > +		if (0 <= k && bitmap_get(active_c, k))
> > +			bitmap_set(lm->scratch, k);
> > +	}
>
> Earlier path_idx() wanted to signal an error by returning negative,
> but the type is size_t that is unsigned so it cannot do so.  We
> instead get
>
>     builtin/last-modified.c:307:23: error: comparison of unsigned expression in '>= 0' is always true [-Werror=type-limits]
>       307 |                 if (0 <= k && bitmap_get(active_c, k))
>           |                       ^~
>
> and in this case we actually deserve it (in the sense that this is
> not the fault of dogmatic trust in -Wsign-compare; this is caused by
> using size_t to count things).
>
> And the solution for this is *not* "size_t" -> "ssize_t", because
> ssize_t is not "store half the range of size_t with negative values
> reserved for something else like errors".  Its width can be much
> narrower (this came up in a separate thread very recently [*]).
> Instead we'd need something ugly like
>
> 	if (k != (size_t)-1 && bitmap_get(active_c, k))
>
> A quick band-aid patch to make it compile is attached at the end,
> but it does not try to address the root causes, which are abuse of
> size_t as count_t and religious use of "-Wsign-compare" [*].
>
>
> [Reference]
>
> * https://lore.kernel.org/git/9eafee4d-ea94-4382-ada0-58000d229d2e@gmail.com/
> * https://staticthinking.wordpress.com/2023/07/25/wsign-compare-is-garbage/

Yeah, this is a true positive. I was curious if GitHub's version of the
code also returned "-1" from a function whose return type is unsigned,
and in fact our version of this function (called diff2idx()) returns an
'int'.

Practically speaking that's probably OK, since we are unlikely to have
so many active paths anyway (or if we did, we'd likely have other
problems to deal with ;-)), but it is gross nonetheless.

I wonder if we should inline all of this into its own function and not
expose the bitmap index for a given path at all? Perhaps something like
the following (on top of Junio's other suggestions to get this compiling
under DEVELOPER=1):

--- 8< ---
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index e9050485a9..ce3ae4fb3d 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -226,13 +226,16 @@ static void last_modified_diff(struct diff_queue_struct *q,
 	}
 }

-static size_t path_idx(struct last_modified *lm, char *path)
+static void last_modified_mark_non_treesame(struct last_modified *lm,
+					    struct bitmap *active_c,
+					    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;
+	if (ent && bitmap_get(active_c, ent->diff_idx))
+		bitmap_set(lm->scratch, ent->diff_idx);
 }

 static void pass_to_parent(struct last_modified *lm,
@@ -303,9 +306,7 @@ static void process_parent(struct last_modified *lm,
 	 */
 	for (i = 0; i < diff_queued_diff.nr; i++) {
 		struct diff_filepair *fp = diff_queued_diff.queue[i];
-		size_t k = path_idx(lm, fp->two->path);
-		if (0 <= k && bitmap_get(active_c, k))
-			bitmap_set(lm->scratch, k);
+		last_modified_mark_non_treesame(lm, active_c, fp->two->path);
 	}
 	for (i = 0; i < lm->all_paths_nr; i++) {
 		if (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))
--- >8 ---

Thanks,
Taylor