看起来很愚蠢,我想知道在尝试调和for
循环的时间成本时是否存在陷阱
从for
循环外部的时间点开始(全局或外部时间成本)
或者,从处于循环内的时间点开始,并被累计考虑(本地或内部时间成本)?
下面的示例说明了我很难获得两个相等的度量值:
#include <iostream>
#include <vector> // std::vector
#include <ctime> // clock(), ..
int main(){
clock_t clockStartLoop;
double timeInternal(0)// the time cost of the loop, summing all time costs of commands within the "for" loop
, timeExternal // time cost of the loop, as measured outside the boundaries of "for" loop
;
std::vector<int> vecInt; // will be [0,1,..,10000] after the loop below
clock_t costExternal(clock());
for(int i=0;i<10000;i++){
clockStartLoop = clock();
vecInt.push_back(i);
timeInternal += clock() - clockStartLoop; // incrementing internal time cost
}
timeInternal /= CLOCKS_PER_SEC;
timeExternal = (clock() - costExternal)/(double)CLOCKS_PER_SEC;
std::cout << "timeExternal = "<< timeExternal << " s ";
std::cout << "vs timeInternal = " << timeInternal << std::endl;
std::cout << "We have a ratio of " << timeExternal/timeInternal << " between the two.." << std::endl;
}
我通常得到一个大约2的比率作为输出,例如
timeExternal = 0.008407 s vs timeInternal = 0.004287
两者之比为1.96105。
,而我希望该比率接近1。
难道仅仅是因为循环内部有一些操作不是由clock()的差异来衡量的(例如递增
timeInternal
)吗?能否在外部测量中忽略
i++
中的for(..)
操作,并解释与内部测量之间的差异?我实际上正在处理一个更复杂的代码,并且我想在一个循环中隔离时间成本,请确保我考虑的所有时间片都构成一个完整的饼图(直到现在我都没有实现。)。非常感谢
最佳答案
timeExternal = 0.008407 s vs timeInternal = 0.004287我们两者之间的比率为1.96105。
比率约为2-循环中最重的调用是clock()
本身(在大多数系统上,clock()
是对内核的syscall)。
假设clock()
实现看起来像下面的伪代码:
clock_t clock() {
go_to_kernel(); // very long operation
clock_t rc = query_process_clock();
return_from_kernel(); // very long operation
return rc;
}
现在回到循环,我们可以注释一下花费时间的地方:
for(int i=0;i<10000;i++){
// go_to_kernel - very long operation
clockStartLoop = clock();
// return_from_kernel - very long operation
vecInt.push_back(i);
// go_to_kernel - very long operation
timeInternal += clock() - clockStartLoop;
// return_from_kernel - very long operation
}
因此,在两次调用
clock()
之间,我们有2个长运算,循环中的总数为4。因此,比率为2比1。仅仅是因为循环内部有一些操作不能通过
clock()
差来衡量(例如递增timeInternal
)吗?不,递增
timeInterval
可以忽略不计。能否在外部测量中忽略
i++
中的for(..)
操作,并解释与内部测量之间的差异?不,
i++
也可以忽略不计。删除对clock()
的内部调用,您将看到更快的执行时间。在我的系统上为0.00003秒。clock()
之后的第二个最昂贵的操作是vector::push_back()
,因为它需要调整vector
的大小。这由二次增长因子摊销,可以通过在进入循环之前调用vector::reserve()
完全消除。结论:进行基准测试时,请确保对整个循环计时,而不要对单个迭代计时。更好的是,使用Google Benchmark之类的框架,这将有助于避免许多其他陷阱(例如编译器优化)。对于简单的案例,还有quick-bench.com(基于Google Benchmark)。