Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

MAINT: Improve performance of polynomial operations (2) #24531

Open
wants to merge 7 commits into
base: main
Choose a base branch
from

Conversation

eendebakpt
Copy link
Contributor

For many polynomial operations (e.g. add, multiply, negate) the operation takes place on the coefficients of the operands and then a new Polynomial is created. For the creation of the new Polynomial we can skip the validation of input arguments, as they are either passed from the operands (which have already been validated) or constructed with internal methods (which have validated output).

Benchmark results:

p + q: Mean +- std dev: [main0] 31.5 us +- 2.1 us -> [prx] 17.4 us +- 0.6 us: 1.81x faster
p * q: Mean +- std dev: [main0] 32.4 us +- 1.3 us -> [prx] 18.3 us +- 1.0 us: 1.77x faster
2 * p: Mean +- std dev: [main0] 24.3 us +- 1.3 us -> [prx] 11.7 us +- 0.4 us: 2.08x faster
-p: Mean +- std dev: [main0] 14.6 us +- 0.6 us -> [prx] 2.50 us +- 0.11 us: 5.84x faster

Geometric mean: 2.50x faster

with script:

import pyperf
from numpy.polynomial import Polynomial

setup = """
from numpy.polynomial import Polynomial

p=Polynomial([.5,4,5])
q=Polynomial([1,0,5])
"""

runner = pyperf.Runner()
runner.timeit(name=f"p + q", stmt="_ = p + q", setup=setup)
runner.timeit(name=f"p * q", stmt="_ = p * q", setup=setup)
runner.timeit(name=f"2 * p", stmt="_ = 2 * q", setup=setup)
runner.timeit(name=f"-p", stmt="_ = - p", setup=setup)

Notes:

  • The as_series and ABCPolyBase.__init__ have an additional flag _validate_input. The default is True (so the PR is backwards compatible), but for internal operations we set it to False
  • Testing was performed by with MAINT: Optimize performance of polynomial operations #24499 included in both main and the PR. Without MAINT: Optimize performance of polynomial operations #24499 there is still a significant performance gain
  • We can do even more optimization if we refactor the polyadd and/or polyutils._add to have a _validate_input flag as well. But this requires more refactoring and the polyadd is public, so this has not yet been done.
  • The modifications have been made for __add__, __neg__, __mul__ and __rmul__. If this PR is considered a merge candidate, we can modify other operations as well.

@eendebakpt eendebakpt changed the title Draft: MAINT: Improve performance of polynomial operations Draft: MAINT: Improve performance of polynomial operations (2) Aug 24, 2023
@eendebakpt eendebakpt changed the title Draft: MAINT: Improve performance of polynomial operations (2) MAINT: Improve performance of polynomial operations (2) Aug 28, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants