Сегодня мы делимся открытым исходным кодом, который может сортировать массивы чисел примерно в десять раз быстрее, чем C++ std::sort, и превосходит современные алгоритмы, специфичные для архитектуры, оставаясь портативным для всех современных архитектур CPU. Ниже мы обсуждаем, как мы этого добились.

Сначала немного предыстории. В последнее время наблюдается тенденция к колоночным базам данных, которые последовательно хранят все значения из определенного столбца, а не все поля записи или «строки» перед полями следующей записи. Это может быть быстрее для фильтрации или сортировки, которые являются ключевыми строительными блоками для SQL-запросов; поэтому мы сосредотачиваемся на этой структуре данных.

Учитывая, что сортировка интенсивно изучалась, как мы можем найти 10-кратное ускорение? Ответ кроется в инструкциях SIMD/векторных. Они выполняют операции над несколькими независимыми элементами в одной инструкции—например, работают с 16 float32 одновременно при использовании набора инструкций AVX-512, или с четырьмя на Arm NEON.

Если вы уже знакомы с SIMD, вы могли слышать, что он используется в суперкомпьютерах, линейной алгебре для приложений машинного обучения, обработке видео или кодеках изображений, таких как JPEG XL. Но если операции SIMD включают только независимые элементы, как мы можем их сортировать, что включает перестановку соседних элементов массива? Представьте, что у нас есть какой-то особый способ сортировки, например, массивов из 256 элементов. Тогда алгоритм быстрой сортировки для сортировки большего массива состоит в разделении его на два подмассива: те, что меньше значения «опорного элемента» (в идеале медианы), и все остальные; затем рекурсивно, пока подмассив не станет размером не более 256 элементов, и использование нашего особого метода для их сортировки. Разделение занимает большую часть времени CPU, поэтому, если мы сможем ускорить его с помощью SIMD, у нас будет быстрая сортировка.

К счастью, современные наборы инструкций (Arm SVE, RISC-V V, x86 AVX-512) включают специальную инструкцию, подходящую для разделения. При отдельном вводе значений да/нет (меньше ли элемент опорного значения), эта инструкция «compress-store» сохраняет в последовательную память только те элементы, соответствующий ввод которых «да». Затем мы можем логически инвертировать значения да/нет и снова применить инструкцию, чтобы записать элементы в другой раздел. Эта стратегия использовалась в быстрой сортировке, специфичной для AVX-512. Но как насчет других наборов инструкций, таких как AVX2, в которых нет compress-store? Предыдущие работы показали, как эмулировать эту инструкцию с помощью инструкций перестановки. Мы опираемся на эти методы, чтобы достичь первой векторизованной быстрой сортировки, портативной для шести наборов инструкций на трех архитектурах, и фактически превосходящей предыдущие сортировки, специфичные для архитектуры.

Наша реализация использует портативные функции SIMD из Highway, поэтому нам не нужно переписывать около 3000 строк C++ для каждой платформы. Highway использует compress-store, когда он доступен, и в противном случае эквивалентные инструкции перестановки. В отличие от предыдущего передового уровня—который также был специфичен для 32-битных целых чисел—мы поддерживаем полный диапазон входных данных от 16 до 128 бит. Несмотря на нашу единственную портативную реализацию, мы достигаем рекордных скоростей как на AVX2, AVX-512 (Intel Skylake), так и на Arm NEON (Apple M1). Для миллиона 32/64/128-битных чисел наш код, работающий на Apple M1, может выдавать отсортированный вывод со скоростью 499/471/466 МБ/с. На Skylake с частотой 3 ГГц с AVX-512 скорости составляют 1123/1119/1120 МБ/с. Интересно, что AVX-512 в 1,4-1,6 раза быстрее AVX2—стоящее ускорение при нулевых дополнительных усилиях (Highway проверяет, какие инструкции доступны на CPU, и использует лучшие из доступных). При работе на AVX2 мы измеряем 798 МБ/с, тогда как предыдущий передовой уровень, оптимизированный для AVX2, достигает только 699 МБ/с. Для сравнения, стандартная библиотека достигает 58/128/117 МБ/с на том же CPU, поэтому мы добились ускорения в 9-19 раз в зависимости от типа чисел.

Ранее сортировка считалась дорогостоящей. Нам интересно увидеть, какие новые приложения и возможности откроются благодаря возможности сортировки на скорости 1 ГБ/с на одном ядре CPU. Исходный код под лицензией Apache2 ...