This series textually depends on en/ort-perf-batch-14, but the ideas are orthogonal to it and orthogonal to previous series. It can be reviewed independently. This series is more about strmaps & memory pools than merge logic. CC'ing Peff since he reviewed the strmap work[1], and that work included a number of decisions that specifically had this series in mind. Changes since v1, addressing Eric's feedback: * Fixed a comment that became out-of-date in patch 1 * Swapped commits 2 and 3 so that one can better motivate the other. Note: Stolee also had an interesting question about whether we should tweak the mem_pool_*() API; he and I were both worried it was a bit much, so I've left it out unless others on list chime in with their opinions on that change. [1] https://lore.kernel.org/git/20201111200701.GB39046@xxxxxxxxxxxxxxxxxxxxxxx/ === Basic Optimization idea === In this series, I make use of memory pools to get faster allocations and deallocations for many data structures that tend to all be deallocated at the same time anyway. === 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: 204.2 ms ± 3.0 ms 198.3 ms ± 2.9 ms mega-renames: 1.076 s ± 0.015 s 661.8 ms ± 5.9 ms just-one-mega: 364.1 ms ± 7.0 ms 264.6 ms ± 2.5 ms 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 === Overall Results across all optimization work === This is my final prepared optimization series. It might be worth reviewing how my optimizations fared overall, comparing the original merge-recursive timings with three things: how much merge-recursive improved (as a side-effect of optimizing merge-ort), how much improvement we would have gotten from a hypothetical infinite parallelization of rename detection, and what I achieved at the end with merge-ort: Timings Infinite merge- merge- Parallelism recursive recursive of rename merge-ort v2.30.0 current detection current ---------- --------- ----------- --------- no-renames: 18.912 s 18.030 s 11.699 s 198.3 ms mega-renames: 5964.031 s 361.281 s 203.886 s 661.8 ms just-one-mega: 149.583 s 11.009 s 7.553 s 264.6 ms Speedup factors Infinite merge- merge- Parallelism recursive recursive of rename v2.30.0 current detection merge-ort ---------- --------- ----------- --------- no-renames: 1 1.05 1.6 95 mega-renames: 1 16.5 29 9012 just-one-mega: 1 13.6 20 565 And, for partial clone users: Factor reduction in number of objects needed Infinite merge- merge- Parallelism recursive recursive of rename v2.30.0 current detection merge-ort ---------- --------- ----------- --------- mega-renames: 1 1 1 181.3 === Caveat === It may be worth noting, though, that my optimization numbers above for merge-ort use test-tool fast-rebase. git rebase -s ort on the three testcases above is 5-20 times slower (taking 3.835s, 6.798s, and 1.235s, respectively). At this point, any further optimization work should go into making a faster full-featured rebase by copying the ideas from fast-rebase: avoid unnecessary process forking, avoid updating the index and working copy until either the rebase is finished or you hit a conflict (and don't write rebase metadata to disk until that point either), get rid of the glacially slow revision walking of the upstream side of history (nuke can_fast_forward(), make --reapply-cherry-picks the default) or at least don't revision walk so many times (multiple calls to get_merge_bases in can_fast_forward() plus a is_linear_history() walk, checking for upstream cherry-picks, probably more), turn off per-commit hooks that probably should have never been on anyway, etc. Elijah Newren (7): diffcore-rename: use a mem_pool for exact rename detection's hashmap merge-ort: add pool_alloc, pool_calloc, and pool_strndup wrappers merge-ort: set up a memory pool merge-ort: switch our strmaps over to using memory pools diffcore-rename, merge-ort: add wrapper functions for filepair alloc/dealloc merge-ort: store filepairs and filespecs in our mem_pool merge-ort: reuse path strings in pool_alloc_filespec diffcore-rename.c | 68 +++++++++++-- diffcore.h | 3 + merge-ort.c | 247 +++++++++++++++++++++++++++++++++++----------- 3 files changed, 252 insertions(+), 66 deletions(-) base-commit: c9ada8369e6575be488028aae0f654422a9b1410 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-990%2Fnewren%2Fort-perf-batch-15-v2 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-990/newren/ort-perf-batch-15-v2 Pull-Request: https://github.com/gitgitgadget/git/pull/990 Range-diff vs v1: 1: 9f8ab62b842 ! 1: ea08b34d29b diffcore-rename: use a mem_pool for exact rename detection's hashmap @@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options) rename_src[i].p->one); @@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options) + for (i = 0; i < rename_dst_nr; i++) renames += find_identical_files(&file_table, i, options); - /* Free the hash data structure and entries */ +- /* Free the hash data structure and entries */ - hashmap_clear_and_free(&file_table, struct file_similarity, entry); ++ /* Free the hash data structure (entries will be freed with the pool) */ + hashmap_clear(&file_table); return renames; 3: e30b8c8fea1 ! 2: fdfc2b93ba4 merge-ort: add pool_alloc, pool_calloc, and pool_strndup wrappers @@ Commit message or mem_pool_alloc, mem_pool_calloc, mem_pool_strndup depending on whether we have a non-NULL memory pool. Add these - functions; the next commit will make use of these. + functions; a subsequent commit will make use of these. Signed-off-by: Elijah Newren <newren@xxxxxxxxx> 2: 77367a69daa = 3: c7150869107 merge-ort: set up a memory pool 4: 8231c8e34cd = 4: dd8839b2843 merge-ort: switch our strmaps over to using memory pools 5: 2db932bc601 = 5: 560800a80ef diffcore-rename, merge-ort: add wrapper functions for filepair alloc/dealloc 6: 629d042884a = 6: 94d60c8a476 merge-ort: store filepairs and filespecs in our mem_pool 7: 17aa0a74849 = 7: fda885dabe6 merge-ort: reuse path strings in pool_alloc_filespec -- gitgitgadget
