Memory usage for large multiplications

[Paul Zimmermann]

       Marco,

> Date: Thu, 28 Jan 2010 22:06:10 +0100 (CET)
> From: bodrato at mail.dm.unipi.it
> 
> Ciao,
> 
> > The below patch changes the interface of mpn_mulmod_bnm1, and reduces
> > the amount of temporary storage needed for mpn_nussbaumer_mul (used for
> 
> The patch has been refined, and some more memory was saved...
> 
> Unfortunately I don't have as much memory as Paul has, so that I can't
> reproduce exactly his test, some estimates follow.
> 
> Let's call rn the length of the result, from the numbers that Paul
> reported I guess that 2rn = 999,000,000. And GMP-4.3.2 allocates something
> like 2.4rn for the product.
> GMP-5.0 used 5rn, thanks to Niels' patch GMP-5.0.0-20100123 uses 4rn
> 
> With the last patches we have 3rn for balanced products and 3.5rn for
> unbalanced. I expect, for the current code
> max mmap bytes   = 2,760,000,000
> 
> It still is a 25% more than GMP-4.3.2...
> 
> Unfortunately  a temporary space of 2rn is allocated by mul_fft, this
> function currently does not accept a scratch parameter, it is difficult to
> further reduce memory usage without completely reorganising the code.
> 
> Can Paul confirm my estimate?
> 
> Best regards,
> Marco

yes I confirm (with the gmp-5.0.1-20100129 snapshot):

patate% ./a.out 
GMP 5.0.1
start product
end product
Arena 0:
system bytes     =     598016
in use bytes     =       2512
Total (incl. mmap):
system bytes     =  999809024
in use bytes     =  999213520
max mmap regions =          5
max mmap bytes   = 2755584000

This gives indeed 25% more than 4.3.2 for the total memory usage (column VIRT
of top, which gives 2109m for 4.3.2 and 2632m for 5.0.1-20100129).

However I believe the "real" memory usage (column RES of top) is more
problematic, since this is really what will limit large computations.
For 4.3.2 top says 1.6g while for 5.0.1-20100129 it still says 2.3g,
thus 44% more (I don't know if it is possible to get more accuracy
for that field in top).

Paul