#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 )
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)
Change History (31)
comment:1 Changed 7 years ago by
- Description modified (diff)
Changed 7 years ago by
comment:2 Changed 7 years ago by
- Dependencies set to #12728
comment:3 Changed 7 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:4 Changed 7 years ago by
- Cc Stefan added
comment:5 Changed 7 years ago by
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
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
I changed "assumes unsigned" -> "assumes signed", which is of course the whole point of the patch ;-)
comment:8 Changed 7 years ago by
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.
comment:9 Changed 7 years ago by
- Description modified (diff)
Ok, sounds good. New patch uses mod_int.pxd
and stdint.pxd
.
comment:10 Changed 7 years ago by
- 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
- Dependencies changed from #12728 to #14634, #12728
- Milestone changed from sage-5.10 to sage-pending
comment:12 Changed 7 years ago by
- Dependencies changed from #14634, #12728 to #12728
- Milestone changed from sage-pending to sage-5.10
comment:13 Changed 7 years ago by
- Milestone changed from sage-5.10 to sage-5.11
comment:14 Changed 7 years ago by
- 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
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()
comment:16 Changed 7 years ago by
I've fixed the 32-bit error, added documentation, and also fixed Jeroen's sig_on
branch issue.
comment:17 Changed 7 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
The second patch needs review only
comment:18 Changed 7 years ago by
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 7 years ago by
Yes, of course I tested it on a 32-bit machine
comment:20 Changed 7 years ago by
- Status changed from needs_review to positive_review
comment:21 Changed 7 years ago by
- 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 7 years ago by
- Status changed from positive_review to needs_work
comment:23 Changed 7 years ago by
- 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 7 years ago by
- Status changed from needs_review to positive_review
Looks good to me
comment:25 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:26 Changed 7 years ago by
- Merged in set to sage-5.12.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:27 Changed 7 years ago by
Could the changes in that ticket be the cause of #15220?
Performance test script