Re: [PATCH 6/7] diffcore-rename: simplify and accelerate register_rename_src()
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Dec 10, 2020, 02:51 UTC
- Message-ID
- <xmqqczzixtiy.fsf@gitster.c.googlers.com>
- In-Reply-To
- <306a48820dd3c338d2b9e2288e5a3e1c7c89f36e.1607223276.git.gitgitgadget@gmail.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.
Show 44 quoted lines
> 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)