FastLanes: SIMD-оптимизированная компрессия
В предыдущем уроке BtrBlocks показал, что каскад из простых кодировок может сжимать лучше, чем одна сложная. Но BtrBlocks не трогает то, как данные раскладываются в памяти перед кодированием. FastLanes (VLDB 2023, Afroozeh & Boncz — CWI Amsterdam) решает ортогональную задачу: как расположить данные так, чтобы любой bit-packing алгоритм автоматически получал SIMD-ускорение — без единой платформенной intrinsic-инструкции.
Проблема: SIMD и bit-packing
Bit-packing — финальная стадия большинства integer encodings. FOR даёт offsets по 4 бита, Delta даёт разности по 3 бита — но эти биты нужно упаковать в байты и распаковать обратно. Скорость распаковки определяет throughput всего pipeline.
Современные CPU имеют SIMD-регистры (SSE = 128 бит, AVX2 = 256 бит, AVX-512 = 512 бит, ARM NEON = 128 бит), которые обрабатывают несколько значений за одну инструкцию. Проблема: написать SIMD-оптимизированный bit-(un)packing нужно отдельно для каждой платформы и для каждой ширины бита (1–64). Это означает тысячи вариантов кода.
Bit-packing: 64 ширины бита × pack + unpack = 128 процедур
Bit-packing: упаковка N-bit значений в непрерывный поток байтов. 64 возможных ширины бита (1–64). Каждая требует своей процедуры pack/unpack.384+ ручных SIMD-функций. Каждая новая ISA → +128. Не масштабируется.
Итого: 128 × 3+ платформ = 384+ функций ручного SIMD-кода. Каждая новая ISA (RISC-V V, SVE2) добавляет ещё 128. Поддерживать невозможно. FastLanes решает это.Unified Transposed Layout: порядок 04261537
Ключевая идея FastLanes: вместо написания SIMD-кода под каждую платформу — переупорядочить данные так, чтобы обычный scalar bit-packing цикл компилятор автоматически векторизовал. Трюк — Unified Transposed Layout (UTL).
UTL работает с блоком из 1024 значений. Вместо натурального порядка (0, 1, 2, 3, 4, 5, 6, 7, …) значения переставляются в порядок 04261537 — interleaved по количеству SIMD-лейнов.
Один scalar for-loop → автовекторизация на SSE/AVX2/AVX-512/NEON
Scalar-код с простым for-loop: for(lane=0; lane<8; lane++) pack(data[lane*stride], ...). Компилятор (Clang/GCC) распознаёт 8 независимых итераций → автоматически генерирует SIMD-инструкции для текущей платформы. SSE → 4 lanes по 32-bit, AVX2 → 8 lanes, AVX-512 → 16. Один и тот же исходный код — разный SIMD на разных CPU.Почему именно 04261537?
Порядок 04261537 — это bit-reversal permutation для 8 элементов. Он гарантирует, что при любой ширине SIMD-регистра (128, 256, 512 бит) значения в одном lane никогда не пересекают байтовые границы другого lane. FastLanes расширяет это до виртуального 1024-bit SIMD-регистра — 1024 значения в блоке, порядок подобран так, что работает для всех реальных ISA.
Порядок 04261537 — упрощение для объяснения на 8 элементах. В полной реализации FastLanes использует 1024-элементные блоки с bit-reversal permutation, адаптированной под целевую виртуальную ширину. Ключевой инвариант: ни один SIMD lane не разделяет битовые boundaries с другим lane — именно это позволяет компилятору безопасно векторизовать.
Data-parallel bit-(un)packing
FastLanes переопределяет bit-packing как data-parallel операцию. Вместо одной функции, которая последовательно пакует значения:
Зависимость → нет SIMD
Последовательная зависимость: каждая итерация модифицирует buf в позиции, зависящей от предыдущей. Компилятор не может распараллелить.Независимые lanes → авто-SIMD
Независимые lanes: lane 0 пишет в байты 0–3, lane 1 — в байты 4–7, ... Нет пересечений → нет зависимостей → SIMD.Полный pipeline декодирования
Закодированный блок: 1024 × W-bit values (UTL order)
Закодированный блок на диске: 1024 значения по W бит в UTL-порядке. Метаданные: bit_width, base (для FOR), block_count.1024 значений в натуральном порядке. Throughput: > 100 млрд int/sec (scalar)
Финальный шаг: если данные закодированы FOR — прибавляем base к каждому значению (SIMD add). Если Delta — префиксная сумма (SIMD prefix sum). Результат: 1024 восстановленных значения в натуральном порядке.Ключевой insight FastLanes: переупорядочивание данных один раз при encode позволяет всем последующим операциям (pack, unpack, FOR, Delta) работать data-parallel без написания SIMD-кода. Компилятор делает всю работу — нужно лишь правильно разложить данные в памяти.
FastLanes File Format v0.1 (VLDB 2025)
В 2025 году те же авторы (Afroozeh & Boncz) опубликовали спецификацию FastLanes File Format — полноценного колоночного формата, построенного вокруг UTL. Два ключевых расширения поверх оригинальной layout-работы:
Expression Encoding
Вместо фиксированного набора кодировок (как в Parquet: PLAIN, RLE_DICTIONARY, DELTA_BINARY_PACKED, …) FastLanes FF определяет кодировки как выражения — комбинации примитивных операций:
Это напрямую поддерживает каскадную идею BtrBlocks: writer может экспериментировать с любыми цепочками кодировок, а reader декодирует их через generic expression evaluator.
Multi-Column Compression (MCC)
Второе расширение: сжатие нескольких колонок совместно, используя корреляции между ними.
Одна колонка + формула + residuals ≈ 50% экономии vs раздельное сжатие
Результат: вместо двух колонок (Delta на каждой) — одна колонка + формула + residual array (часто = all zeros → 1 бит). MCC полезен для log-данных (timestamp коррелирует с sequence_id, offset, row_number).FastLanes File Format (v0.1) — проектная спецификация, не production-ready формат. На момент публикации VLDB 2025 нет широко используемых reader/writer библиотек. DuckDB использует FastLanes-вдохновлённые кодировки внутри своего native формата, но не читает .fastlanes файлы как внешний формат.
Связь с DuckDB
FastLanes и DuckDB — продукты одной исследовательской группы (CWI Amsterdam). Связь конкретная:
Итог
FastLanes — не кодировка и не формат, а layout-принцип: переупорядочить данные один раз так, чтобы все downstream операции получали SIMD-ускорение автоматически. Ключевые числа:
- >100 млрд integers/sec decode throughput на scalar коде (автовекторизация)
- ~40% дополнительного ускорения на AVX-512 поверх scalar baseline
- 0 строк платформенного SIMD-кода — один portable C++ исходник на все ISA
- 1024 значения в блоке — размер оптимизирован под кэш-линии и register spilling
В следующем уроке мы увидим, как та же группа CWI применила FastLanes к проблеме, которую integer encodings не решают: сжатие чисел с плавающей запятой.