Intel добавила сортировку на AVX-512 в OpenJDK: ускорение в 7–15 раз
Корпорация Intel выпустила версию 3.0 библиотеки x86-simd-sort. С помощью этого решения для сортировки на основе SIMD инженеры компании в очередной раз ускорили алгоритмы проекта с открытым исходным кодом. На этот раз в 7–15 раз выросла скорость сортировки в OpenJDK.
В прошлом году Intel без объявления разместила в GitHub репозиторий x86-simd-sort с кодом под 3-пунктовой лицензией BSD. Как следует из названия, это библиотека для высокопроизводительной сортировки на SIMD в инструкциях расширения AVX-512.
Поначалу разработка шла тихо, без пресс-релизов или внимания сообщества. x86-simd-sort заметили позднее:
В сентябре 2022 года инженер Intel предложил в PR #22315 векторизовать в NumPy быструю сортировку 16- и 64-битных типов данных для AVX-512. К пулл-реквесту были приложены убедительные бенчмарки с ускорением 10—17 раз.
Смёрджили изменения в NumPy в феврале 2023 года. В марте вышла x86-simd-sort версии 1.0.
В июле Intel выпустила x86-simd-sort 2.0. Относительно прошлой версии было заявлено ускорение для сортировки 64- и 32-битных типов данных до, соответственно, 1,6 и 1,3 раз. Авторы библиотеки добавили алгоритмы сортировки argsort, quickselect, partial sort и key-value sort.
Сообщество пристально приглядывалось к подарку Intel. К примеру, Лукас Бергдолл в начале июня опубликовал независимый бенчмарк, где сравнил сразу несколько алгоритмов, два из которых — с ручной векторизацией. Библиотека x86-simd-sort и её конкурент от Google vqsort показали себя хорошо, пусть с несколькими «но» в работе и не обязательно на порядок быстрее. Лукас привёл не просто голые числа, он подробно прокомментировал графики.
Сама Intel тоже не забывала о разработчиках. Инженеры компании ходили по различным проектам открытого программного обеспечения и причиняли оптимизацию сортировки с помощью x86-simd-sort. Помощь получили в OceanBase (PR #1325), несколько раз — NumPy (PR #22315, #23435 и #23707).
Позавчера этот список пополнила OpenJDK, открытая реализация Java SE. Ещё в мае сотрудник Intel в пулл-реквесте #14227 предложил провести векторизацию алгоритма сортировки. Лишь два дня назад слегка изменённый вариант x86-simd-sort приняли в проект.
В тот же день вышла версия 3.0 библиотеки x86-simd-sort. В числе новинок — поддержка метода avx512_argselect для вычисления arg nth_element для получения массива индексов для последующего разбития массива. Это было нужно для реализации argpartition в NumPy (PR #24201 принят 1 октября).
Остальные изменения третьей версии мелкие, часто это исправления. К примеру, теперь используется __builtin_cpu_supports вместо cpuinfo.
Как обычно, проект отчитался об ускорении на порядок:
В NumPy np.partition ускорился до 25 раз для 16-, до 17 — для 32- и до 8 раз для 64-битных типов данных.
В OpenJDK прирост скорости сортировки составил до 15 и до 7 раз для, соответственно, 32- и 64-битных типов данных.
AVX-512 — расширение системы команд AVX (Advanced Vector Extensions) до векторов длиной 512 бит. Впервые технологию реализовали в сопроцессорах Xeon Phi, затем она перекочевала в традиционные процессоры, поначалу оказавшись в дорогих решениях Skylake-X. Если в Skylake (6-е поколение) задействование «тяжёлых» инструкций AVX-512 приводило к заметному снижению тактовой частоты для регулирования тепловыделения, то Ice Lake (10-е поколение) замедляется всего на 100 МГц, а Rocket Lake (11-е поколение) не меняет частоту вовсе.
Любопытно, что в «ширпотребном» сегменте Intel больше нет AVX-512. Этот набор инструкций встречается в Xeon — серверных решениях и процессорах рабочих станций. Последний раз модуль AVX-512 в процессоре для домашнего пользователя присутствовал в P-ядрах Alder Lake, в 12-м поколении процессоров Core, но без официальной поддержки и лишь в ранних ревизиях. На более поздних вариантах рабочего модуля AVX-512 нет аппаратно, а в следующих микроархитектурах он отсутствовал изначально.
AMD же наоборот, добавила AVX-512 в микроархитектуре Zen 4. x86-simd-sort работает на Ryzen семитысячной серии и на 4-м поколении EPYC.
Впрочем, это не значит, что владельцы процессоров AMD в однозначном выигрыше. Как объясняют в репозитории x86-simd-sort, реализация инструкции compressstore у AMD не так эффективна. А именно на compressstore так полагается библиотека x86-simd-sort.
Как и в прошлый раз, на производительность у чипов AMD обратили внимание. После замечания в подреддите /r/java участник сообщества раскрутил на AWS инстанс m7a.2xlarge с процессором EPYC 9R14 и поискал прирост производительности от x86-simd-sort. Как оказалось, с включённым AVX-512 на Zen 4 скорость сортировки в OpenJDK даже незначительно падает. Реакции разработчиков по этой проблеме пока нет.