为什么 C# 中的 BigInteger.ModPow 函数比 Java 中的函数慢很多？

Question

我发现 C# 中的 BigInteger.ModPow 函数与 Java 中的 BigInteger.modPow 函数相比非常慢。这让我不愿意使用 C# 来实现执行 mod 平方幂的函数。

我写了一个测试程序来证明。

C#

static void Main(string[] args)
{
    BigInteger num = BigInteger.Parse("444266014606582911577255360081280172978907874637194279031281180366057");
    BigInteger m = 2;
    Console.WriteLine("Start multiply.");
    Stopwatch stopwatch = Stopwatch.StartNew();
    for (int i = 3; i <= 200000; i++)
        m *= i;
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
    stopwatch.Reset();
    Console.WriteLine("Start mod pow.");
    stopwatch.Start();
    for (int i = 0; i < 10; i++)
        BigInteger.ModPow(3, m, num);
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
}

Java

中的等效程序

public static void main(String[] args) {
    BigInteger num = new BigInteger("444266014606582911577255360081280172978907874637194279031281180366057");
    BigInteger m = BigInteger.TWO;
    System.out.println("Start multiply.");
    long startTime = System.currentTimeMillis();
    for (int i = 3; i <= 200000; i++)
        m = m.multiply(BigInteger.valueOf(i));
    System.out.println(System.currentTimeMillis() - startTime);
    System.out.println("Start mod pow.");
    startTime = System.currentTimeMillis();
    for (int i = 0; i < 10; i++)
        BigInteger.valueOf(3).modPow(m, num);
    System.out.println(System.currentTimeMillis() - startTime);
}

程序由两部分组成：

计算200000！产生一个非常大的数字 m.
计算3^mmodnum10次。

您可以更改数字或循环计数以尝试找到不同的结果。

这是我电脑上的执行结果。

规格

CPU: Intel(R) Core(TM) i3-8100 CPU @ 3.60GHz
.网络版本： .NET 6.0.102
Java版本：17.0.1

C#

Start multiply.
19443
Start mod pow.
35292

Java

Start multiply.
14668
Start mod pow.
3462

说明C#中的BigInteger.ModPow函数比Java中的函数慢10倍左右。有谁知道原因吗？这是一个错误吗？

Answer 1

您可以看一下 .Net 实现 here and the java ones here。
java 似乎得到了更深入的研究。

Answer 2

您可以看一下 .Net 实现 here and the java ones here。
java 似乎得到了更深入的研究。

最重要的是，.Net 源显示了一个普通的二进制指数 powermod 算法，但是 Java 使用滑动 windows 和蒙哥马利乘法非常复杂。 Java 代码也仔细地“学习”它的内在函数，反过来，其中一些内在函数是专门为大整数运算编写的。

作为实验，我尝试将 Java 代码移植到 C#。目标是分清有多少性能差异来自代码（算法和实现），有多少来自 JIT 编译器优化的差异。

为了公平比较，Java 版本在我的电脑上是这样的：

Start multiply.
7473
Start mod pow.
1406

使用 BigInteger 和从 Java，分别为：

Builtin:
Start multiply.
8059
Start mod pow.
15696
09F59D6D54CE55B44FDF4F4D70E81DBFC8034ECE19339BC7B922F94EA5
Ported from Java:
Start multiply.
8695
Start mod pow.
4971
00000009F59D6D54CE55B44FDF4F4D70E81DBFC8034ECE19339BC7B922F94EA5

我还重复了我建议的只做一次 modpow 的实验，但这并没有产生任何有趣的结果，只是将“modpow 阶段”的时间大约缩短了 10。

一些仅基于时间的观察：

这与您观察到的 Java 代码和 C#-with-builtin-BigInteger 代码之间的性能比大致相同：multiply 在 Java 中快一点，modPow 在 Java.
C# 和 Java 版本的 modpow 代码，移植时有细微差别，因此算法相同，但性能却大不相同。
来自 Java 的 ModPow，移植到 C#，尽管在 C# 中比在 Java 中慢很多，但仍然比 System.Numerics.BigInteger 中的内置版本有显着优势C#.
移植版本 multiply 不仅比 Java 中的版本慢，而且比 C# 内置的版本慢，但不是很多。

但是为什么。不幸的是，我只会对 C# 版本进行观察，推测 Java 版本。我没有设法从 JVM 中获取相关功能的汇编代码。我尝试了各种命令，例如 explained here 但一无所获。显然，在我什至看不到第二件事的情况下比较两件事是不理想的。如果有人设法提取 Java 方法的程序集，我很乐意 实际上 将两者并排比较。

我看到了很多数组边界检查。 “默认循环”中的数组边界检查（从 0 向上计数到长度 - 1 并使用循环计数器直接访问数组）经常被优化掉，但是 Java 代码有很多向后循环（由于使用 big-endian 肢顺序）并且在该代码的 C# 端口中，这些边界检查未优化（希望在未来的 .NET 版本中得到改进）。这是可能的，但我不确定，向后循环中的数组访问是由 Oracle HotSpot 优化的，这将在这段代码的几乎每个重要功能中给它一个（通常很小的）优势（它们中的大多数都有一个在其中向后循环）。这可能足以解释“乘法阶段”的性能差异（常规 C# 版本和从 Java 移植的版本之间）。这仍然留下了当运行作为实际 Java 代码时 Java 代码如何更快的问题..
不出所料，mulAdd 是“modpow 阶段”中最耗时的函数。我的移植版本如下所示：
```
 static int mulAdd(int[] _out, int[] _in, int offset, int len, int k)
 {
     ulong kLong = (uint)k;
     ulong carry = 0;
     offset = _out.Length - offset - 1;
     for (long j = len - 1; j >= 0; j--)
     {
         ulong product = (uint)_in[j] * kLong +
                       (uint)_out[offset] + carry;
         _out[offset--] = (int)product;
         carry = (product >> 32);
     }
     return (int)carry;
 }
```
我认为这是一个合理的移植，在不使用很多“Java-isms”（使用无符号整数而不是 Java 使用的 & LONG_MASK 的情况下保持接近原始值），并且相关的汇编代码甚至看起来 too 都不是很糟糕......不是很好，它有一堆数组边界检查和无用的 movsxd 指令，但真的要花 3 倍吗？慢下来？ mulAdd 的 self-time 约为 2.4 秒，因此即使与 Java 中发生的情况相比，其他代码异常缓慢，也无法解释差异：到期时间在 C# 中 just mulAdd 已经超过 total 时间 Java 在整个“modpow 阶段”花费的时间.

总而言之，这确实不是一个完整的解释，也许它提出的问题多于它回答的问题，至少它是另一个数据点。

移植的代码不包括在这个问题中，因为 1) 它太大了，以及 2) 我移植它的来源被许可为 GPLv2，这与 Stack Overflow 帖子不兼容。它不会是一个“片段”，这是通常用来证明此类包含的豁免。

为什么 C# 中的 BigInteger.ModPow 函数比 Java 中的函数慢很多？

Why is the BigInteger.ModPow function in C# much slower than that in Java?

java

c#

performance

biginteger

exponentiation

规格