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

[Junio C Hamano <gitster@pobox.com>]

"Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Elijah Newren <newren@gmail.com>
>
> reigster_rename_src() took pains to create an array in rename_src which

register?

> 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.

I originally started writing "I do not recall when the sortedness
stopped mattering", until I realized you wrote "anywhere" not
"anymore".

I do not think of any other reason than we wanted to notice and deal
with the duplicated input.  We do not look up the list of rename
sources by pathname.  So if we were sorting it, it is to prevent
such a bug from breaking the rename machinery.  What you call
"technically the behaviour is different" is "removing the safety".

I do not offhand know which caller might give us such an input in
the current code, so it may be entirely a safe thing to do.
Besides, we use a hashmap of rename sources when computing exact
renames, so even if we need to notice and/or avoid duplicates, we do
not have to have register_rename_src() build the table with an
insertion sort as a way to do so.

> 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)