c# - 为什么通过成对执行计算来计算连续整数数组的乘积会更快？

Question

我在尝试创建自己的阶乘函数时发现，如果成对计算，计算速度是原来的两倍。像这样:

1 组:2*3*4 ... 50000*50001 = 4.1 秒

2 人一组:(2*3)*(4*5)*(6*7) ... (50000*50001) = 2.0 秒

3 人一组:(2*3*4)*(5*6*7) ... (49999*50000*50001) = 4.8 秒

这是我用来测试它的 c#。

Stopwatch timer = new Stopwatch();
timer.Start();

// Seperate the calculation into groups of this size.
int k = 2;

BigInteger total = 1;

// Iterates from 2 to 50002, but instead of incrementing 'i' by one, it increments it 'k' times,
// and the inner loop calculates the product of 'i' to 'i+k', and multiplies 'total' by that result.
for (var i = 2; i < 50000 + 2; i += k)
{
    BigInteger partialTotal = 1;
    for (var j = 0; j < k; j++)
    {
        // Stops if it exceeds 50000.
        if (i + j >= 50000) break;
        partialTotal *= i + j;
    }
    total *= partialTotal;
}

Console.WriteLine(timer.ElapsedMilliseconds / 1000.0 + "s");

我在不同级别对此进行了测试，并将几个测试的平均时间放在条形图中。我预计它会随着组数的增加而变得更有效率，但 3 组效率最低，4 组与 1 组相比没有任何改进。

Link to First Data

Link to Second Data

是什么导致了这种差异，是否有最佳的计算方法？

Answer 1

BigInteger 对于 31 位或更少的数字有一个快速的情况。当您进行成对乘法时，这意味着采用特定的快速路径，将值乘以单个 ulong 并更明确地设置值:

public void Mul(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2) {
  ...
  if (reg1._iuLast == 0) {
    if (reg2._iuLast == 0)
      Set((ulong)reg1._uSmall * reg2._uSmall);
    else {
      ...
    }
  }
  else if (reg2._iuLast == 0) {
    ...
  }
  else {
    ...
  }
}

public void Set(ulong uu) {
  uint uHi = NumericsHelpers.GetHi(uu);
  if (uHi == 0) {
    _uSmall = NumericsHelpers.GetLo(uu);
    _iuLast = 0;
  }
  else {
    SetSizeLazy(2);
    _rgu[0] = (uint)uu;
    _rgu[1] = uHi;
  }
  AssertValid(true);
}

像这样的 100% 可预测分支非常适合 JIT，而且这条快速路径应该得到非常好的优化。 _rgu[0] 和 _rgu[1] 甚至可能是内联的。这非常便宜，因此有效地将实际操作的数量减少了两倍。

那么为什么三人一组会慢很多呢？很明显，它应该比 k = 2 慢；您的优化乘法要少得多。更有趣的是为什么它比 k = 1 慢。这很容易解释为 total 的外部乘法现在到达了慢速路径。对于 k = 2，可以通过将乘法次数减半和数组的潜在内联来减轻这种影响。

但是，这些因素对 k = 3 没有帮助，事实上，慢速情况对 k = 3 的伤害更大。 k = 3 情况下的第二次乘法命中此情况

  if (reg1._iuLast == 0) {
    ...
  }
  else if (reg2._iuLast == 0) {
    Load(ref reg1, 1);
    Mul(reg2._uSmall);
  }
  else {
    ...
  }

分配

  EnsureWritable(1);

  uint uCarry = 0;
  for (int iu = 0; iu <= _iuLast; iu++)
    uCarry = MulCarry(ref _rgu[iu], u, uCarry);

  if (uCarry != 0) {
    SetSizeKeep(_iuLast + 2, 0);
    _rgu[_iuLast] = uCarry;
  }

为什么这很重要？好吧，EnsureWritable(1) 原因

uint[] rgu = new uint[_iuLast + 1 + cuExtra];

所以 rgu 变成了长度 3。 total 代码中的遍数由

决定

public void Mul(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2)

作为

    for (int iu1 = 0; iu1 < cu1; iu1++) {
      ...
      for (int iu2 = 0; iu2 < cu2; iu2++, iuRes++)
        uCarry = AddMulCarry(ref _rgu[iuRes], uCur, rgu2[iu2], uCarry);
      ...
    }

这意味着我们总共有 len(total._rgu) * 3 操作。这并没有为我们节省任何东西!对于 k = 1，只有 len(total._rgu) * 1 次传递 - 我们只做 3 次!

实际上在外层循环上有一个优化，将其减少到 len(total._rgu) * 2:

      uint uCur = rgu1[iu1];
      if (uCur == 0)
        continue;

然而，他们以一种比以前伤害更大的方式“优化”了这种优化:

if (reg1.CuNonZero <= reg2.CuNonZero) {
  rgu1 = reg1._rgu; cu1 = reg1._iuLast + 1;
  rgu2 = reg2._rgu; cu2 = reg2._iuLast + 1;
}
else {
  rgu1 = reg2._rgu; cu1 = reg2._iuLast + 1;
  rgu2 = reg1._rgu; cu2 = reg1._iuLast + 1;
}

对于 k = 2，这会导致外循环超过 total，因为 reg2 很可能不包含零值。这很棒，因为total 比partialTotal 长方式，所以通过次数越少越好。对于 k = 3，EnsureWritable(1) 总是会产生一个备用空间，因为三个长度不超过 15 位的数字相乘永远不会超过 64 位。这意味着，尽管对于 k = 2，我们仍然只在 total 上做一次 pass，但我们做 两次 k = 3!

这开始解释为什么速度再次增加超过 k = 3:每次加法次数的增加比加法次数减少的速度慢，因为你只增加了 ~15 位到每次的内在值(value)。内部乘法相对于大量的 total 乘法来说速度很快，因此合并值所花费的时间越多，total 中传递所节省的时间就越多。此外，优化很少是悲观的。

这也解释了为什么奇数值需要更长的时间:它们向 _rgu 数组添加了一个额外的 32 位整数。如果 ~15 位不是那么接近 32 的一半，这就不会发生得那么干净。

---

值得注意的是，有很多方法可以改进这段代码；这里的评论是关于为什么，而不是如何解决它。最简单的改进是将值放入堆中并一次只乘以两个最小值。