Implement actions using _act_ instead of _call_

[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.

CC: @videlec @tscrim

Component: coercion

Author: Jeroen Demeyer

Branch/Commit: 3a0958d

Reviewer: Travis Scrimshaw

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

[jdemeyer]

Dependencies: #5574

[jdemeyer]

Branch: u/jdemeyer/optimize_action___call__

[sagetrac-git]

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

dd3b5b5	Implement actions using `_act_` instead of _call_
f2b676e	Don't use Set_PythonType in IntegerAction

[sagetrac-git]

Commit: f2b676e

[jdemeyer]

Author: Jeroen Demeyer

[tscrim]

comment:9

Do you have timings with this ticket (at least, my understanding of the description is the "after" does not include this ticket)?

[jdemeyer]

comment:10

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.

[mezzarobba]

comment:12

Replying to @jdemeyer:

The "after" does include this ticket.

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

[jdemeyer]

comment:13

Replying to @mezzarobba:

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

No, I did not...

[tscrim]

comment:14

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?

[jdemeyer]

Changed dependencies from #5574 to none

[sagetrac-git]

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

3dc30bf	Implement actions using `_act_` instead of _call_
0587d3f	Don't use Set_PythonType in IntegerAction

[sagetrac-git]

Changed commit from f2b676e to 0587d3f

[jdemeyer]

comment:18

Many failing tests involving valuations...

[sagetrac-git]

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

a607ecb	Implement actions using `_act_` instead of _call_
30d8bac	Don't use Set_PythonType in IntegerAction

[sagetrac-git]

Changed commit from 0587d3f to 30d8bac

[sagetrac-git]

Changed commit from 30d8bac to 0406b4a

[sagetrac-git]

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

800d30b	Implement actions using `_act_` instead of _call_
0406b4a	Don't use Set_PythonType in IntegerAction

[jdemeyer]

comment:24

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.

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 0406b4a to 800d30b

[sagetrac-git]

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

3a0958d

Implement actions using `_act_` instead of _call_

[sagetrac-git]

Changed commit from 800d30b to 3a0958d

[tscrim]

comment:28

LGTM. Sorry I let this ticket fall off my radar.

[tscrim]

Reviewer: Travis Scrimshaw

[vbraun]

Changed branch from u/jdemeyer/optimize_action___call__ to 3a0958d