Re: [PATCH 3/3] diffcore-rename: guide inexact rename detection based on basenames

On 2/8/2021 3:27 AM, Elijah Newren wrote:

Hi,

On Sun, Feb 7, 2021 at 6:38 AM Derrick Stolee [off-list ref] wrote:

quoted

On 2/6/21 5:52 PM, Elijah Newren via GitGitGadget wrote:

quoted

From: Elijah Newren <redacted>

Make use of the new find_basename_matches() function added in the last
two patches, to find renames more rapidly in cases where we can match up
files based on basenames.

This is a valuable heuristic.

quoted

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:

                            Before                  After
    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

These numbers are very impressive.

Before I get too deep into reviewing these patches, I do want
to make it clear that the speed-up is coming at the cost of
a behavior change. We are restricting the "best match" search
to be first among files with common base name (although maybe
I would use 'suffix'?). If we search for a rename among all
additions and deletions ending the ".txt" we might find a
similarity match that is 60% and declare that a rename, even
if there is a ".txt" -> ".md" pair that has a 70% match.

I'm glad you all are open to possible behavioral changes, but I was
proposing a much smaller behavioral change that is quite different
than what you have suggested here.  Perhaps my wording was poor; I
apologize for forgetting that "basename" has different meanings in
different contexts.  Let me try again; I am not treating the filename
extension as special in any manner here; by "basename" I just mean the
portion of the path ignoring any leading directories.  Thus
    src/foo.txt
might be a good match against
    source/foo.txt
but this optimization as a preliminary step would not consider
matching src/foo.txt against any of
    source/bar.txt
    source/foo.md
since the basenames ('bar.txt' and 'foo.md') do not match our original
file's basename ('foo.txt').

Of course, if this preliminary optimization step fails to find another
"foo.txt" to match src/foo.txt against (or finds more than one and
thus doesn't compare against any of them), then the fallback inexact
rename detection matrix might match it against either of those two
latter paths, as it always has.

Thank you for making it clear that I had misunderstood what the
optimization is actually doing. A much more narrow scope makes
more sense, and avoids the quadratic problem even when many files
of the same suffix are renamed.

quoted

This could be documented in a test case, to demonstrate that
we are making this choice explicitly.

My test is thus bogus, but you could have a similar one for
your actual optimization.

quoted

So, in this way, we are changing the optimization function
that is used to determine the "best" rename available. It
might be good to update documentation for how we choose
renames:

Seems reasonable; I'll add some commentary below on the rules...

Your commentary is helpful. I look forward to reading your
carefully-written docs in the next version ;).

quoted

     i. among files with the same basename (trailer
        after final '.') select pairs with highest
        similarity.

This is an interesting idea, but is not what I implemented.

That's what I get for reading the commit messages quickly and
commenting on what I _think_ is going on instead of actually
reading the code carefully. Sorry about that.

 It is
possible that your suggestion is also a useful optimization; it'd be
hard to know without trying.  However, as noted in optimization batch
8 that I'll be submitting later, I'm worried about having any
optimization pre-steps doing more than O(1) comparisons per path (and
here you suggest comparing each .txt file with all other .txt files);
doing that can interact badly with optimization batch 9.
Additionally, unless we do something to avoid re-comparing files again
when doing the later all-unmatched-files-against-each-other check,
then worst case behavior can approach twice as slow as the original
code.

Right. If Git decides to reorganize all of its *.c files in one
commit, we would still get quadratic behavior in rename detection.
Maybe it's not _that_ much of an improvement.

Thanks,
-Stolee