Re: [PATCH 0/8] Optimization batch 9: avoid detecting irrelevant renames

From: Elijah Newren <newren@gmail.com>
Date: Mar 4, 2021, 07:54 UTC
Message-ID: <CABPp-BEv1BN66A1jJ+P+HThyFSwM9mFevd-uj9FWbnWyMtsCNQ@mail.gmail.com>
In-Reply-To: <pull.845.git.1614484707.gitgitgadget@gmail.com>

Hi,

On Sat, Feb 27, 2021 at 7:58 PM Elijah Newren via GitGitGadget <gitgitgadget@gmail.com> wrote:

Show 17 quoted lines

>
> 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.)