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) Commit: 3a0958dcb4da8ee91b28163172061666de38bd01
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

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 jdemeyer

  • Description modified (diff)

comment:2 Changed 3 years ago by jdemeyer

  • Dependencies set to #5574

comment:3 Changed 3 years ago by jdemeyer

  • Branch set to u/jdemeyer/optimize_action___call__

comment:4 Changed 3 years ago by git

  • Commit set to f2b676ef4e7b13eb4e14f117d39afb8b06ebdc03

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

dd3b5b5Implement actions using _act_ instead of _call_
f2b676eDon't use Set_PythonType in IntegerAction

comment:5 Changed 3 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • 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 jdemeyer

  • Description modified (diff)

comment:7 Changed 3 years ago by jdemeyer

  • 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 jdemeyer

  • Description modified (diff)

comment:9 follow-up: Changed 3 years ago by tscrim

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: Changed 3 years ago by jdemeyer

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 jdemeyer

  • Description modified (diff)

comment:12 in reply to: ↑ 10 ; follow-up: Changed 3 years ago by mmezzarobba

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 jdemeyer

Replying to mmezzarobba:

Did you invert the “before” and “after” parts then?

No, I did not...

comment:14 Changed 3 years ago by tscrim

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 jdemeyer

  • Dependencies #5574 deleted
  • Status changed from needs_review to needs_work

comment:16 Changed 3 years ago by git

  • Commit changed from f2b676ef4e7b13eb4e14f117d39afb8b06ebdc03 to 0587d3f4c1f2a75ecf095461810414ee43a35b1c

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3dc30bfImplement actions using _act_ instead of _call_
0587d3fDon't use Set_PythonType in IntegerAction

comment:17 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:18 Changed 3 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Many failing tests involving valuations...

comment:19 Changed 3 years ago by git

  • Commit changed from 0587d3f4c1f2a75ecf095461810414ee43a35b1c to 30d8bac7fa31db13511c867ec2ca95de76d2313d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a607ecbImplement actions using _act_ instead of _call_
30d8bacDon't use Set_PythonType in IntegerAction

comment:20 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:21 Changed 3 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:22 Changed 3 years ago by git

  • Commit changed from 30d8bac7fa31db13511c867ec2ca95de76d2313d to 0406b4a1a2b91dc7976a5a7271acc770c702eab5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

800d30bImplement actions using _act_ instead of _call_
0406b4aDon't use Set_PythonType in IntegerAction

comment:23 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:24 Changed 3 years ago by jdemeyer

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 git

  • 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 git

  • Commit changed from 800d30b2d3ff09d00978b9223cbeff966d468f66 to 3a0958dcb4da8ee91b28163172061666de38bd01

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3a0958dImplement actions using _act_ instead of _call_

comment:27 Changed 2 years ago by jdemeyer

  • Description modified (diff)

comment:28 Changed 2 years ago by tscrim

  • 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 vbraun

  • Branch changed from u/jdemeyer/optimize_action___call__ to 3a0958dcb4da8ee91b28163172061666de38bd01
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.