[RFC] rename detection: allow more renames

[RFC] rename detection: allow more renames

[Andreas Krey]

Hi all,

we also ran into the maximum rename limit
in the rename detection. (Yes, we get a lot
of rename candidates when cherry-picking
between two specific releases.)

The code talks about limiting the size
of the rename matrix, but as far as I
can see, the matrix itself never exists
as such, and the only thing that could
actually overflow is the computation
for the progress indication. This
can be fixed by reporting just the
destinations checked instead of the
combinations, since we only update
the progress once per destination
anyway.

If the direction is good, I will
shape it up (and obtain the
proper signoffs).


diff --git a/diffcore-rename.c b/diffcore-rename.c
index 749a35d..279f24e 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -368,7 +368,7 @@ static int too_many_rename_candidates(int num_create,
 	int rename_limit = options->rename_limit;
 	int num_src = rename_src_nr;
 	int i;
-
+	static int max_rename_limit = 100000;
 	options->needed_rename_limit = 0;
 
 	/*
@@ -380,8 +380,8 @@ static int too_many_rename_candidates(int num_create,
 	 * but handles the potential overflow case specially (and we
 	 * assume at least 32-bit integers)
 	 */
-	if (rename_limit <= 0 || rename_limit > 32767)
-		rename_limit = 32767;
+	if (rename_limit <= 0 || rename_limit > max_rename_limit)
+		rename_limit = max_rename_limit;
 	if ((num_create <= rename_limit || num_src <= rename_limit) &&
 	    (num_create * num_src <= rename_limit * rename_limit))
 		return 0;
@@ -515,7 +515,7 @@ void diffcore_rename(struct diff_options *options)
 	if (options->show_rename_progress) {
 		progress = start_progress_delay(
 				_("Performing inexact rename detection"),
-				rename_dst_nr * rename_src_nr, 50, 1);
+				rename_dst_nr, 50, 1);
 	}
 
 	mx = xcalloc(num_create * NUM_CANDIDATE_PER_DST, sizeof(*mx));
@@ -552,7 +552,7 @@ void diffcore_rename(struct diff_options *options)
 			diff_free_filespec_blob(two);
 		}
 		dst_cnt++;
-		display_progress(progress, (i+1)*rename_src_nr);
+		display_progress(progress, (i+1));
 	}
 	stop_progress(&progress);


And we would also like to see progress when doing
a cherry pick - in our case this takes a few minutes:

 
diff --git a/sequencer.c b/sequencer.c
index 3c060e0..8fce028 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -282,6 +282,7 @@ static int do_recursive_merge(struct commit *base, struct commit *next,
 
 	for (xopt = opts->xopts; xopt != opts->xopts + opts->xopts_nr; xopt++)
 		parse_merge_opt(&o, *xopt);
+	o.show_rename_progress = isatty(2);
 
 	clean = merge_trees(&o,
 			    head_tree,


Andreas

-- 
"Totally trivial. Famous last words."
From: Linus Torvalds <torvalds@*.org>
Date: Fri, 22 Jan 2010 07:29:21 -0800

Re: [RFC] rename detection: allow more renames

[Jeff King]

On Fri, Nov 13, 2015 at 05:35:06PM +0100, Andreas Krey wrote:

> The code talks about limiting the size
> of the rename matrix, but as far as I
> can see, the matrix itself never exists
> as such, and the only thing that could
> actually overflow is the computation
> for the progress indication. This
> can be fixed by reporting just the
> destinations checked instead of the
> combinations, since we only update
> the progress once per destination
> anyway.

I didn't dig in the archive, but I think we discussed the "just show
progress for destinations" before. The problem you run into is that the
items aren't a good indication of the amount of work. You really are
doing n*m work, so if you just count "m", it can be very misleading if
"n" is high (and vice versa).

Might it make more sense just to move to a larger integer size? Or
perhaps to allow a higher limit for each side as long as the product of
the sides does not overflow?

> And we would also like to see progress when doing
> a cherry pick - in our case this takes a few minutes:
> 
>  
> diff --git a/sequencer.c b/sequencer.c
> index 3c060e0..8fce028 100644
> --- a/sequencer.c
> +++ b/sequencer.c
> @@ -282,6 +282,7 @@ static int do_recursive_merge(struct commit *base, struct commit *next,
>  
>  	for (xopt = opts->xopts; xopt != opts->xopts + opts->xopts_nr; xopt++)
>  		parse_merge_opt(&o, *xopt);
> +	o.show_rename_progress = isatty(2);
>  
>  	clean = merge_trees(&o,
>  			    head_tree,

I think that's sensible, for the same reasons that "merge" shows
progress. I suspect the patch you show above catches "git revert", too,
but if not, it should probably get the same treatment.

-Peff

Re: [RFC] rename detection: allow more renames

[Andreas Krey]

Hi Jeff,

thanks for the reply!

On Tue, 24 Nov 2015 18:33:28 +0000, Jeff King wrote:
...
> I didn't dig in the archive, but I think we discussed the "just show
> progress for destinations" before. The problem you run into is that the
> items aren't a good indication of the amount of work. You really are
> doing n*m work, so if you just count "m", it can be very misleading if
> "n" is high (and vice versa).

True, but the loops do progress indication for destinations only anyway.
So if you only have three destinations and a zillion sources, you
will still get only three progress updates, even if they say
'one zillion (33%)', 'two zillion (67%)', ...

I think as long as this is the case we can as well report the destination
count; maybe put the source count somewhere in the progress text.

> Might it make more sense just to move to a larger integer size?

Which would be? I'd venture into the progress code to identify
the necessary changes.

> Or
> perhaps to allow a higher limit for each side as long as the product of
> the sides does not overflow?

We're somewhat close to getting there. The rename detection runs
for several minutes in our cases.

Andreas

-- 
"Totally trivial. Famous last words."
From: Linus Torvalds <torvalds@*.org>
Date: Fri, 22 Jan 2010 07:29:21 -0800

Re: [RFC] rename detection: allow more renames

[Jeff King]

On Wed, Nov 25, 2015 at 01:03:15PM +0100, Andreas Krey wrote:

> On Tue, 24 Nov 2015 18:33:28 +0000, Jeff King wrote:
> ...
> > I didn't dig in the archive, but I think we discussed the "just show
> > progress for destinations" before. The problem you run into is that the
> > items aren't a good indication of the amount of work. You really are
> > doing n*m work, so if you just count "m", it can be very misleading if
> > "n" is high (and vice versa).
> 
> True, but the loops do progress indication for destinations only anyway.
> So if you only have three destinations and a zillion sources, you
> will still get only three progress updates, even if they say
> 'one zillion (33%)', 'two zillion (67%)', ...
> 
> I think as long as this is the case we can as well report the destination
> count; maybe put the source count somewhere in the progress text.

Ah, true. Though maybe that is something we should be fixing, rather
than building on. I dunno. I cannot recall the last time I saw rename
detection progress myself.

> > Might it make more sense just to move to a larger integer size?
> 
> Which would be? I'd venture into the progress code to identify
> the necessary changes.

I was thinking of uint64_t; the progress code would need to change, but
I don't see a big problem with that.

> We're somewhat close to getting there. The rename detection runs
> for several minutes in our cases.

Yikes. :)

-Peff

Re: [RFC] rename detection: allow more renames

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Fri, Nov 13, 2015 at 05:35:06PM +0100, Andreas Krey wrote:
>
>> The code talks about limiting the size
>> of the rename matrix, but as far as I
>> can see, the matrix itself never exists
>> as such, and the only thing that could
>> actually overflow is the computation
>> for the progress indication. This
>> can be fixed by reporting just the
>> destinations checked instead of the
>> combinations, since we only update
>> the progress once per destination
>> anyway.
>
> I didn't dig in the archive, but I think we discussed the "just show
> progress for destinations" before. The problem you run into is that the
> items aren't a good indication of the amount of work. You really are
> doing n*m work, so if you just count "m", it can be very misleading if
> "n" is high (and vice versa).

Right.

With s/never exists/no longer exists/ in the above observation, I
agree that this topic is sensible that it revisits the stale comment
from days back when we did use the matrix.