Performance of casting ZZ[x] to Qp[x]

[sagetrac-afiori]

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

CC: @roed314 @xcaruso

Component: performance

Keywords: performance padic polynomial casting

Author: Andrew Fiori

Branch/Commit: a297e3c

Reviewer: Xavier Caruso

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

[sagetrac-afiori]

Eliminate unnecessary function calls

[sagetrac-vbraun-spam]

comment:1

Attachment: PadicPolyCastingInt.patch.gz

[fchapoton]

Commit: 76581c9

[fchapoton]

Branch: u/chapoton/15426

[fchapoton]

comment:4

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:

696b23b	trac 5583 adding a doctest
76581c9	trac 15426 some details in padic polynomials

[sagetrac-git]

Changed commit from 76581c9 to d6b6ef1

[sagetrac-git]

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

d6b6ef1

trac 15426 details in padic polynomials

[embray]

comment:6

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

[embray]

comment:8

Ticket retargeted after milestone closed

[mkoeppe]

comment:9

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.

[mkoeppe]

comment:11

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:12

Setting a new milestone for this ticket based on a cursory review.

[fchapoton]

New commits:

a297e3c

some details inside one p-adic file

[fchapoton]

Changed commit from d6b6ef1 to a297e3c

[fchapoton]

Changed branch from u/chapoton/15426 to public/ticket/15426

[fchapoton]

comment:16

bot is morally green, so please review !

[xcaruso]

comment:17

It's not completely clear to me what really changed but it looks okay.

[fchapoton]

Reviewer: Xavier Caruso

[vbraun]

Changed branch from public/ticket/15426 to a297e3c