Компоновка сжатия FastLanes: декодирование более 100 миллиардов целых чисел в секунду с использованием скалярного кода

Проект FastLanes с открытым исходным кодом направлен на совершенствование форматов больших данных, таких как Parquet, ORC и форматы колоночных баз данных, по нескольким направлениям. В данной работе существенно ускоряется декодирование всех распространённых схем лёгкого сжатия (LWC) — DICT, FOR, DELTA и RLE — за счёт повышения эффективности параллелизма обработки данных. Для этого компоновка сжатия перерабатывается на основе двух основных идей: (i) обобщения метода чередования значений в базовой операции распаковки и упаковки битов с ориентацией на виртуальный SIMD-регистр размером 1024 бита; и (ii) переупорядочения кортежей во всех столбцах таблицы в соответствии с единой транспонированной компоновкой (Unified Transposed Layout), которая размещает фрагменты кортежей в общем порядке «04261537» (как объясняется в статье), обеспечивая максимальный объём независимой работы для всех возможных базовых ширин SIMD-ланов: 8, 16, 32 и 64 бита. Для решения проблем разработки, сопровождения и долгосрочной совместимости программного обеспечения, обусловленных растущим разнообразием аппаратных средств, определяется виртуальный набор инструкций размером 1024 бита, состоящий из простых операторов, поддерживаемых всеми диалектами SIMD и, что особенно важно, скалярным кодом. Чередующаяся компоновка и переупорядочение кортежей фактически ускоряют скалярное декодирование, позволяя извлекать больше параллелизма обработки данных из современных процессоров с широким выпуском команд. Важно, что скалярная версия может полностью автоматически векторизоваться современными компиляторами, устраняя технический долг в программном обеспечении, вызванный платформенно-зависимыми SIMD-интринсиками. Микротесты на процессорах Intel, AMD, Apple и AWS показывают, что FastLanes ускоряет декодирование более чем до 40 значений за такт процессора. FastLanes может ускорить выполнение запросов, поскольку сжатие данных снижает требования к пропускной способности, а декодирование становится практически бесплатным.