Karim Belabas on Mon, 14 Dec 2015 09:02:15 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Memory question


* Rob Burns [2015-12-14 04:53]:
> Is anyone able to explain or interpret the following please? I wrote the
> following simple program to test pari memory limits. It calculates powers
> of 2:
> 
>    pari_init(2000000000,2);
> 
> 
> m = gen_1;
> 
> for (i=1; a<1000000; a++) {

I guess the 'i=1' should be an 'a=1'

> 
> m = gmul2n(m, 1);
> 
> }
> 
> 
>   pari_close();
> 
> The PARI stack overflows around a = 179000. However at this point m is only
> around 2800 bytes according to taille2.

Not surprising: after N loops, memory usage is O(N^2) [ = the sum of the
sizes of the successive 'm' whose size grows linearly ]

> Adding in some garbage collection only improves the result by a small
> amount.

You did something wrong, the following program runs to completion:

  #include <pari/pari.h>
  int main()
  {
    pari_sp av;
    long a;
    GEN m;
    pari_init(2000000000,2);
    av = avma; m = gen_1;
    for (a=1; a<1000000; a++) {
      m = gerepileuptoint(av, gmul2n(m, 1));
    }
    pari_close(); return 0;
  }

And so does this one (about 3 times faster since it performs GC once in a
while):

    [...]
    for (a=1; a<1000000; a++) {
      m = gmul2n(m, 1);
      if ((a & 0xfff) == 0) m = gerepileuptoint(av, m);
    }
    [...]

> The same algorithm written with gmp can run up to a = 10^7 while using at
> most 1.93 GB of memory.

Presumably you wrote it in such a way that 'm' is modified in place.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`