[RFC PATCH 0/9] Improve rename detection performance in merge recursive

This series depends on BOTH my rename-limits and directory-detection series (https://public-inbox.org/git/20171110173956.25105-1-newren@gmail.com/ and https://public-inbox.org/git/20171110190550.27059-1-newren@gmail.com/). This series could be modified to be submitted with no dependencies on those series, but it'd end up causing lots of merging conflicts, and having this series depend on the other two seemed most logical to me.

This patch series tries to improve performance rename detection performance in merge recursive where possible. In particular, I was guided by a specific usecase of cherry-picking a small change (by which I mean 7 files with small modifications and one new file) in a repo that has thousands of renames, due to some high-level directories having been renamed. Some of the changes should help rename detection performance in general, but the greatest benefit will be found when one side of history only makes a small number of changes. For my usecase, I dropped the time needed for the cherry-pick from over 9 minutes, down to about 16 seconds.

RFC because:

  * I believe the patch with the biggest performance improvement will
    break directory rename detection in specific, limited cases (which
    are not yet represented in the testsuite).  Should be fixable; I
    just need to implement the fix.  (The fix may reduce the
    performance improvement slightly).
    
  * This series includes changes to conflict handling for conflict
    types that involve two colliding files.  I think the new behavior
    is strictly better, but this is the kind of thing I really need to
    make sure others agree with; comments very welcome.  (Patches 2--6)

  * 16 seconds is still annoyingly slow; we should be able to do better.
    I have one or two ideas.  But since others are asking about the
    performance of small cherry-picks in large repos with lots of renames,
    I figure it's worth posting what I have so far.

Elijah Newren (9):
  diffcore-rename: No point trying to find a match better than exact
  merge-recursive: Avoid unnecessary string list lookups
  merge-recursive: New function for better colliding conflict
    resolutions
  Add testcases for improved file collision conflict handling
  merge-recursive: Fix rename/add conflict handling
  merge-recursive: Improve handling for rename/rename(2to1) conflicts
  merge-recursive: Improve handling for add/add conflicts
  merge-recursive: Accelerate rename detection
  diffcore-rename: Filter rename_src list when possible

 diff.c                               |   1 +
 diff.h                               |   7 +
 diffcore-rename.c                    |  85 ++++++-
 merge-recursive.c                    | 452 ++++++++++++++++++++++++-----------
 t/t2023-checkout-m.sh                |   2 +-
 t/t3418-rebase-continue.sh           |  27 ++-
 t/t3504-cherry-pick-rerere.sh        |  19 +-
 t/t4200-rerere.sh                    |  12 +-
 t/t6020-merge-df.sh                  |   4 +-
 t/t6024-recursive-merge.sh           |  35 +--
 t/t6025-merge-symlinks.sh            |   9 +-
 t/t6031-merge-filemode.sh            |   4 +-
 t/t6036-recursive-corner-cases.sh    |  19 +-
 t/t6042-merge-rename-corner-cases.sh | 212 +++++++++++++++-
 t/t6043-merge-rename-directories.sh  |  13 +-
 t/t7060-wtstatus.sh                  |   1 +
 t/t7064-wtstatus-pv2.sh              |   4 +-
 t/t7506-status-submodule.sh          |  11 +-
 t/t7610-mergetool.sh                 |  28 +--
 19 files changed, 722 insertions(+), 223 deletions(-)