Я пытаюсь сравнить сравнительно небольшие части набора более крупных алгоритмов, которые реализованы в C ++. Проще говоря, можно сказать, что каждый алгоритм реализован с помощью двух функций (назовем их foo() и bar()), которые можно вызывать повторно и в произвольном порядке, и эти функции могут вносить изменения в некоторые структуры данных, внутренние для алгоритма. Помимо прочего, я хочу сравнить производительность алгоритмов, отдельно измеряя общее время, потраченное на foo() и bar() соответственно.
Теперь у меня есть два алгоритма: алгоритм A выполняет некоторую работу в foo(), но очень мало в bar(), тогда как алгоритм B абсолютно ничего не делает в foo() (foo() на самом деле здесь пустая функция), но много работы в bar(). Неожиданная вещь, которую я здесь наблюдал, заключается в том, что общее время, которое Алгоритм B тратит в foo(), во многих случаях превышает общее время, которое Алгоритм A тратит в foo(). После некоторой отладки я обнаружил, что для алгоритма B первый вызов foo () после вызова bar () занимает много времени, тогда как последующие вызовы foo () имеют тенденцию быть быстрее.
В попытке определить этот эффект я предложил следующее упрощение алгоритма B, состоящее из пустой функции (соответствует foo()) и двух функций, в которых я пытался смоделировать работу (соответствует bar(), «реальный» bar() в основном также просто выделяет пространство и перебирает структуры данных):
b.h:
#ifndef B_H
#define B_H
void foo_emptyFunction(unsigned long long u); // foo()
void bar_expensiveFunction1(); // bar() - version 1
void bar_expensiveFunction2(); // bar() - version 2
#endif
b.cpp
#include "b.h"
#include <iostream>
#include <vector>
#include <math.h>
void foo_emptyFunction(unsigned long long )
{
// nothing
}
void bar_expensiveFunction1() {
std::vector<unsigned long> vec;
for (auto i = 0UL; i < 1000000UL; i++) {
vec.push_back(i);
}
std::cout << "Created and filled a vector with " << vec.size() << " elements." << std::endl;
}
void bar_expensiveFunction2() {
std::vector<unsigned long> vec;
for (auto i = 1UL; i <= 1000000UL; i++) {
vec.push_back(i);
}
auto sum = 0ULL;
auto sumSqrts = 0.0;
for (auto i : vec) {
sum += i;
sumSqrts += sqrt(i);
}
std::cout << "Sum of elements from " << vec.front()
<< " to " << vec.back() << " is " << sum
<< ", the sum of their square roots is " << sumSqrts << "." << std::endl;
}
Затем я пытаюсь измерить время, необходимое для вызова пустой функции несколько раз после «дорогой»:
main.cpp:
#include "b.h"
#include <chrono>
#include <thread>
#include <iostream>
#include <math.h>
typedef std::chrono::high_resolution_clock sclock;
typedef unsigned long long time_interval;
typedef std::chrono::duration<time_interval, std::chrono::nanoseconds::period> time_as;
void timeIt() {
auto start = sclock::now();
auto end = start;
for (auto i = 0U; i < 10U; i++) {
start = sclock::now();
asm volatile("" ::: "memory");
foo_emptyFunction(1000ULL);
asm volatile("" ::: "memory");
end = sclock::now();
std::cout << "Call #" << i << " to empty function took " << std::chrono::duration_cast<time_as>(end - start).count() << "ns." << std::endl;
}
}
int main()
{
timeIt();
bar_expensiveFunction1();
timeIt();
std::this_thread::sleep_for(std::chrono::milliseconds(100));
std::cout << "Slept for 100ms." << std::endl;
timeIt();
bar_expensiveFunction2();
timeIt();
bar_expensiveFunction1();
timeIt();
return 0;
}
Если я скомпилирую (g++ -o test main.cpp b.cpp или также g++ -O3 -o test main.cpp b.cpp) и выполню код, я получу вывод, подобный следующему:
. / Тест
Call #0 to empty function took 79ns.
Call #1 to empty function took 57ns.
Call #2 to empty function took 55ns.
Call #3 to empty function took 31ns.
Call #4 to empty function took 35ns.
Call #5 to empty function took 26ns.
Call #6 to empty function took 26ns.
Call #7 to empty function took 36ns.
Call #8 to empty function took 24ns.
Call #9 to empty function took 26ns.
Created and filled a vector with 1000000 elements.
Call #0 to empty function took 84ns.
Call #1 to empty function took 27ns.
Call #2 to empty function took 28ns.
Call #3 to empty function took 27ns.
Call #4 to empty function took 29ns.
Call #5 to empty function took 27ns.
Call #6 to empty function took 29ns.
Call #7 to empty function took 33ns.
Call #8 to empty function took 28ns.
Call #9 to empty function took 23ns.
Slept for 100ms.
Call #0 to empty function took 238ns.
Call #1 to empty function took 106ns.
Call #2 to empty function took 102ns.
Call #3 to empty function took 118ns.
Call #4 to empty function took 199ns.
Call #5 to empty function took 92ns.
Call #6 to empty function took 216ns.
Call #7 to empty function took 118ns.
Call #8 to empty function took 113ns.
Call #9 to empty function took 107ns.
Sum of elements from 1 to 1000000 is 500000500000, the sum of their square roots is 6.66667e+08.
Call #0 to empty function took 126ns.
Call #1 to empty function took 35ns.
Call #2 to empty function took 31ns.
Call #3 to empty function took 30ns.
Call #4 to empty function took 38ns.
Call #5 to empty function took 54ns.
Call #6 to empty function took 29ns.
Call #7 to empty function took 35ns.
Call #8 to empty function took 30ns.
Call #9 to empty function took 29ns.
Created and filled a vector with 1000000 elements.
Call #0 to empty function took 112ns.
Call #1 to empty function took 23ns.
Call #2 to empty function took 23ns.
Call #3 to empty function took 23ns.
Call #4 to empty function took 23ns.
Call #5 to empty function took 22ns.
Call #6 to empty function took 23ns.
Call #7 to empty function took 23ns.
Call #8 to empty function took 24ns.
Call #9 to empty function took 23ns.
Я подозреваю, что различия во времени выполнения, в частности пика при первом вызове, могут быть вызваны каким-то эффектом кэширования, но мне бы очень хотелось понять, что здесь происходит.
Редактировать: Эффект, который я наблюдаю здесь, очень похож на тот, что в реальном коде. При первом вызове почти всегда имеется огромный пик, и он остается постоянным с третьего вызова. Эффект даже более выражен в реальном коде, я подозреваю, потому что B::bar() делает больше работы в реальности (он пересекает график, а не просто список целых чисел). К сожалению, настоящий код является частью довольно большого проекта, поэтому я не могу опубликовать его здесь. Код, который я выложил выше, является довольно серьезным упрощением оригинала, но, похоже, демонстрирует тот же эффект. В действительности, foo() и bar() являются виртуальными (я знаю, что это идет со штрафом времени) и находятся в другом модуле компиляции, поэтому компилятор не может оптимизировать вызов функции. Плюс я также проверил ассемблер реальной программы. Я также осознаю тот факт, что я неизбежно также измеряю время для вызова now () - но я использую тот же код для сравнения для алгоритма A (который по крайней мере что-то делает в своей реализации foo()) и общее время, измеренное для A::foo() меньше ...
Уровень оптимизации, кажется, не имеет (большого) влияния на этот эффект, и я получаю то же самое поведение с clang.
Редактировать 2: Я также запустил тесты алгоритмов на выделенном компьютере (Linux, только системные процессы, регулятор частоты процессора настроен на производительность).
Кроме того, я знаю, что обычно, когда вы выполняете этот тип микробанчмаркинга, вы делаете такие вещи, как разогрев кеша и повторение части кода, которую вы хотите тестировать много раз. К сожалению, каждый вызов foo() или bar() потенциально изменяет внутренние структуры данных, поэтому я не могу просто повторить их. Буду признателен за любые предложения по улучшению.
Спасибо!