company_banner

Новые оптимизации для х86 в ожидаемом GCC 5.0

    Итак, фактическую разработку новых оптимизаций в GCC 5.0 можно считать законченной. Продукт GCC 5.0 находится сейчас в фазе stage3, то есть идет доработка уже внедренных оптимизаций. В данной и последующих статьях я расскажу об оптимизациях, реализованных в GCC 5.0 для х86 и об их влиянии на производительность программ для процессоров линейки Intel Atom и Intel Core. Сегодня речь пойдет о векторизации групповых обращений в память. В последующих статьях я расскажу об ускорениях в 32-битном PIC режиме и дополнительном усилении векторизации.

    Как вы уже, наверное, догадались, в GCC 5.0 существенно улучшена векторизация групповых обращений в память. Под групповым обращением в память понимается итерируемая последовательность обращений. Например:

    x = a[i], y = a[i + 1], z = a[i + 2]

    итерируемое по i — это группа загрузок из памяти длиной 3. Длина группы обращений в память — это расстояние между самым младшим и старшим адресами в группе. Для примера выше — это (i + 2) – (i) + 1 = 3
    Количество обращений в память в группе не превосходит ее длину. Например:

    x = a[i], z = a[i + 2]

    итерируемое по i — это группа длиной 3, несмотря на то, что обращений в память всего 2.

    GCC 4.9 векторизует группы, где длина — это степень 2 (2, 4, 8 …).

    GCC 5.0 векторизует группы, где длина равна 3 или степени 2 (2, 4, 8 …). Другие длины не векторизуются, так как встречаются в реальных приложениях очень редко.

    Чаще всего векторизация группы обращений в память применяется при работе с массивами структур.

    1. Конвертация изображений, скажем, в структуре RGB. Пример.
    2. Работа с N-мерными координатами (скажем, чтобы нормализовать трехмерные точки). Пример.
    3. Умножение векторов на константную матрицу:

    a[i][0] = 7 * b[i][0] - 3 * b[i][1];
    a[i][1] = 2 * b[i][0] + b[i][1];
    

    В целом в GCC 5.0 (по сравнению с 4.9)

    • Появилась векторизация группы обращений в память длиной 3
    • Существенно улучшилась векторизации группы загрузок из памяти для любой длины
    • Стали использоваться техники векторизации групп обращений в память оптимальные для конкретного x86 процессора.

    Далее приведены таблицы, позволяющие оценить увеличение производительности при использовании GCC 5.0 на байтовых структурах (наибольшее количество элементов в векторе) по сравнению с GCC 4.9. Для оценки используется следующий цикл:

      int i, j, k;  
      byte *in = a, *out = b; 
      for (i = 0; i < 1024; i++) 
        { 
          for (k = 0; k < STGSIZE; k++) 
            { 
              byte s = 0; 
              for (j = 0; j < LDGSIZE; j++) 
                s += in[j] * c[j][k]; 
              out[k] = s; 
            } 
          in += LDGSIZE; 
          out += STGSIZE; 
        } 
    

    Где:
    • c — это константная матрица:

    
    const byte c[8][8] = {1, -1, 1, -1, 1, -1, 1, -1, 
                          1, 1, -1, -1, 1, 1, -1, -1, 
                          1, 1, 1, 1, -1, -1, -1, -1, 
                          -1, 1, -1, 1, -1, 1, -1, 1, 
                          -1, -1, 1, 1, -1, -1, 1, 1, 
                          -1, -1, -1, -1, 1, 1, 1, 1, 
                          -1, -1, -1, 1, 1, 1, -1, 1, 
                          1, -1, 1, 1, 1, -1, -1, -1}; 
    

    Такая матрица используется чтобы минимизировать вычисления внутри цикла до сравнительно быстрых сложений и вычитаний.
    • in и out — указатели на глобальные массивы «a[1024 * LDGSIZE]» и «b[1024 * STGSIZE]»
    • byte — это unsigned char
    • LDGSIZE и STGSIZE – макросы, определяющие длину группы загрузок из памяти и сохранений в память соответственно


    Опции компиляции "-Ofast" плюс "-march=slm" для Silvermont, "-march=core-avx2" для Haswell и все комбинации -DLDGSIZE={1,2,3,4,8} -DSTGSIZE={1,2,3,4,8}

    Прирост производительности GCC 5.0 по сравнению с 4.9 (во сколько раз ускорилось, больше — лучше).

    Silvermont: Intel Atom(TM) CPU C2750 @ 2.41GHz

    Прирост до 6.5 раз!

    image

    Как видно из таблицы, результаты для групп сохранений в память длиной 3 не очень хорошие. Это происходит потому, что для такого преобразования требуется 8 инструкций «pshufb», длительность исполнения которой на Silvermont около 5 тактов. Несмотря на это, векторизация других команд в цикле может дать больший прирост. Это видно на примере группы загрузок из памяти длиной 2, 3, 4 и 8.

    Пример GCC ассемблера для группы загрузок из памяти длиной 2:
    GCC 4.9 GCC 5.0
    movdqa .LC0(%rip), %xmm7
    movdqa .LC1(%rip), %xmm6
    movdqa .LC2(%rip), %xmm5
    movdqa .LC3(%rip), %xmm4
    movdqu a(%rax,%rax), %xmm1
    movdqu a+16(%rax,%rax), %xmm0
    movdqa %xmm1, %xmm3
    pshufb %xmm7, %xmm3
    movdqa %xmm0, %xmm2
    pshufb %xmm5, %xmm1
    pshufb %xmm6, %xmm2
    pshufb %xmm4, %xmm0
    por %xmm2, %xmm3
    por %xmm0, %xmm2
    movdqa .LC0(%rip), %xmm3
    movdqu a(%rax,%rax), %xmm0
    movdqu a+16(%rax,%rax), %xmm1
    movdqa %xmm3, %xmm4
    pand %xmm0, %xmm3
    psrlw $8, %xmm0
    pand %xmm1, %xmm4
    psrlw $8, %xmm1
    packuswb %xmm4, %xmm3
    packuswb %xmm1, %xmm0
    Здесь, как и в приведенном ниже примере для Haswell, стоит отметить, что большинство констант ".LC" будут инвариантами в цикле, однако только при наличии свободных регистров. В противном случае их придется ставить непосредственно в phufb: «pshufb .LC0, %xmm3». Такой pshufb будет больше на размер адреса и потенциально дольше исполнятся.

    Haswell: Intel Core(TM) i7-4770K CPU @ 3.50GHz

    Прирост до 3 раз!

    image

    В данном случае результаты для групп сохранений в память длиной 3 намного лучше, так как на Haswell инструкция «pshufb» исполняется за 1 такт. Более того, наибольший прирост здесь именно для внедренной векторизации групп обращений в память длиной 3.

    Пример GCC ассемблера для группы загрузок из памяти длиной 2:
    GCC 4.9 GCC 5.0
    vmovdqa .LC0(%rip), %ymm7
    vmovdqa .LC1(%rip), %ymm6
    vmovdqa .LC2(%rip), %ymm5
    vmovdqa .LC3(%rip), %ymm4
    vmovdqu a(%rax,%rax), %ymm0
    vmovdqu a+32(%rax,%rax), %ymm2
    vpshufb %ymm7, %ymm0, %ymm1
    vpshufb %ymm5, %ymm0, %ymm0
    vpshufb %ymm6, %ymm2, %ymm3
    vpshufb %ymm4, %ymm2, %ymm2
    vpor %ymm3, %ymm1, %ymm1
    vpor %ymm2, %ymm0, %ymm0
    vpermq $216, %ymm1, %ymm1
    vpermq $216, %ymm0, %ymm0
    vmovdqa .LC0(%rip), %ymm3
    vmovdqu a(%rax,%rax), %ymm0
    vmovdqu a+32(%rax,%rax), %ymm2
    vpand %ymm0, %ymm3, %ymm1
    vpsrlw $8, %ymm0, %ymm0
    vpand %ymm2, %ymm3, %ymm4
    vpsrlw $8, %ymm2, %ymm2
    vpackuswb %ymm4, %ymm1, %ymm1
    vpermq $216, %ymm1, %ymm1
    vpackuswb %ymm2, %ymm0, %ymm0
    vpermq $216, %ymm0, %ymm0
    Из всего вышесказанного следует вывод: используя GCC 5.0, можно существенно ускорить производительность приложений, подобных описанным выше. Начинать пробовать можно уже сейчас! Большинство правок планируется портировать в Android NDK.

    Компиляторы используемые в замерах:

    Скачать пример, на котором производились замеры, можно из оригинального текста статьи на английском.
    Intel
    Company

    Comments 33

      +4
      А почему в статье Intel для ассемблера используется синтаксис AT&T? :)
        +4
        Наверное, потому что gcc по умолчанию использует в асм листингах синтаксис AT&T
          +3
          Не совсем так. Правильнее сказать, что компилятор GNU транслирует С/С++ код в код asm для GNU AS (as из пакета GNU binutils), который (как, собственно, и все UNIX-ассемблеры) по историческим причинам и устоявшейся традиции используют AT&T синтаксис.
            –2
            gcc по умолчанию использует в асм листингах синтаксис AT&T

            Не по умолчанию же, а всегда. Инструкции текстом в исходном коде записаны.
              0
              Нет, можно выбирать между AT&T и Intel. Ключевое слово ".intel_syntax". Так же, можно попросить генерировать ассемблерный выхлоп в нужном варианте. Но лично мне AT&T нравится больше.
                +3
                Подтверждаю. Достаточно подать GCC "-masm=intel". В целом дело вкуса. Когда работаешь с «X86 Software Developers Manual» проще понимать Intel asm. Для остальной работы мне тоже больше по вкусу AT&T.
                  0
                  Согласен про мануал. Иногда обратный порядок параметров рвет мозг и ты откровенно не понимаешь почему eax нельзя записать в константу 1 :)
                    +1
                    Особенно весело становится, когда инструкции имеют три операнда, а сама операция некоммутативна, и приходится мучительно пытаться удержать в голове, каков их порядок: src1, src2, dst или dst, src1, src2; а может dst, src2, src1?

                    Ах, да. В мнемониках команд в нотации Intel есть один ньюанс — для некоторых векторных команд порядок операндов соответствует AT&T, а для некоторых нет.
                    0
                    -masm=intel

                    Клёво. Спасибо, не знал.
                      0
                      Можно я ещё задам вопрос не совсем по теме поста, но о gcc (задавал уже здесь: toster.ru/q/139313 ): какими сторонними источниками информации пользуются люди, чтобы научиться менять backend gcc? gccint и код самого gcc не в счёт.
                        0
                        А кроме сорцов и GCC Internals нет более подробных источников информации. Только если отдельные статьи и презентации, поясняющие некоторые моменты.

                        Новые инструкции относительно просто добавить в machine description по аналогии с другими, а вот для автогенерации уже придётся хорошо изучить сорцы.
                          0
                          нет более подробных источников информации

                          Да, у меня сложилось подобное впечатление. Мне эта ситуация кажется просто невероятной: gcc — это ж центральный инструмент GNU, визитная карточка проекта, практически.
                            +1
                            Ну есть еще такой неявный источник как комментарии maintainer-ов при submit-е патча. По сути лишь они детально разбираются во всех уголках GCC. Почти всегда они открыты для помощи.
                              0
                              А что именно вам кажется неверноятным, собственно?

                              gccint довольно подробно описывает части из которых состоит GCC, а как всё устроено внутри — написано в исходниках.

                              То же самое — с ядром Linux'а и прочими другими проектами. Разработчикам же не нужно сертификацию по ISO 9001 получать и за документацию им отдельно никто не платит, так откуда она возьмётся?

                              Её, в общем, вполне достаточно, для того, чтобы разобраться в проекте если вы понимаете C так же хорошо, как английский.
                                0
                                Вот я как знал, что речь зайдёт о линуксе. Смотрите, про внутреннее устройство линукса есть гора книжек, я вот тут собрал список самых на мой взгляд толковых: toster.ru/q/137069#answer_392065
                                Написано в них не только *как* устроено, но часто ещё и *почему* именно так, какие есть альтернативы и что лучше использовать в своём коде в разных ситуациях. И авторы этих книжек в большинстве своём отнюдь не ведущие разработчики ядра.

                                для того, чтобы разобраться в проекте если вы понимаете C так же хорошо, как английский

                                … и у вас много свободного времени, чтобы по коду составить себе большую картину. Чтобы потом не просто выбирать между двумя плохими вариантами найденными в качестве примера, а понимать, чем и когда можно воспользоваться.
                                  –1
                                  Написано в них не только *как* устроено, но часто ещё и *почему* именно так, какие есть альтернативы и что лучше использовать в своём коде в разных ситуациях.
                                  И всё равно всё это — зачастую неправда, так как там описываются заведомо устаревшие подходы.

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

                                  Чтобы потом не просто выбирать между двумя плохими вариантами найденными в качестве примера, а понимать, чем и когда можно воспользоваться.
                                  Вы сами-то пробовали? Всё равно не получится. Сделайте как-нибудь, потом поговорите с maintainer'ами, они вам объяснят как вы налажали и попросят всё переделать. И в Linux'е и в GCC.

                                  Или вы думаете, то все сотни разработчиков Столлман обучал лично, под покровом ночи?
                                    0
                                    И всё равно всё это — зачастую неправда

                                    Весомый аргумент.

                                    там описываются заведомо устаревшие подходы

                                    Вы, мне кажется, не понимаете, что такое «большая картина».

                                    Для GCC тоже есть подобный список.

                                    Ага, только там в основном книжки о фронт-эндах и доки по процессорам. Мой вопрос был о бек-энде. Единственную релевантную книжку, что написал Hans-Peter Nilsson, я видел, но она по сути — рассказ «как я провёл лето» «как я портировал компилятор». Мне бы хотелось увидеть книжку «как портировать компилятор».

                                    Вы сами-то пробовали?

                                    Пробовал, и в линуксе и в gcc, и в других проектах.

                                    Сделайте как-нибудь, потом поговорите с maintainer'ами

                                    Этот подход мне понятен, но он не кажется мне самым эффективным, особенно при начальном погружении в проект.

                                    думаете, то все сотни разработчиков Столлман обучал лично

                                    Думаю, что большинство из них работало в командах, в которых присутствовал локальный gcc эксперт, что позволяло им учиться немного более эффективно.
                                      0
                                      Вы, мне кажется, не понимаете, что такое «большая картина».
                                      Нет, не понимаю. О какой-такой «большой картине» вы собрались говорить применительно к компиляторам? Компилятор — это вам не ядро, где есть десятки разнородных компонент. Его задача на самом высоком уровне «очень проста» — преобразовать один текст в другой. Ну и как же, блин, нам это сделать? Ах, да: взять bison, lex, написать парсер, сконвертировать вот это вот всё в некоторое количество древовидных структур, дальше их маленько покрутить, потом выплюнуть результат обратно в текстовый файл. Всё.

                                      Структуры (GENRIC, GIMPLE, RTL) — описаны, последовательность их пребразований — описана тоже, какую-такую «большую картину» вы хотите увидеть ещё?

                                      Или вы хотите, чтобы вам объяснили как SSA устроен? Ну так это в других книжках описывается (хотя бы даже в Wikipedia можете на список литературы посмотреть). Начинается всё, понятно, с Мучника ну и далее есть куча других книг, статей и прочего.

                                      Мне бы хотелось увидеть книжку «как портировать компилятор».
                                      А смысл? Новые архитектуры не так часто появляются, а процесс портирования меняется всё время. Вы тут много книжек привели для Linux'а — хоть в одной описано подробно как портировать ядро куда-нибудь? Очень частная, довольно редко требуемая задача, да ещё и каждый раз со своей спецификой. Можно написать книгу, где описать как портировать на новую архитектуру какой-нибудь GCC 4.4.4, но смысла в ней будет… не так много.
                                        0
                                        Или вы хотите, чтобы вам объяснили

                                        Если вы хотите объяснить, то вот, например, один из вопросов:
                                        в прологах и эпилогах некоторые инструкции манипулирующие стекпойнтером или фреймпойнтером помечаются следующим образом: RTX_FRAME_RELATED_P (insn) = 1. Зачем? Почему не все? Что будет, если их так не помечать?
                                          +1
                                          Всё, что связано с DWARF'ом поляжет нафиг (а это отладчик и zero-cost exceptions). Кроме того, если их не помечать, то peepholeы могут переставить местами инструкции, которые переставлять нельзя. Про RTX_FRAME_RELATED_P, как и про многое другое, написано в gccint.
                                            0
                                            Хорошо. А о том как работают zero-cost exceptions и как ещё DWARF-информация используется компилятором где можно почитать?

                                            А вот ещё: что такое unspec и unspec_volatile? Да, я могу прочитать чт о них написано в gccint, но яснее от этого не становится.
                                              +1
                                              По исключениям я не спец. Ян Тейлор немного писал по их поводу: тут и тут. В комментариях там ещё есть ссылки.

                                              А что вас по unspec'ам-то неясно? Вы хотите понять чем отличается unspec от unspec_volatile или просто — что такое unspec? unspec — это просто машинно зависимая операция. Любая. Вот не сложение, не вычитание, а нечто-такое-очень-странное.

                                              Хороший пример — это, например, инструкции fnstsw и sahf. UNSPEC_FNSTSW описывает выгрузку флагов 80x87 в AX, UNSPEC_SAHF описывает загрузку из AH в младший байт регистра флагов. Вместе — эта пара инструкций представляет типичную последовательность операций при работе с плавучкой: что-то сравнили/посчитали, перегрузили данные из регистра флагов в AX, а потом и в обычный регистр флагов, сделали переход. Их можно как угодно двигать, можно даже результат выгрузить в память — всё равно всё будет хорошо.

                                              А вот UNSPECV_CMPXCHG так двигать не рекомендуется: что будет если у вас будет цикл, который пытается работать с атомиками, а оптимизатор не зная про семантику cmpxchg вынесет эту операцию из цикла? Ничего хорошего, я вас уверяю.

                                              Или UNSPECV_CLD: он меняет режим работы процессора и если оптимизатор, скажем, решит вынести MOVS из цикла а UNSPECV_CLD оставит в цикле… опять-таки ничего хорошего не будет.

                                              Дальше — тут же возникает хак: так как вызывать cld много раз смысла, в общем-то, не имеет а из-за статуса «volatile» двигать их тоже нельзя, то чтобы избежать лишней работы GCC просто смотрит — нужен ли в функции CLD или нет. Если нужен — вставляет UNSPECV_CLD в пролог (где он вызывается даже в том случае если потом никакие MOVSы не используются). Подобных хаков в GCC довольно много и далеко не все из них описаны, это правда.
                                                0
                                                Большое спасибо.
                0
                Оптимизации эт конечно хорошо.
                Но зачем отдаваться на произвол компилятора если в gcc 5.0 (да и в clang тоже) есть встроеннная поддержка cilk plus? Который как раз для таких вещей и заточен.

                P.S. Кстати, я так и не понял предложение N3409 по добавлению в С++ стандарт cilk'a завернули, или как http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3409.pdf?
                  +2
                  Cilk Plus как и OMP 4.0 сами по себе не могут векторизовать код — нужна поддержа внутри компилятора.
                  Даже при установке «pragma (omp) simd» перед циклом разные компиляторы будут вести себя по разному. Векторизовать код можно оптимально, а можно и не очень. Именно для того чтобы векторизовать оптимально и развиваются техники векторизации. Данная статья описывает улучшения техники векторизации в GCC для x86. Cilk Plus и OMP 4.0 помогут указать где эти улучшения конкретно применять.
                    0
                    Видел демо, кажется Intel'a, там софтверно рендеренные кубики крутились (чёрно-белые).

                    Сначала их рендерили в одном потоке, потом векторизировали, потом векторизировали + по потокам раскидывали. Векторизация дала 4х прирост, векторизация + «потокизирование» 20х.

                    Код показывали в Visual Studio, и помойму какой то плагин там к ней стоял. И вроде как ради демонстрации этого плагина все демо и затевали. :)

                    Не могу найти теперь.

                    Не встречали такого? :)
                  0
                  По поводу принятия в стандарт — дело это долгое. Думаю, что процесс идет, но пока не завершен.
                  0
                  Спасибо за статью. Очень интересно, что там сделали для ускорения PIC в 32-битном коде. Буквально недавно тут поднималось обсуждение этой темы. Жду продолжения с нетерпением!
                    0
                    Кстати, насчет векторных оптимизация и cilk'a.

                    А чего он тут http://goo.gl/t26bbf
                    c[:] = a[:]+b[:];
                    

                    не завекторизировал?
                      0
                      Ошибка. Должны поправить к релизу 5.0.
                        0
                        Конечно не скромный вопрос. Но…
                        А у вас векторизирует? (как я понял у вас есть собранная версия gcc 5.0 под рукой)

                        А то у меня складывается впечетление что синтаксис массивов [:] (аля векторизация) по назначению использует только Intel Compiler…
                          0
                          Есть. Сейчас не векторизует. Есть патч, чтобы векторизовал. Проблема известная и фикс скорее всего будет в 5.0.
                          Так как проблема локально в Cilk Plus части, то скорее всего будет и бекпорт в 4.9.

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