stack space in gcd operations
nisse at lysator.liu.se
Mon Aug 17 07:09:03 CEST 2009
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
> 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
More information about the gmp-devel