Memory usage for large multiplications

[bodrato at mail.dm.unipi.it]

Thank you Paul,

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

This numbers sound strange to me.

Maybe the problem is that top shows some values, measured every now and
then...
GMP-5.0 uses an itch/scratch logic, it allocates (almost) all needed
memory before starting the computation, and frees it all at the end.
GMP-4.3 allocates, then frees, then allocates again, and frees again... It
is much more difficult to get the "maximal" snapshot.


I used the following test. A slightly modified version of your program:

#include <stdio.h>
#include <stdlib.h>
#include "gmp.h"

int
main (int argc, char **argv)
{
  mp_size_t n = atol (argv[1]);
  mp_ptr a, b, c;
  mp_size_t sa = n, sb = n*3/2;
  printf ("GMP %s\n", gmp_version);
  a = malloc (sa * sizeof (mp_limb_t));
  b = malloc (sb * sizeof (mp_limb_t));
  c = malloc ((sa + sb) * sizeof (mp_limb_t));
  mpn_random (a, sa);
  mpn_random(b, sb);
  printf ("Start product: %i x %i.", sb, sa);
  fflush (stdout);
  mpn_mul (c, b, sb, a, sa);
  printf (" ... End product.\n");
  fflush (stdout);

  return 0;
}

I compiled it with both GMP-4.3.2 (official tar.bz2) and GMP-5.0.1 (from
repositories). Then I tested lots of sizes, on an x86_32 with 1G of RAM
and no swap. Here are some relevant results:

portatile:/tmp$ free
             total       used       free     shared    buffers     cached
Mem:       1023132     142340     880792          0        404      34548
-/+ buffers/cache:     107388     915744
Swap:            0          0          0

portatile:/tmp$ for i in 179 180 227 228; do ./prod-4.3 ${i}00002;
./prod-5.0 ${i}00002; done
GMP 4.3.2
Start product: 26850003 x 17900002. ... End product.
GMP 5.0.1
Start product: 26850003 x 17900002. ... End product.
GMP 4.3.2
Start product: 27000003 x 18000002. ... End product.
GMP 5.0.1
Start product: 27000003 x 18000002.Killed
GMP 4.3.2
Start product: 34050003 x 22700002. ... End product.
GMP 5.0.1
Start product: 34050003 x 22700002.GNU MP: Cannot allocate memory
(size=469893120)
GMP 4.3.2
Start product: 34200003 x 22800002.Killed
GMP 5.0.1
Start product: 34200003 x 22800002.GNU MP: Cannot allocate memory
(size=469893120)

The biggest product GMP-5 was able to compute is x179... while GMP-4.3
managed up to x227... The difference is 27%.
As you can see, when the operands are near the memory limit, the process
is able to allocate, but it is killed by the kernel (I'm running Linux)
when it tries to use all allocated memory.
This should be a slow and indirect but, I hope, correct way to estimate
real memory usage. Results are not dramatically different wrt those
obtained with malloc_stats(). I think I'll use the latter for the future.

Regards,
Marco

PS: I used a machine with limited hardware resources, maybe you can
emulate something similar by using ulimit...

-- 
http://bodrato.it/papers/