比较两个函数的执行时间？

Question

我编写了两个功能相同的函数，但是使用了不同的算法。我使用time.h中的clock（）比较执行时间，但结果不一致。

我试图更改函数的执行顺序，但似乎第一个要执行的函数将始终具有更长的运行时间

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

long exponent(int a, int b);
long exponentFast(int a, int b);


int main(void)
{
    int base;
    int power;
    clock_t begin;
    clock_t end;
    double time_spent;

    base = 2;
    power = 25;

    begin = clock();
    long result1 = exponentFast(base, power);
    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("Result1: %li, Time: %.9f\n", result1, time_spent);

    begin = clock();
    long result2 = exponent(base, power);
    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("Result2: %li, Time: %.9f\n", result2, time_spent);
}

long exponent(int a, int b)
{
    ...
}

long exponentFast(int a, int b)
{
    ...
}

我期望result1的time_spent值比result2的低，但输出为

Result1: 33554432, Time: 0.000002000
Result2: 33554432, Time: 0.000001000

在exponentFast（）之前执行exponent（）也会产生相同的结果，这表明我的基准测试实现是错误的。

Answer 1

准确而显着地对此类函数调用执行计时可能出乎意料的困难。这是您的程序的修改，说明了困难：

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

long exponent(int a, int b);
long exponentFast(int a, int b);

void tester(long (*)(int, int));

#define NTRIALS 1000000000

int main(void)
{
    clock_t begin;
    clock_t end;
    double time_spent;

    begin = clock();
    tester(exponentFast);
    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("exponentFast: Time: %.9f = %.10f/call\n", time_spent, time_spent / NTRIALS);

    begin = clock();
    tester(exponent);
    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("exponent: Time: %.9f = %.10f/call\n", time_spent, time_spent / NTRIALS);
}

void tester(long (*func)(int, int))
{
    int base = 2;
    int power = 25;
    int i;
    unsigned long accum = 0;
    for(i = 0; i < NTRIALS; i++) {
        accum += (*func)(base, power);
        base = (base + 1) % 5;
        power = (power + 7) % 16;
    }
    printf("(accum = %lu)\n", accum);
}

long exponent(int a, int b)
{
    return pow(a, b);
}

long exponentFast(int a, int b)
{
    long ret = 1;
    int i;
    for(i = 0; i < b; i++)
        ret *= a;
    return ret;
}

您会注意到：

• 我已经安排执行多次试验，其中涉及添加一个新功能tester()来执行此操作。（tester()因此将指针指向要测试的函数，这是您可能还不熟悉的技术。）
• 我已安排在两次调用之间更改被测函数的参数。
• 我已经准备好对被测函数的返回值进行处理，即将它们全部加起来。

（第二和第三个项目符号遵循Jonathan Leffler的建议，旨在确保过于聪明的编译器不会优化某些或全部有趣的工作。）

当我在计算机（普通的消费者级笔记本电脑）上运行此软件时，得到的结果是：

(accum = 18165558496053920)
exponentFast: Time: 20.954286000 = 0.0000000210/call
(accum = 18165558496053920)
exponent: Time: 23.409001000 = 0.0000000234/call

这里有两件事需要注意。

1. 我每个功能都运行了十亿次。是的，十亿，十亿。但这只花了大约20秒。
2. 即使进行了如此多的试验，“常规”和“快速”版本之间仍然几乎没有明显的区别。平均而言，一个人花费了21纳秒（纳秒！）；另一个花了23纳秒。大声疾呼。

（但是，实际上，该第一次审判明显具有误导性。更多的是它的信息。）

在继续之前，值得提出几个问题。

1. 这些结果是否有意义？这些功能实际上可能仅需要数十纳秒的时间来完成其工作吗？
2. 假设它们是准确的，那么这些结果是否告诉我们，我们在浪费时间，“常规”和“快速”版本之间的差异很小，以至于不值得编写和调试“快速”版本一？

首先，让我们进行快速的信封分析。我的机器声称具有2.2 GHz CPU。这意味着（大致而言），它每秒可以完成22亿次操作，或每件事大约0.45纳秒。因此，耗时21纳秒的函数大约可以完成23 / 0.45 = 45项操作。而且由于我的样本exponentFast函数所进行的乘法运算与指数的值大致相同，因此看起来我们可能处于正确的状态。

为了确认我至少获得了合理的结果，我所做的另一件事是改变了试验次数。随着NTRIALS降低到100000000，整个项目只用了约整整十分之一的时间来运行，这意味着每次通话的时间是一致的。

现在，到第二点，我仍然记得我在程序员中的一种形成经验，当时我编写了标准函数的新的和改进的版本，我刚刚知道它会变得更快，然后花了几个小时调试它以获得它的确发挥了作用，我发现它的测量速度并没有明显提高，直到我将试验次数增加到数百万次，而一分钱（正如他们所说）下降了。

但是正如我所说，到目前为止，我提出的结果是一个偶然的巧合，令人误解。当我第一次汇总一些简单的代码来改变为函数调用提供的参数时，如上所述，我有：

int base = 2;
int power = 25;

然后，在循环内

    base = (base + 1) % 5;
    power = (power + 7) % 16;

这样做的目的是允许base从0到4，power从0到15，选择数字以确保即使在base4 时结果也不会溢出。但这意味着power平均而言，只有8，这意味着我的想法简单exponentFast，只需平均循环8次，而不是您原始帖子中的25次。

当我将迭代步骤更改为

power = 25 + (power - 25 + 1) % 5;

-不变base（因此，使其保持为常数2），并允许power在25到30之间变化，现在每次调用的时间exponentFast增加到了约63纳秒。好消息是，这是有道理的（平均而言，迭代大约是它的三倍，使它的速度慢了大约三倍），但是坏消息是，我的“ exponentFast”函数看起来并不是很快！（不过，显然，我没想到它具有简单的暴力循环。如果我想使其更快，我要做的第一件事就是应用，而无需付出太多的复杂性）“二进制幂”。）

不过，至少还有一件事要担心，那就是如果我们将这些功能调用十亿次，那么我们不仅在计算每个功能完成工作所花费的时间十亿倍，而且还在计算十亿次函数调用开销。如果函数调用开销与该函数正在执行的工作量相等，则我们（a）很难测量实际的工作时间，但是（b）很难加快速度！（我们可以通过内联测试函数来消除函数调用的开销，但是，如果最终程序中对函数的实际使用将涉及实际的函数调用，那显然就没有意义。）

再有一个不准确性是，我们通过计算每个呼叫的base和和/或新值和/或不同值，并将power所有结果相加来引入时序工件，从而使完成这项工作的摊销时间进入了我们一直在叫“每次通话时间”。（至少这个问题，因为它同等地影响任一幂函数，因此不会影响我们评估哪个（如果有）更快的能力。）

附录：由于我最初的“ exponentFast” 指数确实很尴尬，而且二进制表达式是如此简单和优雅，因此我又进行了一次测试，重写exponentFast为

long exponentFast(int a, int b)
{
    long ret = 1;
    long fac = a;

    while(1) {
        if(b & 1) ret *= fac;
        b >>= 1;
        if(b == 0) break;
        fac *= fac;
    }
    return ret;
}

现在-万岁！- exponentFast在我的机器上，平均每次通话的时间下降到大约16 ns。但是“万岁！” 是合格的。显然，它比调用快25％pow()，这确实很有意义，但不是一个数量级或任何数量级。如果我正在使用该程序的所有时间都花在了指数上，那么我也会使该程序的速度提高25％，但如果不这样做，改进的幅度将较小。在某些情况下，改进（在程序的所有预期运行中节省的时间）少于我编写和测试自己的版本所花费的时间。而且我还没有花时间对改进的产品进行适当的回归测试exponentFast函数，但是如果这不是Stack Overflow帖子中的任何内容，我就必须这样做。它有几套边缘情况，并且很可能包含潜伏的错误。