Постановка задачи
Наша цель — понять, насколько можно доверять оптимизацию своего кода компилятору, и можно ли облегчить (осложнить) его задачу?
Почему все одинаково?
Повторим наши замеры (смотри предыдущую статью), попросив компилятор оптимизировать наш код. Чтобы компилятор не увлекся, в код добавим вывод суммы:
cout << "sum=" << sum << endl; Компилируем вариант с accumulate:
sum = accumulate(vec.begin(), vec.end(), 0);
#include <iostream> #include <sys/time.h> #include <iomanip> #include <vector> #include <algorithm> #include <functional> using namespace std; typedef int A; const int COUNT = 1000 * 1000 * 1000; int main () { vector<A>vec(COUNT); generate(begin(vec), end(vec), std::rand); A sum = 0; struct timespec tm1, tm2; clock_gettime(CLOCK_REALTIME, &tm1); sum = accumulate(vec.begin(), vec.end(), A(0)); clock_gettime(CLOCK_REALTIME, &tm2); cout << "accumulate" << endl; double t1 = 1000.0 * tm1.tv_sec + tm1.tv_nsec / (1000.0 * 1000); double t2 = 1000.0 * tm2.tv_sec + tm2.tv_nsec / (1000.0 * 1000); cout << "t=" << setprecision(5) << t2 -t1 << " ms" << endl; cout << "sum=" << sum << endl; return 0; }; с максимальной оптимизацией:
$ g++ -std=c++11 main.cpp -o test -O3 && ./test $ duration 33.995 ms mseconds Сравним этот результат с результатом for_each:
for_each(vec.begin(), vec.end(), [&sum](int i) { sum += i; });
$ g++ -std=c++11 main.cpp -o test -O3 && ./test $ duration 34.21 ms mseconds Варианты с явным циклом дают схожий результат.
Почему скорость после оптимизации стала одинаковой? Для того, чтобы ответить на этот вопрос, давайте заглянем в STL и посмотрим, что из себя представляет функция for_each:
template<typename _InputIterator, typename _Function> for_each(_InputIterator __first, _InputIterator __last, _Function __f) { for (; __first != __last; ++__first) __f(*__first); return__f; } Как видно for_each это и есть цикл, единственная оптимизация — компилятор делает функцию for_each встроенной:
for (; __first != __last; ++__first) [&sum](int i) { sum += i; }(*__first); Тут компилятору кажется разумным и лямбду сделать встроенной. Итераторы вектора по своей сути — указатели, поэтому в итоге конечный ассемблерный код выглядит приблизительно так:
.L4: addq $1, %rax paddd (%rcx), %xmm0 addq $16, %rcx cmpq %r9, %rax jb .L4 Даже если бы я писал код вручную, у меня не получилось бы лучше. Так как программа у нас небольшая и переменных совсем немного, компилятор поместил их в регистры. Никакого лишнего копирования или вызовов функций — превосходно, даже сложение происходит сразу по двум элементам.
Теперь становиться очевидным, почему на скорость конечного кода не влияют “ручные” оптимизации циклов, и даже ключевое слово register.
Всегда ли скорость одинаковая?
Давайте вместо int суммировать простенький классик размером с sizeof(int):
class A { int v = 0; public: A() {} A(int i); A(const A& a); operator int(); A operator +=(const A& a); A operator +(const A& a); }; А его реализацию поместим в отдельный файл.
A::A(int i) : v(i) {} A::A(const A &a) : v(a.v) {} A::operator int() { return v; } A A::operator +=(const A &a){ v += a.v; return v; } A A::operator +(const A &a) { return a.v + v; }
Теперь вариант с for_each:
for_each(vec.begin(), vec.end(), [&](A i) { sum += i; }); Компилируем и запускаем:
$ g++ -std=c++11 main.cpp a.cpp -o test -O3 && ./test $ duration 372.84 ms mseconds И простой цикл:
for(int i = 0; i < COUNT; ++i) { sum += vec[i]; }; Запускаем:
$ g++ -std=c++11 main.cpp a.cpp -o test -O3 && ./test $ duration 240.57 ms mseconds Неужели циклы все-таки быстрее? На самом деле — нет, просто корректный вариант с for_each теперь должен выглядеть так:
for_each(vec.begin(), vec.end(), [&](A &i) { sum += i; }); Тогда:
$ g++ -std=c++11 main.cpp a.cpp -o test -O3 && ./test $ duration 240.8 ms mseconds Дело в том, что компилятор не имеет право просто убрать копирование аргумента, так как он не знает, какие добрые дела мы творим в написанном нами операторе копирования.
Скорость работы for_each сравнялась со скоростью цикла, а вот вариант с accumulate
sum = accumulate(vec.begin(), vec.end(), A(0)); все-таки отстает:
$ g++ -std=c++11 main.cpp a.cpp -o test -O3 && ./test $ duration 410.52 ms mseconds Почему так? Посмотрим на ассемблерный код варианта с for_each:
.L12: leaq 160(%rsp), %rsi leaq 112(%rsp), %rdi movq %rbx, %rdx call _ZN1ApLERKS_ addq $4, %rbx cmpq %rbp, %rbx jne .L12 И сравним его с кодом варианта с accumulate:
.L7: leaq 144(%rsp), %rsi leaq 192(%rsp), %rdi movq %rbx, %rdx call _ZN1AplERKS_ movl 192(%rsp), %eax addq $4, %rbx cmpq %rbx, %rbp movl %eax, 144(%rsp) jne .L7 Все из-за того, что компилятор из оператора "+=" генерирует более легкий код, чем из присваивания суммы:
template<typename _InputIterator, typename _Tp> accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) { for (; __first != __last; ++__first) __init = __init + *__first; return __init; } Отсюда и лишние операции перемещения.
Кстати, вам не кажется странным тот факт, что специализированная функция для подсчета суммы дает худший результат, чем цикл или использование for_each?
Вывод
Компилятор не на столько умен, как человек. И достаточно легкого изменения кода, чтобы компилятор запутался и выдал нам не совсем то, что мы бы хотели или ожидали.
Если мы хотим получить гарантированный результат — нужно все делать “самому”, либо каждый раз проверять, что там компилятор улучшил, а что — ухудшил. Стандартом не гарантируется, что for_each будет оптимизирована так же хорошо, как и цикл, а это важно, если вы пишете переносимый код.
Если же скорость работы не критична — всегда выбирайте STL. Код получается более читабельным, и в среднем код на STL работает быстрее.
ссылка на оригинал статьи http://habrahabr.ru/post/260193/
Добавить комментарий