C# 基本运算时间如何随数字大小变化？

Question

这是一个函数，每帧几乎需要运行一次，因此在性能方面非常关键。此函数包含一个循环，以及其中的操作。

private int MyFunction(int number)
{
    // Code
    for (int i = 0; i <= 10000; i++)
    {
        var value = i * number
        var valuePow2 = value * value;

        // Some code which uses valuePow2 several times
    }
    return 0; // Not actual line
}

现在，由于数学性质，我们知道 (a * b)² 等于 a² * b²

因此，可以将我的函数变成这样：

private int MyFunction(int number)
{
    // Code
    var numberPow2 = number * number;
    for (int i = 0; i <= 10000; i++)
    {
        var iPow2 = i * i
        var valuePow2 = numberPow2 * iPow2;

        // Some code which uses valuePow2 several times
    }
    return 0; // Not actual line
}

直觉上，这似乎应该更快，因为 number² 没有变化，现在只在循环外计算一次。至少，这对人类来说会快得多，因为 x² 操作在循环期间是在一个小得多的数字上完成的。

我想知道的是，在 C# 中，当您使用像 int 这样的类型时，乘法实际上会更快吗？

例如，5 * 5 会比 5000 * 5000 执行得更快吗？

如果是这样，那么第二个版本就更好了，即使是一个小的差距，因为那个。

但是，如果对于给定的数据类型，时间是常数，那么函数的第一个版本更好，因为一半的计算将在较小的数字上完成，因为我在循环两次，但在第二个版本中，我在开始之前做了一个额外的乘法。

我知道就所有意图和目的而言，性能差异可以忽略不计。我在 Code Review 中被建议使用第二个版本，因为该功能很关键，而且我找不到任何文档来支持这两种观点。

Answer 1

对于典型的处理器，无论这些整数中的数据如何，将两个 32 位整数相乘将花费相同的周期数。 Most current processors will take nearly twice the time to multiply 64-bit integers as it takes to multiply 32-bit integers.

我注意到你的两个代码都有问题。当您将两个整数相乘时，它 return 是一个类型 int。 var 类型会将类型设置为 return 值。这意味着，valuePow2 将是一个 int。由于你的循环上升到 10000，如果 number 为 5 或更大，那么你将溢出 valuePow2。

如果您不想让您的整数溢出，您可以将代码更改为

private int MyFunction(int number)
{
    // Code
    for (int i = 0; i <= 10000; i++)
    {
        long value = i * number;        //64bit multiplication          
        long valuePow2 = value * value; //64bit multiplication

        // Some code which uses valuePow2 several times
    }
    return 0; // Not actual line
}

修改后的代码应该更快，因为您可以将 64 位乘法更改为 32 位乘法

private int MyFunction(int number)
{
    // Code
    long numberPow2 = number * number; //64bit multiplication
    for (int i = 0; i <= 10000; i++)
    {
        int iPow2 = i * i;                      //32bit multiplication
        long valuePow2 = numberPow2 * iPow2;    //64bit multiplication

        // Some code which uses valuePow2 several times
    }
    return 0; // Not actual line
}

但是 CPU 中的电路和编译器的优化可以改变最终的循环数运行。最后，你说得最好：

I am aware that for all intent and purposes, the performance difference is negligible.

Answer 2

For example, will 5 * 5 execute faster than 5000 * 5000?

对于编译时常量，5 * x 比 5000 * x 便宜，因为前者可以用 lea eax, [rdi + rdi*4].

完成

但是对于运行时间变量，唯一具有数据依赖性能的整数指令是除法。这适用于任何主流CPU：流水线是如此重要，以至于即使某些情况下可以运行具有较低的延迟，但它们通常不会，因为这会使调度变得更加困难。（你不能让同一个执行单元在同一个周期内产生 2 个结果；相反 CPU 只是想知道在一个周期内输入输入肯定会在 3 个周期后产生答案。）

（对于 FP，同样只有除法和 sqrt 在正常 CPUs 上具有数据相关性能。）

如果分支采用不同的方式，则使用具有任何数据相关分支的整数或 FP 的代码可能会慢得多。（例如，分支预测是 "trained" 在二进制搜索的一个跳跃序列上；使用另一个键搜索会更慢，因为它至少会错误预测一次。）

郑重声明，使用 Math.Pow 而不是整数 * 的建议是疯狂的。简单地将整数转换为 double 并返回比用整数乘法自相乘要慢。

Adam 的回答链接了一个在大数组上循环的基准，可以进行自动矢量化。 SSE/AVX2 只有 32 位整数乘法。而 64 位需要更多的内存带宽。这也是它显示 16 位和 8 位整数加速的原因。因此它发现 c=a*b 运行在 Haswell CPU 上以半速运行，但这 不适用于 循环情况。

在标量代码中，imul r64, r64 在 Intel 主流 CPUs（至少 Nehalem）和 Ryzen（https://agner.org/optimize/）上具有与 imul r32, r32 相同的性能。均为 1 uop，3 周期延迟，1/时钟吞吐量。

只有 AMD Bulldozer 系列、AMD Atom 和 Silvermont，其中 64 位标量乘法较慢。（当然假设是 64 位模式！在 32 位模式下，使用 64 位整数会比较慢。）

优化循环

对于 number 的固定值，编译器可以并将其优化为 inum += number，而不是重新计算 i*number。这称为 strength-reduction optimization，因为加法是 "weaker"（比乘法便宜一点）的运算。

for(...) {
    var value = i * number
    var valuePow2 = value * value;
}

可以编译成 asm，做类似

的事情

var value = 0;
for(...) {
    var valuePow2 = value * value;

    ...

    value += number;
}

您可以尝试以这种方式手动编写，以防编译器不为您完成。

但是整数乘法在现代 CPUs 上非常便宜并且完全流水线化，尤其是。它的延迟比添加略高，并且可以在更少的端口上运行（通常每个时钟吞吐量只有 1 个，而不是添加 4 个），但是你说你正在用 valuePow2 做重要的工作。这应该让乱序执行隐藏延迟。

如果您检查 asm 并且编译器使用一个单独的递增 1 的循环计数器，您也可以尝试让您的编译器优化循环以使用 value 作为循环计数器。


var maxval = number * 10000;
for (var value = 0; i <= maxval; value += number) {
    var valuePow2 = value * value;

    ...
}

如果 number*10000 可能溢出，请小心，如果您需要它正确换行。在那种情况下，此循环将运行迭代次数少得多。（除非 number 太大以至于 value += number 也换行...）

C# 基本运算时间如何随数字大小变化？

C# How do basic operation time vary with the size of the numbers?

c#

optimization

performance

multiplication

micro-optimization

优化循环