Subject: Re: [PATCH v2] diff-index: don't queue unchanged filepairs with diff_change()

From: René Scharfe <[email-masked]>
Date: Wed, 3 Dec 2025 16:06:46 +0100

On 12/2/25 11:07 PM, RenÃ© Scharfe wrote:
> On 11/30/25 7:02 PM, Junio C Hamano wrote:
>> René Scharfe <[email-masked]> writes:
>>
>>> Add a new streamlined function for queuing unchanged filepairs and
>>> use it in show_modified(), which is called by diff_cache() via
>>> oneway_diff() and do_oneway_diff().  It allocates only a single filespec
>>> for each filepair and uses it twice with reference counting.  This has a
>>> measurable effect if there are a lot of them, like in the Linux repo:
>>>
>>> Benchmark 1: ./git_v2.52.0 -C ../linux diff --cached --find-copies-harder
>>>   Time (mean ± σ):      31.8 ms ±   0.2 ms    [User: 24.2 ms, System: 6.3 ms]
>>>   Range (min … max):    31.5 ms …  32.3 ms    85 runs
>>>
>>> Benchmark 2: ./git -C ../linux diff --cached --find-copies-harder
>>>   Time (mean ± σ):      23.9 ms ±   0.2 ms    [User: 18.1 ms, System: 4.6 ms]
>>>   Range (min … max):    23.5 ms …  24.4 ms    111 runs
>>>
>>> Summary
>>>   ./git -C ../linux diff --cached --find-copies-harder ran
>>>     1.33 ± 0.01 times faster than ./git_v2.52.0 -C ../linux diff --cached --find-copies-harder
>>
>> Nice.  Is this technique only applicable to diff-index among the
>> three diff plumbing siblings?
> 
>> [...] it would apply to diff-tree, wouldn't it?
> Yes, but its diff_change() call is behind two layers of callbacks, which
> complicates things.
> 
> And I don't know how to avoid adding an object ID comparison.  Do we
> perhaps have that bit somewhere in tree-diff.c already and can pass it
> along the pathchange call?

Yes, new patch below.  Not sure if it's better, though.

> Benchmark 1: ./git_v2.52.0 diff-tree --find-copies-harder -r v2.51.0 v2.51.1
>   Time (mean ± σ):      78.3 ms ±   0.2 ms    [User: 57.4 ms, System: 19.8 ms]
>   Range (min … max):    77.9 ms …  78.7 ms    36 runs
> 
> Benchmark 2: ./git diff-tree --find-copies-harder -r v2.51.0 v2.51.1
>   Time (mean ± σ):      78.8 ms ±   0.2 ms    [User: 57.9 ms, System: 19.8 ms]
>   Range (min … max):    78.4 ms …  79.2 ms    36 runs
> 
> Summary
>   ./git_v2.52.0 diff-tree --find-copies-harder -r v2.51.0 v2.51.1 ran
>     1.01 ± 0.00 times faster than ./git diff-tree --find-copies-harder -r v2.51.0 v2.51.1
Benchmark 1: ./git_v2.52.0 diff-tree --find-copies-harder -r v2.51.0 v2.51.1
  Time (mean ± σ):      75.6 ms ±   0.6 ms    [User: 57.4 ms, System: 17.2 ms]
  Range (min … max):    75.0 ms …  78.0 ms    37 runs

Benchmark 2: ./git diff-tree --find-copies-harder -r v2.51.0 v2.51.1
  Time (mean ± σ):      76.0 ms ±   0.2 ms    [User: 57.9 ms, System: 17.1 ms]
  Range (min … max):    75.6 ms …  76.4 ms    37 runs

Summary
  ./git_v2.52.0 diff-tree --find-copies-harder -r v2.51.0 v2.51.1 ran
    1.00 ± 0.01 times faster than ./git diff-tree --find-copies-harder -r v2.51.0 v2.51.1

Hmm, I probably ran some background task when I measured yesterday and got
worse results for the git_v2.52.0 baseline than today.

René

---
 builtin/reset.c |  1 +
 diff.c          |  1 +
 diff.h          |  9 +++++++--
 diffcore.h      |  4 ++--
 tree-diff.c     | 48 +++++++++++++++++++++++++++---------------------
 5 files changed, 38 insertions(+), 25 deletions(-)

diff --git a/builtin/reset.c b/builtin/reset.c
index ed35802af1..ec674694dd 100644
--- a/builtin/reset.c
+++ b/builtin/reset.c
@@ -210,6 +210,7 @@ static int read_from_tree(const struct pathspec *pathspec,
 	opt.repo = the_repository;
 	opt.change = diff_change;
 	opt.add_remove = diff_addremove;
+	opt.keep = diff_same;
 
 	if (pathspec->nr && pathspec_needs_expanded_index(the_repository->index, pathspec))
 		ensure_full_index(the_repository->index);
diff --git a/diff.c b/diff.c
index 436da250eb..9671524d2b 100644
--- a/diff.c
+++ b/diff.c
@@ -4847,6 +4847,7 @@ void repo_diff_setup(struct repository *r, struct diff_options *options)
 	/* pathchange left =NULL by default */
 	options->change = diff_change;
 	options->add_remove = diff_addremove;
+	options->keep = diff_same;
 	options->use_color = diff_use_color_default;
 	options->detect_rename = diff_detect_rename_default;
 	options->xdl_opts |= diff_algorithm;
diff --git a/diff.h b/diff.h
index 7eb84aadf4..2e3a5ac04a 100644
--- a/diff.h
+++ b/diff.h
@@ -43,7 +43,8 @@ struct oidset;
  * set_default in diff_options can be used to tweak this more.
  *
  * - As you find different pairs of files, call `diff_change()` to feed
- * modified files, `diff_addremove()` to feed created or deleted files, or
+ * modified files, `diff_addremove()` to feed created or deleted files,
+ * `diff_same()` to feed unmodified files if needed for copy detection, or
  * `diff_unmerge()` to feed a file whose state is 'unmerged' to the API.
  * These are thin wrappers to a lower-level `diff_queue()` function that is
  * flexible enough to record any of these kinds of changes.
@@ -76,7 +77,7 @@ struct rev_info;
 struct userdiff_driver;
 
 typedef int (*pathchange_fn_t)(struct diff_options *options,
-		 struct combine_diff_path *path);
+		 struct combine_diff_path *path, bool is_change);
 
 typedef void (*change_fn_t)(struct diff_options *options,
 		 unsigned old_mode, unsigned new_mode,
@@ -92,6 +93,9 @@ typedef void (*add_remove_fn_t)(struct diff_options *options,
 		    int oid_valid,
 		    const char *fullpath, unsigned dirty_submodule);
 
+typedef void (*keep_fn_t)(struct diff_options *options, unsigned mode,
+			  const struct object_id *oid, const char *fullpath);
+
 typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,
 		struct diff_options *options, void *data);
 
@@ -384,6 +388,7 @@ struct diff_options {
 	pathchange_fn_t pathchange;
 	change_fn_t change;
 	add_remove_fn_t add_remove;
+	keep_fn_t keep;
 	void *change_fn_data;
 	diff_format_fn_t format_callback;
 	void *format_callback_data;
diff --git a/diffcore.h b/diffcore.h
index 9c0a0e7aaf..64b419b33f 100644
--- a/diffcore.h
+++ b/diffcore.h
@@ -35,8 +35,8 @@ struct userdiff_driver;
 /**
  * the internal representation for a single file (blob).  It records the blob
  * object name (if known -- for a work tree file it typically is a NUL SHA-1),
- * filemode and pathname.  This is what the `diff_addremove()`, `diff_change()`
- * and `diff_unmerge()` synthesize and feed `diff_queue()` function with.
+ * filemode and pathname.  This is what `diff_addremove()`, `diff_change()`,
+ * `diff_same()` and `diff_unmerge()` synthesize and feed `diff_queue()`.
  */
 struct diff_filespec {
 	struct object_id oid;
diff --git a/tree-diff.c b/tree-diff.c
index 5988148b60..e711456766 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -163,12 +163,17 @@ static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
  * emits diff to first parent only, and tells diff tree-walker that we are done
  * with p and it can be freed.
  */
-static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_diff_path *p)
+static int emit_diff_first_parent_only(struct diff_options *opt,
+				       struct combine_diff_path *p,
+				       bool is_change)
 {
 	struct combine_diff_parent *p0 = &p->parent[0];
 	if (p->mode && p0->mode) {
-		opt->change(opt, p0->mode, p->mode, &p0->oid, &p->oid,
-			1, 1, p->path, 0, 0);
+		if (is_change)
+			opt->change(opt, p0->mode, p->mode, &p0->oid, &p->oid,
+				    1, 1, p->path, 0, 0);
+		else if (opt->keep)
+			opt->keep(opt, p->mode, &p->oid, p->path);
 	}
 	else {
 		const struct object_id *oid;
@@ -205,7 +210,7 @@ static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_
 static void emit_path(struct combine_diff_path ***tail,
 		      struct strbuf *base, struct diff_options *opt,
 		      int nparent, struct tree_desc *t, struct tree_desc *tp,
-		      int imin, int depth)
+		      int imin, int depth, bool is_change)
 {
 	unsigned short mode;
 	const char *path;
@@ -288,7 +293,7 @@ static void emit_path(struct combine_diff_path ***tail,
 
 		keep = 1;
 		if (opt->pathchange)
-			keep = opt->pathchange(opt, p);
+			keep = opt->pathchange(opt, p, is_change);
 
 		if (keep) {
 			**tail = p;
@@ -518,26 +523,27 @@ static void ll_diff_tree_paths(
 		/* t = p[imin] */
 		if (cmp == 0) {
 			/* are either pi > p[imin] or diff(t,pi) != ø ? */
-			if (!opt->flags.find_copies_harder) {
-				for (i = 0; i < nparent; ++i) {
-					/* p[i] > p[imin] */
-					if (tp[i].entry.mode & S_IFXMIN_NEQ)
-						continue;
+			bool is_change = true;
 
-					/* diff(t,pi) != ø */
-					if (!oideq(&t.entry.oid, &tp[i].entry.oid) ||
-					    (t.entry.mode != tp[i].entry.mode))
-						continue;
+			for (i = 0; i < nparent; ++i) {
+				/* p[i] > p[imin] */
+				if (tp[i].entry.mode & S_IFXMIN_NEQ)
+					continue;
 
-					goto skip_emit_t_tp;
-				}
+				/* diff(t,pi) != ø */
+				if (!oideq(&t.entry.oid, &tp[i].entry.oid) ||
+				    (t.entry.mode != tp[i].entry.mode))
+					continue;
+
+				is_change = false;
+				break;
 			}
 
 			/* D += {δ(t,pi) if pi=p[imin];  "+a" if pi > p[imin]} */
-			emit_path(tail, base, opt, nparent,
-				  &t, tp, imin, depth);
+			if (is_change || opt->flags.find_copies_harder)
+				emit_path(tail, base, opt, nparent,
+					  &t, tp, imin, depth, is_change);
 
-		skip_emit_t_tp:
 			/* t↓,  ∀ pi=p[imin]  pi↓ */
 			update_tree_entry(&t);
 			update_tp_entries(tp, nparent);
@@ -547,7 +553,7 @@ static void ll_diff_tree_paths(
 		else if (cmp < 0) {
 			/* D += "+t" */
 			emit_path(tail, base, opt, nparent,
-				  &t, /*tp=*/NULL, -1, depth);
+				  &t, /*tp=*/NULL, -1, depth, true);
 
 			/* t↓ */
 			update_tree_entry(&t);
@@ -563,7 +569,7 @@ static void ll_diff_tree_paths(
 			}
 
 			emit_path(tail, base, opt, nparent,
-				  /*t=*/NULL, tp, imin, depth);
+				  /*t=*/NULL, tp, imin, depth, true);
 
 		skip_emit_tp:
 			/* ∀ pi=p[imin]  pi↓ */
-- 
2.52.0