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

в 7:30, , рубрики: C, Алгоритмы, высокая производительность, перевод, перевод с английского, Программирование

Оригинал статьи: https://github.com/blu/ascii_pruner
Автор: Мартин Кръстев

Один мой друг обратил мое внимание на интересную статью на 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, поскольку планировщик A72 от компилятора явно хуже в этой версии, что касается кода 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

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

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

Автор: advbg

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js