Make mod_int signed and speed up matrix_modn_dense_float

[vbraun]

As discussed on ​https://groups.google.com/d/msg/sage-devel/hnO8gT8VON4/YyZ5UCM5wUEJ, unsigned longs are much slower than signed longs when converted to a Python object.

Without patch about 20x slower than naive list-of-list implementation:

$ sage test_matrix_modn_float.py
setA:
5 loops, best of 50: 179 ms per loop
setB:
25 loops, best of 50: 10.3 ms per loop

With patch no performance difference:

$ sage test_matrix_modn_float.py
setA:
25 loops, best of 50: 11.5 ms per loop
setB:
25 loops, best of 50: 12.8 ms per loop

Also, I collected some common extern cdef statements in pxd headers and cleaned up the MAX_MODULUS declarations.

Apply

• trac_14627_signed_mod_int.patch​
• trac_14627_32bit.patch​
• trac_14627_more_primes.patch​

[vbraun]

Performance test script

[malb]

Patch looks good, a few small comments/questions:

• "The expression below assumes unsigned." I don't think this is true any more.
• Those pari changes (sage.libs.pari.gen.pari => pari) are a bit out of place? It's not bad enough though to make you take it out, just curious.
• I thought we're supposed to use .pxd in place of .pxi, but you seem to prefer .pxi here?

[vbraun]

I'm just following ​http://wiki.cython.org/FAQ#Whatisthedifferencebetweena.pxdand.pxifile.3FWhenshouldeitherbeused.3F, pxd for class declarations and pxi for include headers.

The sage.libs.pari.gen.pari gave me import errors after taking out some import statements. The module already imports it as pari on module-level so the short version should have been used from the start.

[vbraun]

I changed "assumes unsigned" -> "assumes signed", which is of course the whole point of the patch ;-)

[malb]

re: pxi vs. pxd: They are concluding with "Now that "cimport *" can be used, there is no reason to use .pxi files for external declarations." I think it would be better to use a .pxd which seems to be best practice as recommended by the Cython devs. But I am not insisting on it.

In other news: all tests passed.

[vbraun]

Updated patch

[vbraun]

Ok, sounds good. New patch uses mod_int.pxd and stdint.pxd.

[malb]

• doctests pass
• patch looks okay
• I can confirm the performance improvements

[jdemeyer]

This breaks badly on 32-bit systems:

sage -t --long devel/sage/sage/matrix/matrix2.pyx
**********************************************************************
File "devel/sage/sage/matrix/matrix2.pyx", line 2320, in sage.matrix.matrix2.Matrix.diagonal._right_kernel_matrix_over_field
Failed example:
    P = result[1]; P
Expected:
    [       -1        -1         1         0]
    [-zeta14^3 -zeta14^4         0         1]
Got:
    [         3716055149462127149669597391230365/1741122812024444137450032682964234          3716055149462127149669597391230365/1741122812024444137450032682964234                                                                              1                                                                              0]
    [3716055149462127149669597391230365/1741122812024444137450032682964234*zeta14^3 3716055149462127149669597391230365/1741122812024444137450032682964234*zeta14^4                                                                              0                                                                              1]
**********************************************************************

And many more failures and timeouts: ​http://build.sagemath.org/sage/builders/NTU%20arando%20%28Ubuntu%2012.10%20i686%29/builds/182/steps/shell_8/logs/stdio

[jdemeyer]

There are warnings

RuntimeWarning: sig_off() without sig_on() at build/cythonized/sage/matrix/misc.c:13370

which aren't caused by this ticket, but might as well be fixed: the sig_on() in misc.pyx should be outside the try/finally block:

sig_on()
try:
    stuff
finally:
    sig_off()

[vbraun]

Updated patch

[vbraun]

I've fixed the 32-bit error, added documentation, and also fixed Jeroen's sig_on branch issue.

[vbraun]

The second patch needs review only

[malb]

The changes look good. I don't have a 32-bit machine here to test, but other than that, I'd say it's good to go. Volker, you tested it on a 32-bit system, I presume?

[vbraun]

Yes, of course I tested it on a 32-bit machine

[vbraun]

Initial patch

[vbraun]

I noticed that #10281 intentionally uses 64-bit integers on all platforms for mod_int, since otherwise you can run out of primes. This is checked in one #long doctest that I missed. So the trac_14627_more_primes.patch switches to signed int_fast64_t for mod_int, this is fast on 64-bit Linux/OSX and sub-optimal (but with enough primes) on 64-bit Windows and all 32-bit platforms.

[vbraun]

make ptestlong passes on both 32-bit ad 64-bit now. Martin, can you review the final patch?

[malb]

Looks good to me

[mmezzarobba]

Could the changes in that ticket be the cause of #15220?