stack space in gcd operations

[Niels Möller]

David Harvey <dmharvey at cims.nyu.edu> writes:

> Here is an example with n = 8000.
>
> mpz/invert.c:46: allocate approx n limbs = 64KB (this is just under  the 64KB limit, so goes on the
> stack).
> mpz/invert.c:47: allocate approx n limbs = 64KB
> mpz/gcdext.c:66: allocate approx n limbs = 64KB
> mpz/gcdext.c:67: allocate approx n limbs = 64KB
> mpz/gcdext.c:76: allocate approx n limbs = 64KB
> mpz/gcdext.c:77: allocate approx n limbs = 64KB
> mpn/tdiv_qr.c:369: allocate approx n limbs = 64KB (which are freed  immediately afterwards!)
>
> So far the peak is already 448 KB, and we haven't even got to the  guts of the GCD yet!!!

Hmm. I'm not at all familiar with what the gcd code does before it
reaches mpn_gcd/mpn_gcdext. I wouldn't have expected that it allocated
so much temporary storage.

In any case, I think it would be a good idea lower the 64KB limit if
you for some reason need to work with a small stack. I don't know how
much the overhead for peak allocation costs. Maybe it would make sense
to unconditionally lower that threshold an order of magnitude (current
choice corresponds to 8000 limbs, so my guess is that the overhead
would be noticable only for applications doing linear-time
computations only.

/Niels