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

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

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

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

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

cout << "sum=" << sum << endl;

Компилируем вариант с accumulate:

sum = accumulate(vec.begin(), vec.end(), 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 за подсказку — оператор += должен возвращать ссылку, но в данном случае это не важно, мы не используем результат оператора.

А его реализацию поместим в отдельный файл.


Теперь вариант с 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 работает быстрее.