[Perf] BigInteger formatting performance regression in .NET 9

[xakep139]

Description

After reading Performance Improvements in .NET 9 related to BigInteger, I've noticed a comment indicating that C# has poor performance compared to other programming languages in terms of big integer calculations. After quick investigation, it turned out that half of the time in https://github.com/hanabi1224/Programming-Language-Benchmarks/blob/main/bench/algorithm/edigits/1.cs is spent on formatting of a big integer. On .NET 8 it's done twice as fast, even though there were performance optimizations made in .NET 9.

Here's a benchmark code that shows the issue:

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Numerics;

BenchmarkSwitcher.FromAssembly(typeof(Program).Assembly).Run(args);

[MemoryDiagnoser(false)]
[HideColumns("Job", "Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private char[] _dest = new char[1_000_000];

    private BigInteger _value =
        BigInteger.Pow(BigInteger.Parse(string.Concat(Enumerable.Repeat("1234567890", 30))), 1_000);

    [Benchmark(Baseline = true)]
    public string Stringify() => _value.ToString();

    [Benchmark]
    public bool TryFormat() => _value.TryFormat(_dest, out _);
}

Configuration

BenchmarkDotNet v0.14.0, Windows 11 (10.0.26100.2894)
AMD Ryzen 9 4900H with Radeon Graphics, 1 CPU, 16 logical and 8 physical cores
.NET SDK 9.0.102
  [Host]     : .NET 8.0.12 (8.0.1224.60305), X64 RyuJIT AVX2
  Job-TESATW : .NET 8.0.12 (8.0.1224.60305), X64 RyuJIT AVX2
  Job-VBXNCI : .NET 9.0.1 (9.0.124.61010), X64 RyuJIT AVX2

Regression?

Yes. The same code on .NET 8 executes ~3 times faster (but with much more memory being allocated).

Data

| Method    | Runtime  | Mean    | Ratio | Allocated | Alloc Ratio |
|---------- |--------- |--------:|------:|----------:|------------:|
| Stringify | .NET 8.0 | 1.009 s |  1.00 | 1303.9 KB |       1.000 |
| TryFormat | .NET 8.0 | 1.005 s |  1.00 | 719.71 KB |       0.552 |
| Stringify | .NET 9.0 | 3.657 s |  3.62 | 585.23 KB |       0.449 |
| TryFormat | .NET 9.0 | 3.657 s |  3.63 |   1.05 KB |       0.001 |

Analysis

This regression might be caused by the #100181, but I haven't thoroughly tested that regression on older codebase.
The regression is reproduced on really big integers (order of magnitude 1000+).

[xakep139]

@stephentoub FYI

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

[EgorBo]

@EgorBot -windows_intel -linux_amd --runtimes net8.0 net9.0

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Numerics;

BenchmarkSwitcher.FromAssembly(typeof(Program).Assembly).Run(args);

[MemoryDiagnoser(false)]
[HideColumns("Job", "Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private char[] _dest = new char[1_000_000];

    private BigInteger _value =
        BigInteger.Pow(BigInteger.Parse(string.Concat(Enumerable.Repeat("1234567890", 30))), 1_000);

    [Benchmark(Baseline = true)]
    public string Stringify() => _value.ToString();

    [Benchmark]
    public bool TryFormat() => _value.TryFormat(_dest, out _);
}

[EgorBo]

The bot can repro the regression too, perf points to Math.DivRem(..., TenPowMaxPartial) as the hottest place, but I might be wrong interpretating it

[EgorBo]

@EgorBot -amd -profiler -commit 264e39c vs previous

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Numerics;

BenchmarkSwitcher.FromAssembly(typeof(Program).Assembly).Run(args);

[MemoryDiagnoser(false)]
[HideColumns("Job", "Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private char[] _dest = new char[1_000_000];

    private BigInteger _value =
        BigInteger.Pow(BigInteger.Parse(string.Concat(Enumerable.Repeat("1234567890", 30))), 1_000);

    [Benchmark(Baseline = true)]
    public string Stringify() => _value.ToString();

    [Benchmark]
    public bool TryFormat() => _value.TryFormat(_dest, out _);
}

[EgorBo]

@EgorBot -amd -profiler -commit 7a5fb4f vs previous

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Numerics;

BenchmarkSwitcher.FromAssembly(typeof(Program).Assembly).Run(args);

[MemoryDiagnoser(false)]
[HideColumns("Job", "Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private char[] _dest = new char[1_000_000];

    private BigInteger _value =
        BigInteger.Pow(BigInteger.Parse(string.Concat(Enumerable.Repeat("1234567890", 30))), 1_000);

    [Benchmark(Baseline = true)]
    public string Stringify() => _value.ToString();

    [Benchmark]
    public bool TryFormat() => _value.TryFormat(_dest, out _);
}

[kzrnm]

https://github.com/kzrnm/BigIntegerBenchmark111708

I benchmarked the following implementations on .NET 8 and .NET 9:

• A clone of the .NET 8 (tag: v8.0.8) implementation
• A clone of the .NET 9 (tag: v9.0.1) implementation
• The original .NET implementation

As a result, only the original implementation on .NET 9 is slower than others.

BenchmarkDotNet v0.14.0, Windows 11 (10.0.26100.3037)
13th Gen Intel Core i5-13500, 1 CPU, 20 logical and 14 physical cores
.NET SDK 9.0.102
  [Host]   : .NET 9.0.1 (9.0.124.61010), X64 RyuJIT AVX2
  ShortRun : .NET 8.0.12 (8.0.1224.60305), X64 RyuJIT AVX2

Job=ShortRun  IterationCount=3  LaunchCount=1  
WarmupCount=3  

Method	Toolchain	Mean	Ratio	Allocated	Alloc Ratio
SystemRuntimeNumerics	.NET 8.0	1,119.7 ms	1.00	777752 B	1.000
Net8Clone	.NET 8.0	1,097.0 ms	0.98	777752 B	1.000
Net9Clone	.NET 8.0	985.7 ms	0.88	736 B	0.001
SystemRuntimeNumerics	.NET 9.0	2,010.5 ms	1.00	448 B	1.00
Net8Clone	.NET 9.0	1,126.2 ms	0.56	777752 B	1,736.05
Net9Clone	.NET 9.0	1,010.5 ms	0.50	736 B	1.64

---

In Native AOT, the performance of the original .NET implementation and the cloned implementation became equivalent.

BenchmarkDotNet v0.14.1-nightly.20240828.182, Windows 11 (10.0.26100.3037)
13th Gen Intel Core i5-13500 2.50GHz, 1 CPU, 20 logical and 14 physical cores
.NET SDK 9.0.102
  [Host]   : .NET 9.0.1 (9.0.124.61010), X64 RyuJIT AVX2
  ShortRun : .NET 8.0.12 (8.0.1224.60305), X64 RyuJIT AVX2

Job=ShortRun  IterationCount=3  LaunchCount=1  
WarmupCount=3  

Method	Toolchain	Mean	Ratio	Allocated	Alloc Ratio
SystemRuntimeNumerics	.NET 8.0	1.148 s	1.00	777752 B	1.000
Net8Clone	.NET 8.0	1.147 s	1.00	777752 B	1.000
Net9Clone	.NET 8.0	1.035 s	0.90	736 B	0.001
SystemRuntimeNumerics	.NET 9.0	2.054 s	1.00	736 B	1.00
Net8Clone	.NET 9.0	1.154 s	0.56	777752 B	1,056.73
Net9Clone	.NET 9.0	1.030 s	0.50	400 B	0.54
SystemRuntimeNumerics	Latest ILCompiler	1.030 s	1.00	720 B	1.00
Net8Clone	Latest ILCompiler	1.151 s	1.12	777736 B	1,080.19
Net9Clone	Latest ILCompiler	1.037 s	1.01	720 B	1.00

[kzrnm]

When compiled with NoOptimization, the results became equivalent. It seems that tiered compilation has a significant impact.

        [MethodImpl(MethodImplOptions.NoOptimization)]
        private static unsafe string? FormatBigInteger(
            bool targetSpan, BigInteger value,
            string? formatString, ReadOnlySpan<char> formatSpan,
            NumberFormatInfo info, Span<char> destination, out int charsWritten, out bool spanSuccess)

BenchmarkDotNet v0.14.1-nightly.20240828.182, Windows 11 (10.0.26100.3037)
13th Gen Intel Core i5-13500 2.50GHz, 1 CPU, 20 logical and 14 physical cores
.NET SDK 9.0.102
  [Host]   : .NET 9.0.1 (9.0.124.61010), X64 RyuJIT AVX2
  ShortRun : .NET 8.0.12 (8.0.1224.60305), X64 RyuJIT AVX2

Job=ShortRun  IterationCount=3  LaunchCount=1  
WarmupCount=3  

Method	Toolchain	Mean	Ratio	Allocated	Alloc Ratio
SystemRuntimeNumerics	.NET 8.0	1,141.3 ms	1.00	777752 B	1.000
Net8Clone	.NET 8.0	1,130.0 ms	0.99	777752 B	1.000
Net9Clone	.NET 8.0	1,009.7 ms	0.88	736 B	0.001
Net9NoOptClone	.NET 8.0	2,067.7 ms	1.81	800 B	0.001
SystemRuntimeNumerics	.NET 9.0	2,008.9 ms	1.00	736 B	1.00
Net8Clone	.NET 9.0	1,124.3 ms	0.56	777752 B	1,056.73
Net9Clone	.NET 9.0	1,012.9 ms	0.50	448 B	0.61
Net9NoOptClone	.NET 9.0	2,104.8 ms	1.05	736 B	1.00
SystemRuntimeNumerics	Latest ILCompiler	997.1 ms	1.00	720 B	1.00
Net8Clone	Latest ILCompiler	1,139.5 ms	1.14	777736 B	1,080.19
Net9Clone	Latest ILCompiler	1,003.9 ms	1.01	720 B	1.00
Net9NoOptClone	Latest ILCompiler	1,990.2 ms	2.00	720 B	1.00