Opened 4 years ago
Closed 4 years ago
#20731 closed enhancement (fixed)
shortcut coercion for IntegerRational operations
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage7.3 
Component:  coercion  Keywords:  days74 
Cc:  jdemeyer  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Jeroen Demeyer, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  d535aee (Commits)  Commit:  d535aee38e629195fa6319a8a1d1d2efaecebec6 
Dependencies:  Stopgaps: 
Description (last modified by )
Doing some shortcut to coercion actually fasten the code by a factor 3...
Old version
sage: z = 2 sage: q = QQ((1,5)) sage: %timeit z + q 1000000 loops, best of 3: 930 ns per loop sage: %timeit q + z 1000000 loops, best of 3: 930 ns per loop sage: %timeit z  q 1000000 loops, best of 3: 848 ns per loop sage: %timeit q  z 1000000 loops, best of 3: 776 ns per loop sage: %timeit z * q 1000000 loops, best of 3: 1.15 µs per loop sage: %timeit q * z 1000000 loops, best of 3: 1.17 µs per loop sage: %timeit z / q 1000000 loops, best of 3: 1.09 µs per loop sage: %timeit q / z 1000000 loops, best of 3: 1.1 µs per loop
New version
sage: z = 2 sage: q = QQ((1,5)) sage: %timeit z + q 1000000 loops, best of 3: 265 ns per loop sage: %timeit q + z 1000000 loops, best of 3: 323 ns per loop sage: %timeit z  q 1000000 loops, best of 3: 261 ns per loop sage: %timeit q  z 1000000 loops, best of 3: 319 ns per loop sage: %timeit z * q 1000000 loops, best of 3: 255 ns per loop sage: %timeit q * z 1000000 loops, best of 3: 332 ns per loop sage: %timeit z / q 1000000 loops, best of 3: 289 ns per loop sage: %timeit q / z 1000000 loops, best of 3: 314 ns per loop
Change History (50)
comment:1 Changed 4 years ago by
 Branch set to u/vdelecroix/20731
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Commit set to 33f9fd432ff127a5234b120bebda1f7b63bb0f84
comment:3 Changed 4 years ago by
 Commit changed from 33f9fd432ff127a5234b120bebda1f7b63bb0f84 to 19c075bf18073049fea1607b483c591feef7df22
Branch pushed to git repo; I updated commit sha1. New commits:
19c075b  Trac 20731: fix doctests

comment:4 Changed 4 years ago by
Move src/sage/rings/binop.pyx
to src/sage/libs/gmp
since it has nothing to with rings. And I would just use a .pxd
file with inline functions, no .pyx
file.
comment:5 Changed 4 years ago by
 Commit changed from 19c075bf18073049fea1607b483c591feef7df22 to fdf79acfa3433ef167ee3e865c16dd429caf24e6
Branch pushed to git repo; I updated commit sha1. New commits:
fdf79ac  Trac 20731: get rid of ZZ._div

comment:6 Changed 4 years ago by
 Commit changed from fdf79acfa3433ef167ee3e865c16dd429caf24e6 to eec41681c0fc9bb3b377ad67a31634a40d277782
comment:7 Changed 4 years ago by
 Status changed from needs_review to needs_work
I think that mpq_mul_z
and mpq_div_z
are overkill. Why don't you just multiply the numerator or denominator with the integer and call mpq_canonicalize
, similar to what you do for Integer/Integer
division?
comment:8 Changed 4 years ago by
QQ((2^100, 3^100)) * 3^100
comment:9 Changed 4 years ago by
Right, but that's a rather artificial example. What about simple cases?
comment:10 Changed 4 years ago by
In src/sage/repl/interpreter.py
, there is a good reason that the line numbers were changed to ...
comment:11 Changed 4 years ago by
I just thought about the following very simple algorithm for the multiplication (division is analogous):
To compute (A/B) * C
, you initialize the result as C/B
, canonicalize it and then multiply the numerator by A
.
You don't need to canonicalize the final result, since gcd(A,B) = 1
by assumption.
comment:12 Changed 4 years ago by
 Commit changed from eec41681c0fc9bb3b377ad67a31634a40d277782 to c7a8d8e5b44d49654aab2827f3b5359f4c7acd60
comment:13 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:15 Changed 4 years ago by
Which line numbers?
comment:16 Changed 4 years ago by
I see...
comment:17 Changed 4 years ago by
 Commit changed from c7a8d8e5b44d49654aab2827f3b5359f4c7acd60 to 97a809ecbc63d4dad9c794af1b1fda089fece267
Branch pushed to git repo; I updated commit sha1. New commits:
97a809e  Trac 20731: remove line numbers in a doctest

comment:18 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:20 Changed 4 years ago by
 Commit changed from 97a809ecbc63d4dad9c794af1b1fda089fece267 to 647a17bc7965f7c5daa91490d311eea894a31983
Branch pushed to git repo; I updated commit sha1. New commits:
647a17b  Trac 20731: one more line number

comment:21 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:22 Changed 4 years ago by
Given that the block
mpz_set(mpq_numref(X), A) mpz_set(mpq_denref(X), B) mpq_canonicalize(X)
occurs many times, you should probably make it a separate inline function too, let's call it mpq_div_zz
.
comment:23 followup: ↓ 25 Changed 4 years ago by
I'm still not convinced by the if type(x) is type(y)
. That would break if somebody wants to subclass Integer
for some reason. You can check the types first as an optimization, but you should still support the case where isinstance(x, Integer) and isinstance(y, Integer)
.
comment:24 Changed 4 years ago by
 Commit changed from 647a17bc7965f7c5daa91490d311eea894a31983 to 675f8e617bdcc66e718d18089938b8d1458d0724
Branch pushed to git repo; I updated commit sha1. New commits:
675f8e6  Trac 20731: some factorization

comment:25 in reply to: ↑ 23 Changed 4 years ago by
Replying to jdemeyer:
I'm still not convinced by the
if type(x) is type(y)
. That would break if somebody wants to subclassInteger
for some reason. You can check the types first as an optimization, but you should still support the case whereisinstance(x, Integer) and isinstance(y, Integer)
.
It perfectly works ;)
sage: class A(Integer): pass sage: A() + 1 1 sage: 1 + A() 1
comment:26 Changed 4 years ago by
 Description modified (diff)
comment:27 Changed 4 years ago by
Right, subclassing Integer
works because __add__
calls the coercion model and the coercion model calls _add_
(single underscore).
comment:28 Changed 4 years ago by
 Status changed from needs_review to needs_work
Some hopefully final notes:
 Check documentation (for example,
Rational.__sub__
documents plus)
 In
mpq_div_z
, you do not need to check the sign since the denominator is the product of two denominators, so it must be positive.
 I would remove functions
mpq_sub_z
andmpq_div_z
since they do not commute and are less useful: just implement them directly. Then you can also avoidmpq_neg
andmpq_inv
if you do it correctly.
comment:29 Changed 4 years ago by
 Commit changed from 675f8e617bdcc66e718d18089938b8d1458d0724 to 1c87b3cbb27e4f3489707ec30757dd5caa79df73
comment:30 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:31 Changed 4 years ago by
Curiously Integer + Rational
is faster than Rational + Integer
sage: z = 2 sage: q = QQ((1,5)) sage: %timeit z + q 1000000 loops, best of 3: 251 ns per loop sage: %timeit q + z 1000000 loops, best of 3: 323 ns per loop
comment:32 followup: ↓ 34 Changed 4 years ago by
 Keywords days74 added; sd74 removed
 Status changed from needs_review to needs_work
I'm not quite sure without looking through it. It might be something at a lower level than Sage.
However, this needs rebasing.
comment:33 Changed 4 years ago by
 Commit changed from 1c87b3cbb27e4f3489707ec30757dd5caa79df73 to 1a93a12c39522dbe60b958757e2e3922aa9c23ed
Branch pushed to git repo; I updated commit sha1. New commits:
1a93a12  Merge branch 'develop' into int_rat_coercion

comment:34 in reply to: ↑ 32 ; followup: ↓ 35 Changed 4 years ago by
 Status changed from needs_work to needs_review
Replying to tscrim:
I'm not quite sure without looking through it. It might be something at a lower level than Sage.
I really do not understand this comment.
However, this needs rebasing.
This I understood. Done!
comment:35 in reply to: ↑ 34 ; followup: ↓ 36 Changed 4 years ago by
Replying to vdelecroix:
Replying to tscrim:
I'm not quite sure without looking through it. It might be something at a lower level than Sage.
I really do not understand this comment.
This was in reference to comment:31, where I was thinking the issue with the time difference might be something in mpz instead of something we are doing in Sage. It might be better to take the faster version and utilize that addition/multiplication is commutative to get that extra little bit of speed.
comment:36 in reply to: ↑ 35 Changed 4 years ago by
Replying to tscrim:
Replying to vdelecroix:
Replying to tscrim:
I'm not quite sure without looking through it. It might be something at a lower level than Sage.
I really do not understand this comment.
This was in reference to comment:31, where I was thinking the issue with the time difference might be something in mpz instead of something we are doing in Sage. It might be better to take the faster version and utilize that addition/multiplication is commutative to get that extra little bit of speed.
There is no fundamental difference between z+q
and q+z
. The code is copy paste calling the very same functions. comment:31 is just something that I do not understand.
comment:37 Changed 4 years ago by
 Reviewers set to Jeroen Demeyer, Travis Scrimshaw
Ah, I see it now. I guess the only difference is checking isinstance
for Integer
is longer than that of Rational
because of a longer MRO:
sage: p = 2 sage: p.__class__.__mro__ (<type 'sage.rings.integer.Integer'>, <type 'sage.structure.element.EuclideanDomainElement'>, <type 'sage.structure.element.PrincipalIdealDomainElement'>, <type 'sage.structure.element.DedekindDomainElement'>, <type 'sage.structure.element.IntegralDomainElement'>, <type 'sage.structure.element.CommutativeRingElement'>, <type 'sage.structure.element.RingElement'>, <type 'sage.structure.element.ModuleElement'>, <type 'sage.structure.element.Element'>, <type 'sage.structure.sage_object.SageObject'>, <type 'object'>) sage: q = 2/3 sage: q.__class__.__mro__ (<type 'sage.rings.rational.Rational'>, <type 'sage.structure.element.FieldElement'>, <type 'sage.structure.element.CommutativeRingElement'>, <type 'sage.structure.element.RingElement'>, <type 'sage.structure.element.ModuleElement'>, <type 'sage.structure.element.Element'>, <type 'sage.structure.sage_object.SageObject'>, <type 'object'>)
I'm happy with this ticket asis. Jeroen, any more comments?
comment:38 Changed 4 years ago by
One way to shortcut the isinstance(right, Rational)
is to instead do type(right) is Rational
. That would actually be the fastest. (And it will still work with an element that inherits from Rational
since _add_
, _mul_
etc are properly implemented.) What do you think?
comment:39 Changed 4 years ago by
I was originally thinking that we should keep it as isinstance
, but since we explicitly construct a new Rational
(and I don't think it could be made to work with subtypes [easily]), I think we should only test against Rational
. Plus those extra little nanoseconds can matter at this level. Subclasses can just fall into the coercion framework.
comment:40 Changed 4 years ago by
hum... with isinstance(X,Y)
sage: %timeit z+q 1000000 loops, best of 3: 242 ns per loop sage: %timeit q+z 1000000 loops, best of 3: 306 ns per loop
with type(X) is Y
sage: %timeit z+q 1000000 loops, best of 3: 243 ns per loop sage: %timeit q+z 1000000 loops, best of 3: 334 ns per loop
comment:41 Changed 4 years ago by
Independent time testing with a Cython class (without inheritance)
code  relative time 

type(a) == A  10500000ns 
isinstance(a,A)  559000ns 
type(a) is A  55ns 
I guess something else is happening with z+q
versus q+z
...
comment:42 Changed 4 years ago by
 Commit changed from 1a93a12c39522dbe60b958757e2e3922aa9c23ed to dd2defb5ddf707d2dc5a84419a41fdbcd5c75a30
Branch pushed to git repo; I updated commit sha1. New commits:
dd2defb  Trac 20731: isinstance(X,Y) > type(X) is Y

comment:43 Changed 4 years ago by
 Status changed from needs_review to positive_review
That really suggests that it has to do with the MRO length (comment:37), but I am somewhat surprised that does matter. Well, this is a definite improvement and should get into 7.3.
comment:44 Changed 4 years ago by
 Status changed from positive_review to needs_work
sage t long src/sage/repl/interpreter.py ********************************************************************** File "src/sage/repl/interpreter.py", line 77, in sage.repl.interpreter Failed example: shell.run_cell('1/0') Expected:  ZeroDivisionError Traceback (most recent call last) <ipythoninput...> in <module>() > 1 Integer(1)/Integer(0) <BLANKLINE> .../src/sage/rings/integer.pyx in sage.rings.integer.Integer.__div__ (build/cythonized/sage/rings/integer.c:...)() ... if type(left) is type(right): ... if mpz_sgn((<Integer>right).value) == 0: > ... raise ZeroDivisionError("rational division by zero") ... x = <Rational> Rational.__new__(Rational) ... mpq_div_zz(x.value, (<Integer>left).value, (<Integer>right).value) <BLANKLINE> ZeroDivisionError: rational division by zero Got:  ZeroDivisionError Traceback (most recent call last) <ipythoninput16f88eab09598> in <module>() > 1 Integer(1)/Integer(0) <BLANKLINE> /home/buildslavesage/slave/sage_git/build/src/sage/rings/integer.pyx in sage.rings.integer.Integer.__div__ (/home/buildslavesage/slave/sage_git/build/src/build/cythonized/sage/rings/integer.c:12882)() 1841 if type(left) is type(right): 1842 if mpz_sgn((<Integer>right).value) == 0: > 1843 raise ZeroDivisionError("rational division by zero") 1844 x = <Rational> Rational.__new__(Rational) 1845 mpq_div_zz(x.value, (<Integer>left).value, (<Integer>right).value) <BLANKLINE> ZeroDivisionError: rational division by zero ********************************************************************** 1 item had failures: 1 of 5 in sage.repl.interpreter [133 tests, 1 failure, 3.60 s]
comment:45 Changed 4 years ago by
Dear Volker,
I am not able to reproduce this... could you tell us on which kind of configuration you obtained that?
Vincent
comment:46 Changed 4 years ago by
I think the test is just fragile:
.../src/sage/rings/integer.pyx in sage.rings.integer.Integer.__div__ (build/cythonized/sage/rings/integer.c:...)()
vs the actual output:
/home/buildslavesage/slave/sage_git/build/src/sage/rings/integer.pyx in sage.rings.integer.Integer.__div__ (/home/buildslavesage/slave/sage_git/build/src/build/cythonized/sage/rings/integer.c:12882)()
Note the path is .../build/src/...
and compare with the previous doctest output format.
comment:47 Changed 4 years ago by
 Commit changed from dd2defb5ddf707d2dc5a84419a41fdbcd5c75a30 to d535aee38e629195fa6319a8a1d1d2efaecebec6
Branch pushed to git repo; I updated commit sha1. New commits:
d535aee  Trac 20731: fix doctest

comment:48 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:49 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:50 Changed 4 years ago by
 Branch changed from u/vdelecroix/20731 to d535aee38e629195fa6319a8a1d1d2efaecebec6
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Trac 20731: shortcut coercion for IntegerRational