Предположим, что я дал вам относительно длинную строку, а вы хотите удалить из неё все пробелы. В ASCII мы можем определить пробелы как знак пробела (‘ ’) и знаки окончания строки (‘r’ и ‘n’). Меня больше всего интересуют вопросы алгоритма и производительности, так что мы можем упростить задачу и удалить все байты со значениями меньшими либо равными 32.
В предыдущией статье, где я задавал вопрос об удалении пробелов на скорость, лучшим ответом было использование векторизации с помощью 128-битных регистров (SSE4). Оно оказалось в 5-10 раз быстрее подхода в лоб.
Очень удобно, что во всех процессорах имеются 128-битные векторные регистры, также как в процессорах x64. Неужели процессоры ARM могут работать настолько же быстро, как процессоры x64?
Давайте сначала рассмотрим быструю скалярную реализацию:
size_t i = 0, pos = 0;
while (i < howmany) {
char c = bytes[i++];
bytes[pos] = c;
pos += (c > 32 ? 1 : 0);
}Она удаляет все символы со значениями меньшими либо равными 32 и записывает данные обратно. Работает очень быстро.
Можно ли добиться ещё большей скорости с векторными инструкциями?
На процессорах x64 лучшей стратегией будет захватить 16 байт данных, быстро сравнить на предмет пустых символов, затем извлечь значение маски (или bitset), созданное из 16 бит, один бит на символ, где каждый бит соответствует значению, найден пустой символ или нет. Такой битсет быстро вычисляется на процессоре x64, поскольку там есть специальная инструкция (movemask). На процессорах ARM такой инструкции нет. Можно эмулировать movemask с помощью нескольких инструкций.
Итак, мы не можем обработать данные на ARM так, как на процессорах x86. Что можно предпринять?
Как это делает SS4, мы можем быстро проверить, что значения байтов меньше или равны 32, и так определить пустые символы:
static inline uint8x16_t is_white(uint8x16_t data) {
const uint8x16_t wchar = vdupq_n_u8(' ');
uint8x16_t isw = vcleq_u8(data, wchar);
return isw;
}Теперь мы можем быстро проверить любой из 16 символов, является он пустым, используя всего две инструкции:
static inline uint64_t is_not_zero(uint8x16_t v) {
uint64x2_t v64 = vreinterpretq_u64_u8(v);
uint32x2_t v32 = vqmovn_u64(v64);
uint64x1_t result = vreinterpret_u64_u32(v32);
return result[0];
}Это наталкивает на мысль о полезной стратегии. Вместо сравнения символов по одному, можно сравнить все 16 символов сразу. Если ни один из них не является пустым, то просто копируем 16 символов обратно на вход и идём дальше. В противном случае скатываемся к медленному скалярному подходу, но с дополнительным преимуществом, что здесь не нужно повторять сравнение:
uint8x16_t vecbytes = vld1q_u8((uint8_t *)bytes + i);
uint8x16_t w = is_white(vecbytes);
uint64_t haswhite = is_not_zero(w);
w0 = vaddq_u8(justone, w);
if(!haswhite) {
vst1q_u8((uint8_t *)bytes + pos,vecbytes);
pos += 16;
i += 16;
} else {
for (int k = 0; k < 16; k++) {
bytes[pos] = bytes[i++];
pos += w[k];
}
}Преимущества такого подхода проявятся сильнее всего, если вы ожидаете много потоков по 16 байт без пустых символов. В принципе, такое справедливо для многих приложений.
Я написал бенчмарк, в котором попытался оценить, сколько займёт удаление пробелов, по одной штуке за раз, на основе входных данных с небольшим количеством пустых символов, разбросанных случайным образом. Исходный код доступен, но для запуска вам нужен процессор ARM. Я запускал его на 64-битном ARM-процессоре (сделанном из ядер A57). У Джона Регера есть ещё несколько бенчмарков на такой же машине. Мне кажется, такие же ядра работают в Nintendo Switch.
| скаляр | 1,40 нс |
| NEON | 1,04 нс |
Технические спецификации небогатые. Однако процессор работает на частоте 1,7 ГГц, в чём каждый может убедиться, если запустит perf stat. Вот сколько циклов нам символ нам нужно:
| скаляр | ARM | Недавний x64 |
|---|---|---|
| скаляр | 2,4 цикла | 1,2 цикла |
| векторизованные (NEON и SS4) | 1,8 цикла | 0,25 цикла |
Если сравнить, то на процессоре x64 скалярная версия использует что-то вроде 1,2 цикла на символ, а ARM уступает примерно вдвое по циклам на символ. Это вполне ожидалось, потому что вряд ли ядра A57 могут конкурировать с x64 по производительности циклов. Однако при использовании SS4 на машине x64 я сумел добиться производительности всего 0,25 цикла на символ, что более чем в пять раз быстрее, чем на ARM NEON.
Такое большое отличие объясняется разницей в алгоритмах. На процессорах x64 мы используем сочетание movemask/pshufb и алгоритм без ветвлением с очень малым количеством инструкций. Версия для ARM NEON гораздо слабее.
На процессорах ARM есть много приятных вещей. Код ассемблера гораздо более элегантный, чем аналогичный код для процессоров x86/x64. Даже инструкции ARM NEON кажутся чище, чем инструкции SSE/AVX. Однако для многих задач полное отсутствие инструкции movemask может ограничить вас в работе.
Но, возможно, я недооцениваю ARM NEON… можете выполнить задачу эффективнее, чем удалось мне?
Примечание. Статья была отредактирована: как заметил один из комментаторов, на 64-битных процессорах ARM есть возможность перестановки 16 бит одной инструкцией.
Автор: m1rko
