Speed up SR(Integer/Rational)

[rwst]

Before:

sage: a = ZZ(23)
sage: %timeit SR(a)
100000 loops, best of 3: 3.51 µs per loop
sage: %timeit RR(a)
1000000 loops, best of 3: 218 ns per loop

Profiling with callgrind shows Python code the main contributor (only 0.4% Pynac), with a big chunk from malloc/free.

• simply moving up the check for Integer in SR._element_constructor_() reduces the time to 300ns
• with a mock Integer._symbolic_() member replacing if (hasattr(x, '_symbolic_')): with try: x._symbolic_() gains 100ns

So this ticket will implement a dedicated Integer._symbolic_() that calls helper functions in symbolic/expression.pyx.

Result:

sage: %timeit _=SR(a)
The slowest run took 32.27 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 399 ns per loop

With rational the change is from 4.4µs to 0.6µs.

Component: performance

Author: Ralf Stephan

Branch/Commit: 4997ce4

Reviewer: Travis Scrimshaw

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

[rwst]

Branch: u/rws/speed_up_sr_integer_

[rwst]

comment:2

Note the created ex is "numeric" with type MPZ, i.e. Pynac (always) checks if a Python object is an Integer (using py_funcs.py_is_Integer(o)) and converts it to internal GMP format (using py_funcs.py_mpz_from_integer(o)). This means symbolic operations are optimally fast. It also means the process can be further improved if Pynac provided an interface to create its MPZ numerics directly from a given mpz_t.

---

New commits:

d0a6609

24952: Speed up SR(Integer)

[rwst]

Author: Ralf Stephan

[rwst]

Commit: d0a6609

[tscrim]

comment:3

In pure Python, it is 2-3x faster to check hasattr when such an attribute is not there, but having the attribute is slower, but not by so much:

sage: def check(x):
....:     if hasattr(x,'parent'):
....:         return x.parent()
....:     return None
sage: def check2(x):
....:     try:
....:         return x.parent()
....:     except AttributeError:
....:         return None
sage: z = 5
sage: %timeit check(z)
1000000 loops, best of 3: 205 ns per loop
sage: %timeit check2(z)
10000000 loops, best of 3: 126 ns per loop
sage: z = int(5)
sage: %timeit check(z)
1000000 loops, best of 3: 381 ns per loop
sage: %timeit check2(z)
1000000 loops, best of 3: 889 ns per loop

Similar using Cython:

sage: %%cython
....: def check(x):
....:     if hasattr(x,'parent'):
....:         return x.parent()
....: def check2(x):
....:     try:
....:         return x.parent()
....:     except AttributeError:
....:         return None
....: 
sage: z = 5
sage: %timeit check(z)
10000000 loops, best of 3: 94 ns per loop
sage: %timeit check2(z)
10000000 loops, best of 3: 68.5 ns per loop
sage: z = int(5)
sage: %timeit check(z)
1000000 loops, best of 3: 185 ns per loop
sage: %timeit check2(z)
1000000 loops, best of 3: 395 ns per loop

So I am not convinced that removing the hasattr check is for the better. I guess the question is how often do you expect things to be passed to SR that do not have a _symbolic_? What about also doing SR(Rational)?

[rwst]

comment:4

The usage of 'symbolic' should increase so I'll change it back and add the rational case.

[sagetrac-git]

Changed commit from d0a6609 to 5b2cbb3

[sagetrac-git]

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

5b2cbb3

24952: revert some change; add rational case

[tscrim]

comment:7

Thanks. I agree that more thing should implement a _symbolic_. I just worry it is too much a swing in the other direction in terms of speed to assume it is an attribute.

[tscrim]

Reviewer: Travis Scrimshaw

[kiwifb]

comment:8

Could this ticket be responsible for this

sage -t --long --warn-long 72.7 /usr/lib64/python2.7/site-packages/sage/structure/coerce_actions.pyx
**********************************************************************
File "/usr/lib64/python2.7/site-packages/sage/structure/coerce_actions.pyx", line 525, in sage.structure.coerce_actions.ModuleAction.__invert__
Failed example:
    cm.explain(x, 1, operator.truediv)
Expected:
    Action discovered.
        Right inverse action by Symbolic Constants Subring on Univariate Polynomial Ring in x over Symbolic Constants Subring
        with precomposition on right by Coercion map:
          From: Integer Ring
          To:   Symbolic Constants Subring
    Result lives in Univariate Polynomial Ring in x over Symbolic Constants Subring
    Univariate Polynomial Ring in x over Symbolic Constants Subring
Got:
    Action discovered.
        Right inverse action by Symbolic Constants Subring on Univariate Polynomial Ring in x over Symbolic Constants Subring
        with precomposition on right by Conversion via _symbolic_ method map:
          From: Integer Ring
          To:   Symbolic Constants Subring
    Result lives in Univariate Polynomial Ring in x over Symbolic Constants Subring
    Univariate Polynomial Ring in x over Symbolic Constants Subring
**********************************************************************
1 item had failures:
   1 of  26 in sage.structure.coerce_actions.ModuleAction.__invert__
    [143 tests, 1 failure, 1.06 s]

[tscrim]

comment:9

Yes, I believe it is. What ticket does this come up on and is it a problem?

[tscrim]

comment:10

Oh, I see, a patchbot failure.

[kiwifb]

comment:11

For my own sage-on-gentoo needs I follow the branch were Volker merges stuff. And that one showed up. It took a bit of effort to track a reasonable culprit amongst the tickets merged.

[sagetrac-git]

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

4997ce4

24952: fix doctest

[sagetrac-git]

Changed commit from 5b2cbb3 to 4997ce4

[rwst]

comment:13

I just replaced the ...Coercion... with the ...Conversion... part because the new output does not seem wrong for me.

[kiwifb]

comment:14

Should be good.

[vbraun]

Changed branch from u/rws/speed_up_sr_integer_ to 4997ce4