Re: [PATCH] Optimize rename detection for a huge diff

On Jan 29, 2008, at 8:40 PM, Junio C Hamano wrote:

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.

I can think of cases where you'll throw away better candidates this  
way. How about using a priority queue of size max(N, M)?

I don't know about the details of the current algorithm but it seems  
to me that using a naive Rabin Karp fingerprinting approach would not  
use too much memory: say L is total number of bytes of created files  
and the fingerprint size S and hash size of 4 bytes. To keep track of  
M files You only need to keep 8(additional 4 bytes as an index to the  
file names)*(L/S + M(for filenames)) plus some overhead for the hash  
table in memory. One pass through D (number of bytes of deleted  
files) you can get the NxM scores. The score is defined as Wf * Mf +  
Wt, where Wf is the weight for fingerprinting match and Wt is the  
weight for title match score; Mf is the fingerprint match score =  
(number of matching fingerprints)/(number of fingerprints of original  
(deleted) file). Wf and Wt can be tuned to boost exact basename match.

By pushing the scores into a priority queue you'll get the final top  
(max(N, M) = K) scores in the end. The computation complexity is  
really O(D+L+(MxN)logK) and memory requirement O(L)

You can compute the entire linux source tree renaming (24K files and  
total 260MB uncompressed) this way using only about 92MB of memory in  
18 seconds (limited by hash lookup speed, assuming 15M lookups per  
second based on my past experience).

__Luke