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

Question

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

javac#performancebigintegerexponentiation

3

我发现在C#中，BigInteger.ModPow函数和Java中的BigInteger.modPow函数相比非常慢。这使得我不愿意使用C#来实现执行模幂运算的函数。

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

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 ^ m mod num 10次。

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

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

规格

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

C#

开始乘法。
19443
开始取模幂。
35292

Java

开始乘法。
14668
开始取模幂。
3462

它显示C#中的BigInteger.ModPow函数比Java中的慢约10倍。有人知道原因吗？这是一个bug吗？

- Quicksilver

3

你使用了哪个 .Net 版本？你是在发布版还是调试版下运行的？这与 https://github.com/mono/mono/issues/19908 有关吗？ - Orace

4

建议使用BenchmarkDotNet和JMH进行基准测试，这将提供更准确的结果。参见https://dev59.com/hHRB5IYBdhLWcg3wz6UK - Sweeper

2

似乎.NET 6（C＃，VB，F＃）比Java快两倍以上，但这根本不是问题所在。这只是关于数学函数的实现。一个库可能会更快。 - Bent Tranberg

1

@Sweeper 我不是在做基准测试。打印的经过时间仅供参考。我只想说这个函数非常慢。你可以删除所有计时器代码，只需通过身体感受性能差异即可。显然有时间差！ - Quicksilver

1

我尝试删除循环，让它只运行一次“ModPow”。结果几乎相同。对于两种语言，运行10次“ModPow”的时间大约是运行一次的10倍。 - Quicksilver

显示剩余7条评论

2个回答

3

你可以查看这里的 .Net 实现：链接，以及这里的 Java 实现：链接。
看起来 Java 的实现经过了更深入的研究。

- Orace

4

重点是，.Net源代码显示了一个简单的二进制指数幂取模算法，而Java的算法则使用滑动窗口和蒙哥马利乘法相当复杂。Java代码还精心地“借助”其内置函数，并且其中一些内置函数专门用于大整数算术。 - President James K. Polk

是的，你链接的 .Net 源代码看起来像是平方求幂算法（对于普通数字来说这没问题）... 乘法部分看起来有点可疑，但我懒得进一步分析了。 - Spektre

2

链接的源代码是专门针对小幂次的，完全通用的函数在下面。它确实使用了巴雷特约简（FastReducer），但这不如蒙哥马利乘法高效，并且在.NET版本中没有滑动窗口技巧，因此它不仅使用效率较低的模数乘法，而且使用更多的乘法。 - harold

我在这里留下一条评论，为那些想要追踪.NET中方法的人提供帮助。按位计算入口方法在这里。然后，它会跳转到282>298 > 344>470 > 497>500行。有关FastReducer，请参见此处。 - Quicksilver

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

您可以在此处查看 .Net 实现链接，Java 版本在此处链接。
似乎 Java 版本得到了更深入的研究。

归根结底，.Net 源代码显示的是一个普通的二进制指数幂取模算法，但 Java 的算法相当复杂，使用滑动窗口和蒙哥马利乘法。Java 代码也小心地"倾斜"于其内在函数，并且一些这些内在函数是专门为大整数算术编写的。

作为一个实验，我试图将 Java 代码移植到 C# 中。目标是分解代码（算法和实现）和 JIT 编译器优化之间的性能差异。为了有一个公平比较的东西，这是 Java 版本在我的 PC 上的表现：

Start multiply.
7473
Start mod pow.
1406

使用 BigInteger 和从 Java 移植的版本，C# 版本（在 .NET 6.0 上运行）所需的时间如下（我也打印了一个结果来验证移植代码的有效性）：

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

我也尝试了只进行一次modpow的实验，但结果并没有什么有趣的发现，只是大约将“modpow阶段”的时间缩短了十分之一。

基于时间的一些观察：

这与你观察到的Java代码和带有内置BigInteger代码的C#之间的性能比例大致相同：multiply在Java中稍微快一点，而modPow 在Java中快了10倍以上。
C＃和Java版本的modpow代码，在略有差异的情况下进行移植，因此算法上是相同的，但性能却大不相同。
Java中的ModPow，在C#中被移植后，虽然在C#中比Java慢得多，但仍然比C#内置的System.Numerics.BigInteger版本更具优势。
移植版本multiply不仅比Java中的版本慢，而且比C＃内置的版本慢，但差别不大。

但为什么呢？不幸的是，我只能对C#版本进行观察，并对Java版本进行推测。我无法从JVM中获取相关函数的汇编代码。我尝试了各种命令，例如在这里说明，但没有任何东西。显然，在无法查看第二个东西的情况下进行比较远非理想。如果有人成功提取了Java方法的汇编代码，我很高兴可以将两者并排比较。

I saw a lot of array bounds checks. Array bounds checks in the "default loop" (counting up from 0 to length - 1 and accessing the array directly with the loop counter) are often optimized out, but the Java code has a lot of backwards loops (due to using a big-endian limb order) and in the C# port of that code these bounds checks were not optimized out (hopefully that will be improved in future versions of .NET). It's possible, but I don't know that for sure, that array access in backwards loops are optimized by eg Oracle HotSpot, which would give it a (usually small) edge in nearly every significant function of this code (most of them have a backwards loop in them). That may be enough to explain the performance difference (between the regular C# version and the version that was ported from Java) of the "multiply phase". That still leaves the question of how the Java code is faster when running as actual Java code..

As expected, mulAdd is the single most time consuming function during the "modpow phase". My ported version of it looks like this:

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; }

I think that's a reasonable port, staying close to the original while not using many "Java-isms" (using unsigned integers instead of the & LONG_MASK that Java uses), and the associated assembly code doesn't even look too bad .. not great, it has a bunch of array bounds checks and useless movsxd instructions, but should that really cost a 3x slowdown? mulAdd has a self-time of about 2.4 seconds, so even if it's the other code that is unusually slow compared to what happens in Java, that wouldn't explain the difference: the time due to just mulAdd in C# is already more than the total time that Java spent on the entire "modpow phase".

总的来说，这并不是一个完整的解释，也许会引起更多问题，至少它是另一个数据点。
本问题中未包含移植代码，原因如下：1）代码太大；2）源代码采用GPLv2许可证，与Stack Overflow帖子不兼容。它不会是一个“片段”，通常用于证明此类包含的例外。