Измерение производительности с использованием хронографа, порядок, кажется, имеет значение, хотя это не должно - PullRequest
Новая
       16

Измерение производительности с использованием хронографа, порядок, кажется, имеет значение, хотя это не должно

0 голосов
/ 28 марта 2019

В качестве упражнения я пытаюсь измерить эффективность двух алгоритмов, которые должны выполнять одну и ту же задачу: упорядочить стек, используя только стек в качестве вспомогательной структуры данных: 

#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";
}

, запускающая эту программу Iполучить последовательно, что 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

1 Ответ

5 голосов
/ 28 марта 2019

Запуск кода только один раз не надежен для бенчмаркинга. Ваш код (после исправления main для возврата int) выполняется на моей машине менее чем за микросекунду (используя -O2, поскольку он должен быть оптимизирован).

Если я изменю его для запуска кода 100000 раз, я получу результаты, что sortStack быстрее, чем sortStackRevisited, независимо от того, в каком порядке они выполняются.

Бег sortStack сначала: 30141 32997

Бег sortStackRevisited сначала: 31244 26642

Даже здесь вы можете увидеть разницу при запуске только 100 тыс. Тестов. Это все еще не очень точное время.

Итак, я предполагаю, что вы запускаете неоптимизированный код и выполняете только один прогон, который может иметь всевозможные артефакты, вызывающие проблемы с результатами. Одним из них является то, что вы измеряете результаты в реальном времени, а не процессорное время, что означает, что все, что ОС выдает на ЦП, на которых выполняется код, приведет к замедлению работы в реальном времени, даже если время ЦП будет таким же. Или может привести к тому, что кэш процессора будет обрабатывать вещи по-другому, или тому, или другому. Есть много возможностей.

Кроме того, неоптимизированный код на моей машине работает в 20 раз медленнее, чем оптимизированный, что показывает, что компилятор может многое сделать, чтобы улучшить ситуацию и повлиять на конечный результат.

Но запуск, например, миллион раз, даст сравнительно хороший результат при сравнении их друг с другом. Оба значения будут различаться, но по сравнению друг с другом они останутся более одинаковыми. Например, на моей машине время, разделенное на другое, составляет 1.139-1.142, поэтому совершенно очевидно, что другой метод работает на 14% медленнее. Если я сделаю всего 10 запусков, то результат будет на 200% медленнее. С 1000 пробегами это на 12-28% медленнее. Так что больше попыток приносит больше точности, как говорит статистика.

...