Avoid underscored arithmetic methods in Python

[jdemeyer]

In categories, it is better to write x + y instead of x._add_(y) since the latter can be a lot slower if _add_ is implemented in Cython.

We also remove several redundant implementations of _sub_ where they coincide with the default implementation from ModuleElement.

Depends on #20767

CC: @nthiery

Component: performance

Author: Jeroen Demeyer

Branch/Commit: ca0f7ba

Reviewer: Nicolas M. Thiéry

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

[jdemeyer]

Branch: u/jdemeyer/ticket/21448

[jdemeyer]

Last 10 new commits:

343131a	Fix doctest for Trac #20767
1f964c7	20767: minor documentation reformating / improvements
6b1f65f	20767: additional test, use Element rather than RingElement in some tests, minor doc improvement
35b64a8	Fix division action
2e8f9e4	Return exception instead of error message
59a04e4	Improve documentation and tests
2d40948	20767: Proofreading doc + doc of cdef `_add_` trick + TODO about _add_long / _mul_long
fec4abe	Further doc additions
25c9d7d	Add tests for _add_long and _mul_long
ca0f7ba	Avoid underscored arithmetic methods in Python

[jdemeyer]

Commit: ca0f7ba

[tscrim]

comment:7

This is counterintuitive to me:

In categories, it is better to write x + y instead of x.add(y) since the latter can be a lot slower if _add_ is implemented in Cython.

I would think that avoiding the additional call to __add__ (which does some additional checks) would result in a speed gain. Does this have to do with how cpdef functions are implemented in Cython?

[jdemeyer]

comment:8

Rule number 1 of optimizing Python: a method is slow. Almost anything is faster than a method lookup.

[jdemeyer]

comment:9

And the call of x + y to x.__add__(y) is optimized by Python, so it is reasonably fast. Compare:

sage: timeit('a + a', number=10^6, repeat=20)
1000000 loops, best of 20: 62.3 ns per loop
sage: timeit('a._add_(a)', number=10^6, repeat=20)
1000000 loops, best of 20: 115 ns per loop
sage: timeit('a.__add__(a)', number=10^6, repeat=20)
1000000 loops, best of 20: 162 ns per loop

I don't really have an explanation of why __add__ is slower than _add_, I would have expected them to be equally slow.

[jdemeyer]

comment:10

On the topic of methods being slow, note the difference between:

sage: a = 1
sage: timeit('parent(a)', number=10^6, repeat=20)
1000000 loops, best of 20: 74.6 ns per loop
sage: timeit('a.parent()', number=10^6, repeat=20)
1000000 loops, best of 20: 93.5 ns per loop

[nthiery]

comment:11

I checked the diff and it does what the ticket claims.

Just for a complete confirmation, could you post it a new benchmark where the code to be benchmarked is called 100 times in a loop inside a function? Just to make sure that there is no interference from the fact that we are timing at very low granularity.

Once confirmed, you can set a positive review on my behalf.

Thanks!

[nthiery]

Reviewer: Nicolas M. Thiéry

[tscrim]

comment:13

Thank you for the explanations Jeroen!

[jdemeyer]

comment:14

I made a benchmark which should be close to possible real-life usage. The conclusion:

With _add_: 5 loops, best of 3: 85.2 ms per loop

With +: 5 loops, best of 3: 78.1 ms per loop

[jdemeyer]

comment:16

Note that the benchmark also shows that implementing arithmetic in the category is really slow:

With _add_ implemented in Cython: 125 loops, best of 3: 5.57 ms per loop

With _sub_ implemented in the category: 5 loops, best of 3: 78.1 ms per loop

[jdemeyer]

Benchmark

[vbraun]

Changed branch from u/jdemeyer/ticket/21448 to ca0f7ba

[vbraun]

comment:17

Attachment: Single-underscore benchmark.ipynb.gz