Opened 6 years ago

Closed 5 years ago

#11257 closed enhancement (fixed)

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

Reported by: nborie Owned by: nborie
Priority: major Milestone: sage-5.0
Component: performance Keywords: coercion, element, power, zero, Cernay2012
Cc: sage-combinat, SimonKing Merged in: sage-5.0.beta4
Authors: Nicolas Borie Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11900 Stopgaps:

Description (last modified by nborie)

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

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

Attachments (1)

trac_11257_avoid_coercion_power_zero-nb.patch (1.5 KB) - added by nborie 5 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 6 years ago by nborie

  • Status changed from new to needs_review

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

comment:2 Changed 6 years ago by nborie

  • Status changed from needs_review to needs_work

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

comment:3 Changed 6 years ago by nborie

  • Status changed from needs_work to needs_review

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.

comment:4 follow-up: Changed 6 years ago by nthiery

  • Authors set to Nicolas Borie
  • Cc SimonKing added

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

comment:5 in reply to: ↑ 4 ; follow-up: Changed 6 years ago by SimonKing

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.

comment:6 in reply to: ↑ 5 Changed 6 years ago by nthiery

Replying to SimonKing:

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

comment:7 Changed 6 years ago by nborie

  • Status changed from needs_review to needs_work

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.

comment:8 follow-up: Changed 6 years ago by nborie

  • Status changed from needs_work to needs_review

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!

comment:9 in reply to: ↑ 8 ; follow-up: Changed 6 years ago by nthiery

Replying to 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

comment:10 Changed 6 years ago by nborie

  • Description modified (diff)

comment:11 Changed 6 years ago by nborie

  • Status changed from needs_review to needs_work

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.

comment:12 Changed 6 years ago by nborie

  • Status changed from needs_work to needs_review

comment:13 in reply to: ↑ 9 Changed 6 years ago by SimonKing

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

comment:14 Changed 6 years ago by nborie

  • Description modified (diff)
  • Status changed from needs_review to needs_work

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,

comment:15 Changed 5 years ago by nborie

  • Keywords Cernay2012 added

comment:16 Changed 5 years ago by nborie

  • Status changed from needs_work to needs_review

comment:17 Changed 5 years ago by nborie

  • Dependencies set to #11900

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

comment:18 Changed 5 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

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

Nathann

comment:19 Changed 5 years ago by jdemeyer

  • Merged in set to sage-5.0.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.