时间戳

首页 > 解决方案 > C# 基本运算时间如何随数字的大小而变化？

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

问题描述

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

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 中被建议使用第二个版本，因为该功能很关键，而且我找不到任何文档来支持这两种视图。

标签： c#performanceoptimizationmultiplicationmicro-optimization

解决方案

例如，5 * 5 的执行速度会比 5000 * 5000 快吗？

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

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

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

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

并且为了记录，使用Math.Pow而不是整数的建议*是疯狂的。简单地将整数转换为整数double比使用整数乘法自身相乘要慢。

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

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

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

优化你的循环

对于 的固定值，编译器可以并将其优化为number，而不是重新计算。这称为强度降低优化，因为加法是比乘法“更弱”（稍微便宜）的操作。i*numberinum += number

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

可以编译成 asm 做类似的事情

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

    ...

    value += number;
}

您可以尝试以这种方式手动编写它，以防编译器不为您执行此操作。

但是整数乘法非常便宜，并且在现代 CPU 上是完全流水线的，尤其是。它的延迟比 add 稍高，并且可以在更少的端口上运行（通常每个时钟吞吐量只有 1 个，而不是 add 的 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也能包起来……）

推荐阅读