Re: [PATCH 3/3] diff: correct warning message when renameLimit exceeded

Elijah Newren [off-list ref] writes:

The exhaustiveness of the quadratic portion comes from comparing each
file to more other files, not in using a different type of comparison.

Exactly.  By culling potential matches early with heuristics, we
make a trade-off of risking false-negatives but save a lot of cycles
while trying to find "renames with modifications (which is what we
called 'inexact rename')", and my comment equated  fewer false-negatives
with more precision.

On Tue, Jul 13, 2021 at 6:10 PM Junio C Hamano [off-list ref] wrote:

Elijah Newren [off-list ref] writes:

quoted

The exhaustiveness of the quadratic portion comes from comparing each
file to more other files, not in using a different type of comparison.

Exactly.  By culling potential matches early with heuristics, we
make a trade-off of risking false-negatives but save a lot of cycles
while trying to find "renames with modifications (which is what we
called 'inexact rename')", and my comment equated  fewer false-negatives
with more precision.

Okay, I think I'm following what you're saying now, mostly, but I'm
curious about the false negative comment.

Am I mixing up negatives/positives (as I'm prone to do), or would it
be more correct to say the new algorithm risks suboptimal positives
rather than that it risks false negatives?

In particular, the new algorithm will compare files with the same
basename and just accept that pairing if they are similar enough, even
if there might be a better match elsewhere.  However, a lack of a
match in same-basenamed files will not cause those files to have no
match; they will instead just be included in the exhaustive detection
portion, so we can still detect renames for such paths.

Elijah Newren [off-list ref] writes:

Am I mixing up negatives/positives (as I'm prone to do), or would it
be more correct to say the new algorithm risks suboptimal positives
rather than that it risks false negatives?

I'm prone to mixing them up, too, but I think they are the sides of
the same coin.  Imagine there is a path X on the source side, and
two paths Y and Z on the destination side.  With exhaustive match,
Z might be a better match (content-wise) to X than Y is to X.

For the path X on the source that is matched with a suboptimal
counterpart Y on the destination side, we may call the situation a
false-positive because with a more exhaustive search we might have
been able to find Z that is a better match.  For the path Z on the
destination side that was culled too early with heuristics and
failed to be matched with the source path X that got matched with a
suboptimal destination path Y, it is a loss for Z---it wasn't chosen
when it should have been (i.e. a false negative, as Z saw no
counterparts).

In any case, during the word search for "inexact", "more precise",
"more expensive", I do not think negatives and positives will play a
big role anyway, so...

On Tue, Jul 13, 2021 at 10:17 PM Junio C Hamano [off-list ref] wrote:

Elijah Newren [off-list ref] writes:

quoted

Am I mixing up negatives/positives (as I'm prone to do), or would it
be more correct to say the new algorithm risks suboptimal positives
rather than that it risks false negatives?

I'm prone to mixing them up, too, but I think they are the sides of
the same coin.  Imagine there is a path X on the source side, and
two paths Y and Z on the destination side.  With exhaustive match,
Z might be a better match (content-wise) to X than Y is to X.

For the path X on the source that is matched with a suboptimal
counterpart Y on the destination side, we may call the situation a
false-positive because with a more exhaustive search we might have
been able to find Z that is a better match.  For the path Z on the
destination side that was culled too early with heuristics and
failed to be matched with the source path X that got matched with a
suboptimal destination path Y, it is a loss for Z---it wasn't chosen
when it should have been (i.e. a false negative, as Z saw no
counterparts).

In any case, during the word search for "inexact", "more precise",
"more expensive", I do not think negatives and positives will play a
big role anyway, so...

Indeed, I've gotten us off on a bit of a tangent, but thanks for
taking the time to answer my questions.  :-)