Changes between Version 3 and Version 8 of Ticket #21388
 Timestamp:
 09/02/16 09:47:22 (3 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #21388

Property
Authors
changed from
Erik Bray
toErik Bray, Jeroen Demeyer

Property
Summary
changed from
Make Psi2 function less likely to break the stack
toOptimize Psi2()

Property
Branch
changed from
u/embray/psi2
tou/jdemeyer/psi2

Property
Commit
changed from
9b22d75ac27fcae0d07065daccab96ba14562f79
tobdce5dced1e9f811616836253c4e7cd45b71fcf3

Property
Authors
changed from

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: 1 We greatly optimize the `Psi2()` function. 2 3 Before: 4 {{{ 5 sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2 6 sage: timeit('Psi2.f(71)') 7 5 loops, best of 3: 9.36 s per loop 8 }}} 9 10 After: 11 {{{ 12 sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2 13 sage: timeit('Psi2.f(71)') 14 5 loops, best of 3: 875 ms per loop 15 }}} 16 17 (note the use of `Psi2.f()` to bypass caching) 18 19  20 21 This also provides a workaround to a test that caused the Python interpreter to segfault on Windows. The specific call that caused the segfault is: 2 22 3 23 `Psi2(71)` 4 5 I don't know if that function needs to be implemented the way it isit's possible that it could be reworked from the ground up to not need this workaround, but I don't know. I still don't understand the coercion model wellenough.6 24 7 25 But 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. … … 9 27 The problem is that this expression can become too large for the stackspecifically 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. 10 28 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 Pythonsmaller expressions to eval.29 The optimization gives smaller expressions to eval. 12 30 13 31 A more general fix to this problem would be nice thoughI'm writing up some thoughts I have on it in a separate post.