Opened 11 years ago

Closed 11 years ago

Last modified 11 years ago

#7526 closed defect (fixed)

polynomial_template should avoid unnecessary coercions

Reported by: ylchapuy Owned by: tbd
Priority: major Milestone: sage-4.3
Component: performance Keywords:
Cc: Merged in: sage-4.3.alpha1
Authors: Yann Laigle-Chapuy Reviewers: Martin Albrecht
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (2)

trac_7256-polynomial_template_coercion.patch (5.7 KB) - added by ylchapuy 11 years ago.
based on 4.3.alpha0
trac_7256-polynomial_template_coercion_faster.patch (2.1 KB) - added by malb 11 years ago.

Download all attachments as: .zip

Change History (9)

Changed 11 years ago by ylchapuy

based on 4.3.alpha0

comment:1 Changed 11 years ago by ylchapuy

  • Status changed from new to needs_review

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.

comment:2 follow-up: Changed 11 years ago by malb

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.

comment:3 in reply to: ↑ 2 Changed 11 years ago by ylchapuy

Replying to malb:

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

I think you attached the patch for #7531.

comment:4 Changed 11 years ago by malb

Woops, fixed.

comment:5 Changed 11 years ago by ylchapuy

  • Status changed from needs_review to positive_review

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

comment:6 Changed 11 years ago by mhansen

  • Authors set to Yann Laigle-Chapuy
  • Merged in set to sage-4.3.alpha1
  • Resolution set to fixed
  • Reviewers set to Martin Albrecht
  • Status changed from positive_review to closed

comment:7 Changed 11 years ago by mvngu

  • Milestone set to sage-4.3
Note: See TracTickets for help on using tickets.