gh-102221: Optimize math.integer.lcm() for multiple arguments (size-guarded stack)#153358
Open
serhiy-storchaka wants to merge 8 commits into
Open
gh-102221: Optimize math.integer.lcm() for multiple arguments (size-guarded stack)#153358serhiy-storchaka wants to merge 8 commits into
serhiy-storchaka wants to merge 8 commits into
Conversation
Instead of merging intermediate results at fixed points (binary counter), merge a new value with stacked values while it has at least half as many digits, so every stack entry has more than twice as many digits as the one above it. Small arguments are combined with each other before touching a much larger partial result. Also fix a reference leak on the error path of the merge loop. Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
Merge a new value with stacked values while it has at least 3/4 (instead of 1/2) as many digits: this matches the balanced pairing of equal-sized arguments while keeping the size adaptivity, and removes the slowdown for many equal-sized arguments. Cache the digit counts of stacked values in a parallel array. Since entry sizes now grow at least 4/3 times (instead of 2 times) per entry, enlarge the stack from 8*sizeof(Py_ssize_t) to 24*sizeof(Py_ssize_t) entries, which covers the new depth bound of log(PY_SSIZE_T_MAX)/log(4/3) + 1. Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
Member
|
I suspect this will be slightly worse for small number of arguments. Do we have measurable difference wrt the main here? |
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
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.
Combine intermediate results in size-balanced order instead of a sequential fold: a new value is merged with stacked intermediate results while it has at least 3/4 as many digits as the top stack entry, otherwise it is pushed.
Entry sizes thus grow at least 4/3 times per stack entry, which bounds the stack depth by log(PY_SSIZE_T_MAX)/log(4/3) + 1: 153 entries on 64-bit and 76 on 32-bit platforms.
Unlike merging at predefined points (recursive halving in #135554, binary counter in #135609), the merge order adapts to the actual sizes of intermediate results: small arguments are combined with each other before touching a much larger partial result. This helps in particular when a few large arguments are mixed with many small ones and gcd cancellation keeps the partial results small — the large values then participate in a single merge instead of ~log(n) merges.
Benchmarks (non-debug build, x86-64):
Alternative to #135554 and #135609.