Opened 3 years ago

Closed 3 years ago

#24952 closed enhancement (fixed)

Speed up SR(Integer/Rational)

Reported by: rws Owned by:
Priority: major Milestone: sage-8.2
Component: performance Keywords:
Cc: Merged in:
Authors: Ralf Stephan Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 4997ce4 (Commits, GitHub, GitLab) Commit: 4997ce484795c50455fe850fbc1b5fad60dd5ae4
Dependencies: Stopgaps:

Status badges

Description (last modified by rws)

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.

Change History (15)

comment:1 Changed 3 years ago by rws

  • Branch set to u/rws/speed_up_sr_integer_

comment:2 Changed 3 years ago by rws

  • Authors set to Ralf Stephan
  • Commit set to d0a6609bf472a5a28becee1da5433aedaf48b3d7
  • Description modified (diff)
  • Status changed from new to needs_review

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:

d0a660924952: Speed up SR(Integer)

comment:3 Changed 3 years ago by tscrim

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

comment:4 Changed 3 years ago by rws

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

comment:5 Changed 3 years ago by git

  • Commit changed from d0a6609bf472a5a28becee1da5433aedaf48b3d7 to 5b2cbb3d7bac593926277e7820688f0e9a7cff3f

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

5b2cbb324952: revert some change; add rational case

comment:6 Changed 3 years ago by rws

  • Description modified (diff)
  • Summary changed from Speed up SR(Integer) to Speed up SR(Integer/Rational)

comment:7 Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

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.

comment:8 Changed 3 years ago by fbissey

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]

comment:9 Changed 3 years ago by tscrim

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

comment:10 Changed 3 years ago by tscrim

  • Status changed from positive_review to needs_work

Oh, I see, a patchbot failure.

comment:11 Changed 3 years ago by fbissey

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.

comment:12 Changed 3 years ago by git

  • Commit changed from 5b2cbb3d7bac593926277e7820688f0e9a7cff3f to 4997ce484795c50455fe850fbc1b5fad60dd5ae4

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

4997ce424952: fix doctest

comment:13 Changed 3 years ago by rws

  • Status changed from needs_work to needs_review

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

comment:14 Changed 3 years ago by fbissey

  • Status changed from needs_review to positive_review

Should be good.

comment:15 Changed 3 years ago by vbraun

  • Branch changed from u/rws/speed_up_sr_integer_ to 4997ce484795c50455fe850fbc1b5fad60dd5ae4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.