Re: [PATCH 0/7] Optimization batch 11: avoid repeatedly detecting same renames

[Junio C Hamano <gitster@pobox.com>]

"Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:

> === Basic Optimization idea ===
>
> This series avoids repeatedly detecting the same renames in a sequence of
> merges such as a rebase or cherry-pick of several commits. When there are
> many renames between the old base and the new base, traditionally all those
> renames are re-detected for every commit that is transplanted. This
> optimization avoids redoing that work.

Unless this section is easily understandable, the readers have no
incentive to read on, but the above is a bit too hand wavy.

> This one adds a fourth (remember-renames), with some interesting properties:
>
>  * unlike basename-guided rename detection, there are no behavioral changes
>    (there is no heuristic involved)[2].
>
>  * like skip-because-irrelevant, this optimization does not apply to all git
>    commands using the rename machinery. In fact, this one is even more
>    restrictive since it is ONLY useful for rebases and cherry-picks (not
>    even merges), and only for second and later commits in a linear series.

So, is it correct to understand that one case this would help is
this scenario?

 ---o---o---o---X---o---o---o---O ours
     \
      A---B---C topic

where there is a side branch A--B--C that touched some files, while
on our side, there is a commit X that is unknown to the side branch
that renamed these files.  Now we want to transplant the side topic
to the tip of our history, replaying the changes A--B--C made to
these files under their original name to the corresponding files
that have been renamed.

And each step in this "rebase" is a 3-way merge of commits A, B and
C onto HEAD, using the parent of the commit being cherrk-picked as a
virtual common ancestor.  Which means

 - To transplant A (i.e. the first step), we'd compare the diff of
   A^..O (i.e. what our side did, including the renames done at X)
   and diff of A^..A (i.e. what the first commit did in the range),
   and the former does quite a lot of rename detection.

 - After transplanting B (i.e. the second step), then we'd compare
   the diff of A^..A' (where A' is A cherry-picked on O, i.e. the
   result of the previous step).  If we are lucky, O..A' did not
   rename anything so the renames done in A^..O (i.e. what we
   detected during the first step) and A^..A' (i.e. what we should
   be computing for this second step) should be quite similar.

   If we assume that the "quite similar" is good enough, then we can
   blindly reuse the record of "<path in A^> correspnds to <path in
   O>" as if it were "<path in A^> corresponds to <path in A'>".

 - Do the same for C, pretending that renames discovered between A^
   and O is identical to the renames between A^ and B' (i.e. the
   result of cherry-picking A--B on top of O).