[PATCH v3 7/9] diffcore-rename: simplify and accelerate register_rename_src()

From: Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>
Date: Dec 29, 2020, 20:05 UTC
Message-ID: <a58639b2927fc9b51351d2d1da134a757c657723.1609272328.git.gitgitgadget@gmail.com>
In-Reply-To: <pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com>

From: Elijah Newren <newren@gmail.com>

register_rename_src() took pains to create an array in rename_src which was sorted by pathname of the contained diff_filepair. The sorting was entirely unnecessary since callers pass filepairs to us in sorted order. We can simply append to the end of the rename_src array, speeding up diffcore_rename() setup time.

Also, note that I dropped the return type on the function since it was unconditionally discarded anyway.

This patch is being submitted in a different order than its original development, but in a large rebase of many commits with lots of renames and with several optimizations to inexact rename detection, diffcore_rename() setup time was a sizeable chunk of overall runtime. This patch dropped execution time of rebasing 35 commits with lots of renames by 2% overall.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diffcore-rename.c | 39 +++++++++++++--------------------------
 1 file changed, 13 insertions(+), 26 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 55a188abcc3..a215421a9cb 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -76,36 +76,23 @@ static struct diff_rename_src {
 } *rename_src;
 static int rename_src_nr, rename_src_alloc;
 
-static struct diff_rename_src *register_rename_src(struct diff_filepair *p)
+static void register_rename_src(struct diff_filepair *p)
 {
-	int first, last;
-	struct diff_filespec *one = p->one;
-	unsigned short score = p->score;
-
-	first = 0;
-	last = rename_src_nr;
-	while (last > first) {
-		int next = first + ((last - first) >> 1);
-		struct diff_rename_src *src = &(rename_src[next]);
-		int cmp = strcmp(one->path, src->p->one->path);
-		if (!cmp)
-			return src;
-		if (cmp < 0) {
-			last = next;
-			continue;
-		}
-		first = next+1;
-	}
+	/*
+	 * If we have multiple entries at the same path in the source tree
+	 * (an invalid tree, to be sure), avoid using more more than one
+	 * such entry in rename detection.  Once upon a time, doing so
+	 * caused segfaults; see commit 25d5ea410f ("[PATCH] Redo
+	 * rename/copy detection logic.", 2005-05-24).
+	 */
+	if (rename_src_nr > 0 &&
+	    !strcmp(rename_src[rename_src_nr-1].p->one->path, p->one->path))
+		return;
 
-	/* insert to make it at "first" */
 	ALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);
+	rename_src[rename_src_nr].p = p;
+	rename_src[rename_src_nr].score = p->score;
 	rename_src_nr++;
-	if (first < rename_src_nr)
-		MOVE_ARRAY(rename_src + first + 1, rename_src + first,
-			   rename_src_nr - first - 1);
-	rename_src[first].p = p;
-	rename_src[first].score = score;
-	return &(rename_src[first]);
 }
 
 static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)

-- 
gitgitgadget