stack space in gcd operations

[Niels Möller]

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

> The code below creates a new thread with the requested amount of
> stack space and attempts an n-limb mpz_invert operation. On OS X
> this fails (bus error) e.g. when the stack is 448 KB and n = 2800,

> It is reasonable for GMP to require so much stack space for xgcd?

I don't think so. Direct stack allocation (automatic C variables and
stuff) ought to be O(log(n)) with a fairly small constant factor,
without reading the code, I'd guess around a hundred bytes or smaller
per factor of two in n.

Then there's allocation by TMP_ALLOC, which tries to allocate "small"
(currently, up to 64 KB, it seems) chunks on the stack, and large
chunks on the heap. For gcdext, all storage is allocated up front in
one chunk by mpn_gcdext, based on various ITCH-macros.

This allocation does not include temporary storage for the udnerlying
multiplications, though, since the current multiplication functions
don't use an itch/scratch interface. But I think that storage should
be limited to, say, 2n, or 44 KB if you have 64-bit limbs.

So maybe you could try to instrument the TMP_ALLOC calls to see what
sizes are requested, and then check if they're allocated from the heap
or the stack. Or you could try reconfiguring with --disable-alloca and
see if that helps.

/Niels