[PATCH 2/3] builtin/log: prefetch necessary blobs for `git cherry`

["Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com>]

From: Elijah Newren <newren@gmail.com>

In partial clones, `git cherry` fetches necessary blobs on-demand one
at a time, which can be very slow.  We would like to prefetch all
necessary blobs upfront.  To do so, we need to be able to first figure
out which blobs are needed.

`git cherry` does its work in a two-phase approach: first computing
header-only IDs (based on file paths and modes), then falling back to
full content-based IDs only when header-only IDs collide -- or, more
accurately, whenever the oidhash() of the header-only object_ids
collide.

patch-ids.c handles this by creating an ids->patches hashmap that has
all the data we need, but the problem is that any attempt to query the
hashmap will invoke the patch_id_neq() function on any colliding objects,
which causes the on-demand fetching.

Insert a new prefetch_cherry_blobs() function before checking for
collisions.  Use a temporary replacement on the ids->patches.cmpfn
in order to enumerate the blobs that would be needed without yet
fetching them, and then fetch them all at once, then restore the old
ids->patches.cmpfn.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/log.c                                 | 125 +++++++++++
 investigations/cherry-prefetch-design-spec.md | 210 ++++++++++++++++++
 t/t3500-cherry.sh                             |  18 ++
 3 files changed, 353 insertions(+)
 create mode 100644 investigations/cherry-prefetch-design-spec.md

diff --git a/builtin/log.c b/builtin/log.c
index 8c0939dd42..df19876be6 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -21,10 +21,12 @@
 #include "color.h"
 #include "commit.h"
 #include "diff.h"
+#include "diffcore.h"
 #include "diff-merges.h"
 #include "revision.h"
 #include "log-tree.h"
 #include "oid-array.h"
+#include "oidset.h"
 #include "tag.h"
 #include "reflog-walk.h"
 #include "patch-ids.h"
@@ -43,9 +45,11 @@
 #include "utf8.h"
 
 #include "commit-reach.h"
+#include "promisor-remote.h"
 #include "range-diff.h"
 #include "tmp-objdir.h"
 #include "tree.h"
+#include "userdiff.h"
 #include "write-or-die.h"
 
 #define MAIL_DEFAULT_WRAP 72
@@ -2602,6 +2606,125 @@ static void print_commit(char sign, struct commit *commit, int verbose,
 	}
 }
 
+/*
+ * Enumerate blob OIDs from a single commit's diff, inserting them into blobs.
+ * Skips files whose userdiff driver explicitly declares binary status
+ * (drv->binary > 0), since patch-ID uses oid_to_hex() for those and
+ * never reads blob content.  Use userdiff_find_by_path() since
+ * diff_filespec_load_driver() is static in diff.c.
+ *
+ * Clean up with diff_queue_clear() (from diffcore.h).
+ */
+static void collect_diff_blob_oids(struct commit *commit,
+				   struct diff_options *opts,
+				   struct oidset *blobs)
+{
+	struct diff_queue_struct *q;
+
+	/*
+	 * Merge commits are filtered out by patch_id_defined() in patch-ids.c,
+	 * so we'll never be called with one.
+	 */
+	assert(!commit->parents || !commit->parents->next);
+
+	if (commit->parents)
+		diff_tree_oid(&commit->parents->item->object.oid,
+			      &commit->object.oid, "", opts);
+	else
+		diff_root_tree_oid(&commit->object.oid, "", opts);
+	diffcore_std(opts);
+
+	q = &diff_queued_diff;
+	for (int i = 0; i < q->nr; i++) {
+		struct diff_filepair *p = q->queue[i];
+		struct userdiff_driver *drv;
+
+		/* Skip binary files */
+		drv = userdiff_find_by_path(opts->repo->index, p->one->path);
+		if (drv && drv->binary > 0)
+			continue;
+
+		if (DIFF_FILE_VALID(p->one))
+			oidset_insert(blobs, &p->one->oid);
+		if (DIFF_FILE_VALID(p->two))
+			oidset_insert(blobs, &p->two->oid);
+	}
+	diff_queue_clear(q);
+}
+
+static int always_match(const void *cmp_data UNUSED,
+			const struct hashmap_entry *entry1 UNUSED,
+			const struct hashmap_entry *entry2 UNUSED,
+			const void *keydata UNUSED)
+{
+	return 0;
+}
+
+/*
+ * Prefetch blobs for git cherry in partial clones.
+ *
+ * Called between the revision walk (which builds the head-side
+ * commit list) and the has_commit_patch_id() comparison loop.
+ *
+ * Uses a cmpfn-swap trick to avoid reading blobs: temporarily
+ * replaces the hashmap's comparison function with a trivial
+ * always-match function, so hashmap_get()/hashmap_get_next() match
+ * any entry with the same oidhash bucket.  These are the set of oids
+ * that would trigger patch_id_neq() during normal lookup and cause
+ * blobs to be read on demand, and we want to prefetch them all at
+ * once instead.
+ */
+static void prefetch_cherry_blobs(struct repository *repo,
+				  struct commit_list *list,
+				  struct patch_ids *ids)
+{
+	struct oidset blobs = OIDSET_INIT;
+	hashmap_cmp_fn original_cmpfn;
+
+	/* Exit if we're not in a partial clone */
+	if (!repo_has_promisor_remote(repo))
+		return;
+
+	/* Save original cmpfn, replace with always_match */
+	original_cmpfn = ids->patches.cmpfn;
+	ids->patches.cmpfn = always_match;
+
+	/* Find header-only collisions, gather blobs from those commits */
+	for (struct commit_list *l = list; l; l = l->next) {
+		struct commit *c = l->item;
+		bool match_found = false;
+		for (struct patch_id *cur = patch_id_iter_first(c, ids);
+		     cur;
+		     cur = patch_id_iter_next(cur, ids)) {
+			match_found = true;
+			collect_diff_blob_oids(cur->commit, &ids->diffopts,
+					       &blobs);
+		}
+		if (match_found)
+			collect_diff_blob_oids(c, &ids->diffopts, &blobs);
+	}
+
+	/* Restore original cmpfn */
+	ids->patches.cmpfn = original_cmpfn;
+
+	/* If we have any blobs to fetch, fetch them */
+	if (oidset_size(&blobs)) {
+		struct oid_array to_fetch = OID_ARRAY_INIT;
+		struct oidset_iter iter;
+		const struct object_id *oid;
+
+		oidset_iter_init(&blobs, &iter);
+		while ((oid = oidset_iter_next(&iter)))
+			oid_array_append(&to_fetch, oid);
+
+		promisor_remote_get_direct(repo, to_fetch.oid, to_fetch.nr);
+
+		oid_array_clear(&to_fetch);
+	}
+
+	oidset_clear(&blobs);
+}
+
 int cmd_cherry(int argc,
 	       const char **argv,
 	       const char *prefix,
@@ -2673,6 +2796,8 @@ int cmd_cherry(int argc,
 		commit_list_insert(commit, &list);
 	}
 
+	prefetch_cherry_blobs(the_repository, list, &ids);
+
 	for (struct commit_list *l = list; l; l = l->next) {
 		char sign = '+';
 
diff --git a/investigations/cherry-prefetch-design-spec.md b/investigations/cherry-prefetch-design-spec.md
new file mode 100644
index 0000000000..a499d9538e
--- /dev/null
+++ b/investigations/cherry-prefetch-design-spec.md
@@ -0,0 +1,210 @@
+# Design Spec: Batch Blob Prefetch for `git cherry` in Partial Clones
+
+## Problem
+
+In a partial clone with `--filter=blob:none`, `git cherry` compares
+commits using patch IDs.  Patch IDs are computed in two phases:
+
+1. Header-only: hashes file paths and mode changes only (no blob reads)
+2. Full: hashes actual diff content (requires reading blobs)
+
+Phase 2 only runs when two commits have matching header-only IDs
+(i.e. they modify the same set of files with the same modes).  This
+is common — any two commits touching the same file(s) will collide.
+
+When phase 2 needs a blob that isn't local, it triggers an on-demand
+promisor fetch.  Each fetch is a separate network round-trip.  With
+many collisions, this means many sequential fetches.
+
+## Solution Overview
+
+Add a preparatory pass before the existing comparison loop in
+`cmd_cherry()` that:
+
+1. Identifies which commit pairs will collide on header-only IDs
+2. Collects all blob OIDs those commits will need
+3. Batch-prefetches them in one fetch
+
+After this pass, the existing comparison loop runs as before, but
+all needed blobs are already local, so no on-demand fetches occur.
+
+## Detailed Design
+
+### 1. No struct changes to patch_id
+
+The existing `struct patch_id` and `patch_id_neq()` are not
+modified.  `is_null_oid()` remains the sentinel for "full ID not
+yet computed".  No `has_full_patch_id` boolean, no extra fields.
+
+Key insight: `init_patch_id_entry()` stores only `oidhash()` (the
+first 4 bytes of the header-only ID) in the hashmap bucket key.
+The real `patch_id_neq()` comparison function is invoked only when
+`hashmap_get()` or `hashmap_get_next()` finds entries with a
+matching oidhash — and that comparison triggers blob reads.
+
+The prefetch needs to detect exactly those oidhash collisions
+*without* triggering blob reads.  We achieve this by temporarily
+swapping the hashmap's comparison function.
+
+### 2. The prefetch function (in builtin/log.c)
+
+This function takes the repository, the head-side commit list (as
+built by the existing revision walk in `cmd_cherry()`), and the
+patch_ids structure (which contains the upstream entries).
+
+#### 2.1 Early exit
+
+If the repository has no promisor remote, return immediately.
+Use `repo_has_promisor_remote()` from promisor-remote.h.
+
+#### 2.2 Swap in a trivial comparison function
+
+Save `ids->patches.cmpfn` (the real `patch_id_neq`) and replace
+it with a trivial function that always returns 0 ("equal").
+
+```
+static int patch_id_match(const void *unused_cmpfn_data,
+                          const struct hashmap_entry *a,
+                          const struct hashmap_entry *b,
+                          const void *unused_keydata)
+{
+    return 0;
+}
+```
+
+With this cmpfn in place, `hashmap_get()` and `hashmap_get_next()`
+will match every entry in the same oidhash bucket — exactly the
+same set that would trigger `patch_id_neq()` during normal lookup.
+No blob reads occur because we never call the real comparison
+function.
+
+#### 2.3 For each head-side commit, probe for collisions
+
+For each commit in the head-side list:
+
+- Use `patch_id_iter_first(commit, ids)` to probe the upstream
+  hashmap.  This handles `init_patch_id_entry()` + hashmap lookup
+  internally.  With our swapped cmpfn, it returns any upstream
+  entry whose oidhash matches — i.e. any entry that *would*
+  trigger `patch_id_neq()` during the real comparison loop.
+  (Merge commits are already handled — `patch_id_iter_first()`
+  returns NULL for them via `patch_id_defined()`.)
+- If there's a match: collect blob OIDs from the head-side commit
+  (see section 3).
+- Then walk `patch_id_iter_next()` to find ALL upstream entries
+  in the same bucket.  For each, collect blob OIDs from that
+  upstream commit too.  (Multiple upstream commits can share the
+  same oidhash bucket.)
+- Collect blob OIDs from the first upstream match too (from
+  `patch_id_iter_first()`).
+
+We need blobs from BOTH sides because `patch_id_neq()` computes
+full patch IDs for both the upstream and head-side commit when
+comparing.
+
+#### 2.4 Restore the original comparison function
+
+Set `ids->patches.cmpfn` back to the saved value (patch_id_neq).
+This MUST happen before returning — the subsequent
+`has_commit_patch_id()` loop needs the real comparison function.
+
+#### 2.5 Batch prefetch
+
+If the oidset is non-empty, populate an oid_array from it using
+`oidset_iter_first()`/`oidset_iter_next()`, then call
+`promisor_remote_get_direct(repo, oid_array.oid, oid_array.nr)`.
+
+This is a single network round-trip regardless of how many blobs.
+
+#### 2.6 Cleanup
+
+Free the oid_array and the oidset.
+
+### 3. Collecting blob OIDs from a commit (helper function)
+
+Given a commit, enumerate the blobs its diff touches.  Takes an
+oidset to insert into (provides automatic dedup — consecutive
+commits often share blob OIDs, e.g. B:foo == C^:foo when C's
+parent is B).
+
+- Compute the diff: `diff_tree_oid()` for commits with a parent,
+  `diff_root_tree_oid()` for root commits.  Then `diffcore_std()`.
+- These populate the global `diff_queued_diff` queue.
+- For each filepair in the queue:
+  - Check the userdiff driver for the file path.  If the driver
+    explicitly declares the file as binary (`drv->binary != -1`),
+    skip it.  Reason: patch-ID uses `oid_to_hex()` for binary
+    files (see diff.c around line 6652) and never reads the blob.
+    Use `userdiff_find_by_path()` (NOT `diff_filespec_load_driver`
+    which is static in diff.c).
+  - For both sides of the filepair (p->one and p->two): if the
+    side is valid (`DIFF_FILE_VALID`) and has a non-null OID,
+    check the dedup oidset — `oidset_insert()` handles dedup
+    automatically (returns 1 if newly inserted, 0 if duplicate).
+- Clear the diff queue with `diff_queue_clear()` (from diffcore.h,
+  not diff.h).
+
+Note on `drv->binary`: The value -1 means "not set" (auto-detect
+at read time by reading the blob); 0 means explicitly text (will
+be diffed, blob reads needed); positive means explicitly binary
+(patch-ID uses `oid_to_hex()`, no blob read needed).
+
+The correct skip condition is `drv && drv->binary > 0` — skip
+only known-binary files.  Do NOT use `drv->binary != -1`, which
+would also skip explicitly-text files that DO need blob reads.
+(The copilot reference implementation uses `!= -1`, which is
+technically wrong but harmless in practice since explicit text
+attributes are rare.)
+
+### 4. Call site in cmd_cherry()
+
+Insert the call between the revision walk loop (which builds the
+head-side commit list) and the comparison loop (which calls
+`has_commit_patch_id()`).
+
+### 5. Required includes in builtin/log.c
+
+- promisor-remote.h  (for repo_has_promisor_remote,
+                       promisor_remote_get_direct)
+- userdiff.h         (for userdiff_find_by_path)
+- oidset.h           (for oidset used in blob OID dedup)
+- diffcore.h         (for diff_queue_clear)
+
+## Edge Cases
+
+- No promisor remote: early return, zero overhead
+- No collisions: probes the hashmap for each head-side commit but
+  finds no bucket matches, no blobs collected, no fetch issued
+- Merge commits in head-side list: skipped (no patch ID defined)
+- Root commits (no parent): use diff_root_tree_oid instead of
+  diff_tree_oid
+- Binary files (explicit driver): skipped, patch-ID doesn't read
+  them
+- The cmpfn swap approach matches at oidhash granularity (4 bytes),
+  which is exactly what the hashmap itself uses to trigger
+  patch_id_neq().  This means we prefetch for every case the real
+  code would trigger, plus rare false-positive oidhash collisions
+  (harmless: we fetch a few extra blobs that won't end up being
+  compared).  No under-fetching is possible.
+
+## Testing
+
+See t/t3500-cherry.sh on the copilot-faster-partial-clones branch
+for two tests:
+
+Test 5: "cherry batch-prefetches blobs in partial clone"
+  - Creates server with 3 upstream + 3 head-side commits modifying
+    the same file (guarantees collisions)
+  - Clones with --filter=blob:none
+  - Runs `git cherry` with GIT_TRACE2_PERF
+  - Asserts exactly 1 fetch (batch) instead of 6 (individual)
+
+Test 6: "cherry prefetch omits blobs for cherry-picked commits"
+  - Creates a cherry-pick scenario (divergent branches, shared
+    commit cherry-picked to head side)
+  - Verifies `git cherry` correctly identifies the cherry-picked
+    commit as "-" and head-only commits as "+"
+  - Important: the head side must diverge before the cherry-pick
+    so the cherry-pick creates a distinct commit object (otherwise
+    the commit hash is identical and it's in the symmetric
+    difference, not needing patch-ID comparison at all)
diff --git a/t/t3500-cherry.sh b/t/t3500-cherry.sh
index 78c3eac54b..17507d9a28 100755
--- a/t/t3500-cherry.sh
+++ b/t/t3500-cherry.sh
@@ -78,4 +78,22 @@ test_expect_success 'cherry ignores whitespace' '
 	test_cmp expect actual
 '
 
+# Reuse the expect file from the previous test, in a partial clone
+test_expect_success 'cherry in partial clone does bulk prefetch' '
+	test_config uploadpack.allowfilter 1 &&
+	test_config uploadpack.allowanysha1inwant 1 &&
+	test_when_finished "rm -rf copy" &&
+
+	git clone --bare --filter=blob:none file://"$(pwd)" copy &&
+	(
+		cd copy &&
+		GIT_TRACE2_EVENT="$(pwd)/trace.output" git cherry upstream-with-space feature-without-space >actual &&
+		test_cmp ../expect actual &&
+
+		grep "child_start.*fetch.negotiationAlgorithm" trace.output >fetches &&
+		test_line_count = 1 fetches &&
+		test_trace2_data promisor fetch_count 4 <trace.output
+	)
+'
+
 test_done
-- 
gitgitgadget