Opened 3 years ago
Closed 2 years ago
#24500 closed enhancement (fixed)
Implement actions using _act_ instead of _call_
Reported by: | jdemeyer | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.5 |
Component: | coercion | Keywords: | |
Cc: | vdelecroix, tscrim | Merged in: | |
Authors: | Jeroen Demeyer | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | 3a0958d (Commits, GitHub, GitLab) | Commit: | 3a0958dcb4da8ee91b28163172061666de38bd01 |
Dependencies: | Stopgaps: |
Description (last modified by )
We change the internal API of Action
: instead of the existing _call_
method, we implement an _act_
method which always takes (g, x)
as arguments, where g
is the acting element and x
is the acted-on element.
The current implementation using _call_
takes a left and right argument. This is less efficient because many actions can be left or right actions. This means that every _call_
method needs to "decode" its arguments as g
and x
.
Work on #24247 shows that a significant amount of time is spent in Action.__call__
. This ticket optimizes that quite a bit. It also adds documentation to Action
.
Change History (29)
comment:1 Changed 3 years ago by
- Description modified (diff)
comment:2 Changed 3 years ago by
- Dependencies set to #5574
comment:3 Changed 3 years ago by
- Branch set to u/jdemeyer/optimize_action___call__
comment:4 Changed 3 years ago by
- Commit set to f2b676ef4e7b13eb4e14f117d39afb8b06ebdc03
comment:5 Changed 3 years ago by
- Component changed from performance to coercion
- Description modified (diff)
- Status changed from new to needs_review
- Summary changed from Optimize Action.__call__ to Implement action using _act_ instead of _call_
comment:6 Changed 3 years ago by
- Description modified (diff)
comment:7 Changed 3 years ago by
- Cc vdelecroix added
- Summary changed from Implement action using _act_ instead of _call_ to Implement actions using _act_ instead of _call_
comment:8 Changed 3 years ago by
- Description modified (diff)
comment:9 follow-up: ↓ 10 Changed 3 years ago by
Do you have timings with this ticket (at least, my understanding of the description is the "after" does not include this ticket)?
comment:10 in reply to: ↑ 9 ; follow-up: ↓ 12 Changed 3 years ago by
Replying to tscrim:
Do you have timings with this ticket (at least, my understanding of the description is the "after" does not include this ticket)?
The "after" does include this ticket.
comment:11 Changed 3 years ago by
- Description modified (diff)
comment:12 in reply to: ↑ 10 ; follow-up: ↓ 13 Changed 3 years ago by
Replying to jdemeyer:
The "after" does include this ticket.
Did you invert the “before” and “after” parts then?
comment:13 in reply to: ↑ 12 Changed 3 years ago by
comment:14 Changed 3 years ago by
On 8.2.beta4:
sage: k.<a> = GF(4, impl="ntl"); n = 2; timeit('a ^ n', number=100000, repeat=20) 100000 loops, best of 20: 343 ns per loop sage: a = RDF(2); n = ZZ(2); timeit('a ^ n', number=100000, repeat=20) 100000 loops, best of 20: 137 ns per loop sage: a = ZZ.ideal(2); n = ZZ(2); timeit('a ^ n', number=10000, repeat=20) 10000 loops, best of 20: 7.62 µs per loop sage: a = AA(8); n = 1/3; timeit('a ^ n', number=10000, repeat=20) 10000 loops, best of 20: 7 µs per loop
vs with #5574:
sage: k.<a> = GF(4, impl="ntl"); n = 2; timeit('a ^ n', number=100000, repeat=20) 100000 loops, best of 20: 341 ns per loop sage: a = RDF(2); n = ZZ(2); timeit('a ^ n', number=100000, repeat=20) 100000 loops, best of 20: 139 ns per loop sage: a = ZZ.ideal(2); n = ZZ(2); timeit('a ^ n', number=10000, repeat=20) 10000 loops, best of 20: 7.71 µs per loop sage: a = AA(8); n = 1/3; timeit('a ^ n', number=10000, repeat=20) 10000 loops, best of 20: 8.75 µs per loop
vs with #24500:
sage: k.<a> = GF(4, impl="ntl"); n = 2; timeit('a ^ n', number=100000, repeat=20) 100000 loops, best of 20: 356 ns per loop sage: a = RDF(2); n = ZZ(2); timeit('a ^ n', number=100000, repeat=20) 100000 loops, best of 20: 141 ns per loop sage: a = ZZ.ideal(2); n = ZZ(2); timeit('a ^ n', number=10000, repeat=20) 10000 loops, best of 20: 7.53 µs per loop sage: a = AA(8); n = 1/3; timeit('a ^ n', number=10000, repeat=20) 10000 loops, best of 20: 8.91 µs per loop
So I can explain why the first test is slower: there is an additional if action._is_left
that is needed to be performed that previously was not there because powering could assume things in a specific order. The last one slowing down is due to #5574 (and some numerical noise). The middle two are almost identical (at least within the numerical noise I was getting), which is expected considering they perform the same number of checks in Cython.
However, I did get an improvement when something was calling is_left()
in Python:
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x = M(x); xy = M(x*y); z=M(z); n=2 sage: timeit('x * n', number=10000, repeat=20) 10000 loops, best of 20: 6.52 µs per loop sage: timeit('n * x', number=10000, repeat=20) 10000 loops, best of 20: 6.43 µs per loop
vs with #24500
sage: timeit('n * x', number=10000, repeat=20) 10000 loops, best of 20: 6.14 µs per loop sage: timeit('x * n', number=10000, repeat=20) 10000 loops, best of 20: 6.17 µs per loop
So my conclusion is this ticket does do a little bit of optimizing in certain cases and a regression in others. My current inclination is to give this ticket a positive review because it makes the action interface more clean by removing some of the implementation burden (i.e., deciding which input is which type). Do you agree with my assessment? Anyone else have any objections?
comment:15 Changed 3 years ago by
- Dependencies #5574 deleted
- Status changed from needs_review to needs_work
comment:16 Changed 3 years ago by
- Commit changed from f2b676ef4e7b13eb4e14f117d39afb8b06ebdc03 to 0587d3f4c1f2a75ecf095461810414ee43a35b1c
comment:17 Changed 3 years ago by
- Status changed from needs_work to needs_review
comment:18 Changed 3 years ago by
- Status changed from needs_review to needs_work
Many failing tests involving valuations...
comment:19 Changed 3 years ago by
- Commit changed from 0587d3f4c1f2a75ecf095461810414ee43a35b1c to 30d8bac7fa31db13511c867ec2ca95de76d2313d
comment:20 Changed 3 years ago by
- Status changed from needs_work to needs_review
comment:21 Changed 3 years ago by
- Status changed from needs_review to needs_work
comment:22 Changed 3 years ago by
- Commit changed from 30d8bac7fa31db13511c867ec2ca95de76d2313d to 0406b4a1a2b91dc7976a5a7271acc770c702eab5
comment:23 Changed 3 years ago by
- Status changed from needs_work to needs_review
comment:24 Changed 3 years ago by
Part of the slowdown in this ticket was caused by the second commit removing Set_PythonType
. I'll drop that commit, then the regressions are gone for me.
comment:25 Changed 3 years ago by
- Commit changed from 0406b4a1a2b91dc7976a5a7271acc770c702eab5 to 800d30b2d3ff09d00978b9223cbeff966d468f66
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:26 Changed 2 years ago by
- Commit changed from 800d30b2d3ff09d00978b9223cbeff966d468f66 to 3a0958dcb4da8ee91b28163172061666de38bd01
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3a0958d | Implement actions using _act_ instead of _call_
|
comment:27 Changed 2 years ago by
- Description modified (diff)
comment:28 Changed 2 years ago by
- Milestone changed from sage-8.2 to sage-8.5
- Reviewers set to Travis Scrimshaw
- Status changed from needs_review to positive_review
LGTM. Sorry I let this ticket fall off my radar.
comment:29 Changed 2 years ago by
- Branch changed from u/jdemeyer/optimize_action___call__ to 3a0958dcb4da8ee91b28163172061666de38bd01
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
Implement actions using _act_ instead of _call_
Don't use Set_PythonType in IntegerAction