[PATCH 0/3] Optimization batch 7: use file basenames to guide rename detection

["Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com>]

This series depends on ort-perf-batch-6[1], which has not yet appeared in
seen despite being reviewed by both Junio and Stolee.

This series uses file basenames in a basic fashion to guide rename
detection. It represents "Optimization #3" from my Git Merge 2020 talk[2],
and is based on the fact that real world repositories tend to have a large
majority of the renames they have done in history be ones that do not affect
the basenames of the renamed files (in other words, they are simply moving
files into different directories). 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:       13.815 s ±  0.062 s    13.138 s ±  0.086 s
mega-renames:   1799.937 s ±  0.493 s   169.488 s ±  0.494 s
just-one-mega:    51.289 s ±  0.019 s     5.061 s ±  0.017 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://lore.kernel.org/git/xmqqlfc4byt6.fsf@gitster.c.googlers.com/ [2]
https://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf

Elijah Newren (3):
  diffcore-rename: compute basenames of all source and dest candidates
  diffcore-rename: complete find_basename_matches()
  diffcore-rename: guide inexact rename detection based on basenames

 diffcore-rename.c | 181 +++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 177 insertions(+), 4 deletions(-)


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