This series depends on en/merge-ort-perf.
For the very curious who are wondering about the first five optimization
batches; see the end of this email.
This series makes full use of exact renames; see commit messages for
details. It represents "Optimization #1" from my Git Merge 2020 talk[1]. 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: 14.263 s ± 0.053 s 13.815 s ± 0.062 s
mega-renames: 5504.231 s ± 5.150 s 1799.937 s ± 0.493 s
just-one-mega: 158.534 s ± 0.498 s 51.289 s ± 0.019 s
As a reminder, before any merge-ort/diffcore-rename performance work, the
performance results we started with (as noted in the same commit message)
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
[1]
https://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf
=== Previous optimization batches ===
I'm labeling this as the "6th" batch, due to other optimizations submitted
previously, and a number of optimizations baked into the design of
fast-rebase and merge-ort.
1. Previously submitted hashmap/strmap optimizations 1a) 33f20d8217
(hashmap: introduce a new hashmap_partial_clear()) 1b) 6ccdfc2a20
(strmap: enable faster clearing and reusing of strmaps) 1c) a208ec1f0b
(strmap: enable allocations to come from a mem_pool) 1d) 23a276a9c4
(strmap: take advantage of FLEXPTR_ALLOC_STR when relevant)
2. Previously submitted diffcore-rename optimizations 2a) b970b4ef62
(diffcore-rename: simplify and accelerate register_rename_src()) 2b)
9db2ac5616 (diffcore-rename: accelerate rename_dst setup) 2c) 350410f6b1
(diffcore-rename: remove unnecessary duplicate entry checks)
3. fast-rebase optimizations 3a) Avoid updating working-tree/index with
every intermediate patch 3b) avoid reading/writing rebase metadata until
conflict or completion
4. Small stuff baked into merge-ort design 4a) Using pahole to note I can
reduce size of merged_info by 8 bytes 4b) Avoid recomparing hashes (due
to use of match_masks) 4c) Avoid unconditional dropping and re-reading
of the index 4d) avoid checking index matches HEAD with every patch; do
it at start only
5. Big stuff baked into merge-ort design 5a) Avoid quadratic behavior with
O(N) insertions/removals of index entries 5b) Avoid numerous expensive
mini-tree traversals done by merge-recursive 5c) Avoid recursing into
trees where both sides match merge base
Elijah Newren (2):
diffcore-rename: no point trying to find a match better than exact
diffcore-rename: filter rename_src list when possible
diffcore-rename.c | 69 ++++++++++++++++++++++++++++++++++++++++++-----
1 file changed, 62 insertions(+), 7 deletions(-)
base-commit: 557ac0350d9efa1f59c708779ca3fb3aee121131
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-842%2Fnewren%2Fort-perf-batch-6-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-842/newren/ort-perf-batch-6-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/842
--
gitgitgadget
