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

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个组没有改善.

链接到第一个数据

链接到第二个数据

造成这种差异的原因是什么,是否有最佳的计算方法？

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业务.这没有拯救我们任何东西!只有len(total._rgu) * 1通行证k = 1- 我们只做了三次!

外环上实际上有一个优化,可以将其减少到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位.这意味着,尽管我们仍然只能做一个传过total了k = 2,我们做2的k = 3!

这开始解释为什么速度再次增加超过k = 3:每次加法的次数增加慢于加法次数减少,因为每次只增加〜15位内部值.内部乘法相对于大量total乘法而言是快速的,因此合并值所花费的时间越多,经过的时间就越多total.此外,优化不那么频繁是悲观.

它还解释了为什么奇数值需要更长的时间:它们为_rgu数组添加了额外的32位整数.如果~15位不是那么接近32的一半,这将不会如此干净地发生.

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