Changes between Version 3 and Version 8 of Ticket #21388


Ignore:
Timestamp:
09/02/16 09:47:22 (23 months ago)
Author:
jdemeyer
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #21388

    • Property Authors changed from Erik Bray to Erik Bray, Jeroen Demeyer
    • Property Summary changed from Make Psi2 function less likely to break the stack to Optimize Psi2()
    • Property Branch changed from u/embray/psi2 to u/jdemeyer/psi2
    • Property Commit changed from 9b22d75ac27fcae0d07065daccab96ba14562f79 to bdce5dced1e9f811616836253c4e7cd45b71fcf3
  • Ticket #21388 – Description

    v3 v8  
    1 This provides a workaround to a test that caused the Python interpreter to segfault on Windows.  The specific call that caused the segfault is:
     1We greatly optimize the `Psi2()` function.
     2
     3Before:
     4{{{
     5sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2
     6sage: timeit('Psi2.f(71)')
     75 loops, best of 3: 9.36 s per loop
     8}}}
     9
     10After:
     11{{{
     12sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2
     13sage: timeit('Psi2.f(71)')
     145 loops, best of 3: 875 ms per loop
     15}}}
     16
     17(note the use of `Psi2.f()` to bypass caching)
     18
     19--------
     20
     21This also provides a workaround to a test that caused the Python interpreter to segfault on Windows.  The specific call that caused the segfault is:
    222
    323`Psi2(71)`
    4 
    5 I don't know if that function needs to be implemented the way it is--it's possible that it could be reworked from the ground up to not need this work-around, but I don't know.  I still don't understand the coercion model well-enough.
    624
    725But in brief, the crash occurs because we have (in the original code) a large element of `Univariate Quotient Polynomial Ring in v over Multivariate Polynomial Ring in x, u over Rational Field with modulus v^2 - u^4 + 10*u^3 + 3*u^2 - 4*u + 8`.  This is then being cast simply to a multivariate rational polynomial over x, u, v.  Because there is no direct coercion between these types this involves `eval()`-ing the polynomial as a Python expression.
     
    927The problem is that this expression can become too large for the stack--specifically in Python's symbol visibility analysis, a step it performs just before compiling an expression to bytecode.  The implementation of that recurses into binary expressions, leading to a stack overflow for such a large expression.  This issue has come up once before in #16014 where it was worked around by a rewrite of the code.  This particular test worked on Linux where the default stack size is 8MB, but it crashed on Windows where the typical stack is just 1MB.
    1028
    11 The workaround this time is to simply cast each term in the final sum individually and then sum those terms, rather than summing first and then casting.  This is probably slower, but gives Python smaller expressions to eval.
     29The optimization gives smaller expressions to eval.
    1230
    1331A more general fix to this problem would be nice though--I'm writing up some thoughts I have on it in a separate post.