Pull to refresh

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

C++ *

Постановка задачи


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

Почему все одинаково?


Повторим наши замеры (смотри предыдущую статью), попросив компилятор оптимизировать наш код. Чтобы компилятор не увлекся, в код добавим вывод суммы:

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 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 работает быстрее.
Tags:
Hubs:
Total votes 21: ↑12 and ↓9 +3
Views 9.5K
Comments 17
Comments Comments 17