shortcut coercion for Integer-Rational operations #20731

videlec · 2016-05-31T13:38:42Z

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

CC: @jdemeyer

Component: coercion

Keywords: days74

Author: Vincent Delecroix

Branch/Commit: d535aee

Reviewer: Jeroen Demeyer, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/20731

The text was updated successfully, but these errors were encountered:

videlec · 2016-05-31T13:44:41Z

Branch: u/vdelecroix/20731

sagetrac-git · 2016-05-31T13:44:45Z

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

`33f9fd4`	`Trac 20731: shortcut coercion for Integer-Rational`

sagetrac-git · 2016-05-31T13:44:45Z

Commit: 33f9fd4

sagetrac-git · 2016-05-31T19:20:28Z

Changed commit from 33f9fd4 to 19c075b

sagetrac-git · 2016-05-31T19:20:28Z

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

`19c075b`	`Trac 20731: fix doctests`

jdemeyer · 2016-06-01T08:21:40Z

comment:4

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.

sagetrac-git · 2016-06-01T08:26:01Z

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

`fdf79ac`	`Trac 20731: get rid of ZZ._div`

sagetrac-git · 2016-06-01T08:26:01Z

Changed commit from 19c075b to fdf79ac

sagetrac-git · 2016-06-01T08:30:51Z

Changed commit from fdf79ac to eec4168

sagetrac-git · 2016-06-01T08:30:51Z

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

`9078830`	`Trac 20731: moving binop`
`eec4168`	`Trac 20731: fix the move`

jdemeyer · 2016-06-01T15:52:51Z

comment:7

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?

videlec · 2016-06-01T16:24:46Z

comment:8

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

jdemeyer · 2016-06-01T16:28:54Z

comment:9

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

jdemeyer · 2016-06-01T16:30:04Z

comment:10

In src/sage/repl/interpreter.py, there is a good reason that the line numbers were changed to ...

jdemeyer · 2016-06-01T19:55:20Z

comment:11

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.

sagetrac-git · 2016-06-02T02:44:24Z

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

`72f77b9`	`Trac 20731: simpler operations`
`c7a8d8e`	`20731: simpler mpq_mul_z/mpq_div_z`

sagetrac-git · 2016-06-02T02:44:24Z

Changed commit from eec4168 to c7a8d8e

jdemeyer · 2016-06-02T08:13:58Z

comment:14

[comment:10]

tscrim · 2016-06-26T21:29:30Z

comment:35

Replying to @videlec:

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.

videlec · 2016-06-27T05:45:47Z

comment:36

Replying to @tscrim:

Replying to @videlec:

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.

tscrim · 2016-06-27T13:58:04Z

Reviewer: Jeroen Demeyer, Travis Scrimshaw

tscrim · 2016-06-27T13:58:04Z

comment:37

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?

videlec · 2016-07-08T20:37:05Z

comment:38

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?

tscrim · 2016-07-09T19:19:34Z

comment:39

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.

videlec · 2016-07-09T20:35:46Z

comment:40

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

videlec · 2016-07-09T20:50:47Z

comment:41

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

sagetrac-git · 2016-07-09T20:51:59Z

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

`dd2defb`	`Trac 20731: isinstance(X,Y) -> type(X) is Y`

sagetrac-git · 2016-07-09T20:51:59Z

Changed commit from 1a93a12 to dd2defb

tscrim · 2016-07-10T18:01:19Z

comment:43

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.

vbraun · 2016-07-10T21:44:47Z

comment:44

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]

videlec · 2016-07-11T16:15:31Z

comment:45

Dear Volker,

I am not able to reproduce this... could you tell us on which kind of configuration you obtained that?

Vincent

tscrim · 2016-07-15T20:00:53Z

comment:46

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.

sagetrac-git · 2016-07-22T22:41:34Z

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

`d535aee`	`Trac 20731: fix doctest`

sagetrac-git · 2016-07-22T22:41:34Z

Changed commit from dd2defb to d535aee

vbraun · 2016-07-23T18:38:25Z

Changed branch from u/vdelecroix/20731 to d535aee

videlec added this to the sage-7.3 milestone May 31, 2016

videlec added c: coercion labels May 31, 2016

This comment has been minimized.

Sign in to view

videlec added the s: needs review label May 31, 2016

jdemeyer added s: needs work and removed s: needs review labels Jun 1, 2016

videlec added s: needs review and removed s: needs work labels Jun 2, 2016

jdemeyer added s: needs work and removed s: needs review labels Jun 2, 2016

videlec added s: needs review and removed s: needs work labels Jun 26, 2016

tscrim added s: positive review and removed s: needs review labels Jul 10, 2016

vbraun added s: needs work and removed s: positive review labels Jul 10, 2016

videlec added s: needs review and removed s: needs work labels Jul 22, 2016

tscrim added s: positive review and removed s: needs review labels Jul 22, 2016

vbraun removed the s: positive review label Jul 23, 2016

vbraun closed this as completed in 38381df Jul 23, 2016

videlec mentioned this issue Jul 8, 2016

faster __invert__ for integers #20777

Closed

shortcut coercion for Integer-Rational operations #20731

shortcut coercion for Integer-Rational operations #20731

Comments

videlec commented May 31, 2016

This comment has been minimized.

videlec commented May 31, 2016

sagetrac-git mannequin commented May 31, 2016

sagetrac-git mannequin commented May 31, 2016

sagetrac-git mannequin commented May 31, 2016

sagetrac-git mannequin commented May 31, 2016

jdemeyer commented Jun 1, 2016

sagetrac-git mannequin commented Jun 1, 2016

sagetrac-git mannequin commented Jun 1, 2016

sagetrac-git mannequin commented Jun 1, 2016

sagetrac-git mannequin commented Jun 1, 2016

jdemeyer commented Jun 1, 2016

videlec commented Jun 1, 2016

jdemeyer commented Jun 1, 2016

jdemeyer commented Jun 1, 2016

jdemeyer commented Jun 1, 2016

sagetrac-git mannequin commented Jun 2, 2016

sagetrac-git mannequin commented Jun 2, 2016

jdemeyer commented Jun 2, 2016

tscrim commented Jun 26, 2016

videlec commented Jun 27, 2016

tscrim commented Jun 27, 2016

tscrim commented Jun 27, 2016

videlec commented Jul 8, 2016

tscrim commented Jul 9, 2016

videlec commented Jul 9, 2016

videlec commented Jul 9, 2016

sagetrac-git mannequin commented Jul 9, 2016

sagetrac-git mannequin commented Jul 9, 2016

tscrim commented Jul 10, 2016

vbraun commented Jul 10, 2016

videlec commented Jul 11, 2016

tscrim commented Jul 15, 2016

sagetrac-git mannequin commented Jul 22, 2016

sagetrac-git mannequin commented Jul 22, 2016

vbraun commented Jul 23, 2016