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

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