gh-102221: Optimize math.lcm() for multiple arguments (non-recursive) #135609
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
792d234 to
26d961e
Compare
26d961e to
78731c0
Compare
How common it is? Where the cutoff when this version will payoff us it's complexity over #135554? |
|
I did not measure it. But estimation for #135554 on abstract machine is 6 words/level (return address, two parameters and three local variables), so this is 6 and 11 on 32- and 64-bit platforms. Or 64 and 2048 arguments correspondingly. It may be less if recursion needs more than just a return address or larger if the compiler is extra clever in reusing stack variable. The maximal stack consumption of this version is 8*64=512 bytes for the stack variable, plus up to 64 byte for other variables/parameters (but registers can be used for many of them). In #135554 it can be about 3KB in worst case. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This version uses manually supported stack instead of the C stack. It has less C stack consumption for very large number of arguments. But for not such large number of arguments (thousands or millions) it may actually have larger C stack consumption.