Opened 3 years ago
Closed 3 years ago
#25079 closed defect (fixed)
Use _mul_long Matrix*int
Reported by: | SimonKing | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.3 |
Component: | coercion | Keywords: | Matrix _mul_long |
Cc: | Merged in: | ||
Authors: | Simon King | Reviewers: | Jeroen Demeyer |
Report Upstream: | N/A | Work issues: | |
Branch: | 3c4a06d (Commits, GitHub, GitLab) | Commit: | 3c4a06d3080dd8528053be95b86154822d4d2b79 |
Dependencies: | #25476 | Stopgaps: |
Description
sage.structure.element does support the use of _mul_long for a multiplication of the form Element*int. However, the multiplication of Matrix*int does not use that short-cut.
In fact, currently only one matrix type implements _mul_long, namely Matrix_gfpn_dense. Unfortunately it uses a conversion that does not coincide with the coercion into the base ring.
So, this ticket is about fixing both issues.
Change History (34)
comment:1 Changed 3 years ago by
- Branch set to u/SimonKing/use__mul_long_matrix_int
comment:2 Changed 3 years ago by
- Commit set to e81581c9cbcb518b7eba0e91639a521015875cce
- Status changed from new to needs_review
comment:3 Changed 3 years ago by
- Commit changed from e81581c9cbcb518b7eba0e91639a521015875cce to a6a63a9f70691d61ae964800c0ce00f0397769c5
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a6a63a9 | Enable _mul_long for matrices
|
comment:4 Changed 3 years ago by
- Commit changed from a6a63a9f70691d61ae964800c0ce00f0397769c5 to 31f085e4c1ad2823bf30174781be12662192e573
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
31f085e | Enable _mul_long for matrices
|
comment:5 Changed 3 years ago by
Sorry, I had forgotten to add a test. So, I changed the last commit (sorry for the forced push, but nobody was using the old commit yet).
Here is what happens for other matrix types: With the branch:
sage: M = random_matrix(GF(3,'x'), 64,51) sage: %timeit c*M The slowest run took 52.64 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 26 µs per loop
Without the branch:
sage: M = random_matrix(GF(3,'x'), 64,51) sage: %timeit c*M The slowest run took 123.98 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 24.4 µs per loop
So, it seems that enabling _mul_long (which basically means: Using the existing default _mul_long) seems to not slow down the old code substantially.
comment:6 Changed 3 years ago by
All tests pass (with meataxe installed)...
comment:7 Changed 3 years ago by
I might review this, but I would rather do that after the dependencies have been merged.
comment:8 follow-up: ↓ 10 Changed 3 years ago by
- Status changed from needs_review to needs_work
Already this comment is wrong:
Multiply an MTX matrix with a field element represented by a Python integer.
It's certainly not a Python integer, it's a C long
. It would be fine for me to keep the old wording ("an integer").
comment:9 follow-up: ↓ 12 Changed 3 years ago by
The code in src/sage/structure/element.pyx
looks strange. It's certainly inefficient because have_same_parent()
calls classify_elements
so you're effectively calling classify_elements
twice. It's also missing the typical return NotImplemented
fallback that other operators have.
comment:10 in reply to: ↑ 8 ; follow-up: ↓ 11 Changed 3 years ago by
Replying to jdemeyer:
Already this comment is wrong:
Multiply an MTX matrix with a field element represented by a Python integer.It's certainly not a Python integer, it's a C
long
. It would be fine for me to keep the old wording ("an integer").
This ticket is related with an error that was actually solved (but not via _mul_long_
) and was of the form M*int(1)
. That's why I wrote "Python integer".
But if you prefer "C long", I'm fine with it.
comment:11 in reply to: ↑ 10 Changed 3 years ago by
Replying to SimonKing:
This ticket is related with an error that was actually solved (but not via
_mul_long_
) and was of the formM*int(1)
. That's why I wrote "Python integer".
Right, this ticket fixes a problem involving a Python integer. But the function _mul_long
itself has nothing to do with Python integers.
But if you prefer "C long", I'm fine with it.
Either that or revert to the old wording.
comment:12 in reply to: ↑ 9 Changed 3 years ago by
Replying to jdemeyer:
The code in
src/sage/structure/element.pyx
looks strange. It's certainly inefficient becausehave_same_parent()
callsclassify_elements
so you're effectively callingclassify_elements
twice. It's also missing the typicalreturn NotImplemented
fallback that other operators have.
I copied it from some other place of element.pyx
and it may very well be that I did wrong. So, I should call classify_elements
in the beginning and then call HAVE_SAME_PARENT(cl)
instead of have_same_parents
.
And I'll return to the original wording.
comment:13 Changed 3 years ago by
- Commit changed from 31f085e4c1ad2823bf30174781be12662192e573 to 1103493866985a869f2a64d8a2c3b5ab4a74332d
Branch pushed to git repo; I updated commit sha1. New commits:
1103493 | Use classify_elements more efficiently
|
comment:15 Changed 3 years ago by
PS: I repeated the timings that I provided in comment:2 and comment:5.
sage: M = random_matrix(GF(9,'x'), 64,51) sage: type(M) <type 'sage.matrix.matrix_gfpn_dense.Matrix_gfpn_dense'> sage: c = int(4) sage: %timeit M*c The slowest run took 29.39 times longer than the fastest. This could mean that an intermediate result is being cached. 1000000 loops, best of 3: 1.26 µs per loop sage: %timeit c*M The slowest run took 15.87 times longer than the fastest. This could mean that an intermediate result is being cached. 1000000 loops, best of 3: 1.26 µs per loop sage: M = random_matrix(GF(3,'x'), 64,51) sage: type(M) <type 'sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float'> sage: %timeit M*c The slowest run took 53.27 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 20.7 µs per loop sage: %timeit c*M 10000 loops, best of 3: 21 µs per loop
Hence, there is now a slight improvement for Matrix_modn_dense_float (with the old branch, there was a small deterioration), and the improvement for Matrix_gfpn_dense is now even better. So, thank you for spotting the issue with classify_elements
--- it had a noticeable effect.
comment:16 follow-up: ↓ 18 Changed 3 years ago by
- Reviewers set to Jeroen Demeyer
- Status changed from needs_review to needs_work
Can you also add the except TypeError: return NotImplemented
fallback from Element.__mul__
comment:17 Changed 3 years ago by
- Commit changed from 1103493866985a869f2a64d8a2c3b5ab4a74332d to 236024890ba6a7667006f073bd414904d8c22ba9
Branch pushed to git repo; I updated commit sha1. New commits:
2360248 | Return NotImplemented when a TypeError occurs in matrix times long
|
comment:18 in reply to: ↑ 16 Changed 3 years ago by
- Status changed from needs_work to needs_review
Replying to jdemeyer:
Can you also add the
except TypeError: return NotImplemented
fallback fromElement.__mul__
Done, I think.
comment:19 Changed 3 years ago by
Do you have any idea why the patchbot reports failing tests? I don't get those failures.
comment:20 Changed 3 years ago by
- Dependencies #25076 deleted
- Milestone changed from sage-8.2 to sage-8.3
comment:21 Changed 3 years ago by
Please add tests for multiplying with a negative integer.
comment:22 follow-up: ↓ 23 Changed 3 years ago by
- Status changed from needs_review to needs_work
Code looks good to me. So once you add the negative integer tests for meataxe, I will run full doctests. If that passes => positive review
comment:23 in reply to: ↑ 22 Changed 3 years ago by
Replying to jdemeyer:
Code looks good to me. So once you add the negative integer tests for meataxe, I will run full doctests. If that passes => positive review
Good catch --- there is in fact a bug for multiplication with a negative Python long.
comment:24 Changed 3 years ago by
Problem: Apparently -1%3
evaluates to -1
, not 2
. Is there an easy way to get a non-negative remainder?
comment:25 follow-up: ↓ 26 Changed 3 years ago by
Strange enough: I just tried to create cython code in which -1%3
evaluates to -1
, but I failed --- but in the MeatAxe wrapper it does evaluate to -1
. Why?
comment:26 in reply to: ↑ 25 ; follow-up: ↓ 27 Changed 3 years ago by
Replying to SimonKing:
Strange enough: I just tried to create cython code in which
-1%3
evaluates to-1
, but I failed --- but in the MeatAxe wrapper it does evaluate to-1
. Why?
The Python convention is rounding down, so -1 divided by 3 gives quotient -1 and remainder 2.
The C convention is truncating, so -1 divided by 3 gives quotient 0 and remainder -1.
Cython always uses the Python convention, unless the cdivision=True
directive is set (which is not the default, but it is set in Sage) and one of the arguments is a C integer.
Examples:
Python integers, always Python convention:
sage: cython(''' ....: print((-1) % 3) ....: ''') 2
C integers, result depends on cdivision
:
sage: cython(''' ....: print(<int>(-1) % <int>3) ....: ''') 2
sage: cython(''' ....: cimport cython ....: ....: with cython.cdivision(True): ....: print(<int>(-1) % <int>3) ....: ''') -1
In fact, it suffices that one of the arguments is a C integer:
sage: cython(''' ....: cimport cython ....: ....: with cython.cdivision(True): ....: print(<int>(-1) % 3) ....: ''') -1 sage: cython(''' ....: cimport cython ....: ....: with cython.cdivision(True): ....: print((-1) % <int>3) ....: ''') -1
Sage is compiled with cdivision=True
for historical reasons and for efficiency (cdivision=False
adds a bit of overhead for every division of signed C integers).
comment:27 in reply to: ↑ 26 ; follow-up: ↓ 28 Changed 3 years ago by
Replying to jdemeyer:
Sage is compiled with
cdivision=True
for historical reasons and for efficiency (cdivision=False
adds a bit of overhead for every division of signed C integers).
So, the easiest way out is to use with cython.cdivision(False)
in this single line of code, right?
comment:28 in reply to: ↑ 27 Changed 3 years ago by
Replying to SimonKing:
So, the easiest way out is to use
with cython.cdivision(False)
in this single line of code, right?
Sure.
comment:29 Changed 3 years ago by
- Commit changed from 236024890ba6a7667006f073bd414904d8c22ba9 to 6b17d582db337fab1c87fd3bf0b28e11370ef013
Branch pushed to git repo; I updated commit sha1. New commits:
6b17d58 | Fix 'Matrix_gfpn_dense times negative int'
|
comment:30 Changed 3 years ago by
- Status changed from needs_work to needs_review
Thank you for pointing me to the cdivision directive.
I added a test showing that multiplication with a negative int works, and with that make ptest
passes on my laptop. So, needs review.
comment:31 Changed 3 years ago by
- Branch changed from u/SimonKing/use__mul_long_matrix_int to u/jdemeyer/use__mul_long_matrix_int
comment:32 Changed 3 years ago by
- Commit changed from 6b17d582db337fab1c87fd3bf0b28e11370ef013 to 3c4a06d3080dd8528053be95b86154822d4d2b79
- Dependencies set to #25476
comment:33 Changed 3 years ago by
- Status changed from needs_review to positive_review
comment:34 Changed 3 years ago by
- Branch changed from u/jdemeyer/use__mul_long_matrix_int to 3c4a06d3080dd8528053be95b86154822d4d2b79
- Resolution set to fixed
- Status changed from positive_review to closed
In the current branch, I am basically copying relevant parts of
Element.__mul__
intoMatrix.__mul__
. The timings improve considerably, at least for Matrix_gfpn_dense.Without the branch:
With the branch:
I didn't run the test suite yet, but for now I am asking for review...
New commits:
New MatrixArgs object to deal with constructing matrices
Merge branch 'u/jdemeyer/new_matrixinput_object_to_deal_with_constructing_matrices' of git://trac.sagemath.org/sage into t/25076/fix_matrix_gfpn_dense___int
Add a test ensuring that #24742 remains fixed
Modify the test that ensures that #24742 remains fixed
Enable _mul_long for matrices