consolidate shifts in polynomial_template

[robertwb]

See discussion at end of #4965.

CC: @malb @burcin

Component: algebra

Author: Alex Ghitza, Martin Albrecht

Reviewer: Alex Ghitza, Martin Albrecht

Merged: sage-4.3.alpha1

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

[sagetrac-mabshoff]

comment:2

3.4 is for ReST tickets only.

Cheers,

Michael

[aghitza]

comment:3

The point was to consolidate the three shift methods shift, __lshift__, and __rshift__ by having shift do all the work and the other two call it. (Right now there's significant code triplication going on.)

The attached patch does this.

[aghitza]

Author: Alex Ghitza

[aghitza]

comment:4

Attachment: trac_4982.patch.gz

I'm ccing the participants in the discussion at #4965 in case they had something else in mind.

[malb]

comment:5

The only issue I can see is the potential performance overhead.

Vanilla 4.2.1:

sage: P.<x> = GF(2)[]
sage: f = P.random_element(50)
sage: %timeit f<<50
1000000 loops, best of 3: 792 ns per loop

This patch:

sage: P.<x> = GF(2)[]
sage: f = P.random_element(50)
sage: %timeit f<<50
1000000 loops, best of 3: 952 ns per loop

Maybe a cdef method could be added which everyone (shift, __lshift__, __rshift__) calls?

[malb]

comment:6

Doctests pass btw., applies cleanly etc.

[malb]

comment:7

Attachment: trac_4982_speedup.patch.gz

Alex and I were discussing this off-list. The speedup patch does the following:

• added a new C function which all methods call now
• I inlined it
• and I changed the code to avoid some initialisation

Here is what I got:

Vanilla:

sage: P.<x> = GF(2)[]
sage: f = P.random_element(50)
sage: %timeit f<<50
1000000 loops, best of 3: 730 ns per loop

Patch:

sage: P.<x> = GF(2)[]
sage: f = P.random_element(50)
sage: %timeit f<<50
1000000 loops, best of 3: 1.06 µs per loop

Patch + Speed-up:

sage: P.<x> = GF(2)[]
sage: %timeit f<<50
1000000 loops, best of 3: 761 ns per loop

So there is still some overhead, but I think its acceptable.

[aghitza]

Changed author from Alex Ghitza to Alex Ghitza, Martin Albrecht

[aghitza]

comment:8

So I believe that Martin gave a positive review to my patch, except for the performance issue.

I have read and tested his patch, and I'm happy with it.

[mwhansen]

Reviewer: Alex Ghitza, Martin Albrecht

[mwhansen]

Merged: sage-4.3.alpha1