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.

Sign up for GitHub

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

Jump to bottom

Increase speed of Fractions.limit_denominator #93476

Closed
mscuthbert opened this issue Jun 3, 2022 · 1 comment
Closed

Increase speed of Fractions.limit_denominator #93476

mscuthbert opened this issue Jun 3, 2022 · 1 comment
Labels
3.12 bugs and security fixes performance Performance or resource usage stdlib Python modules in the Lib dir type-feature A feature request or enhancement

Comments

@mscuthbert
Copy link

Feature or enhancement

Speed up Fractions.limit_denominator by not creating intermediary Fraction objects

Pitch

Fractions.limit_denominator returns a new Fraction, but along the way for Fractions > max_denominator creates 3 Fraction objects that are discarded: the fraction farther from the bound and two temporary fractions (bound1 - self and bound2 - shelf) which are created just for getting their absolute values.

Similar code speedups have been part of the music21 library since 2015--where we call limit_denominator after every arithmetic operation on note placement--and timing tests give a 7.3x speedup. (see music21 Source )

For fractions with denominators equal to or below max_denominator, instantiate the new Fraction with Fraction(self._numerator, self._denominator) instead of Fraction(self) for a 23% speedup.

PR to follow.
@mscuthbert mscuthbert added the type-feature A feature request or enhancement label Jun 3, 2022
mscuthbert added a commit to mscuthbert/cpython that referenced this issue Jun 3, 2022
@mscuthbert
pythongh-93476: Fraction.limit_denominator speed increases
599c55b 
Create only one new Fraction object during `limit_denominator()` instead of the four previously made.

Fixes python#93476

I believe that each of the calls to `Fraction()` can be called with `_normalize=False` but I have not included that in this PR to limit the scope of changes to the minimum to verify no change in implementation.
@mscuthbert mscuthbert mentioned this issue Jun 3, 2022
Closed
@AlexWaygood AlexWaygood added performance Performance or resource usage stdlib Python modules in the Lib dir 3.12 bugs and security fixes labels Jun 3, 2022
@rhettinger
Copy link
Contributor

In this case, we value algorithmic clarity over a minor performance gain from inlining.

Also, we would lose some of the recent optimizations in the Fraction class.

The limit_denominator code is almost never in a performance critical section of code, so no one would notice the small benefit, but we would incur a loss of understanding about how it works.

Thanks for the suggestion, but we will decline this one.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
3.12 bugs and security fixes performance Performance or resource usage stdlib Python modules in the Lib dir type-feature A feature request or enhancement
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

gh-93476: Fraction.limit_denominator speed increase mscuthbert/cpython
3 participants
@rhettinger @mscuthbert @AlexWaygood