Opened 4 years ago

Closed 4 years ago

#20731 closed enhancement (fixed)

shortcut coercion for Integer-Rational operations

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-7.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 vdelecroix)

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 vdelecroix

  • Branch set to u/vdelecroix/20731
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to 33f9fd432ff127a5234b120bebda1f7b63bb0f84

Branch pushed to git repo; I updated commit sha1. New commits:

33f9fd4Trac 20731: shortcut coercion for Integer-Rational

comment:3 Changed 4 years ago by git

  • Commit changed from 33f9fd432ff127a5234b120bebda1f7b63bb0f84 to 19c075bf18073049fea1607b483c591feef7df22

Branch pushed to git repo; I updated commit sha1. New commits:

19c075bTrac 20731: fix doctests

comment:4 Changed 4 years ago by jdemeyer

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 git

  • Commit changed from 19c075bf18073049fea1607b483c591feef7df22 to fdf79acfa3433ef167ee3e865c16dd429caf24e6

Branch pushed to git repo; I updated commit sha1. New commits:

fdf79acTrac 20731: get rid of ZZ._div

comment:6 Changed 4 years ago by git

  • Commit changed from fdf79acfa3433ef167ee3e865c16dd429caf24e6 to eec41681c0fc9bb3b377ad67a31634a40d277782

Branch pushed to git repo; I updated commit sha1. New commits:

9078830Trac 20731: moving binop
eec4168Trac 20731: fix the move

comment:7 Changed 4 years ago by jdemeyer

  • 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 vdelecroix

QQ((2^100, 3^100)) * 3^100

comment:9 Changed 4 years ago by jdemeyer

Right, but that's a rather artificial example. What about simple cases?

comment:10 Changed 4 years ago by jdemeyer

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 jdemeyer

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 git

  • Commit changed from eec41681c0fc9bb3b377ad67a31634a40d277782 to c7a8d8e5b44d49654aab2827f3b5359f4c7acd60

Branch pushed to git repo; I updated commit sha1. New commits:

72f77b9Trac 20731: simpler operations
c7a8d8e20731: simpler mpq_mul_z/mpq_div_z

comment:13 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:14 Changed 4 years ago by jdemeyer

  • Status changed from needs_review to needs_work

10

comment:15 Changed 4 years ago by vdelecroix

Which line numbers?

comment:16 Changed 4 years ago by vdelecroix

I see...

comment:17 Changed 4 years ago by git

  • Commit changed from c7a8d8e5b44d49654aab2827f3b5359f4c7acd60 to 97a809ecbc63d4dad9c794af1b1fda089fece267

Branch pushed to git repo; I updated commit sha1. New commits:

97a809eTrac 20731: remove line numbers in a doctest

comment:18 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:19 Changed 4 years ago by jdemeyer

  • Status changed from needs_review to needs_work

12883

comment:20 Changed 4 years ago by git

  • Commit changed from 97a809ecbc63d4dad9c794af1b1fda089fece267 to 647a17bc7965f7c5daa91490d311eea894a31983

Branch pushed to git repo; I updated commit sha1. New commits:

647a17bTrac 20731: one more line number

comment:21 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:22 Changed 4 years ago by jdemeyer

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 follow-up: Changed 4 years ago by jdemeyer

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 git

  • Commit changed from 647a17bc7965f7c5daa91490d311eea894a31983 to 675f8e617bdcc66e718d18089938b8d1458d0724

Branch pushed to git repo; I updated commit sha1. New commits:

675f8e6Trac 20731: some factorization

comment:25 in reply to: ↑ 23 Changed 4 years ago by vdelecroix

Replying to jdemeyer:

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).

It perfectly works ;-)

sage: class A(Integer): pass
sage: A() + 1
1
sage: 1 + A()
1

comment:26 Changed 4 years ago by vdelecroix

  • Description modified (diff)

comment:27 Changed 4 years ago by jdemeyer

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 jdemeyer

  • Status changed from needs_review to needs_work

Some ---hopefully final--- notes:

  1. Check documentation (for example, Rational.__sub__ documents plus)
  1. 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.
  1. I would remove functions mpq_sub_z and mpq_div_z since they do not commute and are less useful: just implement them directly. Then you can also avoid mpq_neg and mpq_inv if you do it correctly.

comment:29 Changed 4 years ago by git

  • Commit changed from 675f8e617bdcc66e718d18089938b8d1458d0724 to 1c87b3cbb27e4f3489707ec30757dd5caa79df73

Branch pushed to git repo; I updated commit sha1. New commits:

07f054bTrac 20731: fix doc + simpler code
1c87b3cTrac 20731: remove mpq_sub_z and mpq_div_z

comment:30 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:31 Changed 4 years ago by vdelecroix

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 follow-up: Changed 4 years ago by tscrim

  • 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 git

  • Commit changed from 1c87b3cbb27e4f3489707ec30757dd5caa79df73 to 1a93a12c39522dbe60b958757e2e3922aa9c23ed

Branch pushed to git repo; I updated commit sha1. New commits:

1a93a12Merge branch 'develop' into int_rat_coercion

comment:34 in reply to: ↑ 32 ; follow-up: Changed 4 years ago by vdelecroix

  • 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 ; follow-up: Changed 4 years ago by 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.

comment:36 in reply to: ↑ 35 Changed 4 years ago by vdelecroix

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 tscrim

  • 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 as-is. Jeroen, any more comments?

Last edited 4 years ago by tscrim (previous) (diff)

comment:38 Changed 4 years ago by vdelecroix

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 tscrim

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 vdelecroix

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 vdelecroix

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 git

  • Commit changed from 1a93a12c39522dbe60b958757e2e3922aa9c23ed to dd2defb5ddf707d2dc5a84419a41fdbcd5c75a30

Branch pushed to git repo; I updated commit sha1. New commits:

dd2defbTrac 20731: isinstance(X,Y) -> type(X) is Y

comment:43 Changed 4 years ago by tscrim

  • 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 vbraun

  • 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)
    <ipython-input-...> 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)
    <ipython-input-1-6f88eab09598> in <module>()
    ----> 1 Integer(1)/Integer(0)
    <BLANKLINE>
    /home/buildslave-sage/slave/sage_git/build/src/sage/rings/integer.pyx in sage.rings.integer.Integer.__div__ (/home/buildslave-sage/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 vdelecroix

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 tscrim

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/buildslave-sage/slave/sage_git/build/src/sage/rings/integer.pyx in sage.rings.integer.Integer.__div__ (/home/buildslave-sage/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 git

  • Commit changed from dd2defb5ddf707d2dc5a84419a41fdbcd5c75a30 to d535aee38e629195fa6319a8a1d1d2efaecebec6

Branch pushed to git repo; I updated commit sha1. New commits:

d535aeeTrac 20731: fix doctest

comment:48 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:49 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:50 Changed 4 years ago by vbraun

  • Branch changed from u/vdelecroix/20731 to d535aee38e629195fa6319a8a1d1d2efaecebec6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.