Оригинал статьи: 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.6363SSSE3 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
.4230Xeon 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.6186SSSE3 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
.3774Intel 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.5060AMD 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.4113Marvell 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.3805ASIMD2 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.0503ASIMD2 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
.9267AMD 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.5751SSSE3 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.8215MediaTek 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.6568ASIMD2 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
