12.06.2015 19:20
ferus 17 7173 Источник

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


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

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


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

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 работает быстрее.

Комментарии (17)


  1. 0xd34df00d
    12.06.2015 22:47
    #8458833

    std::accumulate использует в теле цикла выражение вида acc = acc + *next; с понятными для производительности последствиями.

    Еще, в качестве просто замечания, имеет смысл из operator+= возвращать ссылку на this, а не копию объекта.


  1. kmu1990
    12.06.2015 23:34
    #8458891

    Ассемблерный код выглядит так как будто компилировали с -Os, а не с -O3. Например, вот код который сгенерировал g++ у меня (g++ (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2) с -Os:

            movq    8(%rdi), %rdx
        movq    (%rdi), %rax
        xorl    %esi, %esi
.L2:
        cmpq    %rdx, %rax
        je      .L6
        addl    (%rax), %esi
        addq    $4, %rax
        jmp     .L2


    причем он одинаковый и для for_each и для accumulate (у меня += возвращает ссылку). Код же с -O3 я приводить не буду потому что в нем развернут цикл, используются векторные инструкции и прочее, но и там версии для accumulate и for_each одинаковые.

    Стандартом не гарантируется, что for_each будет оптимизирована так же хорошо, как и цикл, а это важно, если вы пишете переносимый код.

    а гарантии по оптимизации циклов стандарт дает что ли?

    Кстати, вам не кажется странным тот факт, что специализированная функция для подсчета суммы дает худший результат, чем цикл или использование for_each?

    может дело не в accumulate, а в вашей реализации +=?


    1. ferus Автор
      12.06.2015 23:53
      #8458933

      accumulate не использует +=, вот в чем штука. Оператор поправлю, спасибо.

      а гарантии по оптимизации циклов стандарт дает что ли?

      их никто не дает


      1. kmu1990
        13.06.2015 00:01
        #8458953

        accumulate не использует +=, вот в чем штука. Оператор поправлю, спасибо

        принято, я неправ.

        их никто не дает

        тогда я не понимаю, к чему вы написали это:
        Стандартом не гарантируется, что for_each будет оптимизирована так же хорошо, как и цикл, а это важно, если вы пишете переносимый код.


        1. ferus Автор
          13.06.2015 00:07
          #8458967
          +1

          Я имел в виду, что ни конкретная реализация, ни скорость ее работы не гарантируется.


  1. DaylightIsBurning
    13.06.2015 00:41
    #8458997

    g++ -std=c++11 main.cpp -o test -O3 && ./test
    duration 33.995 ms mseconds

    снова что-то не так. Выполнил приведенный вами код:
    $ g++ -std=c++11 acc.cpp -o test -O3 && ./test 
accumulate
t=291.32 ms
sum=-1471389927


    1. ferus Автор
      13.06.2015 09:27
      #8459151

      const int COUNT = 1000 * 1000 * 100;


  1. halyavin
    13.06.2015 09:33
    #8459155

    Даже если бы я писал код вручную, у меня не получилось бы лучше.

    Очевидно, что можно избавиться от счетчика eax. Для выхода из цикла мы можем вместо него проверять указатель ecx.
    даже сложение происходит сразу по двум элементам.

    Бедные XMM регистры были унижены до 64-битных.


  1. arseny30
    13.06.2015 10:49
    #8459187
    +2

    Если кого-то огорчает, что вынос функции в отдельный файл замедляет тест в 10 раз, то специально для таких случаев есть link time optimization (-flto).


    1. ilmirus
      13.06.2015 12:29
      #8459301
      +1

      Вот это мне и нравится в gcc! Чего-то не хватает? Добавь ключик! Кстати, остались еще ключики -fparallelize-tree, -fopenmp и -fopenacc (два последних требуют прагму поставить).


  1. kosmos89
    13.06.2015 15:10
    #8459459
    +2

    Ну опять он унижает компиляторы, а на деле позорится сам. Включи link-time code optimization, или как оно в GCC называется, и будут у тебя все тесты абсолюно одинаково быстро выполняться.
    Единственное, что мой компилятор (VC++ 2013) не переварил — так это не векторизовал цикл при сложении классов. Но при отключенной векторизации получается одно и то же.


    1. ferus Автор
      13.06.2015 17:53
      #8459565
      -1

      Вы пытаетесь «закостылить» конкретную проблему, не уловив сути. Отдельным модулем я имитировал неизвестное «компилятору» поведение. Это могла бы быть библиотека, например. И класс А может быть мало-ли каким.


      1. DaylightIsBurning
        13.06.2015 18:41
        #8459597
        +2

        В таких случаях проблему нельзя будет решить никакими ручными микрооптимизациями. Основная критика ваших статей в том, что подобные оптимизации в мире современных компиляторов имеют лишь теоретический и педагогический интерес — для обучения устройству компиляторов, например. Для практики программирования в описанных Вами оптимизациях смысла нет, т.к. -O3 -flto сводят все их на нет. Интересны были бы такие оптимизации, которые компиляторы не умеют производить, а особенно, если не сумеют и через 10 лет, но их Вы не описываете…


      1. kosmos89
        13.06.2015 18:50
        #8459601
        +2

        >закостылить
        тут не понял. Что значит закостылить, когда это и полагается использовать?
        >не уловив сути
        Ну так опишите явно свою задумку. Не все же такие умные. Вот и получаете обвинения.
        >Отдельным модулем я имитировал неизвестное «компилятору» поведение
        Оно может быть неизвестным только в двух случаях — кодогенерация на лету и внешний вызов. Заниматься микрооптимизациями на границе исполняемого модуля — довольно бестолковая затея. Ну а кодогенерация — особый случай, ее мы не рассматриваем.

        >Кстати, вам не кажется странным тот факт, что специализированная функция для подсчета суммы дает худший результат, чем цикл или использование for_each?
        В Стандарте сказано, что accumulate:
        >Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first,last) in order.
        Так что все вопросы к Стандарту. Его писатели полагаются на то, что компилятору все известно и a = a + b даст тот же машинный код, что и a += b.


      1. ilmirus
        14.06.2015 13:14
        #8460157
        +4

        Раз уж заговорили про костыли, позвольте мне рассказать небольшую историю про эти самые костыли.

        Давайте вернемся в те времена, когда компьютеры были большими, а памяти было мало. Когда еще не было формата ELF, а (единственный) компилятор Си не был оптимизирующим. Когда еще не было стандарта Си, а тоненькая книжка за авторством Ритчи и Кернигана еще даже не была написана.

        Представьте, что вам надо скомпилировать ядро Юникса. Практически в каждом исходном файле описаны используемые функции и количество их параметров, возможно, даже с именами (без типов, ибо, как мы помним, АНСИ Си еще не существует) и глобальные переменные, которые, в свою очередь экспортятся из других исходных файлов. Так как памяти у нас мало, мы создаем т. н. объектные файлы, которые потом объединяются в один большой исполняемый файл редактором связей, линковщиком. Этот линковщик — хитроумный костыль, придуманный для того, чтобы не тратить кучу памяти для хранения внутренних данных компилятора, что произошло бы, если бы мы компилировали всю программу целиком и сразу. Более того, это положение сохранилось до сих пор, костыль прижился и даже схема компиляции по файлам была стандартизирована и сегодня каждый компилятор, даже в том случае, если ему хватает памяти на компиляцию всей программы сразу, компилирует отдельные Compilation Unit'ы.

        К слову, чтобы не писать каждый раз обьявления используемых функций, примерно в то же время придумали заголовочные файлы и их включение в Compilation Unit. Этот костыль тоже дожил до наших дней. Но весь этот абзац был только к слову — речь о редакторе связей нано же.

        Так вот, Linking Time Optimization — это костыль, который позволяет оптизировать всю программу целиком, а не по отдельным Compilation Unit'ам. Другими словами — это костыль, скрывающий другой костыль. Кстати говоря, последние версии GCC по умолчанию собираются с включеным флагом -flto, который, как уже пояснили выше, включает этот костыль.

        Однако, обнаружилась проблемка с этим ключом: дело в том, что GNU make умеет запускать несколько процессов GCC для компиляции нескольких исходников одновременно. Это назвали паралельной сборкой. И эта возможность напрямую следует из архитектуры make и не является костылем. Линковщик же однопоточный. В результате, время компиляции увеличилось, так как парсинг и кодогенерация — это дешевые операции по сравнению с оптимизацией (тем более, всей программы).

        Как же GCC собираются решить эту проблему? Костылем! Дело в том, что можно линковать два объектника и на выходе получить еще один объектник. И эти проженные инженеры собираются использовать возможности того же make для параллельной линковки.

        А теперь пару слов о том, как же выглядит процесс компиляции программы с использованием LTO. Компилятор генерирует промежуточное преставление и вместо того, чтобы оптимизировать, сразу дампит его в отдельную секцию ELF файла. А оптимизатор запускается линковщиком.

        И даже на этом этапе обнаружились проблемы — получаемые после компилятора объектные файлы оказались просто огромными из-за, по сути, не нужного бинарного кода, который все равно будет выкинут и заменен оптимизированным. А просто так выкинуть этот код нельзя — на него завязаны утилиты ar и nm. Что же делать? Хачить! И после этих костылей, вставленых в эти две утилиты, стало возможным уменьшить размер объектников, без потери возможности использовать статические библиотеки и смотреть список символов, определенных а объектнике.

        Сколько костылей из-за линкера насчитали? Вот-вот, а выкинуть его нельзя, ибо эта инфраструктура копилась годами, и потребуются годы, чтобы ее заменить. А так — работает же, хоть и раз в пару лет надо еще одну подпорку поставить.

        В сторону: а некоторые считают Autotools одним из самых больших нагромождений костылей на костылях.


        1. DaylightIsBurning
          14.06.2015 15:05
          #8460237

          То что вы описываете — это не костыли. Это просто устаревшие реализации. Дело в том, что когда они создавались — они были призваны реализовать расширенную функциональность (уменьшить потребление ресурсов во время сборки) и для реализации этой функциональности архитектура решения была адекватная (не костыльная). Сейчас эта функциональность уже утратила свою актуальность, отчасти, и её можно было бы выкинуть, упростив архитектуру сборки, но пока ещё потребность не так сильно назрела.


          1. ilmirus
            14.06.2015 15:28
            #8460263

            Представте, что весь комментарий написан красным курсивом ;)