Repository navigation
Optimize representation-independent BigInteger arithmetic - #132709
tannergooding merged 19 commits into
Conversation
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
Preserve baseline kernels for ordinary operands, gate specialized arithmetic at measured crossovers, and address cross-platform and review findings. Co-authored-by: Copilot App <[email protected]>
Assert span and aliasing contracts and avoid copying dividend buffers before Burnikel-Ziegler fallthroughs. Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
|
Azure Pipelines: Successfully started running 3 pipeline(s). 13 pipeline(s) were filtered out due to trigger conditions. There may be pipelines that require an authorized user to comment /azp run to run. |
|
Tagging subscribers to this area: @dotnet/area-system-numerics |
There was a problem hiding this comment.
Pull request overview
Optimizes BigInteger arithmetic by detecting structured operands and dispatching to specialized multiplication, division, GCD, shift, and exponentiation kernels.
Changes:
- Adds structured-limb and Mersenne arithmetic paths.
- Adds cached power tables for factors 3, 5, and 7.
- Expands property tests across signs, architectures, and arithmetic boundaries.
Two unresolved findings remain: an untested shifted-limb fallback and an unreachable power-of-two branch.
Show a summary per file
| File | Description |
|---|---|
BigIntegerPropertyTests.cs |
Adds structured arithmetic coverage. |
BigIntegerCalculator.Utils.cs |
Moves shared debug initialization. |
BigIntegerCalculator.SquMul.cs |
Adds structured multiplication paths. |
BigIntegerCalculator.ShiftRot.cs |
Moves shared right-shift logic. |
BigIntegerCalculator.PowTables.cs |
Adds packed power tables. |
BigIntegerCalculator.PowMod.cs |
Adds table-backed exponentiation. |
BigIntegerCalculator.GcdInv.cs |
Optimizes common-zero-limb GCD. |
BigIntegerCalculator.DivRem.cs |
Adds specialized and Mersenne division. |
BigInteger.cs |
Integrates optimized arithmetic dispatch. |
System.Runtime.Numerics.csproj |
Includes the power-table source. |
BigIntegerCalculator.Shared.cs |
Adds shared arithmetic kernels. |
Review details
- Files reviewed: 11/11 changed files
- Comments generated: 2
- Review effort level: Balanced
Co-authored-by: Copilot App <[email protected]>
|
Azure Pipelines: Successfully started running 3 pipeline(s). 13 pipeline(s) were filtered out due to trigger conditions. There may be pipelines that require an authorized user to comment /azp run to run. |
There was a problem hiding this comment.
Review details
Suppressed comments (1)
Previously missed (1) — in code that hasn't changed since the last review.
src/libraries/System.Private.CoreLib/src/System/Numerics/BigIntegerCalculator.Shared.cs:996
- This 32-bit implementation is unreachable: both production callers are guarded by
nint.Size == 8(BigIntegerCalculator.SquMul.cs:40-43and:286-288), and there are no other call sites. Keeping an unexercised architecture branch risks divergence; either remove it and make the helper explicitly 64-bit-only, or enable the x86 dispatch and add benchmark-backed tests.
else
{
if (((ulong)(uint)repeatedLimb * convolutionLength) > uint.MaxValue)
{
return false;
- Files reviewed: 11/11 changed files
- Comments generated: 1
- Review effort level: Balanced
Co-authored-by: Copilot App <[email protected]>
There was a problem hiding this comment.
Review details
Suppressed comments (1)
Previously missed (1) — in code that hasn't changed since the last review.
src/libraries/System.Private.CoreLib/src/System/Numerics/BigIntegerCalculator.Shared.cs:787
- This file is compiled into both System.Private.CoreLib and System.Runtime.Numerics, but the new sparse/repeated multiplication and specialized scalar-division kernels starting here have no System.Private.CoreLib call sites;
System.Number.BigIntegerstill usesMul1/MultiplyNaiveand its own division path. Together with the movedRightShiftSelf, this adds hundreds of lines of unused IL (and potentially R2R code) to CoreLib for optimizations consumed only by System.Runtime.Numerics. Please keep only genuinely shared helpers in this file and place the BigInteger-only kernels in the Runtime.Numerics partial files, or quantify and justify the CoreLib binary-size cost.
internal static void MultiplyNaiveSparse(ReadOnlySpan<nuint> left, ReadOnlySpan<nuint> right, Span<nuint> bits)
- Files reviewed: 11/11 changed files
- Comments generated: 0 new
- Review effort level: Balanced
Co-authored-by: Copilot App <[email protected]>
Co-authored-by: Copilot App <[email protected]>
There was a problem hiding this comment.
Copilot review overview
Review tier: Balanced
Findings: 1
New issues introduced by this change (1)
| Severity | Finding |
|---|---|
src/libraries/System.Runtime.Numerics/tests/BigInteger/BigIntegerPropertyTests.cs — The shifted scalar cases here (6, 12, and 20) all reduce to the dedicated 3/5 paths, while… |
Issues resolved since last review (1)
| Severity | Finding |
|---|---|
src/libraries/System.Runtime.Numerics/tests/BigInteger/BigIntegerPropertyTests.cs — The new table-continuation path is not covered by these cases: the largest single-factor exponent… View resolved comment |
Suppressed comments (1)
Previously missed (1) — in code that hasn't changed since the last review.
src/libraries/System.Private.CoreLib/src/System/Numerics/BigIntegerCalculator.Shared.cs:787
- This structured-multiplication kernel is only referenced from
System.Runtime.Numerics-specific files, but placing it in the shared source also emits it intoSystem.Private.CoreLib. The same applies to the repeated-run helpers, scalar division machinery, and relocatedRightShiftSelf; repository-wide caller searches find no CoreLib consumers for those methods. Please keep or conditionally compile the Numerics-only kernels outsideSYSTEM_PRIVATE_CORELIB, otherwise this optimization adds hundreds of lines of unused IL to CoreLib without binary-size evidence.
internal static void MultiplyNaiveSparse(ReadOnlySpan<nuint> left, ReadOnlySpan<nuint> right, Span<nuint> bits)
Co-authored-by: Copilot Autofix powered by AI <[email protected]>
There was a problem hiding this comment.
Copilot review overview
Review tier: Balanced
Findings: None
Issues resolved since last review (1)
| Severity | Finding |
|---|---|
src/libraries/System.Runtime.Numerics/tests/BigInteger/BigIntegerPropertyTests.cs — The shifted scalar cases here (6, 12, and 20) all reduce to the dedicated 3/5 paths, while… View resolved comment |
Suppressed comments (4)
Previously missed (2) — in code that hasn't changed since the last review.
src/libraries/System.Private.CoreLib/src/System/Numerics/BigIntegerCalculator.Shared.cs:994
- The 32-bit implementation in this
elsebranch is unreachable: the only production call sites inSquareandMultiplyboth requirenint.Size == 8before invoking this helper. Either remove the 32-bit branch to avoid carrying dead arithmetic code, or remove those caller guards and add x86 coverage if the path is intended to run there.
else
{
if (((ulong)(uint)repeatedLimb * convolutionLength) > uint.MaxValue)
src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.PowTables.cs:78
- This explanation omits the adjacent base-7 constant and therefore does not describe how
Log2OfSevenFractionalBitsorlog2OfSevenLoweris derived. Includefloor((log2(7) - 2) * 2^64)and state that prepending 2 reconstructs both the base-5 and base-7 values.
This issue also appears in the following locations of the same file:
- line 123
- line 402
// Accordingly, these constants are:
// floor((log2(3) - 1) * 2^64)
// floor((log2(5) - 2) * 2^64)
// Prepending 1 and 2 below reconstructs floor(log2(3) * 2^64) and
// floor(log2(5) * 2^64), respectively.
src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.PowTables.cs:125
- These hand-authored packed tables are executable arithmetic data, but the added tests do not validate every cached entry against an independent calculation (for example, several intermediate powers are never selected by the deterministic cases). A single bad limb would silently return an incorrect
BigInteger.Powresult. Add a test that enumerates every 3/5/7 entry for the native layout and compares it with repeated multiplication; the existing x86/x64 test runs will then validate both layouts.
private static ReadOnlySpan<ulong> Pow3TableStorage64 =>
[
1, 0x0006954FE21E3E81, // 3^32
src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.PowTables.cs:408
- Both the 32-bit and 64-bit packed power tables are embedded in every architecture-neutral build, so this optimization adds a substantial amount of permanent assembly data even though only one layout is used per process. Please report the resulting System.Runtime.Numerics binary-size delta and weigh it against the end-to-end gains; if the cost is material, consider a representation that avoids duplicating every limb while preserving startup performance.
private static ReadOnlySpan<int> Pow3TableIndices32 =>
[
0, 2, 5, 10, 18, 32, 59,
];
private static ReadOnlySpan<uint> Pow3TableStorage32 =>
[
jeffhandley
left a comment
There was a problem hiding this comment.
@tannergooding @PranavSenthilnathan @eiriktsarpalis - I scanned through this and chatted with Tanner about this and agreed to proceed with merging this PR, which will unblock subsequent PRs in the queue. I want to start getting coverage of these changes early in .NET 12 Preview 1. Before we finish the comprehensive BigInteger wave of work in preview 1 though, let's plan for Pranav, Tanner, and perhaps Eirik doing a collaborative walkthrough over all the changes in this area.

Optimize representation-independent BigInteger arithmetic
BigIntegercurrently carries every native limb through arithmetic even when the operand hasstructure that makes much of that work unnecessary. This change keeps the existing representation
but adds shared arithmetic kernels for:
3,5, and7, including factor-aware powers;B^k - 1.The dispatches are crossover-gated, and ordinary grammar-school division and multiplication retain
their original kernels. Packed
3/5/7power tables carry both 32-bit and 64-bit storage inarchitecture-neutral IL and select the native layout through JIT-folded
nint.Size.Representative Windows x64 results use identical hosts, six alternating processes, and
DOTNET_TieredCompilation=0. Values are medians of six processes.Public BigInteger
Common operand sizes
3^47201.17 ns133.75 ns-33.5%3^257538.82 ns150.77 ns-72.0%7^257582.91 ns168.80 ns-71.0%10^257589.54 ns191.08 ns-67.6%21^128414.49 ns262.76 ns-36.6%35^257718.07 ns446.44 ns-37.8%3118.93 ns96.87 ns-18.5%7215.44 ns156.24 ns-27.5%124.12 ns101.80 ns-18.0%217.82 ns136.68 ns-37.3%(3 << 257)viaDivRem1,084.26 ns776.16 ns-28.4%Larger structured operands
3^10251,531.49 ns202.40 ns-86.8%7^10252,130.20 ns228.66 ns-89.3%10^10252,527.87 ns258.62 ns-89.8%2,128.02 ns265.36 ns-87.5%DivRembyB^31 - 16,804.60 ns706.29 ns-89.6%(3 << 2,047)viaDivRem2,565.31 ns499.77 ns-80.5%24,280.55 ns563.00 ns-97.7%631.86 ns110.10 ns-82.6%1,593.95 ns401.64 ns-74.8%Allocations are unchanged for the operation-focused representative matrix; the improvement comes
from avoiding arithmetic and scans after structure has been recognized.
End-to-end PiDigits
The established
PiDigits_3Benchmarks Game workload exercises repeatedBigIntegermultiplication, addition, and division together. The canonical benchmark uses 3,000 digits; 300 and
1,000 digits show how the same changes scale at more common operand sizes.
3.546 ms2.964 ms2.767 ms-16.4%-6.6%-22.0%37.017 ms28.029 ms25.143 ms-24.3%-10.3%-32.1%354.370 ms258.965 ms223.798 ms-26.9%-13.6%-36.8%The current baseline has the same allocation volume as .NET 10. Layer 1 reduces it by approximately
1.9%: from8,846,344to8,676,064bytes at 300 digits,114,149,160to111,944,520bytes at1,000 digits, and
1,175,501,536to1,152,812,312bytes at 3,000 digits.Controls and tradeoffs
60.08 ns60.76 ns+1.1%68.92 ns69.43 ns+0.7%85.57 ns84.46 ns-1.3%126.76 ns128.00 ns+1.0%87.83 ns90.76 ns+3.3%435.11 ns445.86 ns+2.5%1145.84 ns47.63 ns+3.9%DivRemby three-limb Mersenne divisor246.58 ns253.96 ns+3.0%(3 << 47)viaDivRem819.44 ns823.00 ns+0.4%The small regressions above are the fixed dispatch cost before enough arithmetic is available to
amortize it. Larger instances cross over sharply; no representative control regresses by 5%.
Validation
System.Runtime.Numericstests pass on Windows x64.DOTNET_EnableHWIntrinsic=0.streams, Mersenne division, scalar division, powers, GCD, and both process widths.
Note
This pull request description was drafted with GitHub Copilot.