我编写了两个功能相同的函数,但是使用了不同的算法。我使用time.h中的clock()比较执行时间,但结果不一致。
我试图更改函数的执行顺序,但似乎第一个要执行的函数将始终具有更长的运行时间
#include#include 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()也会产生相同的结果,这表明我的基准测试实现是错误的。
准确而显着地对此类函数调用执行计时可能出乎意料的困难。这是您的程序的修改,说明了困难:
#include#include #include 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 您会注意到:
我已经安排执行多次试验,其中涉及添加一个新功能
tester()
来执行此操作。(tester()
因此将指针指向要测试的函数,这是您可能还不熟悉的技术。)我已安排在两次调用之间更改被测函数的参数。
我已经准备好对被测函数的返回值进行处理,即将它们全部加起来。
(第二和第三个项目符号遵循Jonathan Leffler的建议,旨在确保过于聪明的编译器不会优化某些或全部有趣的工作。)
当我在计算机(普通的消费者级笔记本电脑)上运行此软件时,得到的结果是:
(accum = 18165558496053920) exponentFast: Time: 20.954286000 = 0.0000000210/call (accum = 18165558496053920) exponent: Time: 23.409001000 = 0.0000000234/call这里有两件事需要注意。
我每个功能都运行了十亿次。是的,十亿,十亿。但这只花了大约20秒。
即使进行了如此多的试验,“常规”和“快速”版本之间仍然几乎没有明显的区别。平均而言,一个人花费了21纳秒(纳秒!);另一个花了23纳秒。大声疾呼。
(但是,实际上,该第一次审判明显具有误导性。更多的是它的信息。)
在继续之前,值得提出几个问题。
这些结果是否有意义?这些功能实际上可能仅需要数十纳秒的时间来完成其工作吗?
假设它们是准确的,那么这些结果是否告诉我们,我们在浪费时间,“常规”和“快速”版本之间的差异很小,以至于不值得编写和调试“快速”版本一?
首先,让我们进行快速的信封分析。我的机器声称具有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,选择数字以确保即使在base
4 时结果也不会溢出。但这意味着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帖子中的任何内容,我就必须这样做。它有几套边缘情况,并且很可能包含潜伏的错误。