Opened 7 years ago

Closed 6 years ago

Last modified 6 years ago

#14627 closed enhancement (fixed)

Make mod_int signed and speed up matrix_modn_dense_float

Reported by: vbraun Owned by: jason, was
Priority: major Milestone: sage-5.12
Component: linear algebra Keywords:
Cc: Stefan Merged in: sage-5.12.beta0
Authors: Volker Braun Reviewers: Martin Albrecht
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12728 Stopgaps:

Description (last modified by 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

Attachments (4)

test_matrix_modn_float.py (684 bytes) - added by vbraun 7 years ago.
Performance test script
trac_14627_signed_mod_int.patch (26.3 KB) - added by vbraun 7 years ago.
Updated patch
trac_14627_32bit.patch (9.0 KB) - added by vbraun 6 years ago.
Updated patch
trac_14627_more_primes.patch (2.9 KB) - added by vbraun 6 years ago.
Initial patch

Download all attachments as: .zip

Change History (31)

comment:1 Changed 7 years ago by vbraun

  • Description modified (diff)

Changed 7 years ago by vbraun

Performance test script

comment:2 Changed 7 years ago by vbraun

  • Dependencies set to #12728

comment:3 Changed 7 years ago by vbraun

  • Authors set to Volker Braun
  • Description modified (diff)
  • Status changed from new to needs_review

comment:4 Changed 7 years ago by Stefan

  • Cc Stefan added

comment:5 Changed 7 years ago by 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?

comment:6 Changed 7 years ago by 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.

comment:7 Changed 7 years ago by vbraun

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

comment:8 Changed 7 years ago by 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.

Changed 7 years ago by vbraun

Updated patch

comment:9 Changed 7 years ago by vbraun

  • Description modified (diff)

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

comment:10 Changed 7 years ago by malb

  • Reviewers set to Martin Albrecht
  • Status changed from needs_review to positive_review
  • doctests pass
  • patch looks okay
  • I can confirm the performance improvements

comment:11 Changed 7 years ago by jdemeyer

  • Dependencies changed from #12728 to #14634, #12728
  • Milestone changed from sage-5.10 to sage-pending

comment:12 Changed 7 years ago by jdemeyer

  • Dependencies changed from #14634, #12728 to #12728
  • Milestone changed from sage-pending to sage-5.10

comment:13 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.10 to sage-5.11

comment:14 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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

comment:15 Changed 7 years ago by 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()

Changed 6 years ago by vbraun

Updated patch

comment:16 Changed 6 years ago by vbraun

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

comment:17 Changed 6 years ago by vbraun

  • Description modified (diff)
  • Status changed from needs_work to needs_review

The second patch needs review only

comment:18 Changed 6 years ago by 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?

comment:19 Changed 6 years ago by vbraun

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

comment:20 Changed 6 years ago by malb

  • Status changed from needs_review to positive_review

Changed 6 years ago by vbraun

Initial patch

comment:21 Changed 6 years ago by vbraun

  • Description modified (diff)

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.

comment:22 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:23 Changed 6 years ago by vbraun

  • Status changed from needs_work to needs_review

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

comment:24 Changed 6 years ago by malb

  • Status changed from needs_review to positive_review

Looks good to me

comment:25 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:26 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.12.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:27 Changed 6 years ago by mmezzarobba

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

Note: See TracTickets for help on using tickets.