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:  sage8.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: 
Description (last modified by )
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
inSR._element_constructor_()
reduces the time to 300ns  with a mock
Integer._symbolic_()
member replacingif (hasattr(x, '_symbolic_')):
withtry: 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
 Branch set to u/rws/speed_up_sr_integer_
comment:2 Changed 3 years ago by
 Commit set to d0a6609bf472a5a28becee1da5433aedaf48b3d7
 Description modified (diff)
 Status changed from new to needs_review
comment:3 Changed 3 years ago by
In pure Python, it is 23x 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
The usage of '_symbolic_' should increase so I'll change it back and add the rational case.
comment:5 Changed 3 years ago by
 Commit changed from d0a6609bf472a5a28becee1da5433aedaf48b3d7 to 5b2cbb3d7bac593926277e7820688f0e9a7cff3f
Branch pushed to git repo; I updated commit sha1. New commits:
5b2cbb3  24952: revert some change; add rational case

comment:6 Changed 3 years ago by
 Description modified (diff)
 Summary changed from Speed up SR(Integer) to Speed up SR(Integer/Rational)
comment:7 Changed 3 years ago by
 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
Could this ticket be responsible for this
sage t long warnlong 72.7 /usr/lib64/python2.7/sitepackages/sage/structure/coerce_actions.pyx ********************************************************************** File "/usr/lib64/python2.7/sitepackages/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
Yes, I believe it is. What ticket does this come up on and is it a problem?
comment:10 Changed 3 years ago by
 Status changed from positive_review to needs_work
Oh, I see, a patchbot failure.
comment:11 Changed 3 years ago by
For my own sageongentoo 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
 Commit changed from 5b2cbb3d7bac593926277e7820688f0e9a7cff3f to 4997ce484795c50455fe850fbc1b5fad60dd5ae4
Branch pushed to git repo; I updated commit sha1. New commits:
4997ce4  24952: fix doctest

comment:13 Changed 3 years ago by
 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
 Status changed from needs_review to positive_review
Should be good.
comment:15 Changed 3 years ago by
 Branch changed from u/rws/speed_up_sr_integer_ to 4997ce484795c50455fe850fbc1b5fad60dd5ae4
 Resolution set to fixed
 Status changed from positive_review to closed
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 (usingpy_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 givenmpz_t
.New commits:
24952: Speed up SR(Integer)