看起来很愚蠢,我想知道在尝试调和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)。

09-10 00:21
查看更多