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

This series builds on ort-readiness, but it's semantically orthogonal to the previous series and represents a new independent optimization.

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

This represents "Optimization #4" from my Git Merge 2020 talk[1]; the details are a bit more involved than I realized at the time, but the high level idea is the same.

=== Comparison to previous series ===

I previously noted that we had three major rename-related optimizations:

 * exact rename detection (applies when unmodified on renamed side)
 * skip-because-irrelevant (applies when unmodified on unrenamed side)
 * basename-guided rename detection (applies when basename unchanged)

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.

 * unlike the three previous optimizations, there are no requirements about
   the types of changes done to the file; it just caches renames on the
   "upstream" side of history for subsequent commit picking.

It's also worth noting despite wording about "remembering" or "caching" renames, that this optimization does NOT write this cache to disk; it's an in-memory only cache. When the rebase or cherry-pick completes (or hits a conflict and stops), the cache is discarded.

=== Results ===

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin performance work; instrument with trace2_region_* calls", 2020-10-28), the changes in just this series improves the performance as follows:

                     Before Series           After Series
no-renames:        5.665 s ±  0.129 s     5.624 s ±  0.077 s 
mega-renames:     11.435 s ±  0.158 s    10.213 s ±  0.032 s
just-one-mega:   494.2  ms ±  6.1  ms   497.6  ms ±  5.3  ms

By design, this optimization could not help the just-one-mega testcase. The gains for the other two testcases may look somewhat smaller than one would expect given the description (only ~10% for the mega-renames testcase), but the point was to spend less time detecting renames...and there just wasn't that much time spent in renames for these testcases before this series for us to remove. However, if we undid the basename-guided rename detection and skip-because-unnecessary optimizations, then this series alone would have improved performance as follows:

                   Before Basename Series   After Just This Series
    no-renames:      13.815 s ±  0.062 s      5.814 s ±  0.094 s
    mega-renames:  1799.937 s ±  0.493 s    303.225 s ±  1.330 s

Showing that this optimization has the ability to improve things when the other optimizations do not apply. In fact, when I originally implemented this optimization, it improved the mega-renames testcase by a factor of 2 (at the time, I did not have all the optimizations from ort-perf-batch-7 thru ort-perf-batch-10 in their current shape).

As a reminder, before any merge-ort/diffcore-rename performance work, the performance results we started with were:

no-renames-am: 6.940 s ± 0.485 s no-renames: 18.912 s ± 0.174 s mega-renames: 5964.031 s ± 10.459 s just-one-mega: 149.583 s ± 0.751 s

=== Further discussion of results ===

If we change our focus from absolute time taken, to the percentage of overall time spent on rename detection, then we find the following picture comparing our starting point at the beginning of the performance work to what we achieve at the end of this series:

       Percentage of time spent on rename detection
   
                  commit 557ac0350d      After this Series
no-renames:             39.4%                   0.2%
mega-renames:           96.6%                   2.7%
just-one-mega:          95.0%                   9.0%

Since this optimization is only applicable for the first two testcases (because the third only involves rebasing a single commit), even if this optimization had removed all the remaining time in rename detection it would have only sped it up the mega-renames case by ~12% rather than the 10% it achieved. This table makes it clear that our attempts to accelerate rename detection have succeeded, and any further work to accelerate merges needs to start concentrating on other areas.

[1] https://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf

[2] Well, almost no changes. There's technically a very narrow way that this could change the behavior; see the really long "Technically," bullet point in patch 3 for discussion of this.

Elijah Newren (7):
  merge-ort: add data structures for in-memory caching of rename
    detection
  merge-ort: populate caches of rename detection results
  merge-ort: add code to check for whether cached renames can be reused
  merge-ort: avoid accidental API mis-use
  merge-ort: preserve cached renames for the appropriate side
  merge-ort: add helper functions for using cached renames
  merge-ort, diffcore-rename: employ cached renames when possible

 diffcore-rename.c |  22 +++-
 diffcore.h        |   3 +-
 merge-ort.c       | 273 +++++++++++++++++++++++++++++++++++++++++++---
 merge-ort.h       |   2 +
 4 files changed, 282 insertions(+), 18 deletions(-)

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