From 6d24ad971c8195b00cd9678fbff7c2aaddb00908 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Tue, 29 Jan 2008 20:54:56 -0800 Subject: [PATCH] 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 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 --- diffcore-rename.c | 80 ++++++++++++++++++++++++++++++++++------------- 1 file changed, 58 insertions(+), 22 deletions(-) diff --git a/diffcore-rename.c b/diffcore-rename.c index 3d377251b..5974362d3 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -112,8 +112,8 @@ static int basename_same(struct diff_filespec *src, struct diff_filespec *dst) struct diff_score { int src; /* index in rename_src */ int dst; /* index in rename_dst */ - int score; - int name_score; + unsigned short score; + short name_score; }; static int estimate_similarity(struct diff_filespec *src, @@ -223,6 +223,12 @@ static int score_compare(const void *a_, const void *b_) { const struct diff_score *a = a_, *b = b_; + /* sink the unused ones to the bottom */ + if (a->dst < 0) + return (0 <= b->dst); + else if (b->dst < 0) + return -1; + if (a->score == b->score) return b->name_score - a->name_score; @@ -387,6 +393,22 @@ static int find_exact_renames(void) return i; } +#define NUM_CANDIDATE_PER_DST 4 +static void record_if_better(struct diff_score m[], struct diff_score *o) +{ + int i, worst; + + /* find the worst one */ + worst = 0; + for (i = 1; i < NUM_CANDIDATE_PER_DST; i++) + if (score_compare(&m[i], &m[worst]) > 0) + worst = i; + + /* is it better than the worst one? */ + if (score_compare(&m[worst], o) > 0) + m[worst] = *o; +} + void diffcore_rename(struct diff_options *options) { int detect_rename = options->detect_rename; @@ -473,47 +495,61 @@ void diffcore_rename(struct diff_options *options) if (num_create * num_src > rename_limit * rename_limit) goto cleanup; - mx = xmalloc(sizeof(*mx) * num_create * num_src); + mx = xcalloc(num_create * NUM_CANDIDATE_PER_DST, sizeof(*mx)); for (dst_cnt = i = 0; i < rename_dst_nr; i++) { - int base = dst_cnt * num_src; struct diff_filespec *two = rename_dst[i].two; + struct diff_score *m; + if (rename_dst[i].pair) continue; /* dealt with exact match already. */ + + m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST]; + for (j = 0; j < NUM_CANDIDATE_PER_DST; j++) + m[j].dst = -1; + for (j = 0; j < rename_src_nr; j++) { struct diff_filespec *one = rename_src[j].one; - struct diff_score *m = &mx[base+j]; - m->src = j; - m->dst = i; - m->score = estimate_similarity(one, two, - minimum_score); - m->name_score = basename_same(one, two); + struct diff_score this_src; + this_src.score = estimate_similarity(one, two, + minimum_score); + this_src.name_score = basename_same(one, two); + this_src.dst = i; + this_src.src = j; + record_if_better(m, &this_src); diff_free_filespec_blob(one); } /* We do not need the text anymore */ diff_free_filespec_blob(two); dst_cnt++; } + /* cost matrix sorted by most to least similar pair */ - qsort(mx, num_create * num_src, sizeof(*mx), score_compare); - for (i = 0; i < num_create * num_src; i++) { - struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; - struct diff_filespec *src; + qsort(mx, dst_cnt * NUM_CANDIDATE_PER_DST, sizeof(*mx), score_compare); + + for (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) { + struct diff_rename_dst *dst; + + if ((mx[i].dst < 0) || + (mx[i].score < minimum_score)) + break; /* there is no more usable pair. */ + dst = &rename_dst[mx[i].dst]; if (dst->pair) continue; /* already done, either exact or fuzzy. */ - if (mx[i].score < minimum_score) - break; /* there is no more usable pair. */ - src = rename_src[mx[i].src].one; - if (src->rename_used) + if (rename_src[mx[i].src].one->rename_used) continue; record_rename_pair(mx[i].dst, mx[i].src, mx[i].score); rename_count++; } - for (i = 0; i < num_create * num_src; i++) { - struct diff_rename_dst *dst = &rename_dst[mx[i].dst]; + + for (i = 0; i < dst_cnt * NUM_CANDIDATE_PER_DST; i++) { + struct diff_rename_dst *dst; + + if ((mx[i].dst < 0) || + (mx[i].score < minimum_score)) + break; /* there is no more usable pair. */ + dst = &rename_dst[mx[i].dst]; if (dst->pair) continue; /* already done, either exact or fuzzy. */ - if (mx[i].score < minimum_score) - break; /* there is no more usable pair. */ record_rename_pair(mx[i].dst, mx[i].src, mx[i].score); rename_count++; } -- 2.30.2