polynomial_template should avoid unnecessary coercions

[sagetrac-ylchapuy]

e.g. in __mod__, we should coerce other only if needed.
This gives great speed up, e.g:

sage: R.<x> = GF(3)[]
sage: p=x^100 + x^81 + x^67 + x^33 + 1
sage: q=x^10 + x^8 + x^6 + x^3 + 1
sage: timeit('p%q')
625 loops, best of 3: 677 µs per loop  #Before
625 loops, best of 3: 60.3 µs per loop #After

Component: performance

Author: Yann Laigle-Chapuy

Reviewer: Martin Albrecht

Merged: sage-4.3.alpha1

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

[sagetrac-ylchapuy]

Attachment: trac_7256-polynomial_template_coercion.patch.gz

based on 4.3.alpha0

[sagetrac-ylchapuy]

comment:1

I'm not totally sure of how this should be done as I don't know the details of coercions, neither the details of the polynomial templating used.

At least, my patch doesn't break any doctest for me.

It touch for methods, the ones using coerce.

It test for parent equality before applying coercion. I also introduce a variable

parent = (<Polynomial_template>self)._parent

for readability.

[malb]

comment:2

The patch looks good and applies & doctests cleanly for me. However, we can do a little better.

On my machine I get the following:

Before

sage: R.<x> = GF(3)[]
sage: p=x^100 + x^81 + x^67 + x^33 + 1
sage: q=x^10 + x^8 + x^6 + x^3 + 1
sage: timeit('p%q')
625 loops, best of 3: 193 µs per loop

Patch

sage: R.<x> = GF(3)[]
sage: p=x^100 + x^81 + x^67 + x^33 + 1
sage: q=x^10 + x^8 + x^6 + x^3 + 1
sage: timeit('p%q')
625 loops, best of 3: 26.6 µs per loop

With my incremental reviewer patch I get:

sage: R.<x> = GF(3)[]
sage: p=x^100 + x^81 + x^67 + x^33 + 1
sage: q=x^10 + x^8 + x^6 + x^3 + 1
sage: timeit('p%q')
625 loops, best of 3: 18.2 µs per loop

So, this is a positive review if someone reviews my reviewer patch.

[sagetrac-ylchapuy]

comment:3

Replying to @malb:

So, this is a positive review if someone reviews my reviewer patch.

I think you attached the patch for #7531.

[malb]

comment:4

Attachment: trac_7256-polynomial_template_coercion_faster.patch.gz

Woops, fixed.

[sagetrac-ylchapuy]

comment:5

Great thanks. Still applies fine and doctests ok.
And here is the positive review!

[mwhansen]

Reviewer: Martin Albrecht

[mwhansen]

Merged: sage-4.3.alpha1

[mwhansen]

Author: Yann Laigle-Chapuy