Оригинал статьи
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 (по совпадению, коммит был сделан всего несколько часов назад, на момент написания статьи).
Я не буду углубляться в математику (я даже не до конца её понимаю), но главный цикл имеет четыре независимые цепочки задержки, которые выглядят примерно так:
На первый взгляд, я бы сказал, что цепочка задержек была такая: 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:
Код выше работает на M1 с производительностью около 70 ГБ/с, достигая 75 ГБ/с, если сборка настроена так, чтобы всегда иметь правильные пары слияний. Скорее всего есть возможности для улучшения, но я вполне доволен и этим.
Мой тестовый код находится в открытом доступе, хоть и не предназначен для использования в реальных условиях "как есть".
CRC32 - алгоритм чексумм, представленный ещё в 1961, сейчас используется самых разных контекстах, чувствительных к производительности, от форматов файлов (zip, png, gzip), до файловых систем (ext4, btrfs) и протоколов (как Ethernet и SATA). Поэтому, естественно, в течение многих лет было потрачено много усилий на его оптимизацию. Однако я открыл простое обновление широко используемой техники, которое позволяет работать на Apple M1 в два раза производительнее существующих решений.
В поисках новейшей информации, я нашёл огромное количество устаревших постов, что неудивительно для проблемы шестидесятилетней давности. В конечном итоге я нашёл пост в блоге MySQL от ноября 2021, в котором представлен следующий график, включая M1, и который даёт нам представление о том, что 30 ГБ/с считается быстрым:
Я захотел реализовать свою версию функции. Так что я начал с очевидного - специальной инструкции 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.
