Code

Optimize rename detection for a huge diff
authorJunio C Hamano <gitster@pobox.com>
Wed, 30 Jan 2008 04:54:56 +0000 (20:54 -0800)
committerJunio C Hamano <gitster@pobox.com>
Wed, 13 Feb 2008 23:44:20 +0000 (15:44 -0800)
commit6d24ad971c8195b00cd9678fbff7c2aaddb00908
treec7c87ecec384bdb47abe67e98f704a5bb68c860e
parent7a2078b4b00fb1c5d7b0bf8155778f79377b8f2f
Optimize rename detection for a huge diff

When there are N deleted paths and M created paths, we used to
allocate (N x M) "struct diff_score" that record how similar
each of the pair is, and picked the <src,dst> pair that gives
the best match first, and then went on to process worse matches.

This sorting is done so that when two new files in the postimage
that are similar to the same file deleted from the preimage, we
can process the more similar one first, and when processing the
second one, it can notice "Ah, the source I was planning to say
I am a copy of is already taken by somebody else" and continue
on to match itself with another file in the preimage with a
lessor match.  This matters to a change introduced between
1.5.3.X series and 1.5.4-rc, that lets the code to favor unused
matches first and then falls back to using already used
matches.

This instead allocates and keeps only a handful rename source
candidates per new files in the postimage.  I.e. it makes the
memory requirement from O(N x M) to O(M).

For each dst, we compute similarlity with all sources (i.e. the
number of similarity estimate computations is still O(N x M)),
but we keep handful best src candidates for each dst.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-rename.c