Re: gcopy_avma() is wasting stack memory compared to gcopy()

[Jens Schmidt <crashdump@meine-dateien.info>]

Thanks for your explanation.

I'm using gcopy_avma() outside threads in some situations where it's
very effective and works fine. Appended is an example that computes
vampire numbers.

The only difficult is to ensure that there is no memory overlapping when
copying stack objects. During analyzation of repiled stack I noticed
increased consumption with gcopy_avma() and non-recusive types.

LG - Jens


Karim Belabas schrieb:
> * Jens Schmidt [2017-07-04 07:47]:
>> Hello PARI developer.
>>
>> PARI Library Guide (PDF) writes: "GEN gcopy_avma(GEN x, pari_sp *AVMA)
>> return a copy of x as from gcopy, except that we pretend that initially
>> avma is *AVMA, and that *AVMA is updated accordingly (so that the total
>> size of x is the difference between the two successive values of *AVMA)."
>> I noticed that gcopy_avma() needs more memory (~ 20%-30%) than gcopy()
>> to create a copy of a GEN object if GEN is of non recursive type, e.g.
>> t_POL or t_SER. Therefore I've written a shot test function to dissect
>> the PARI stack.
> 
> The difference is due to gen_0: gcopy is allowed to keep (or create) pointers
> to "universal objects", which need not be copied, whereas gcopy_avma is
> a low-level function that was used to serialize objects out of a PARI
> session and thus makes a deep copy of everything. It makes a huge
> difference for sparse structures.
> 
> I am not sure a gcopy_avma with the above semantic [which has never been
> documented] is useful anymore, it does not seem to be used in the PARI
> sources any longer; it is present twice: in gclone (where it's
> definitely not needed) and in the pthread interface (where I *believe*
> at this point that it's not needed). I'll investigate.
> 
> The function used nowadays to serialize objects is copy_bin() [which
> replaces a 0 t_INT by NULL, is as efficient as gcopy memory-wise]
> 
> 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 21 23
> 351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
> `
> 


/*
 * PARI/GP func: vampire numbers (http://oeis.org/A014575)
 *
 * return: vampire numbers of n in vector with pair of fangs or empty
 *
 *      n: integer number (always in decimal system)
 *   base: optional radix of numeral system of integer number (default=10)
 *
 *  integers are always returned base 10
 *
 *
 * gp code: install("vampire", "GD0,L,", "vampire", "<library path>");
 */
GEN vampire(GEN n, long base)
{
  long i, l, z = 1;
  GEN B, D, F, p, q, R, S, V;

  if (typ(n) != t_INT)
    pari_err_TYPE("number", n);

  pari_sp ltop = avma;                  /* save stack pointer */

  base = (base < 2)? 10: base;

  B = utoipos(base);

  V = digits(n, B);                     /* digits of num in base B */
  l = lg(V) - 1;                        /* count of digits */

  if (l % 2 == 0) {                     /* even? */
    S = vecsort0(gtovecsmall(V), NULL, 0);              /* sort digits */
    D = divisors(n);                    /* vector with divisors of n */
    R = cgetg(lg(D), t_VEC);            /* create result vector (probably too large) */

    for (i = 1; i < lg(D); i++) {       /* examine divisors of n */
      p = gel(D, i);
      q = divii(n, p);

      if (((strlen(itostr(p)) == l/2 && strlen(itostr(q)) == l/2)
        && gequal(S, vecsort0(gtovecsmall(concat(digits(p, B), digits(q, B))), NULL, 0)))
        && (smodis(p, base) | smodis(q, base)))
      {
        if (cmpii(sqri(p), n) > 0)      /* complete? */
          break;

        F = cgetg(3, t_VEC);            /* write pair of fangs p,q */
        gel(F, 1) = p;
        gel(F, 2) = q;

        gel(R, z++) = F;                /* append fangs to result vector */
      }
    }
  }

  if (z == 1) {                 /* no result */
    avma = ltop;                /* garbage collection */
    return cgetg(1, t_VEC);     /* return empty vector */
  }

  setlg(R, z);                  /* clip vector to result (no stackdummy required) */

  R = gcopy_avma(R, &ltop);     /* copy result to top of stack (no memory overlapping) */

  avma = ltop;                  /* garbage collection */

  return R;
}