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: sage-9.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)

PadicPolyCastingInt.patch (1013 bytes) - added by afiori 7 years ago.
Eliminate unnecessary function calls

Download all attachments as: .zip

Change History (11)

Changed 7 years ago by afiori

Eliminate unnecessary function calls

comment:1 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:2 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:3 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:4 Changed 17 months ago by chapoton

  • Branch set to u/chapoton/15426
  • Cc caruso added
  • Commit set to 76581c9e6f0b397055549ff1225230b1780112b9
  • Milestone changed from sage-6.4 to sage-8.8
  • Status changed from new to needs_review

I have made the suggested change. It does not seem to have nay impact on the speed. Maybe worth doing nevertheless. Also some other small changes, that should be good for speed.


New commits:

696b23btrac 5583 adding a doctest
76581c9trac 15426 some details in padic polynomials

comment:5 Changed 17 months ago by git

  • Commit changed from 76581c9e6f0b397055549ff1225230b1780112b9 to d6b6ef1e7975b1a84bff179431d1862607875c6f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d6b6ef1trac 15426 details in padic polynomials

comment:6 Changed 16 months ago by embray

  • Milestone changed from sage-8.8 to sage-8.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 chapoton

  • Milestone changed from sage-8.9 to sage-9.0
  • Status changed from needs_review to needs_work

comment:8 Changed 10 months ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:9 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.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 mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3
Note: See TracTickets for help on using tickets.