Opened 16 months ago

Closed 15 months ago

Last modified 14 months ago

#26433 closed defect (fixed)

Slowness in generic quo_rem

Reported by: caruso Owned by:
Priority: major Milestone: sage-8.5
Component: commutative algebra Keywords:
Cc: Merged in:
Authors: Xavier Caruso, Travis Scrimshaw Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 7047040 (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by tscrim)

While working on #26405, I noticed that the generic implementation of quo_rem is very slow. Indeed, compare:

sage: R.<a> = Zq(2^3)
sage: S.<x> = R[]
sage: P = S.random_element(degree=100)
sage: t = R.random_element()

sage: %timeit _ = P(t)
10000 loops, best of 3: 145 µs per loop

sage: Q = x - t
sage: %timeit _ = P % Q
1000 loops, best of 3: 1.06 ms per loop

Change History (14)

comment:1 Changed 16 months ago by caruso

  • Description modified (diff)

comment:2 Changed 16 months ago by caruso

  • Branch set to u/caruso/slowness_in_generic_quo_rem

comment:3 Changed 16 months ago by git

  • Commit set to cb8db697a1b1bd8d9aaeb20774c581641fb56e97

Branch pushed to git repo; I updated commit sha1. New commits:

cb8db69Faster implementation of generic quo_rem

comment:4 Changed 16 months ago by caruso

Timings are now:

sage: %timeit _ = P % Q
1000 loops, best of 3: 210 µs per loop

comment:5 Changed 16 months ago by caruso

  • Status changed from new to needs_review

comment:6 Changed 16 months ago by git

  • Commit changed from cb8db697a1b1bd8d9aaeb20774c581641fb56e97 to ce544ccf681b94ca149803ca5d5ca5f0d3c3ce2c

Branch pushed to git repo; I updated commit sha1. New commits:

ce544ccTypo

comment:7 Changed 16 months ago by tscrim

  • Branch changed from u/caruso/slowness_in_generic_quo_rem to u/tscrim/slowness_generic_quo_rem-26433
  • Commit changed from ce544ccf681b94ca149803ca5d5ca5f0d3c3ce2c to 1ca2c054271ae4dfa6719efe6bae1fc6bcc331fe
  • Description modified (diff)
  • Reviewers set to Travis Scrimshaw

I made a few Cython improvements. I also pulled out the if statement because I felt the code duplication was minimal and it would be better to avoid doing the if check every time in the loop.

If my changes are good, then positive review (with the author name is filled in).

Last edited 16 months ago by tscrim (previous) (diff)

comment:8 Changed 16 months ago by git

  • Commit changed from 1ca2c054271ae4dfa6719efe6bae1fc6bcc331fe to 7047040f0fb3294c955241d3751f6b168ea020ef

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7047040Some small other improvements.

comment:9 Changed 16 months ago by caruso

  • Authors set to Xavier Caruso, Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:10 Changed 16 months ago by caruso

The patchbot reports one failing doctest in src/sage/geometry/polyhedron/library.py but I guess it is not related to this ticket (and the test passes on my computer).

comment:11 Changed 15 months ago by vbraun

  • Branch changed from u/tscrim/slowness_generic_quo_rem-26433 to 7047040f0fb3294c955241d3751f6b168ea020ef
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:12 Changed 15 months ago by embray

  • Milestone changed from sage-8.4 to sage-8.5

This should be re-targeted for 8.5.

comment:13 Changed 14 months ago by mmezzarobba

  • Commit 7047040f0fb3294c955241d3751f6b168ea020ef deleted

A regression that may be due to this change: #26433.

comment:14 Changed 14 months ago by tscrim

See #26907.

Note: See TracTickets for help on using tickets.