不同算子的执行时间

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.3=145[1481,5]

总的来说这是我所期望的（除法和模运算很慢，浮点结果也是如此）。

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

Answer 1

要测试执行时间，请查看汇编列表中生成的指令并查看这些指令的处理器文档，并注意 FPU 是否正在执行该操作，或者它是否直接在代码中执行。

然后，将每条指令的执行时间相加。

但是，如果 cpu 是流水线或多线程的，则操作所花的时间可能比计算的时间少得多。

Answer 2

除法和取模（除法运算）确实比加法慢。这背后的原因是ALU（算术逻辑单元）的设计。 ALU 是并行加法器和逻辑电路的组合。除法是通过重复减法来执行的，因此需要更多级别的减法逻辑，使除法比加法慢。涉及分裂的门的传播延迟增加了蛋糕上的樱桃。

Answer 3

不同的指令在相同的指令上花费不同的时间CPU；并且相同的指令在不同的 CPU 上可能需要不同的时间。例如，对于 Intel 最初的 Pentium 4，移位成本相对较高，而加法速度相当快，因此向自身添加寄存器比将寄存器左移 1 更快；对于 Intel 最近的 CPUs 移位和加法速度大致相同（移位比原来的 Pentium 4 快，加法慢，"cycles"）。

更复杂的是，不同的 CPU 可能可以同时做更多或更少的事情，并且还有其他影响性能的差异。

理论上（实际上不一定）：

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

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

分裂主要是"compare and subtract if larger, repeated"。它是最慢的，因为它不能并行完成（下一次比较需要减法的结果）。模是除法的余数，与除法基本相同（对于大多数 CPUs 它实际上是相同的指令 - 例如 DIV 指令给你一个商和一个余数）。

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

注意：为了更容易理解，我在各个地方进行了简化。

不同算子的执行时间

Execution time of different operators

c

optimization

cpu

timing

cpu-architecture