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

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

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

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

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

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

#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());    
}