Ускорение вычисления CRC32 на Apple M1
Оригинал статьи
 
CRC32 - алгоритм чексумм, представленный ещё в 1961, сейчас используется самых разных контекстах, чувствительных к производительности, от форматов файлов (zip, png, gzip), до файловых систем (ext4, btrfs) и протоколов (как Ethernet и SATA). Поэтому, естественно, в течение многих лет было потрачено много усилий на его оптимизацию. Однако я открыл простое обновление широко используемой техники, которое позволяет работать на Apple M1 в два раза производительнее существующих решений.
 
В поисках новейшей информации, я нашёл огромное количество устаревших постов, что неудивительно для проблемы шестидесятилетней давности. В конечном итоге я нашёл пост в блоге MySQL от ноября 2021, в котором представлен следующий график, включая M1, и который даёт нам представление о том, что 30 ГБ/с считается быстрым:
   
Действительно, в моём собственном тестировании функции crc32 из zlib, я увидел, что она выдаёт около 30 ГБ/с на M1, что даже чуть быстрее, чем на графике, и это многообещающе. Вероятно, та версия была оптимизированна Apple?
 
Я захотел реализовать свою версию функции. Так что я начал с очевидного - специальной инструкции ARM64, созданной для вычисления CRC32 - CRC32X. Она может выдавать 8-байтные чексуммы с задержкой в 3 такта. И, теоретически, с этой инструкцией мы можем получить 3.2 Гц / 3 * 8 Б = 8.5 ГБ/с. С другой стороны, CRC32X имеет пропускную способность один раз за такт, поэтому, предположительно, мы можем избежать задержки (например, вычисляя биты CRC по частям, а затем объединяя их), мы можем достичь 3.2 ГГц / 1 * 8 Б = 25.6 ГБ/с. Это может быть чуть лучше, чем на графике от MySQL, но это лучший теоретический вариант, не учитывающий накладные расходы на объединение результатов.
 
Итак, сможем ли мы сделать лучше, чем CRC32X? M1 может работать с 8 инструкциями за такт, а наша лучшая идея пока что работает только с одной инструкцией за такт, так что, наверное, мы сможем. Кроме того, я уже протестировал zlib, и он уже работает со скоростью 30 ГБ/с, так что я точно знаю, что есть способ получше.
 
Способ получше был опубликован Intel в работе 2009 года Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction. Этот алгоритм был широко реализован, и перенесен для использования эквивалентных инструкций ARM64, PMULL и PMULL2, например, в Chromium (по совпадению, коммит был сделан всего несколько часов назад, на момент написания статьи).
 
Я не буду углубляться в математику (я даже не до конца её понимаю), но главный цикл имеет четыре независимые цепочки задержки, которые выглядят примерно так:
Код:
x5 = (uint64x2_t) pmull_lo(x1, x0);
y7 = vld1q_u64((const uint64_t *)(buf));
x1 = (uint64x2_t) pmull_hi(x1, x0);
x1 = veorq_u64(x1, x5);
x1 = veorq_u64(x1, y5);
 
На первый взгляд, я бы сказал, что цепочка задержек была такая: PMULL2 (3) + EOR (2) + EOR (2) = 7 тактов. Однако M1 может объединить инструкции PMULL/PMULL2 с последующими инструкциями EOR, что даёт один uop с задержкой в три такта. Поэтому мы можем поменять их местами: [PMULL + EOR] (3) + [PMULL2 + EOR] (3) = 6 тактов (идеально для максимизации пропускной способности, т.к. уменьшает количество объединённых uop, но если вы хотите уменьшить задержки, вы можете убрать PMULL2 из критического пути: [PMULL + EOR] (3) + EOR (2) = 5 тактов).
 
Итак, мы знаем, что каждая цепочка будет иметь задержку в 6 тактов и 2 (объединённых) uop. Эти uop имеют пропускную способность 4 за цикл, поэтому мы можем подсчитать, сколько независимых цепочек мы бы могли использовать. За 6 тактов мы можем выполнить 6 * 4 = 24 uop. Поскольку каждой цепочке нужны 2 uop, мы можем выиграть от наличия 24 / 2 = 12 независимых цепочек - в три раза больше, чем в работе 2009 года, и также в три раза больше, чем я видел в современных реализациях.
 
Для пущего оптимизма, если бы пропускная способность SIMD была узким местом, это могло бы работать за 0.5 такта на 16-битный регистр. 3.2 ГГц / 0.5 * 16 Б = 102 ГБ/с. Однако такая пропускная способность требует, чтобы мы поддерживали выполнение не более восьми инструкций за такт, что не оставит времени на загрузку значений из памяти. Поскольку нам потребуется 1 загруженный uop на каждые 4 неиспользуемые uop (всего пять из восьми возможных неиспользуемых uop за цикл), более реалистичная оценка предела производительности фронтенда составляет 3.2 ГГц / (5 / 8) * 16 Б = 82 ГБ/с.
 
(Для контраста, если бы мы обрабатывали только 4 * 16 Б = 64 Б за такт, и имели критический путь в 6 тактов, мы бы достигли не более, чем 3.2 ГГц / 6 * 64 Б = 34 ГБ/с.)
 
Реализация этого довольно проста - пошаговое увеличение на 192 байта и копирование кода для добавления цепочек задержки, но это требует вычисления новых значений для k1 и k2, что я сделал, вызывая приватную функцию x2nmodp в zlib:
Код:
uint64_t k1 = (uint64_t)x2nmodp(12*128+32, 0) << 1; // 0x1821d8bc0
uint64_t k2 = (uint64_t)x2nmodp(12*128-32, 0) << 1; // 0x12e968ac4
 
Код выше работает на M1 с производительностью около 70 ГБ/с, достигая 75 ГБ/с, если сборка настроена так, чтобы всегда иметь правильные пары слияний. Скорее всего есть возможности для улучшения, но я вполне доволен и этим.

Мой тестовый код находится в открытом доступе, хоть и не предназначен для использования в реальных условиях "как есть".
It's time to kick gum and chew ass. And i'm all out of ass.
Ответ
Перевод, скорее всего, получился кривым, если кто-то знает, как лучше - пишите, поправлю.
It's time to kick gum and chew ass. And i'm all out of ass.
Ответ
Тихо подозреваю, что если покопаться, то с подобным подходом к оптимизации сейчас можно улучшить очень много кода к любой существующей архитектуре )
Ответ
(28.05.2022 10:May)lonelywoolf Написал: Тихо подозреваю, что если покопаться, то с подобным подходом к оптимизации сейчас можно улучшить очень много кода к любой существующей архитектуре )

Учитывая как пишут современный код, даже обезьяна сможет его оптимизировать. А инженер, нормальный инженер, сможет бустануть эффективность на порядки!
Правила форума
[Новичкам] Как правильно задавать вопросы, чтобы Вам помогли

«Буду бить аккуратно, но сильно!» © Лёлик, х/ф «Бриллиантовая рука»
Ответ
Во-во. Проблема в написании эффективного кода - время. И это время, в общем, не окупается пока можно завалить производительностью железа... Но что-то мне говорит о том, что эра дешевой мощности подходит к концу.
Ответ
(28.05.2022 13:May)lonelywoolf Написал: Во-во. Проблема в написании эффективного кода - время. И это время, в общем, не окупается пока можно завалить производительностью железа... Но что-то мне говорит о том, что эра дешевой мощности подходит к концу.

Проблема в том что сейчас любой, кто осилил
Код:
if..else
, считает себя ниибацо погромистом. А ещё эта практика с "пох какой ты программист, лишь бы человек был хороший!"

Раньше код писали математики, инженеры, сейчас — студенты. Они сбили ценник, потому профессионалы либо работают за еду, либо уходят из профессии.
Правила форума
[Новичкам] Как правильно задавать вопросы, чтобы Вам помогли

«Буду бить аккуратно, но сильно!» © Лёлик, х/ф «Бриллиантовая рука»
Ответ
Ну здесь опять же проблема в "дефективных" менеджерах. На практике, хрен бы сним, если бы такой подход к написанию приложений не лез в промышленность и ответственные применения. И вот здесь уже становится плохо и больно. Дело даже не в том, что пишет код студент - дело в том, что этот студент не понимает, КАК оно работает, а от этого изобретает лютую дичь. По граблям мы все ходили так или иначе, но вот эффективность все же зависит от понимания сути. Три строки на скриптовом языке - это не решение, на самом деле - это лишь попытка снизить себестоимость разработки. Есть места, где применение такого подхода оправдано, а есть все же ответственные задачи. И вот пока в ответственные задачи не полезли "хипсторы" - трава была зеленее, ИМХО.
Ответ