Opened 7 years ago

Closed 4 years ago

#9542 closed enhancement (wontfix)

optimize znpoly arithmetic -- it's way, way too slow because of the polynomial template thingy

Reported by: was Owned by: AlexGhitza
Priority: minor Milestone: sage-6.2
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description


Attachments (1)

trac_9542-znpoly_timing.patch (3.7 KB) - added by was 7 years ago.
speeds up multiplication by a factor of *20* for many benchmarks... but causes a segfault when doctesting rings/arith.py

Download all attachments as: .zip

Change History (7)

Changed 7 years ago by was

speeds up multiplication by a factor of *20* for many benchmarks... but causes a segfault when doctesting rings/arith.py

comment:1 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 4 years ago by jpflori

Maybe this can be closed now... I'll run basic test laters.

comment:4 Changed 4 years ago by jpflori

  • Reviewers set to Jean-Pierre Flori
  • Status changed from new to needs_review

Based on the same idea (_mul_no_template_):

sage: K = Integers(2**6)
sage: R.<x> = K[]
sage: f = R([1,2,5,-9]); g = R([1,2,3,4])
sage: %timeit f._mul_zn_poly(g)
100000 loops, best of 3: 5.32 us per loop
sage: %timeit f._mul_(g)
1000000 loops, best of 3: 1 us per loop
sage: %timeit f._mul_no_template(g)
1000000 loops, best of 3: 790 ns per loop
sage: %timeit f*g
1000000 loops, best of 3: 845 ns per loop

So it seems the templating overhead is not so terrible. It also varies a little bit depending on the finite field. And it does not seem the templating code can be really trimmed down and further optimized.

So I suggest to close this ticket as won't fix.

comment:5 Changed 4 years ago by jpflori

  • Status changed from needs_review to positive_review

comment:6 Changed 4 years ago by vbraun

  • Resolution set to wontfix
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.