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

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 17

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

      Еще, в качестве просто замечания, имеет смысл из operator+= возвращать ссылку на this, а не копию объекта.
        0
        Ассемблерный код выглядит так как будто компилировали с -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, а в вашей реализации +=?
          0
          accumulate не использует +=, вот в чем штука. Оператор поправлю, спасибо.

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

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

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

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

            тогда я не понимаю, к чему вы написали это:
            Стандартом не гарантируется, что for_each будет оптимизирована так же хорошо, как и цикл, а это важно, если вы пишете переносимый код.
              +1
              Я имел в виду, что ни конкретная реализация, ни скорость ее работы не гарантируется.
          0
          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
          
            0
            const int COUNT = 1000 * 1000 * 100;
            0
            Даже если бы я писал код вручную, у меня не получилось бы лучше.

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

            Бедные XMM регистры были унижены до 64-битных.
              +2
              Если кого-то огорчает, что вынос функции в отдельный файл замедляет тест в 10 раз, то специально для таких случаев есть link time optimization (-flto).
                +1
                Вот это мне и нравится в gcc! Чего-то не хватает? Добавь ключик! Кстати, остались еще ключики -fparallelize-tree, -fopenmp и -fopenacc (два последних требуют прагму поставить).
                +2
                Ну опять он унижает компиляторы, а на деле позорится сам. Включи link-time code optimization, или как оно в GCC называется, и будут у тебя все тесты абсолюно одинаково быстро выполняться.
                Единственное, что мой компилятор (VC++ 2013) не переварил — так это не векторизовал цикл при сложении классов. Но при отключенной векторизации получается одно и то же.
                  –1
                  Вы пытаетесь «закостылить» конкретную проблему, не уловив сути. Отдельным модулем я имитировал неизвестное «компилятору» поведение. Это могла бы быть библиотека, например. И класс А может быть мало-ли каким.
                    +2
                    В таких случаях проблему нельзя будет решить никакими ручными микрооптимизациями. Основная критика ваших статей в том, что подобные оптимизации в мире современных компиляторов имеют лишь теоретический и педагогический интерес — для обучения устройству компиляторов, например. Для практики программирования в описанных Вами оптимизациях смысла нет, т.к. -O3 -flto сводят все их на нет. Интересны были бы такие оптимизации, которые компиляторы не умеют производить, а особенно, если не сумеют и через 10 лет, но их Вы не описываете…
                      +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.
                        +4
                        Раз уж заговорили про костыли, позвольте мне рассказать небольшую историю про эти самые костыли.

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

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

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

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

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

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

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

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

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

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

                    Only users with full accounts can post comments. Log in, please.