[PATCH] Split out "exact content match" phase of rename detection
- From
Linus Torvalds <torvalds@linux-foundation.org>
- Date
- Oct 21, 2007, 18:40 UTC
- Message-ID
- <alpine.LFD.0.999.0710211137480.10525@woody.linux-foundation.org>
- In-Reply-To
- <alpine.LFD.0.999.0710201158580.10525@woody.linux-foundation.org>
Split out "exact content match" phase of rename detection
This makes the exact content match a separate function of its own. Partly to cut down a bit on the size of the diffcore_rename() function (which is too complex as it is), and partly because there are smarter ways to do this than an O(m*n) loop over it all, and that function should be rewritten to take that into account.
Whether I'll get to the rewrite or not is not clear, but this is a worthy cleanup regardless.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> ---
So, I'm looking a bit at rename handling, since it's got the scalability problems. Andy Chu of google pointed to an algorithm that doesn't use a m*n array, but instead a hash table to match things up, and that should be much better. No promises as to whether I'll ever actually implement it, but just looking at that diffcore_rename function makes your head ache, and while this doesn't improve any code, at least it splits one independent thing out of it..
--- diffcore-rename.c | 90 +++++++++++++++++++++++++++++++++-------------------- 1 files changed, 56 insertions(+), 34 deletions(-)
diff --git a/diffcore-rename.c b/diffcore-rename.c index 142e537..2077a9b 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -262,6 +262,58 @@ static int compute_stays(struct diff_queue_struct *q, return 1; } +/* + * Find exact renames first. + * + * The first round matches up the up-to-date entries, + * and then during the second round we try to match + * cache-dirty entries as well. + * + * Note: the rest of the rename logic depends on this + * phase also populating all the filespecs for any + * entry that isn't matched up with an exact rename, + * see "is_exact_match()". + */ +static int find_exact_renames(void) +{ + int rename_count = 0; + int contents_too; + + for (contents_too = 0; contents_too < 2; contents_too++) { + int i; + + for (i = 0; i < rename_dst_nr; i++) { + struct diff_filespec *two = rename_dst[i].two; + int j; + + if (rename_dst[i].pair) + continue; /* dealt with an earlier round */ + for (j = 0; j < rename_src_nr; j++) { + int k; + struct diff_filespec *one = rename_src[j].one; + if (!is_exact_match(one, two, contents_too)) + continue; + + /* see if there is a basename match, too */ + for (k = j; k < rename_src_nr; k++) { + one = rename_src[k].one; + if (basename_same(one, two) && + is_exact_match(one, two, + contents_too)) { + j = k; + break; + } + } + + record_rename_pair(i, j, (int)MAX_SCORE); + rename_count++; + break; /* we are done with this entry */ + } + } + } + return rename_count; +} + void diffcore_rename(struct diff_options *options) { int detect_rename = options->detect_rename; @@ -270,12 +322,11 @@ void diffcore_rename(struct diff_options *options) struct diff_queue_struct *q = &diff_queued_diff; struct diff_queue_struct outq; struct diff_score *mx; - int i, j, rename_count, contents_too; + int i, j, rename_count; int num_create, num_src, dst_cnt; if (!minimum_score) minimum_score = DEFAULT_RENAME_SCORE; - rename_count = 0; for (i = 0; i < q->nr; i++) { struct diff_filepair *p = q->queue[i]; @@ -318,40 +369,11 @@ void diffcore_rename(struct diff_options *options) if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit) goto cleanup; - /* We really want to cull the candidates list early + /* + * We really want to cull the candidates list early * with cheap tests in order to avoid doing deltas. - * The first round matches up the up-to-date entries, - * and then during the second round we try to match - * cache-dirty entries as well. */ - for (contents_too = 0; contents_too < 2; contents_too++) { - for (i = 0; i < rename_dst_nr; i++) { - struct diff_filespec *two = rename_dst[i].two; - if (rename_dst[i].pair) - continue; /* dealt with an earlier round */ - for (j = 0; j < rename_src_nr; j++) { - int k; - struct diff_filespec *one = rename_src[j].one; - if (!is_exact_match(one, two, contents_too)) - continue; - - /* see if there is a basename match, too */ - for (k = j; k < rename_src_nr; k++) { - one = rename_src[k].one; - if (basename_same(one, two) && - is_exact_match(one, two, - contents_too)) { - j = k; - break; - } - } - - record_rename_pair(i, j, (int)MAX_SCORE); - rename_count++; - break; /* we are done with this entry */ - } - } - } + rename_count = find_exact_renames(); /* Have we run out the created file pool? If so we can avoid * doing the delta matrix altogether.