Как найти эффективность выполнения кода на С++

Я пытаюсь найти эффективность программы, которую я недавно разместил в stackoverflow.

Как эффективно удалять элементы из вектора, заданного другим вектором

Чтобы сравнить эффективность моего кода с другими ответами, я использую объект chrono.

Правильно ли он проверяет эффективность работы?

Если нет, то любезно предложите способ сделать это с примером.

Код на Coliru

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <ctime>
using namespace std;

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{
    if(!vDestination.empty() && !vSource.empty())
    {
        for(auto i: vSource) {
            vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end());
        }
    }
}

int main() {
    vector<int> v1={1,2,3};
    vector<int> v2={4,5,6};
    vector<int> v3={1,2,3,4,5,6,7,8,9};
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    remove_elements(v3,v1);
    remove_elements(v3,v2);
    std::chrono::steady_clock::time_point end= std::chrono::steady_clock::now();
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() <<std::endl;
    for(auto i:v3)
        cout << i << endl;
    return 0;
}

Выход

Time difference = 1472
7
8
9

Ответы

Ответ 1

Правильно ли он проверяет эффективность выполнения?

Похоже, это не лучший способ сделать это. Я вижу следующие недостатки в вашем методе:

  • Значения сортируются. Прогнозирование ветвей может вызывать смешные эффекты при тестировании отсортированных или несортированных значений с тем же алгоритмом. Возможное исправление: проверка как отсортированных, так и несортированных и сравнение результатов.
  • Значения жестко закодированы. Кэш CPU - это сложная вещь, и он может вводить тонкие различия между тестами на жестко закодированные значения и реальные. В реальном мире вы вряд ли будете выполнять эти операции с жестко закодированными значениями, поэтому вы можете либо прочитать их из файла, либо создать случайные.
  • Слишком мало значений. Время выполнения вашего кода намного меньше, чем точность таймера.
  • Вы запускаете код только один раз. Если вы исправите все другие проблемы и дважды запустите код, второй запуск может быть намного быстрее, чем первый из-за разминки кеша: последующие прогоны имеют меньше пропустил кеш, чем первый.
  • Вы запускаете код один раз на данные фиксированного размера. Было бы лучше запустить в противном случае правильные тесты, по крайней мере, четыре раза, чтобы покрыть декартово произведение следующих параметров:
    • отсортированные или несортированные данные
    • v3 соответствует размеру кэша ЦП и v3 превышает кеш ЦП. Также рассмотрите случаи, когда (v1.length() + v3.length()) * sizeof(int) подходит к кешу или нет, (v1.length() + v2.length() + v3.length()) * sizeof(int) подходит для кеша или нет и т.д. Для всех комбинаций.

Ответ 2

Самые большие проблемы с вашим подходом:

1) Код, который вы тестируете, слишком короткий и предсказуемый. Вам нужно запустить его по крайней мере несколько тысяч раз, чтобы между измерениями было не менее нескольких сотен миллисекунд. И вам нужно сделать набор данных более крупным и менее предсказуемым. В общем, кэши CPU действительно делают точные измерения на основе синтетических входных данных PITA.

2) Компилятор может изменить ваш код. В общем, довольно сложно гарантировать, что код, который вы синхронизируете, будет выполняться между вызовами, чтобы проверить время (и ничего больше, если на то пошло). С одной стороны, вы можете набрать оптимизацию, а с другой - измерить оптимизированный код.

Одно из решений - отключить оптимизацию всей программы и поместить вызовы синхронизации в другой блок компиляции.

Еще одно возможное решение - использовать забор памяти вокруг вашего теста, например.

    std::atomic_thread_fence(std::memory_order_seq_cst);

(требуется #include <atomic> и компилятор с поддержкой С++ 11).

Кроме того, вы можете дополнить свои измерения данными профилировщика, чтобы узнать, насколько эффективны кеши L1/2/3, узкие места в памяти, скорость выхода на пенсию и т.д. К сожалению, лучший инструмент для Intel x86 для этого является коммерческим ( vtune), но на AMD x86 аналогичный инструмент является бесплатным (codeXL).

Ответ 3

Вы можете использовать библиотеку для сравнения, например Celero, чтобы выполнить измерения для вас и справиться с сложными частями измерений производительности, в то время как вы по-прежнему сосредоточены на коде, который вы пытаетесь оптимизировать. Более сложные примеры доступны в коде, который я связал в ответе на ваш предыдущий вопрос (Как эффективно удалять элементы из вектора, заданного другим вектором), но простой пример использования будет выглядеть следующим образом:

BENCHMARK(VectorRemoval, OriginalQuestion, 100, 1000)
{
    std::vector destination(10000);
    std::generate(destination.begin(), destination.end(), std::rand);
    std::sample(destination.begin(), destination.end(), std::back_inserter(source), 
        100, std::mt19937{std::random_device{}()})    

    for (auto i: source)
        destination.erase(std::remove(destination.begin(), destination.end(), i), 
            destination.end());    
}