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

From: Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>
Date: Dec 6, 2020, 02:54 UTC
Message-ID: <306a48820dd3c338d2b9e2288e5a3e1c7c89f36e.1607223276.git.gitgitgadget@gmail.com>
In-Reply-To: <pull.929.git.git.1607223276.gitgitgadget@gmail.com>

From: Elijah Newren <newren@gmail.com>

reigster_rename_src() took pains to create an array in rename_src which was sorted by pathname of the contained diff_filepair. However, the fact that this array was sorted was not needed anywhere, and thus represented wasted time. Simply append to the end of the array, which in a usecase of note saved 45% of diffcore_rename() setup time for me.

Technically, there is one difference in the end result for the code. IF the caller of diffcore-rename provides a set of pairs with a duplicate filename in the sources (an erroneous input condition), the old code would simply ignore the duplicate (without warning or error). The new code will simply swallow it and thus allow multiple pairings for the "same" source file. Checking for this error condition is expensive (basically undoing the optimization) and the only existing callers already avoid passing such an invalid input. If someone really wants to add some error checking here on this input condition, I believe they should add a separate function which can be called before diffcore_rename(), and then other callers that don't need additional checks because of their design (such as merge-ort) can avoid the extra overhead.

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 | 30 +++---------------------------
 1 file changed, 3 insertions(+), 27 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 3d637ba4645..816d2fbac44 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -76,36 +76,12 @@ 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;
-	}
-
-	/* 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