Avoid a coercion when computing an element to the power of 0

[sagetrac-nborie]

In the generic structure of element, a coercion is called to compute an element z to the power of 0 : z^0

The goal of this ticket is trying to replace all call of Parent(1) by Parent.one() to avoid the coercion. (and hope Sage is ready for a such change...)

Before :

sage: K = CyclotomicField(46)
sage: z = K.gen()
sage: %prun z^0
         11 function calls in 0.000 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 number_field.py:4871(_coerce_non_number_field_element_in)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 number_field.py:6702(_element_constructor_)
        1    0.000    0.000    0.000    0.000 number_field.py:4221(polynomial_ntl)
        4    0.000    0.000    0.000    0.000 {isinstance}
        1    0.000    0.000    0.000    0.000 number_field.py:4210(absolute_polynomial_ntl)
        1    0.000    0.000    0.000    0.000 gap.py:1299(is_GapElement)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

sage: %prun z^3
         2 function calls in 0.000 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

And for the speed :

sage: timeit('z^0')
625 loops, best of 3: 28 µs per loop
sage: timeit('z^3')
625 loops, best of 3: 7.78 µs per loop

depends on #9065
depends on #9138

Depends on #11900

CC: @sagetrac-sage-combinat @simon-king-jena

Component: performance

Keywords: element, power, zero, Cernay2012

Author: Nicolas Borie

Reviewer: Nathann Cohen

Merged: sage-5.0.beta4

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

[sagetrac-nborie]

comment:1

With the patch applied, same tests give:

sage: K = CyclotomicField(46)
sage: z = K.gen()
sage: %prun z^0
         2 function calls in 0.000 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

sage: %prun z^3
         2 function calls in 0.000 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

And

sage: timeit('z^0')
625 loops, best of 3: 1.01 µs per loop
sage: timeit('z^3')
625 loops, best of 3: 7.68 µs per loop

We will see what the builbot will say. What pass, what crash ....

[sagetrac-nborie]

comment:2

Three parents does not have the method one and don't pass the change.

[sagetrac-nborie]

comment:3

I looked at the three parents for which elements didn't pass the tests. Every times, it seems clear to me that they deserve to have a method one. I had some. I also fixed some typos on the way and ran a 'delete-trailing-whitespace' which make the patch a little bit more long...

I hope all will be fix now with this one.

[nthiery]

Author: Nicolas Borie

[nthiery]

comment:4

Bonjour Nicolas!

Thanks for your work on that. Please investigate the test failure reported by the patchbot, and double check that TestSuite is run on every parent that you modified. While we are at it, we probably want to implement .one() as a cached_method. I am not sure about the deletion of trailing whitespaces outside of the lines you change anyway, as this is subject to making conflicts.

Ah, and do we want to do the same for .zero()?

Amitiés,
Nicolas

[simon-king-jena]

comment:5

Hi Nicolas,

Replying to @nthiery:

While we are at it, we probably want to implement .one() as a cached_method. I am not sure about the deletion of trailing whitespaces outside of the lines you change anyway, as this is subject to making conflicts.
Ah, and do we want to do the same for .zero()?

I suspect that question is partially addressed to me, as it may relate with #11115?

I didn't look at the patch. But if you mean to make .zero() and .one() a cached method of the parent class of a category, then in fact #11115 is needed in order to make the cache work on those parent structures that do not allow attribute assignment.

[nthiery]

comment:6

Replying to @simon-king-jena:

I suspect that question is partially addressed to me, as it may relate with #11115?

Yup. And to detect potential conflicts with the ongoing changes in rings and such.

I didn't look at the patch. But if you mean to make .zero() and .one() a cached method of the parent class of a category, then in fact #11115 is needed in order to make the cache work on those parent structures that do not allow attribute assignment.

+1

[sagetrac-nborie]

comment:7

Hello you both,

For the failures from the buildbot, I can't reproduce them.

nicolas@lancelot:/opt/sage/devel/sage-combinat$ hg qtop
trac_11257_avoid_coercion_power_zero-nb.patch
nicolas@lancelot:/opt/sage/devel/sage-combinat$ sage -t sage/tests/cmdline.py 
sage -t  "devel/sage-combinat/sage/tests/cmdline.py"        
	 [14.7 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 14.7 seconds
nicolas@lancelot:/opt/sage/devel/sage-combinat$ sage -t ../sagenb-main/sagenb/misc/misc.py
sage -t  "devel/sagenb-main/sagenb/misc/misc.py"            
	 [1.9 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 1.9 seconds

For the TestSuite, there is some work to be done. A new version is on the way...

Cheers,
Nicolas.

[sagetrac-nborie]

comment:8

I tried to do the best... Fix the TestSuite on old parents is not a simple job. Especially when one doesn't know enough about old category system... I fix properly the categories of affected parents, but I do not know how to do for the elements (especially when there is some facade with a separate implementation of the elements).

(((
sage: w = SymmetricGroup(2)([2,1])
sage: G = ArithmeticSubgroup_Permutation(w, w)
sage: G.category()
Category of facade groups
sage: TestSuite(G).run(skip=['_test_elements'])
)))

I think I passed already a lot of time on these parents (major part of today of trying to understand what they represent mathematically speaking...). Especially for the FreeMonoid feature. In the new category framework, the example of monoid (i.e. "Monoids().example()") is the free monoid. And the one coming from the category framework inherit of a LOT of top level methods. I try to fix FreeMonoidElement in sage/monoid with categories but if the choice was mine, I would just overwrite the 2005 version with these coming from category...

Hoping the patchbot will be happy this time! The patch does already much more than the ticket!

[nthiery]

comment:9

Replying to @sagetrac-nborie:

I tried to do the best... Fix the TestSuite on old parents is not a simple job. Especially when one doesn't know enough about old category system... I fix properly the categories of affected parents, but I do not know how to do for the elements (especially when there is some facade with a separate implementation of the elements).

(((
sage: w = SymmetricGroup(2)([2,1])
sage: G = ArithmeticSubgroup_Permutation(w, w)
sage: G.category()
Category of facade groups
sage: TestSuite(G).run(skip=['_test_elements'])
)))

I think I passed already a lot of time on these parents (major part of today of trying to understand what they represent mathematically speaking...). Especially for the FreeMonoid feature. In the new category framework, the example of monoid (i.e. "Monoids().example()") is the free monoid. And the one coming from the category framework inherit of a LOT of top level methods. I try to fix FreeMonoidElement in sage/monoid with categories but if the choice was mine, I would just overwrite the 2005 version with these coming from category...

Hoping the patchbot will be happy this time! The patch does already much more than the ticket!

Oops, this is going far beyond what I expected! I just meant to add
TestSuite, and skip tests not related to zero / one. Now, this is not
wasted time, so thanks! One should just be careful that this does not
overlap with changes by Simon.

Cheers,
Nicolas

[sagetrac-nborie]

comment:11

Sorry for spamming, but I don't know how to tell the builbot that dependencies have change otherwise than change the status of the ticket.

[simon-king-jena]

comment:13

Replying to @nthiery:

Oops, this is going far beyond what I expected! I just meant to add
TestSuite, and skip tests not related to zero / one. Now, this is not
wasted time, so thanks! One should just be careful that this does not
overlap with changes by Simon.

I don't have the time to verify whether there is an overlap. But: If there is an overlap then it is with #9944 or #9138. These two tickets try to make all rings use the category framework properly, and in some cases it also provides them with the new coercion model.

If what you do is about something else but rings, then it is very likely that there is no overlap.

Best regards,

Simon

[sagetrac-nborie]

comment:14

There going to have a little conflict with #9138 and its second patch trac9138_categories_for_more_rings.patch. As Simon make a better categorifycation than me, I will place this patch after. I will also begin the review of #9138, I won't probably review everything (It is not a small patch), but I will give a list of what I review (according my skills). Thanks very very much for #9138 (not an amazing task but it has to be done!)

Cheers,

[sagetrac-nborie]

Changed keywords from element, power, zero to element, power, zero, Cernay2012

[sagetrac-nborie]

Dependencies: #11900

[sagetrac-nborie]

comment:17

Attachment: trac_11257_avoid_coercion_power_zero-nb.patch.gz

I just added a one method for EtaGroup... With the categories for all(more) ring from Simon, all tests should pass...

[nathanncohen]

comment:18

I tested it again, and it is good to go :-)

Nathann

[nathanncohen]

Reviewer: Nathann Cohen

[jdemeyer]

Merged: sage-5.0.beta4