Opened 7 years ago
Last modified 7 weeks ago
#15426 needs_work enhancement
Performance of casting ZZ[x] to Qp[x]
Reported by:  afiori  Owned by:  

Priority:  minor  Milestone:  sage9.3 
Component:  performance  Keywords:  performance padic polynomial casting 
Cc:  roed, caruso  Merged in:  
Authors:  Andrew Fiori  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/chapoton/15426 (Commits)  Commit:  d6b6ef1e7975b1a84bff179431d1862607875c6f 
Dependencies:  Stopgaps: 
Description
One probably expects that casting ZZ[x] to Qp[x] is at least as fast as casting QQ[x] to Q[x]. This appeared not to be the case:
sage: prim=primes_first_n(1000) sage: ZZX=ZZ['x'] sage: QQX=QQ['x'] sage: polysZZ = [ ZZX(prim[i:i+30]) for i in range(1,900)] sage: polysQQ = [ QQX(prim[i:i+30]) for i in range(1,900)] sage: QP=Qp(3,30); sage: QPX=QP['x'] sage: def test1(PR,l): return [PR(P) for P in l]; sage: %timeit test1(QPX,polysZZ) 1 loops, best of 3: 395 ms per loop sage: %timeit test1(QPX,polysQQ) 1 loops, best of 3: 244 ms per loop
This appears to have been caused by unneccisary repeat virtual function calls in polynomial_padic_capped_relative_dense::_comp_valaddeds. The number of excess calls was proportional to the degree of the polynomial, hence this likely does not cause noticeable performance issue for very low degree polynomials.
The attached patch should correct this, I have new timings
sage: %timeit test1(QPX,polysZZ) 1 loops, best of 3: 171 ms per loop sage: %timeit test1(QPX,polysQQ) 1 loops, best of 3: 256 ms per loop
Attachments (1)
Change History (11)
Changed 7 years ago by
comment:1 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:2 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:3 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:4 Changed 17 months ago by
 Branch set to u/chapoton/15426
 Cc caruso added
 Commit set to 76581c9e6f0b397055549ff1225230b1780112b9
 Milestone changed from sage6.4 to sage8.8
 Status changed from new to needs_review
comment:5 Changed 17 months ago by
 Commit changed from 76581c9e6f0b397055549ff1225230b1780112b9 to d6b6ef1e7975b1a84bff179431d1862607875c6f
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
d6b6ef1  trac 15426 details in padic polynomials

comment:6 Changed 16 months ago by
 Milestone changed from sage8.8 to sage8.9
Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).
comment:7 Changed 11 months ago by
 Milestone changed from sage8.9 to sage9.0
 Status changed from needs_review to needs_work
comment:8 Changed 10 months ago by
 Milestone changed from sage9.0 to sage9.1
Ticket retargeted after milestone closed
comment:9 Changed 6 months ago by
 Milestone changed from sage9.1 to sage9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:10 Changed 7 weeks ago by
 Milestone changed from sage9.2 to sage9.3
Eliminate unnecessary function calls