[PATCH 0/5] Optimization batch 13: partial clone optimizations for merge-ort

This series optimizes blob downloading in merges for partial clones. It can apply on master.

=== Conflict heads up ===

This series has two minor textual conflicts with https://lore.kernel.org/git/cover.1622580781.git.jonathantanmy@google.com/, because we both add a repo parameter to fetch_objects() but Jonathan makes additional other nearby changes. If it'd help, I can rebase my series on his if he resolves the GIT_TEST_DEFAULT_HASH=sha256 issue, but I thought I'd send this out while the topic is fresh on Jonathan's mind.

(This topic is semantically and textually independent of my other in-flight and not-yet-submitted ort-perf-batch-* topics, so this series need not include those.)

=== Basic Optimization idea ===

merge-ort was designed to minimize the computation needed to complete a merge, and much of that (particularly the "irrelevant rename" determinations) also dramatically reduced the amount of data needed for the merge. Reducing the amount of data needed to do computations ought to benefit partial clones as well by enabling them to download less information. However, my previous series didn't modify the prefetch() command in diffcore-rename to take advantage of these reduced data requirements. This series changes that.

Further, although diffcore-rename batched downloads of objects for rename detection, the merge machinery did not do the same for three-way content merges of files. This series adds batch downloading of objects within merge-ort to correct that.

=== Modified performance measurement method ===

The testcases I've been using so far to measure performance were not run in a partial clone, so they aren't directly usable for comparison. Further, partial clone performance depends on network speed which can be highly variable. So I want to modify one of the existing testcases slightly and focus on two different but more stable metrics:

 1. Number of git fetch operations during rebase
 2. Number of objects fetched during rebase

The first of these should already be decent due to Jonathan Tan's work to batch fetching of missing blobs during rename detection (see commit 7fbbcb21b1 ("diff: batch fetching of missing blobs", 2019-04-05)), so we are mostly looking to optimize the second but would like to also decrease the first if possible.

The testcase we will look at will be a modification of the mega-renames testcase from commit 557ac0350d ("merge-ort: begin performance work; instrument with trace2_region_* calls", 2020-10-28). In particular, we change

$ git clone \
    git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git

to

$ git clone --sparse --filter=blob:none \
    https://github.com/github/linux

(The change in clone URL is just to get a server that supports the filter predicate.)

We otherwise keep the test the same (in particular, we do not add any calls to "git-sparse checkout {set,add}" which means that the resulting repository will only have 7 total blobs from files in the toplevel directory before starting the rebase).

=== Results ===

For the mega-renames testcase noted above (which rebases 35 commits across an upstream with ~26K renames in a partial clone), I found the following results for our metrics of interest:

     Number of `git fetch` ops during rebase

                     Before Series   After Series
merge-recursive:          62              63
merge-ort:                30              20

     Number of objects fetched during rebase

                     Before Series   After Series
merge-recursive:         11423          11423
merge-ort:               11391             63

So, we have a significant reduction (factor of ~3 relative to merge-recursive) in the number of git fetch operations that have to be performed in a partial clone to complete the rebase, and a dramatic reduction (factor of ~180) in the number of objects that need to be fetched.

=== Summary ===

It's worth pointing out that merge-ort after the series needs only ~1.8 blobs per commit being transplanted to complete this particular rebase. Essentially, this reinforces the fact the optimization work so far has taken rename detection from often being an overwhelmingly costly portion of a merge (leading many to just capitulate on it), to what I have observed in my experience so far as being just a minor cost for merges.

Elijah Newren (5):
  promisor-remote: output trace2 statistics for number of objects
    fetched
  t6421: add tests checking for excessive object downloads during merge
  diffcore-rename: allow different missing_object_cb functions
  diffcore-rename: use a different prefetch for basename comparisons
  merge-ort: add prefetching for content merges

 diffcore-rename.c              | 149 +++++++++---
 merge-ort.c                    |  50 ++++
 promisor-remote.c              |   7 +-
 t/t6421-merge-partial-clone.sh | 433 +++++++++++++++++++++++++++++++++
 4 files changed, 605 insertions(+), 34 deletions(-)
 create mode 100755 t/t6421-merge-partial-clone.sh

base-commit: 01352fcdf3a96480ffa4e25a103a83a9e5d7f67a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-969%2Fnewren%2Fort-perf-batch-13-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-969/newren/ort-perf-batch-13-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/969