Opened 11 years ago

Closed 10 years ago

#4982 closed enhancement (fixed)

consolidate shifts in polynomial_template

Reported by: robertwb Owned by: tbd
Priority: major Milestone: sage-4.3
Component: algebra Keywords:
Cc: malb, burcin Merged in: sage-4.3.alpha1
Authors: Alex Ghitza, Martin Albrecht Reviewers: Alex Ghitza, Martin Albrecht
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

See discussion at end of #4965.

Attachments (2)

trac_4982.patch (3.6 KB) - added by AlexGhitza 10 years ago.
trac_4982_speedup.patch (3.6 KB) - added by malb 10 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 11 years ago by AlexGhitza

  • Type changed from defect to enhancement

comment:2 Changed 11 years ago by mabshoff

  • Milestone changed from sage-3.4 to sage-3.4.1

3.4 is for ReST tickets only.

Cheers,

Michael

comment:3 Changed 10 years ago by AlexGhitza

  • Authors set to Alex Ghitza
  • Status changed from new to needs_review

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.

Changed 10 years ago by AlexGhitza

comment:4 Changed 10 years ago by AlexGhitza

  • Cc malb burcin added

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

comment:5 Changed 10 years ago by malb

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?

comment:6 Changed 10 years ago by malb

Doctests pass btw., applies cleanly etc.

Changed 10 years ago by malb

comment:7 Changed 10 years ago by malb

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.

comment:8 Changed 10 years ago by AlexGhitza

  • Authors changed from Alex Ghitza to Alex Ghitza, Martin Albrecht
  • Report Upstream set to N/A
  • Status changed from needs_review to positive_review

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.

comment:9 Changed 10 years ago by mhansen

  • Merged in set to sage-4.3.alpha1
  • Resolution set to fixed
  • Reviewers set to Alex Ghitza, Martin Albrecht
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.