Opened 7 years ago
Last modified 7 years ago
#15427 new enhancement
Performance of casting polynomials to polynomials over finite fields
Reported by: | afiori | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.4 |
Component: | performance | Keywords: | FiniteField Polynomial Casting |
Cc: | roed, jpflori | Merged in: | |
Authors: | Andrew Fiori | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
One would expect the performance of casting the usual way (as in test 1 below) to be at least not much worse than test 2:
sage: QQX=QQ['x'] sage: QP=Qp(3,30); sage: R=QP.residue_field(); sage: RX=R['x']; sage: prim=primes_first_n(1000) sage: polysQQ = [ QQX(prim[i:i+30]) for i in range(1,900)] sage: def test1(PR,l): return [PR(P) for P in l]; ....: sage: def test2(PR,l): return [PR([PR.base_ring()(coef) for coef in P.list()]) for P in l]; ....: sage: %timeit test1(RX,polysQQ) 1 loops, best of 3: 478 ms per loop sage: %timeit test2(RX,polysQQ) 1 loops, best of 3: 230 ms per loop
Especially since the actual implementation of casting that is performed essentially reduces to converting to a list and casting as we do in test 2.
The problem is that the implementation of list->polynomial casting provided by Polynomial_template is very much not optimal, sufficiently so that two of the three implementing classes handle lists in their own init rather than passing through to polynomial template.
The polynomial->polynomial casting is then also inefficient as it converts the poly to a list and recalls init. In the original code this bypassed the optimized list implementations in the implementing class, this is what the current patch changes. The effect on performance is as follows:
sage: %timeit test1(RX,polysQQ) 1 loops, best of 3: 219 ms per loop
There is still room for improvement, the current (and with patch) implementation will in most cases end up calling Polynomial_template.init twice, and likely also Polynomial.init twice, this is wasteful (even though the calls are largely no-ops). It would probably be better to, in addition to the currently proposed patch, special case casts from polynomials in the implementing classes the same way lists are done to avoid this.
Attachments (1)
Change History (6)
Changed 7 years ago by
comment:1 Changed 7 years ago by
comment:2 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:3 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:4 Changed 7 years ago by
- Cc jpflori added
comment:5 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4