Opened 3 years ago

Closed 3 years ago

#25291 closed enhancement (fixed)

speed up generic polynomials

Reported by: mmezzarobba Owned by:
Priority: minor Milestone: sage-8.3
Component: algebra Keywords:
Cc: Merged in:
Authors: Marc Mezzarobba, Travis Scrimshaw Reviewers: Travis Scrimshaw, Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: 1922631 (Commits, GitHub, GitLab) Commit: 19226310609d1f5e95b95210e78376915e9acfa1
Dependencies: Stopgaps:

Status badges

Description


Change History (10)

comment:1 Changed 3 years ago by mmezzarobba

  • Status changed from new to needs_review

comment:2 Changed 3 years ago by git

  • Commit changed from f584428af0d57ba2a2cac79e77dda747acf39d0c to 7bb0dc8c263d8af8deed5a5ff11002c6e7a245d8

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

7bb0dc8optimize generic polynomial coefficient access

comment:3 follow-up: Changed 3 years ago by tscrim

I know this is close to bikeshedding, but I think a slightly more descriptive name would be more appropriate, such as get_coeff or get_coeff_c, would be better in the long-term for code readability.

Have you also run some timings?

I will also push some further changes that are micro-optimizations (mostly avoiding extra calls to degree() by using get_unsafe() because we have already checked the degree is non-negative).

comment:4 in reply to: ↑ 3 Changed 3 years ago by mmezzarobba

Replying to tscrim:

I know this is close to bikeshedding, but I think a slightly more descriptive name would be more appropriate, such as get_coeff or get_coeff_c, would be better in the long-term for code readability.

Fine with me.

Have you also run some timings?

No micro-benchmarks, but this change seems to speed up the “real-world” code I was profiling by ~3%.

comment:5 Changed 3 years ago by git

  • Commit changed from 7bb0dc8c263d8af8deed5a5ff11002c6e7a245d8 to 31be20254270b9e152f57af986a160e23e560bd9

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

31be202optimize generic polynomial coefficient access

comment:6 follow-up: Changed 3 years ago by tscrim

  • Branch changed from u/mmezzarobba/polynomial_get_fast to u/tscrim/polynomial_get_coeff_c-25291
  • Commit changed from 31be20254270b9e152f57af986a160e23e560bd9 to 19226310609d1f5e95b95210e78376915e9acfa1
  • Reviewers set to Travis Scrimshaw

I chose get_coeff_c to be more explicit that it is a C-level method and so that there would be less chances of accidental conflicts with subclasses.

All of the other changes I did should be micro-optimizations as they avoid checks, multiple calls to other functions (e.g., degree()), have more direct paths. I didn't do every possible place because I felt the code clarity outweighed a (very) micro speed gain. Unfortunately there were a few places where having the field with 1 element made it so we had to have different cases (the unit code in particular).

Marc, could you run your "real-world" example again against the code on your branch to see if you notice any differences?


New commits:

1922631get_fast -> get_coeff_c and some micro-optimizations.

comment:7 in reply to: ↑ 6 ; follow-up: Changed 3 years ago by mmezzarobba

Replying to tscrim:

Marc, could you run your "real-world" example again against the code on your branch to see if you notice any differences?

It seems again a bit (2%?) faster. (Of course, that may be measurement error--perhaps even more than with my first commit, which was motivated by __getitem__() showing up in the profiler output!)

comment:8 in reply to: ↑ 7 Changed 3 years ago by tscrim

Replying to mmezzarobba:

Replying to tscrim:

Marc, could you run your "real-world" example again against the code on your branch to see if you notice any differences?

It seems again a bit (2%?) faster. (Of course, that may be measurement error--perhaps even more than with my first commit, which was motivated by __getitem__() showing up in the profiler output!)

Thank you for running it. That is about what I was generically expecting given my changes (not clearly significant, but a noticeable improvement).

So if my changes are good, feel free to set a positive review. Thank you for your work.

comment:9 Changed 3 years ago by mmezzarobba

  • Authors changed from Marc Mezzarobba to Marc Mezzarobba, Travis Scrimshaw
  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Marc Mezzarobba
  • Status changed from needs_review to positive_review

Thank you!

comment:10 Changed 3 years ago by vbraun

  • Branch changed from u/tscrim/polynomial_get_coeff_c-25291 to 19226310609d1f5e95b95210e78376915e9acfa1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.