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

["Elijah Newren via GitGitGadget" <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