Hi,

On Sat, Feb 27, 2021 at 7:58 PM Elijah Newren via GitGitGadget
[off-list ref] wrote:

This series depends textually on ort-perf-batch-8, but semantically it's
almost completely unrelated and can be reviewed without any familiarity with
any of the previous patch series.

=== Basic Optimization idea ===

The basic idea here is that if side A of history:

 * only modifies/adds/deletes a few files
 * adds new files to few if any of the directories that side B deleted or
   renamed

then when we do rename detection on side B we can avoid even looking at most
(and perhaps even all) paths that side B deleted. Since commits being
rebased or cherry-picked tend to only modify a few files, this optimization
tends to be particularly effective for rebases and cherry-picks.

After thinking it over a bit more, there's a much better way to put
this summary:

    We only need expensive rename detection on the subset of files
changed on *both* sides (for the most part).

This is because:

1. The primary reason for rename detection in merges is enabling
three-way content merges
2. The purpose of three-way content merges is reconciling changes when
*both* sides of history modified some file
3. If a file was only modified by the side that renamed the file, then
detecting the rename is irrelevant; we'll get the same answer without
knowing about the rename.
4. (Well...there are rare cases where we need the rename for reasons
other than three-way content merges.  Patch 5 explains those.)