Быстрое удаление пробелов из строк на процессорах ARM — альтернативный анализ

    Оригинал статьи
    Автор: Мартин Кръстев


    Один мой друг обратил мое внимание на интересную статью на habrahabr.ru — русский перевод статьи Дэниела Лемира Быстрое удаление пробелов из строк на процессорах ARM. Эта статья заинтриговала меня по двум причинам: во-первых, кто-то на самом деле потратил время и усилия по поиску оптимального решения общей проблемы на не-x86 архитектуре (ура!), а во-вторых, результаты автор дал в конце статьи немного озадачили меня: порядка 6-ти кратное преимущество для Intel? Автор сделал однозначный вывод, что ARM-у ну очень далеко по соотношению «эффективность на такт» до «большого железа» от Интела в этой простой задаче.


    Вызов принят!


    Но начнем с самого начала! Автор начал с некого бейзлайна — последовательной реализации, поэтому я тоже решил начать оттуда и двигаться вверх. Давайте назовем этот базис testee00 для пущей запутанности:


    inline void testee00() {
        size_t i = 0, pos = 0;
        while (i < 16) {
            const char c = input[i++];
            output[pos] = c;
            pos += (c > 32 ? 1 : 0);
        }
    }

    Я запускал testee00 на нескольких процессорах amd64 и одном процессоре arm64, используя разные версии компилятора GCC и Clang, всегда беря за основу лучший результат компиляции. Ниже приведены результаты соотношения такт/символ, рассчитанные perf -e cycles, деленным на количество обработанных символов (в нашем случае — 5 10^7 16) и усеченные до 4-й цифры после десятичной точки:


    CPU Compiler & flags clocks/character
    Intel Xeon E5-2687W (SNB) g++-4.8 -Ofast 1.6363
    Intel Xeon E3-1270v2 (IVB) g++-5.1 -Ofast 1.6186
    Intel i7-5820K (HSW) g++-4.8 -Ofast 1.5223
    AMD Ryzen 7 1700 (Zen) g++-5.4 -Ofast 1.4113
    Marvell 8040 (Cortex-A72) g++-5.4 -Ofast 1.3805

    Таблица 1. Производительность testee00 на десктоповых ядрах


    Интересно, не так ли? Маленький чип телефона (3-Decoder OoO) действительно дает лучшее соотношение такт / символ, чем более крупный настольный чип (в конце этой статьи вы можете увидеть фактические данные статистики).


    Итак, давайте перейдем к SIMD. Я не претендую на то, чтобы считаться опытным кодером на NEON, но иногда я заморачиваюсь с ARM SIMD. Я не буду инлайнить подпрограммы SIMD в основную часть этой статьи, чтобы не отпугнуть читателя; Вместо этого весь тестовый код и участвующие тестовые процедуры можно найти в конце этой статьи.


    Я взял на себя смелость изменить первоначальную процедуру обрезки SSSE3 Даниэля — на самом деле, я использовал свою версию для теста. Причина? Я не могу просто так взять 2 ^ 16 * 2 ^ 4 = 1 Мбайт таблицы поиска в моем коде — это был бы большой пожиратель кеша для любых сценариев, где мы не просто обрезаем потоки ascii, но вызов подпрограммы облегчает другую работу. Версия LSS-less SSSE3 поставляется с ценой немногочисленных вычислений, но работает только на регистрах, и, как вы увидите, цена за исключение таблицы не является запретительной даже при интенсивных нагрузках на обрезку. Более того, как новая версия SSSE3, так и версия NEON (ASIMD2) используют один и тот же алгоритм, поэтому сравнение является настолько прямым, насколько это возможно физически:


    CPU Compiler & flags clocks/character
    Intel Xeon E5-2687W (SNB) g++-4.8 -Ofast -mssse3 .4230
    Intel Xeon E3-1270v2 (IVB) g++-5.4 -Ofast -mssse3 .3774
    Marvell 8040 (Cortex-A72) g++-5.4 -Ofast -mcpu=cortex-a57 1.0503

    Таблица 2. Производительность testee01 на десктопных ядрах


    Замечание: Тюнинг микроархитектуры для A57 передается в билд arm64, поскольку дефолтный планировщик от компилятора явно хуже в этой версии, что касается кода NEON, и A57 является довольно «общим» общим знаменателем ARMv8, когда дело доходит до планирования.


    Как вы видите, эффективность в расчете на такта составляет 2x в пользу Sandy Bridge — ядро, которое при том же (или аналогичном) fabnode будет в 4 раза больше по площади A72. Так что все не так уж плохо для телефонных чипов; )


    Бонусный материал: тот же тест на малых arm64 and amd64 CP:


    CPU Compiler & flags clocks/character, scalar clocks/character, vector
    AMD C60 (Bobcat) g++-4.8 -Ofast -mssse3 3.5751 1.8215
    MediaTek MT8163 (Cortex-A53) clang++-3.6 -march=armv8-a -mtune=cortex-a53 -Ofast 2.6568 1.7100

    Таблица 3. Производительность testee00 на testee01 на entry-level ядрах




    Xeon E5-2687W @ 3.10GHz


    Scalar version


    $ g++-4.8 prune.cpp -Ofast
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234
    
     Performance counter stats for './a.out':
    
            421.886991      task-clock (msec)         #    0.998 CPUs utilized
         1,309,087,898      cycles                    #    3.103 GHz
         4,603,132,268      instructions              #    3.52  insns per cycle
    
           0.422602570 seconds time elapsed
    
    $ echo "scale=4; 1309087898 / (5 * 10^7 * 16)" | bc
    1.6363

    SSSE3 version (batch of 16, misaligned write)


    $ g++-4.8 prune.cpp -Ofast -mssse3
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234a
    
     Performance counter stats for './a.out':
    
            109.063426      task-clock (msec)         #    0.997 CPUs utilized
           338,414,215      cycles                    #    3.103 GHz
         1,052,118,398      instructions              #    3.11  insns per cycle
    
           0.109422808 seconds time elapsed
    
    $ echo "scale=4; 338414215 / (5 * 10^7 * 16)" | bc
    .4230



    Xeon E3-1270v2 @ 1.60GHz


    Scalar version


    $ g++-5 -Ofast prune.cpp
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234
    
     Performance counter stats for './a.out':
    
            810.515709 task-clock (msec)         #    0.999 CPUs utilized
         1,294,903,960 cycles                    #    1.598 GHz
         4,601,118,631 instructions              #    3.55  insns per cycle
    
           0.811646618 seconds time elapsed
    
    $ echo "scale=4; 1294903960 / (5 * 10^7 * 16)" | bc
    1.6186

    SSSE3 version (batch of 16, misaligned write)


    $ g++-5 -Ofast prune.cpp -mssse3
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234a
    
     Performance counter stats for './a.out':
    
            188.995814 task-clock (msec)         #    0.997 CPUs utilized
           301,931,101 cycles                    #    1.598 GHz
         1,050,607,539 instructions              #    3.48  insns per cycle
    
           0.189536527 seconds time elapsed
    
    $ echo "scale=4; 301931101 / (5 * 10^7 * 16)" | bc
    .3774



    Intel i7-5820K


    Scalar version


    $ g++-4.8 -Ofast prune.cpp
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234
    
     Performance counter stats for './a.out':
    
            339.202545      task-clock (msec)         #    0.997 CPUs utilized
         1,204,872,493      cycles                    #    3.552 GHz
         4,602,943,398      instructions              #    3.82  insn per cycle
    
           0.340089829 seconds time elapsed
    
    $ echo "scale=4; 1204872493 / (5 * 10^7 * 16)" | bc
    1.5060



    AMD Ryzen 7 1700


    Scalar version


    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234
    
     Performance counter stats for './a.out':
    
            356,169901      task-clock:u (msec)       #    0,999 CPUs utilized
            1129098820      cycles:u                  #    3,170 GHz
            4602126161      instructions:u            #    4,08  insn per cycle
    
           0,356353748 seconds time elapsed
    
    $ echo "scale=4; 1129098820 / (5 * 10^7 * 16)" | bc
    1.4113



    Marvell ARMADA 8040 (Cortex-A72) @ 1.30GHz


    Scalar version


    $ g++-5 prune.cpp -Ofast
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234
    
     Performance counter stats for './a.out':
    
            849.549040      task-clock (msec)         #    0.999 CPUs utilized
         1,104,405,671      cycles                    #    1.300 GHz
         3,251,212,918      instructions              #    2.94  insns per cycle
    
           0.850107930 seconds time elapsed
    
    $ echo "scale=4; 1104405671 / (5 * 10^7 * 16)" | bc
    1.3805

    ASIMD2 version (batch of 16, misaligned write)


    $ g++-5 prune.cpp -Ofast -mcpu=cortex-a57 -mtune=cortex-a57
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234
    
     Performance counter stats for './a.out':
    
            646.394560      task-clock (msec)         #    0.999 CPUs utilized
           840,305,966      cycles                    #    1.300 GHz
           801,000,092      instructions              #    0.95  insns per cycle
    
           0.646946289 seconds time elapsed
    
    $ echo "scale=4; 840305966 / (5 * 10^7 * 16)" | bc
    1.0503

    ASIMD2 version (batch of 32, misaligned write)


    $ clang++-3.7 prune.cpp -Ofast -mcpu=cortex-a57 -mtune=cortex-a57
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234
    
     Performance counter stats for './a.out':
    
           1140.643640      task-clock (msec)         #    0.999 CPUs utilized
         1,482,826,308      cycles                    #    1.300 GHz
         1,504,011,807      instructions              #    1.01  insns per cycle
    
           1.141241760 seconds time elapsed
    
    $ echo "scale=4; 1482826308 / (5 * 10^7 * 32)" | bc
    .9267



    AMD C60 (Bobcat) @ 1.333GHz


    Scalar version


    $ g++-4.8 prune.cpp -Ofast
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234
    
     Performance counter stats for './a.out':
    
           2208.190651 task-clock (msec)         #    0.997 CPUs utilized
         2,860,081,604 cycles                    #    1.295 GHz
         4,602,968,860 instructions              #    1.61  insns per cycle
    
           2.214173331 seconds time elapsed
    
    $ echo "scale=4; 2860081604 / (5 * 10^7 * 16)" | bc
    3.5751

    SSSE3 version (batch of 16, misaligned write)


    $ clang++-3.5 prune.cpp -Ofast -mssse3
    $ perf stat -e task-clock,cycles,instructions -- ./a.out
    alabalanica1234a
    
     Performance counter stats for './a.out':
    
           1098.519499 task-clock (msec)         #    0.998 CPUs utilized
         1,457,266,396 cycles                    #    1.327 GHz
         1,053,073,591 instructions              #    0.72  insns per cycle
    
           1.101240320 seconds time elapsed
    
    $ echo "scale=4; 1457266396 / (5 * 10^7 * 16)" | bc
    1.8215



    MediaTek MT8163 (Cortex-A53) @ 1.50GHz (sans perf)


    Scalar version


    $ ../clang+llvm-3.6.2-aarch64-linux-gnu/bin/clang++ prune.cpp -march=armv8-a -mtune=cortex-a53 -Ofast
    $ time ./a.out
    alabalanica1234
    
    real    0m1.417s
    user    0m1.410s
    sys     0m0.000s
    $ echo "scale=4; 1.417 * 1.5 * 10^9 / (5 * 10^7 * 16)" | bc
    2.6568

    ASIMD2 version (batch of 16, misaligned write)


    $ ../clang+llvm-3.6.2-aarch64-linux-gnu/bin/clang++ prune.cpp -march=armv8-a -mtune=cortex-a53 -Ofast
    $ time ./a.out
    alabalanica1234
    
    real    0m0.912s
    user    0m0.900s
    sys     0m0.000s
    $ echo "scale=4; 0.912 * 1.5 * 10^9 / (5 * 10^7 * 16)" | bc
    1.7100

    Мартин Кръстев.


    Перевод: Дмитрий Александров

    Similar posts

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

    More
    Ads

    Comments 11

      0
      Интересно, почему не предложили тестов с g++ 6.*? Вроде бы свежая статья.
        0
        Перевод ответа от Мартина Кръстева: Да, хорошо было бы. Но есть одно но: естество теста таково, что компилятору особенно нечего оптимизировать, кроме упорядочивания инструкций оптимальным образом (scheduler). Но хорошо бы действительно посмотреть на g++ по-новее. У меня самого не хватило времени обеспечить наличие g++ 6.x на разных платформах, в то время как 4.х и 5.х уже были там.
        0
        Я взял на себя смелость изменить первоначальную процедуру обрезки SSSE3 Даниэля — на самом деле, я использовал свою версию для теста. Причина? Я не могу просто так взять 2 ^ 16 * 2 ^ 4 = 1 Мбайт таблицы поиска в моем коде — это был бы большой пожиратель кеша для любых сценариев, где мы не просто обрезаем потоки ascii, но вызов подпрограммы облегчает другую работу.


        Если не использовать кеш на полную, то всё, что на самаом деле будет измеряться, — это скорость памяти. Так получилось исторически, что в армах и x86 память одинаково медленная. Так получилось, что тактовая частота у х86 больше. Поэтому, больше циклов расходуется впустую в ожидании ответа от памяти. Отсюда и результаты измерния в «тактах ЦП на символ».

          0
          Но и использовать мегабайт кеша на весьма и весьма вспомогательную задачу — очень расточительно. Однако есть большая проблема: в оригинальной статье только версия для SSSE3 использует эту гигантскую таблицу! SSE4.2 и AVX обходятся без неё!

          А с учётом того, что процессоры без поддержки SSE4.2 пропали из продажи примерно тогда же, когда в продаже только появились ARMv8 процессоры… таки странное сравнение вышло, да.

          Хотя и небесполезное: из него мы можем видеть что архитектурно ARM отстаёт от x86 вдвое, хотя практически — вшестеро.

          P.S. И, несмотря на это, у меня есть ощущение, что ARM вытеснит-таки x86 со временем. Просто потому что x86 архитектуру «вылизывать» уже, в общем-то, некуда — а стоит она куда дороже. Классика подрывных инноваций. Но ещё лет 10-20, я думаю, у старичка есть…
            0
            Всё зависит от задачи. Вылизывать ARM до уровня x86 стоит денег и времени. Когда это будет сделано, то и цены будут схожие.
              0
              Разница в том, что x86 вылизывают две компании, а арм — куча конкурирующих. Не факт, что вылизывание будет лучше, но что будет дешевле, чем в случае олигополии — факт.
                0
                Собственно до относительно недавнего времени ARM вообще не играл на поле «быстрых» CPU. Размер ядра (и, соответственно, цена) — было самой важной ценностью. После буквально десятилетий развития Intel'а на поле «быстрее, выше, сильнее» и ARM'а на поле «дешевле, эффективнее» тренд развернулся меньше 10 лет назад (догадайтесь из-за чего, или, вернее, из-за кого). И тот факт, что разница между Inetl и ARM'ом уже всего лишь двукратная — плохой знак для Intel'а…
              0
              Вот способ по скорости сопоставимый с версией использующей таблицу на 1Mb но без таблицы. Не очень простой для понимания, но быстрый и без дополнительной памяти
            0

            В коде, в начале статьи, ошибка. Функция не удаляет последний пробел если он последний во входном массиве. В результате в статье производится сравнение быстродействия процессоров на каком-то алгоритме, но не на декларируемом. ;)

              +1
              Общий ответ от Мартина Кръстева:
              Тест идет полностью из L1, который всега работает на частоте процессора, так что частота процессора не играет роли в этом тесте.
              В оригинале Даниела поищите despace_mask16 — это таблица.

              Апропо, идея данного теста быть микро- и макро-архитектурным — т.е. какие инструкции сколько работы успевают сделать — не случайно он не должен зависеть от доступа к памяти (вне L1)
              А задуман он именно так, потому что если помните, Даниел жаловался что не хватает одной важной инструкции в ARM (которая на нем заменяется двумя), и поэтому он не мог написать быстрый пруннер.
              Я считаю, что скалярный тест и векторный тест показывают довольно ясно, что архитектурно ARM справляется лучше — больше работы за меньше инструкций. И это видно по результатам лучшего соотношения работа/такт в скалярной версии, но в SIMD версии ARM отстает в два раза из-за плохой микроархитекрурной реализации.
              (т.е. там инструкций меньше, но они выполняются за больше тактов)
              А по теме 'а практически — в шестеро!' — посмотрите следующую статья Даниела, где он сам приходит к выводу, что ARM ~3 раза медленнее (после всех правок и советов его читателей).

              Спасибо)
                0
                Небольшое дополнение без перевода:
                github.com/blu/ascii_pruner/blob/master/README.md

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