Веселі старти 2: for_each vs accumulate

Постановка завдання

Наша мета — зрозуміти, наскільки можна довіряти оптимізацію свого коду компілятора, і чи можна полегшити (ускладнити) його завдання?

Чому всі однаково?

Повторимо наші виміри (дивись попередню статті), попросивши компілятор оптимізувати наш код. Щоб компілятор не захопився, код додамо висновок суми:
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 * 100;

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

UPDATE. Спасибі 0xd34df00d, kmu1990 за підказку — оператор += повинен повертати посилання, але в даному випадку це не важливо, ми не використовуємо результат оператора.

А його реалізацію помістимо в окремий файл.
a.cpp
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 *this;
}
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 працює швидше.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.