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
--
gitgitgadget
