From: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> Subject: [PATCH 6/6] Do exact rename detection regardless of rename limits Now that the exact rename detection is linear-time (with a very small constant factor to boot), there is no longer any reason to limit it by the number of files involved. In some trivial testing, I created a repository with a directory that had a hundred thousand files in it (all with different contents), and then moved that directory to show the effects of renaming 100,000 files. With the new code, that resulted in [torvalds@woody big-rename]$ time ~/git/git show -C | wc -l 400006 real 0m2.071s user 0m1.520s sys 0m0.576s ie the code can correctly detect the hundred thousand renames in about 2 seconds (the number "400006" comes from four lines for each rename: diff --git a/really-big-dir/file-1-1-1-1-1 b/moved-big-dir/file-1-1-1-1-1 similarity index 100% rename from really-big-dir/file-1-1-1-1-1 rename to moved-big-dir/file-1-1-1-1-1 and the extra six lines is from a one-liner commit message and all the commit information and spacing). Most of those two seconds weren't even really the rename detection, it's really all the other stuff needed to get there. With the old code, this wouldn't have been practically possible. Doing a pairwise check of the ten billion possible pairs would have been prohibitively expensive. In fact, even with the rename limiter in place, the old code would waste a lot of time just on the diff_filespec checks, and despite not even trying to find renames, it used to look like: [torvalds@woody big-rename]$ time git show -C | wc -l 1400006 real 0m12.337s user 0m12.285s sys 0m0.192s ie we used to take 12 seconds for this load and not even do any rename detection! (The number 1400006 comes from fourteen lines per file moved: seven lines each for the delete and the create of a one-liner file, and the same extra six lines of commit information). Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> --- This obviously just moves the rename detection call. It made sense as a separate patch largely because of the explanation that goes along with it, but it conceptually is very different from actually improving the rename detection logic itself. So it got a patch of its own. diffcore-rename.c | 12 ++++++------ 1 files changed, 6 insertions(+), 6 deletions(-) diff --git a/diffcore-rename.c b/diffcore-rename.c index e7e370b..3946932 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -429,6 +429,12 @@ void diffcore_rename(struct diff_options *options) goto cleanup; /* nothing to do */ /* + * We really want to cull the candidates list early + * with cheap tests in order to avoid doing deltas. + */ + rename_count = find_exact_renames(); + + /* * This basically does a test for the rename matrix not * growing larger than a "rename_limit" square matrix, ie: * @@ -444,12 +450,6 @@ 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 - * with cheap tests in order to avoid doing deltas. - */ - rename_count = find_exact_renames(); - /* Have we run out the created file pool? If so we can avoid * doing the delta matrix altogether. */ -- 1.5.3.4.330.g1dec6 - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
