使用计时器测量性能，顺序似乎很重要，尽管它不应该

Question

作为练习，我试图测量应该执行相同任务的两个算法的效率，排序堆栈，仅使用堆栈作为支持数据结构：

#include <stack>
#include <iostream>
#include <chrono>

std::stack<int> sortStack(std::stack<int>& inS){
  std::stack<int> tmpS;
  int tmpV=0;
  tmpS.push(inS.top());
  inS.pop();

  while(!inS.empty()){
    if(inS.top()>=tmpS.top()){
      tmpS.push(inS.top());
      inS.pop();
    }else{
      tmpV = inS.top();
      inS.pop();
      int count = 0;

      //reverse the stack until we find the item that is smaller
      while(!tmpS.empty()){
        if(tmpS.top()>tmpV){
          inS.push(tmpS.top());
          tmpS.pop();
          count++;
        }else{
          break;
        }
      }
      //tmpS.top is smaller (or =) than tmpV
      tmpS.push(tmpV);

      //and revert the other stack
      for(int i=0; i< count; i++){
        tmpS.push(inS.top());
        inS.pop();
      }
    }
  }

  return tmpS;
}

std::stack<int> sortStackRevisited(std::stack<int>& inS){
  std::stack<int> tmpS;
  int tmpV=0;

  while(!inS.empty()){
    tmpV = inS.top();
    inS.pop();
    //reverse the stack until we find the item that is smaller
      while(!tmpS.empty() && tmpS.top()>tmpV){
          inS.push(tmpS.top());
          tmpS.pop();
      }
      tmpS.push(tmpV);
    }

  return tmpS;
}
int main(){

using namespace std::chrono;
  std::stack<int> s1({1,0,123,3,5,89,23,12,1000});

  std::stack<int> s({1,0,123,3,5,89,23,12,1000});

  auto t1 = high_resolution_clock::now() ;

  std::stack<int> ordered = sortStackRevisited(s);

  auto t2 = high_resolution_clock::now() ;

  std::stack<int> ordered2 = sortStack(s1);

  auto t3 = high_resolution_clock::now() ;

  std::cout<<"\n";
  std::cout<<duration_cast<microseconds>(t2-t1).count()<<" "<<duration_cast<microseconds>(t3-t2).count()<<"\n";
}

运行这个程序我一致得到t2 - t1大于t3-t2。如果我改变函数调用的顺序，即：

  auto t1 = high_resolution_clock::now() ;

  std::stack<int> ordered = sortStack(s);

  auto t2 = high_resolution_clock::now() ;

  std::stack<int> ordered2 = sortStackRevisited(s1);

  auto t3 = high_resolution_clock::now() ;

我仍然得到t2 - t1大于t3-t2。怎么了？我错过了什么吗？

要编译我使用g++ --std=c++11 sortStack.cpp

Answer 1

仅运行一次代码对于基准测试是不可靠的。你的代码（在修复main以返回int之后）在我的机器上运行不到一微秒（使用-O2，因为它应该被优化）。

如果我将其更改为运行代码100000次，我得到的结果是sortStack比sortStackRevisited更快，无论它们运行的​​顺序如何。

首先运行sortStack：30141 32997

首先运行sortStackRevisited：31244 26642

即使在这里，您只能在运行100k测试时看到变化。它的时机仍然不是很准确。

所以我假设您运行的是未经优化的代码，并且只执行一次运行，这可能会导致所有类型的工件导致结果出现问题。其中一个是测量实时结果，而不是CPU时间，这意味着操作系统在运行代码的CPU上抛出的任何内容都会导致它在实时运行速度较慢，即使CPU时间相同也是如此。或者可能导致CPU缓存处理不同的事情，或者这个或那个。有很多可能性。

我的机器上的未经优化的代码运行速度比优化的慢20倍，这表明编译器可以做很多事情来使事情变得更好并影响最终结果。

但是，如果将它们相互比较，那么运行两次例如将会产生相对好的结果。两个值都会有所不同，但相互比较它们会保持不变。例如，在我的机器上，时间除以另一个是1.139-1.142，所以很明显，另一种方法慢了14％。如果我只进行10次运行，结果就是速度慢了200％。 1000次运行速度慢了12-28％。因此，统计数据显示，更多尝试会带来更多准