c - 不同算子的执行时间

Question

我在阅读高德纳 (Knuth) 的《计算机编程艺术》，我注意到他指出 DIV 命令比他的 MIX 汇编语言中的 ADD 命令花费的时间长 6 倍。

为了测试与现代架构的相关性，我编写了以下代码片段:

#include <time.h>
#include <stdio.h>
#include <stdlib.h>


int main(int argc, char *argv[])
{
    clock_t start;
    unsigned int ia=0,ib=0,ic=0;
    int i;
    float fa=0.0,fb=0.0,fc=0.0;
    int sample_size=100000;

    if (argc > 1)
        sample_size = atoi(argv[1]);

#define TEST(OP) \
    start = clock();\
    for (i = 0; i < sample_size; ++i)\
        ic += (ia++) OP ((ib--)+1);\
    printf("%d,", (int)(clock() - start))
    TEST(+);
    TEST(*);
    TEST(/);
    TEST(%);
    TEST(>>);
    TEST(<<);
    TEST(&);
    TEST(|);
    TEST(^);
#undef TEST

//TEST must be redefined for floating point types
#define TEST(OP) \
    start = clock();\
    for (i = 0; i < sample_size; ++i)\
        fc += (fa+=0.5) OP ((fb-=0.5)+1);\
    printf("%d,", (int)(clock() - start))
    TEST(+);
    TEST(*);
    TEST(/);
#undef TEST

    printf("\n");
    return ic+fc;//to prevent optimization!
}

然后我使用此命令行生成了 4000 个测试样本(每个包含每种类型的样本大小为 100000 次操作):

for i in {1..4000}; do ./test >> output.csv; done

最后，我用 Excel 打开结果并绘制平均值。我的发现相当令人惊讶。这是结果图:

实际平均值是(从左到右):463.36475,437.38475,806.59725,821.70975,419.56525,417.85725,426.35975,425.9445,423.792,549.91975,544.118215,525>425>

总体而言，这是我所期望的(除法和模运算很慢，浮点结果也是如此)。

我的问题是:为什么整数和浮点乘法的执行速度都比加法快？这是一个很小的因素，但它在众多测试中是一致的。在 TAOCP 中，Knuth 将 ADD 列为占用 2 个时间单位，而 MUL 占用 10 个时间单位。此后 CPU 架构是否发生了某些变化？

Answer 1

不同的指令在同一个 CPU 上花费不同的时间；并且相同的指令在不同的 CPU 上可能需要不同的时间。例如，对于 Intel 最初的 Pentium 4，移位成本相对较高，而加法速度相当快，因此向自身添加寄存器比将寄存器左移 1 更快；对于英特尔最近的 CPU，移位和加法的速度大致相同(就“周期”而言，移位比原来的奔腾 4 快，加法慢)。

更复杂的是，不同的 CPU 可能同时处理更多或更少的事情，并且存在影响性能的其他差异。

理论上(不一定在实践中):

移位和 bool 运算(AND、OR、XOR)应该是最快的(每个位都可以并行完成)。接下来应该是加法和减法(比较简单，但是结果的所有位不能并行完成，因为从一对位到下一位的进位)。

乘法应该慢得多，因为它涉及许多加法，但其中一些加法可以并行完成。举一个简单的例子(使用十进制数字而不是二进制)，像 12 * 34(有多个数字)这样的东西可以分解成“单个数字”形式，变成 2*4 + 2*3 * 10 + 1*4 * 10 + 1 *3 * 100；其中所有“个位数”乘法可以并行完成，然后 2 个加法可以并行完成，最后一个加法可以完成。

除法主要是“比较和减去如果更大，重复”。它是最慢的，因为它不能并行完成(下一次比较需要减法的结果)。 Modulo 是除法的余数，本质上与除法相同(对于大多数 CPU，它实际上是相同的指令 - 例如 DIV 指令为您提供商和余数)。

对于 float ；每个数字都有 2 个部分(尾数和指数)，所以事情变得有点复杂。浮点移位实际上是对指数进行加法或减法(并且成本应该与整数加法/减法大致相同)。对于浮点加法、减法和 bool 运算，您需要对指数进行均衡，然后单独对有效数字进行运算(“均衡”和“执行运算”不能并行进行)。乘法是将有效数相乘并加上指数(并调整偏差)，这两个部分可以并行完成，因此总成本以最慢的为准(乘以有效数)；所以它和整数乘法一样快。除法是除有效数并减去指数(并调整偏差)，这两个部分可以并行完成，总成本以最慢的为准(除有效数)；所以它和整数除法一样快。

注意:我在多个地方进行了简化以使其更易于理解。