[PATCH 0/7] Final optimization batch (#15): use memory pools

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.

[1] https://lore.kernel.org/git/20201111200701.GB39046@coredump.intra.peff.net/

=== 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: set up a memory pool
  merge-ort: add pool_alloc, pool_calloc, and pool_strndup wrappers
  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 |  66 +++++++++++--
 diffcore.h        |   3 +
 merge-ort.c       | 247 +++++++++++++++++++++++++++++++++++-----------
 3 files changed, 251 insertions(+), 65 deletions(-)

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