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.

[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

[tscrim]

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

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

[mmezzarobba]

Replying to jdemeyer:

The "after" does include this ticket.

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

[jdemeyer]

Replying to mmezzarobba:

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

No, I did not...

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

[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

[jdemeyer]

Many failing tests involving valuations...

[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

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

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.

[git]

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

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

[tscrim]

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