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

• attachment: trac_14627_signed_mod_int.patch
• attachment: trac_14627_32bit.patch
• attachment: trac_14627_more_primes.patch​

Depends on #12728

CC: @sagetrac-Stefan

Component: linear algebra

Author: Volker Braun

Reviewer: Martin Albrecht

Merged: sage-5.12.beta0

Issue created by migration from https://trac.sagemath.org/ticket/14627

[vbraun]

Attachment: test_matrix_modn_float.py.gz

Performance test script

[vbraun]

Dependencies: #12728

[vbraun]

Author: Volker Braun

[malb]

comment:5

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]

comment:6

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]

comment:7

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

[malb]

comment:8

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]

Attachment: trac_14627_signed_mod_int.patch.gz

Updated patch

[vbraun]

comment:9

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

[malb]

Reviewer: Martin Albrecht

[malb]

comment:10

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

[jdemeyer]

Changed dependencies from #12728 to #14634, #12728

[jdemeyer]

Changed dependencies from #14634, #12728 to #12728

[jdemeyer]

comment:15

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]

comment:16

Attachment: trac_14627_32bit.patch.gz

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

[vbraun]

comment:17

The second patch needs review only

[malb]

comment:18

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]

comment:19

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

[vbraun]

Attachment: trac_14627_more_primes.patch.gz

Initial patch

[vbraun]

comment:21

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]

comment:23

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

[malb]

comment:24

Looks good to me

[jdemeyer]

Merged: sage-5.12.beta0

[mezzarobba]

comment:27

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