На фоне анонсов Intel и AMD вспомнилась хорошая история:
PEXT (parallel extract) и PDEP (parallel deploy) являются инструкциями, которые появились в Intel Haswell и в наборе инструкций BMI2. Они очень полезны, так как переносят и распространяют биты в 64 битных числах склеиванием и расклеиванием соответственно:
Если сейчас поискать по кодовой базе протобуфа, то вы не увидите этих инструкций, казалось бы, почему не использовать их?
Проблема очень неожиданно оказалась в процессорах AMD поколения Zen1, тогда заметили, что PEXT и PDEP используют 19-300 циклов заместо 3 как у Intel Haswell. Даже деление использует меньше циклов (30-40), чем PEXT и PDEP. И самое смешное, что архитектура Zen2 оказалось с той же проблемой (она, например, до сих пор производится и есть в PS5).
На время 2019 года процессоры AMD на серверном поприще стали давать уже серьёзную конкуренцию intel, и многие большие компании решили закупить AMD. И когда обнаружились такие эффекты, я лично очень сильно удивился.
Слава богу в Zen3 это уже починили, но закупленное железо в 2019 году вряд ли денется куда-то ещё 5-7 лет. И поэтому эти инструкции фактически бесполезны компиляторам и на уровне оптимизиации микроархитектуры, например, для Cloud.
Доходит до того, что эмуляция при константной маске быстрее работает, чем сам вызов инструкции на AMD. Интересный вопрос, а что происходит при неконстантной маске, можно ли как-то избежать циклов и if?
Оказывается ответ можно:
Давайте для каждого бита маски посчитаем сколько бит до него не стоит, так мы будем знать смещение. Таких сумм 64, но так как лучше бы нам использовать SIMD, применяется табличная архитектура: давайте в шести 64-битных числа будем хранить биты этих счётчиков, нулевое число хранит все нулевые биты, первое все первые и тд. Счётчики по значению меньше 64, поэтому хватит 6 бит для всех.
В итоге надо сначала посчитать количество нулей по модулю 2, потом по модулю 4 и тд. Для этого можно использовать инструкции CLMUL (polynomial multiplication) с -2 несколько раз, всегда, когда возникает такая сумма, её можно представить в виде многочлена. Все детали я оставлю в ссылках, здесь у меня нет желания чётко расписывать математику.
В итоге получается около 41 цикл при полностью паралеллельной имплементации, что лучше, чем 300, конечно.
И у AMD бывают плохие дни, что поделать. Хорошо, что в Zen3 уже всё починено.
Компилятор Intel может спокойно вставлять pext/pdep вместо shift (написав правильную маску) и опять говорить, что они быстрее всех :)
[1] Парсинг Varint в protobuf
[2] BMI2
[3] Более быстрая эмуляция pext/pdep на github, там и математика
[4] 41 цикл в godbolt с этой имлементацией
[5] Таблица PEXT/PDEP у Zen2
PEXT (parallel extract) и PDEP (parallel deploy) являются инструкциями, которые появились в Intel Haswell и в наборе инструкций BMI2. Они очень полезны, так как переносят и распространяют биты в 64 битных числах склеиванием и расклеиванием соответственно:
PEXT: mask=0xff00fff0 src=0x12345678 dst=0x00012567Их применение достаточно часто можно оправдать. Скажем, можно использовать для того, чтобы быстрее парсить целые числа в протобуфах, где первый бит отвечает за то, последнее ли это число, а остальные 7 являются числовыми -- тем самым можно сделать pext с маской, которая склеит только биты с 1 по 7 у каждого байта, получив число. Такие числа называют varint, в 2000х годах это было хорошим компромиссом, так как они экономят место по сети/диску, если числа маленькие (что является очень частым кейсом).
PDEP: mask=0xff00fff0 src=0x00012567 dst=0x12005670
Если сейчас поискать по кодовой базе протобуфа, то вы не увидите этих инструкций, казалось бы, почему не использовать их?
Проблема очень неожиданно оказалась в процессорах AMD поколения Zen1, тогда заметили, что PEXT и PDEP используют 19-300 циклов заместо 3 как у Intel Haswell. Даже деление использует меньше циклов (30-40), чем PEXT и PDEP. И самое смешное, что архитектура Zen2 оказалось с той же проблемой (она, например, до сих пор производится и есть в PS5).
На время 2019 года процессоры AMD на серверном поприще стали давать уже серьёзную конкуренцию intel, и многие большие компании решили закупить AMD. И когда обнаружились такие эффекты, я лично очень сильно удивился.
Слава богу в Zen3 это уже починили, но закупленное железо в 2019 году вряд ли денется куда-то ещё 5-7 лет. И поэтому эти инструкции фактически бесполезны компиляторам и на уровне оптимизиации микроархитектуры, например, для Cloud.
Доходит до того, что эмуляция при константной маске быстрее работает, чем сам вызов инструкции на AMD. Интересный вопрос, а что происходит при неконстантной маске, можно ли как-то избежать циклов и if?
Оказывается ответ можно:
Давайте для каждого бита маски посчитаем сколько бит до него не стоит, так мы будем знать смещение. Таких сумм 64, но так как лучше бы нам использовать SIMD, применяется табличная архитектура: давайте в шести 64-битных числа будем хранить биты этих счётчиков, нулевое число хранит все нулевые биты, первое все первые и тд. Счётчики по значению меньше 64, поэтому хватит 6 бит для всех.
В итоге надо сначала посчитать количество нулей по модулю 2, потом по модулю 4 и тд. Для этого можно использовать инструкции CLMUL (polynomial multiplication) с -2 несколько раз, всегда, когда возникает такая сумма, её можно представить в виде многочлена. Все детали я оставлю в ссылках, здесь у меня нет желания чётко расписывать математику.
В итоге получается около 41 цикл при полностью паралеллельной имплементации, что лучше, чем 300, конечно.
И у AMD бывают плохие дни, что поделать. Хорошо, что в Zen3 уже всё починено.
Компилятор Intel может спокойно вставлять pext/pdep вместо shift (написав правильную маску) и опять говорить, что они быстрее всех :)
[1] Парсинг Varint в protobuf
[2] BMI2
[3] Более быстрая эмуляция pext/pdep на github, там и математика
[4] 41 цикл в godbolt с этой имлементацией
[5] Таблица PEXT/PDEP у Zen2