Re: git-revert is a memory hog

Jeff King [off-list ref] writes:

On Wed, Jan 30, 2008 at 08:51:09AM +1100, Linus Torvalds wrote:

quoted

I definitely can reproduce it, it's horrid.

This is from "top" fairly late in the game, but with the thing not even 
done yet. Current git, pretty much fully (and fairly aggressively) packed 
current kernel repo, and using "diff.renamelmit=0".

Hrm, setting diff.renamelimit to 0 lets me reproduce (I thought I tried
it before, but clearly not...).

Hmph.  But I wonder why this part does not trigger, even when
you have renamelimit set to 0.

	/*
	 * This basically does a test for the rename matrix not
	 * growing larger than a "rename_limit" square matrix, ie:
	 *
	 *    rename_dst_nr * rename_src_nr > rename_limit * rename_limit
	 *
	 * 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_dst_nr > rename_limit && rename_src_nr > rename_limit)
		goto cleanup;
	if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)
		goto cleanup;

I wonder if the second one for the overflow avoidance should be
using || instead of &&, though.

On Tue, Jan 29, 2008 at 02:36:24PM -0800, Junio C Hamano wrote:

Hmph.  But I wonder why this part does not trigger, even when
you have renamelimit set to 0.
[...]
	if (rename_limit <= 0 || rename_limit > 32767)
		rename_limit = 32767;

It does trigger; we set the limit to the obscenely high 32767. My matrix
was something like 8000x3500.

	if (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)
		goto cleanup;
	if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)
		goto cleanup;

I wonder if the second one for the overflow avoidance should be
using || instead of &&, though.

Hrm, yes, I think it can still overflow. (e.g., a 2 by 2^32-1
situation). But changing it to || isn't right, either; you would
disallow 1 by 101, which is quite do-able (and the normal case for -C
-C, I would think).

-Peff

On Tue, 29 Jan 2008, Junio C Hamano wrote:

I wonder if the second one for the overflow avoidance should be
using || instead of &&, though.

No, we want to be able to handle the case where there is (for example) 
just one removed file, but lots of new ones. That's not expensive at all. 
So we don't want to require that *both* the counts for removed and new 
files are low, we really want to check that we don't have too many 
combinations together.

But  the

        if (rename_limit <= 0 || rename_limit > 32767)
                rename_limit = 32767;

which is there purely to avoid overflow in 32-bit multiplication should 
probably be changed to be more reasonable. We'll never want to try to do a 
matrix that is really 32k * 32k in size, even if we can calculate its size 
;)

So maybe we should just make that hard limit more reasonable. 100x100 was 
too small, but a 1000x1000 matrix might be acceptable.

Or, better yet (which was what I was hoping for originally), we'd just 
make the inexact rename detection be linear-size/time rather than O(m*n). 
But those patches never really came together, so we do need to limit it 
more aggressively.

		Linus

On Tue, Jan 29, 2008 at 05:45:58PM -0500, Jeff King wrote:

quoted

	if (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)
		goto cleanup;

Hrm, yes, I think it can still overflow. (e.g., a 2 by 2^32-1
situation). But changing it to || isn't right, either; you would

I think the correct solution is just:

  /* check for overflow of square */
  if (rename_dst_nr > ULONG_MAX / rename_src_nr)
          goto cleanup;

-Peff

On Wed, Jan 30, 2008 at 09:49:44AM +1100, Linus Torvalds wrote:

But  the

        if (rename_limit <= 0 || rename_limit > 32767)
                rename_limit = 32767;

which is there purely to avoid overflow in 32-bit multiplication should 

Ah, right, that first conditional handles the overflow. Then what is the
second one doing? If they are both larger than the rename limit, then
won't there square by definition be larger than the square of the rename
limit? I.e., can't we just get rid of the second conditional?

Or, better yet (which was what I was hoping for originally), we'd just 
make the inexact rename detection be linear-size/time rather than O(m*n). 
But those patches never really came together, so we do need to limit it 
more aggressively.

I had trouble getting the memory usage to a reasonable level. The hash
tables were just getting enormous.

-Peff