#6304: intermittent crash in bernmm (4.0.2.rc0)
---------------------------+------------------------------------------------
Reporter: dmharvey | Owner: mhansen
Type: defect | Status: new
Priority: major | Milestone: sage-4.1.2
Component: combinatorics | Keywords:
Reviewer: | Author:
Merged: |
---------------------------+------------------------------------------------
Comment(by dmharvey):
Finally got somewhere.
It appears to be a stack overflow issue. It occurs inside GMP's xgcd
function. The default stack size for new threads is 8 MB on sage.math but
apparently only 512 KB on OSX. If I increase the thread stack size inside
bernmm, the crashes stop happening.
I wrote a test program (below) that calls {{{mpz_invert}}} for a given
input size using a given thread stack size. (The {{{mpz_invert}}} call is
what seems to be causing the problems in bernmm.) I found that for stack
size = 512 KB, GMP doesn't have any problems, but if I bump it down to
only 448 KB, it starts crashing for inputs of 2800 limbs and above. This
is around about the largest size that is used in bernmm for computing
B(40000), which is the value of k where problems seem to start occurring.
So if bernmm is only using a few 10's of KB of stack, it could push GMP
over the limit.
I haven't tried any of this with MPIR, but given that it uses a similar
quasi-linear XGCD algorithm, it wouldn't surprise me that the cause is the
same.
This is not so easy to address. A band-aid solution is to make bernmm use
a bigger stack. The real issue is whether it is reasonable for GMP to
require so much stack space for the XGCD operation (or conversely whether
the default stack size on OSX is too small). I will ask on the GMP mailing
list about this.
{{{
#include <limits.h>
#include <stdio.h>
#include <gmp.h>
#include <pthread.h>
void*
worker (void* arg)
{
size_t n = * (size_t*) arg;
mpz_t a, b;
mpz_init (a);
mpz_init (b);
/* try to invert a random number modulo B^n + 1 */
mpz_random (a, n);
mpz_set_ui (b, 1);
mpz_mul_2exp (b, b, n * GMP_NUMB_BITS);
mpz_add_ui (b, b, 1);
mpz_invert (a, a, b);
mpz_clear (b);
mpz_clear (a);
}
int
main (int argc, char* argv[])
{
if (argc < 3)
{
printf ("syntax: test <n> <stacksize>\n");
return 0;
}
size_t n = atol (argv[1]);
size_t old_stacksize;
size_t new_stacksize = atol (argv[2]);
pthread_attr_t attr;
pthread_attr_init (&attr);
pthread_attr_getstacksize (&attr, &old_stacksize);
printf ("old stacksize = %ld\n", old_stacksize);
int retval = pthread_attr_setstacksize (&attr, new_stacksize);
if (retval != 0)
{
printf ("PTHREAD_STACK_MIN = %ld\n", PTHREAD_STACK_MIN);
printf ("pthread_attr_setstacksize call failed with size = %ld\n",
new_stacksize);
return 0;
}
pthread_t thread;
pthread_create (&thread, &attr, worker, &n);
pthread_join (thread, NULL);
pthread_attr_destroy (&attr);
return 0;
}
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6304#comment:15>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
