Как ускорить разжатие LZ4

Как ускорить разжатие LZ4

SELECT * FROM hits_100m
WHERE URL LIKE '%metrika%'
ORDER BY EventTime LIMIT 10

0.772 sec.
11.0 GiB/sec.
125.98 million rows/sec.

Что такое LZ4

— библиотека для сжатия данных;

— высокая скорость работы;

— частный случай алгоритма LZ77;

— не специализирована под конкретные типы данных;

— существует с 2011 года;

— используется в ClickHouse с 2011 года;

— автор — Yann Collet;

— аналоги: Snappy, QuickLZ, LZO, FastLZ, BriefLZ, LZF;

Почему именно LZ4

Он почти «парето-оптимален».

Сравниваем алгоритмы по трём параметрам
на всевозможных датасетах:
— коэффициент сжатия;
— скорость сжатия;
— скорость разжатия;

Алгоритм называется «парето-оптимальным», если нет другого, который лучше хотя бы по одному параметру и не хуже по всем остальным.

Есть варианты немного «круче»:

Lizard (бывший LZ5): https://github.com/inikep/lizard/

LZSSE: https://github.com/ConorStokes/LZSSE/

density: https://github.com/centaurean/density

LZTURBO: https://sites.google.com/site/powturbo/

Почему разжатие — узкое место?

Типичная скорость разжатия — несколько ГБ/сек на одном ядре CPU.

Разжатие производится в несколько потоков,
что даёт скорость 10 ГБ/сек и больше.

Это больше скорости массива HDD и SSD
и разжатие не должно быть узким местом?

Но:

С дисковой подсистемы читаются сжатые данные, что уменьшает IO.

Данные часто находятся в page cache
— тогда узким местом всегда будет CPU, а не IO.

Стоит ли вообще сжимать данные?

— да.

Если этого не делать — упрёмся в IO или объём данных.

Сжимайте данные всегда:
— при хранении, даже если у вас массив из быстрых NVM-e SSD;
— при передаче данных по сети, даже если 10 GBit без переподписки;

Как устроен LZ4*

Сжатый файл - это набор команд двух видов,
при выполнении которых, происходит разжатие данных:

Literals: скопируй следующие N байт сжатых данных как есть.

Match: скопируй N байт по смещению M,
которые уже были недавно разжаты.

Hello world Hello
literals 12 "Hello world " match 5 12

* — за исключением мелких деталей; любой алгоритм семейства LZ77;

Как сжимать данные

— идём по данным;

— хэшируем следующие 4 байта;

— кладём смещение в хэш-таблицу;

— если там уже есть эти 4 байта - мы нашли совпадение;

— смотрим максимальную длину совпадения;

— записываем команду "повторить данные такой-то длины по такому-то смещению" в сжатый файл;

Как разжимать данные

while (...) { read(input_pos, literal_length, match_length); copy(output_pos, input_pos, literal_length); output_pos += literal_length; read(input_pos, match_offset); copy(output_pos, output_pos - match_offset, match_length); output_pos += match_length; }

Как скопировать кусок памяти?

memcpy

— memcpy тормозит*;

— memcpy не всегда
корректно использовать;

* — в данном сценарии работы;

Почему memcpy — неоптимально?

1. Потому что memcpy обычно находится в библиотеке libc, а библиотека libc обычно линкуется динамически, и вызов memcpy будет идти косвенно, через PLT.

2. Потому что функция memcpy с неизвестным в compile time аргументом size не инлайнится.

3. Потому что функция memcpy делает много усилий для корректной обработки «хвостов» куска памяти, не кратных размеру машинного слова или регистра.

Можно писать лишние байты

Можем всегда копировать кусками кратными 8 (или 16, 32...) байт.

Эта оптимизация уже присутствует в оригинальной реализации LZ4.

Hello world ........... ^^^^^ - src ^^^^^ - dst Hello world Hello wo... ^^^^^^^^ - src ^^^^^^^^ - dst

(но нужна проверка выхода за границы буфера)

Можно писать лишние байты

void copy8(UInt8 * dst, const UInt8 * src) { /// Здесь memcpy не вызывается (builtin). memcpy(dst, src, 8); } void wildCopy8( UInt8 * dst, const UInt8 * src, UInt8 * dst_end) { do { copy8(dst, src); dst += 8; src += 8; } while (dst < dst_end); }

Нужна проверка выхода за границы буфера

The last 5 bytes are always literals
The last match must start at least 12 bytes before end of block.
Consequently, a block with less than 13 bytes cannot be compressed.


https://github.com/lz4/lz4/wiki/lz4_Block_format.md

Почему копируем именно по 8 байт?

— почему цикл не развёрнут?

— почему не используем SSE или AVX регистры?

void copy16(UInt8 * dst, const UInt8 * src) { _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), _mm_loadu_si128(reinterpret_cast(src))); } void wildCopy16( UInt8 * dst, const UInt8 * src, UInt8 * dst_end) { do { copy16(dst, src); dst += 16; src += 16; } while (dst < dst_end); }

Почему копируем именно по 8 байт?

— не очевидно, как лучше;

— в оригинальной реализации LZ4
это связано с условиями в формате сжатых данных,
предотвращающими проезд по памяти;

Копирование match, простой случай

Копируем 5 байт по смещению 12:

Hello world ........... ^^^^^ - src ^^^^^ - dst Hello world Hello wo... ^^^^^ - src ^^^^^ - dst

Копирование match, сложный случай

Копируем 10 байт по смещению 3:

abc............. ^^^^^^^^^^ - src ^^^^^^^^^^ - dst abcabcabcabca... ^^^^^^^^^^ - src ^^^^^^^^^^ - dst

Нужно копировать так,
как если бы мы делали это побайтово

op[0] = match[0]; op[1] = match[1]; op[2] = match[2]; op[3] = match[3]; ...
abca............ ^ - src ^ - dst abcab........... ^ - src ^ - dst abcabc.......... ^ - src ^ - dst abcabca......... ^ - src ^ - dst abcabcab........ ^ - src ^ - dst

Копируем первые 4 байта побайтово:

abcabca......... ^^^^ - src ^^^^ - dst

Теперь можно скопировать 4 байта сразу:

abcabcabcab..... ^^^^ - src ^^^^ - dst

Теперь можно скопировать 8 байт сразу:

abcabcabcabcabcabca..... ^^^^^^^^ - src ^^^^^^^^ - dst

Удивительно непонятный код

const unsigned dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; const int dec64 = dec64table[offset]; op[0] = match[0]; op[1] = match[1]; op[2] = match[2]; op[3] = match[3]; match += dec32table[offset]; memcpy(op+4, match, 4); match -= dec64;
void copyOverlap8(UInt8 * op, const UInt8 *& match, const size_t offset) { /// 4 % n. /// Or if 4 % n is zero, we use n. /// It gives equivalent result, but is better CPU friendly. static constexpr int shift1[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /// 8 % n - 4 % n static constexpr int shift2[] = { 0, 0, 0, 1, 0, -1, -2, -3 }; op[0] = match[0]; op[1] = match[1]; op[2] = match[2]; op[3] = match[3]; match += shift1[offset]; memcpy(op + 4, match, 4); match += shift2[offset]; }
void copyOverlap16(UInt8 * op, const UInt8 *& match, const size_t offset) { /// 4 % n. static constexpr int shift1[] = { 0, 1, 2, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }; /// 8 % n - 4 % n static constexpr int shift2[] = { 0, 0, 0, 1, 0, -1, -2, -3, -4, 4, 4, 4, 4, 4, 4, 4 }; /// 16 % n - 8 % n static constexpr int shift3[] = { 0, 0, 0, -1, 0, -2, 2, 1, 8, -1, -2, -3, -4, -5, -6, -7 }; op[0] = match[0]; op[1] = match[1]; op[2] = match[2]; op[3] = match[3]; match += shift1[offset]; memcpy(op + 4, match, 4); match += shift2[offset]; memcpy(op + 8, match, 8); match += shift3[offset]; }

Можно ли реализовать «хитрое» копирование более оптимально?

Может быть есть магическая SIMD инструкция,
которая сделает сразу всё что нужно?

Инструкция pshufb

— от слова shuffle;

— входит в SSSE3 (три буквы S).

Принимает два 16-байтных регистра:

— данные, которые надо shuffle;

— «селектор» — из какого байта взять i-ый байт результата.

Пример

xmm0: abc............. xmm1: 0120120120120120 pshufb %xmm1, %xmm0 xmm0: abcabcabcabcabca

Каждый байт результата мы заполнили выбранным нами байтом исходных данных - как раз то, что нужно!

void copyOverlap16Shuffle(UInt8 * op, const UInt8 *& match, const size_t offset) { static constexpr UInt8 __attribute__((__aligned__(16))) masks[] = { /* offset = 0, not used as mask, but for shift amount instead */ 0, 1, 2, 1, 4, 1, 4, 2, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* offset = 1 */ 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, }; _mm_storeu_si128(reinterpret_cast<__m128i *>(op), _mm_shuffle_epi8( _mm_loadu_si128(reinterpret_cast(match)), _mm_load_si128(reinterpret_cast(masks) + offset))); match += masks[offset]; }

Инструкция pshufb

Можно применять и для 8 байт:

— используя MMX регистры (плохо);

— используя 16 байтные регистры, просто переставляя ненужные байты во второй половине.

Аналогичные инструкции:

— в AVX2: vpermb (неполноценная);

— в AVX-512 VBMI - сразу для 64 байт;

— в ARM Neon: vtbl (неполноценная).

Как избежать проверки
выхода за границы массива?

— просто попросить пользователя
выделить больше памяти для буферов.

— но может быть деградация производительности из-за аллокатора.

Три оптимизации

1. Копирование по 16 байт вместо 8 байт.

2. Использование shuffle инструкции для случая offset < 16.

3. Убран один лишний if.

Даёт ли это ускорение?

Пример 1:

Xeon E2650v2, данные Яндекс.Браузера, столбец AppVersion.

reference: 1.67 GB/sec.
16 bytes, shuffle: 2.94 GB/sec (на 76% быстрее!).

Пример 2:

Xeon E2650v2, данные Яндекс.Директа, столбец ShowsSumPosition.

reference: 2.30 GB/sec.
16 bytes, shuffle: 1.91 GB/sec (на 20% медленнее).

Сделаем 4 варианта кода

— оперируем 8 или 16 байтными кусочками;

— используем или не используем shuffle инструкцию.

template <size_t copy_amount, bool use_shuffle> void NO_INLINE decompressImpl( const char * const source, char * const dest, size_t dest_size)
sudo echo 'performance' | tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor kill -STOP $(pidof firefox) $(pidof chromium)
sudo kill -STOP \ $(pidof python) \ $(pidof perl) \ $(pgrep -u skynet) \ $(pidof cqudp-client)


Иначе результаты будут нестабильными.

Как выбрать лучший вариант?

— выбрать тот, который лучше в среднем,
на репрезентативной нагрузке и актуальных моделях CPU;

— вручную вписать условия
в зависимости от коэффициента сжатия
и модели CPU;

— протестировать все варианты на всех доступных CPU
или читать справочники по latency и throughput инструкций.

Источник: https://learnforeverlearn.com/bandits/

Многорукие бандиты

— выбираем разные варианты случайно;

— считаем статистику для каждого;

— рассматриваем время каждого варианта как случайную величину;

— оцениваем распределение времени для каждого варианта;

Thompson Sampling

— «разыгрываем в уме» случайную величину для каждого варианта;

— выбираем тот, для которого разыгранное значение оказалось лучше.

Как оценивать распределение

— байесовский метод;

— параметрически, что-нибудь типа Gamma распределения;

— параметрически, нормальное распределение;

Тестирование на разных CPU

Intel(R) Xeon(R) CPU
— E5-2650 v2 @ 2.60GHz
— E5-2660 v4 @ 2.00GHz
— E5-2660 0 @ 2.20GHz
— E5-2683 v4 @ 2.10GHz
— E5-2667 v2 @ 3.30GHz
— E312xx (Sandy Bridge)
— E5645 @ 2.40GHz
— E5530 @ 2.40GHz
— E5440 @ 2.83GHz

AMD EPYC 7351 16-Core Processor
AMD Opteron(TM) Processor 6274
AMD Opteron(tm) Processor 6380

Cavium ThunderX2

Тестирование на разных CPU и dataset-ах

— имеется 13 серверов;

— на каждом из них запускается тест на 256 файлах;

— в 6 вариантах (reference, 0, 1, 2, 3, adaptive);

— и каждый тест запускаем 10 раз, чередуя варианты в перемешку.

Получается 199 680 результатов, и их можно сравнивать.

Тестирование на разных CPU и dataset-ах

— на современных Intel ускорение — 13..17% в среднем;

— на AMD EPYC ускорение — 19.7% в среднем;

— на старом Intel E5440 — −1%;

— на Cavium — 3..4% (предварительные результаты);

— на всех кроме E5440 многорукие бандиты в среднем
всегда лучше любого наперёд выбранного варианта.

.

Pull request: https://github.com/yandex/ClickHouse/pull/1890
(уже помержили)

┌─cpu───────────────────┬──ref─┬─adapt─┬──max─┬─best─┬─adapt_boost─┬─max_boost─┬─adapt_over_max─┐ │ E5-2667 v2 @ 3.30GHz │ 2.81 │ 3.19 │ 3.15 │ 3 │ 1.14 │ 1.12 │ 1.01 │ │ E5-2650 v2 @ 2.60GHz │ 2.5 │ 2.84 │ 2.81 │ 3 │ 1.14 │ 1.12 │ 1.01 │ │ E5-2683 v4 @ 2.10GHz │ 2.26 │ 2.63 │ 2.59 │ 3 │ 1.16 │ 1.15 │ 1.02 │ │ E5-2660 v4 @ 2.00GHz │ 2.15 │ 2.49 │ 2.46 │ 3 │ 1.16 │ 1.14 │ 1.01 │ │ AMD EPYC 7351 │ 2.03 │ 2.44 │ 2.35 │ 3 │ 1.2 │ 1.16 │ 1.04 │ │ E5-2660 0 @ 2.20GHz │ 2.13 │ 2.39 │ 2.37 │ 3 │ 1.12 │ 1.11 │ 1.01 │ │ E312xx (Sandy Bridge) │ 1.97 │ 2.2 │ 2.18 │ 3 │ 1.12 │ 1.11 │ 1.01 │ │ E5530 @ 2.40GHz │ 1.65 │ 1.93 │ 1.94 │ 3 │ 1.17 │ 1.18 │ 0.99 │ │ E5645 @ 2.40GHz │ 1.65 │ 1.92 │ 1.94 │ 3 │ 1.16 │ 1.18 │ 0.99 │ │ AMD Opteron 6380 │ 1.47 │ 1.58 │ 1.56 │ 1 │ 1.07 │ 1.06 │ 1.01 │ │ AMD Opteron 6274 │ 1.15 │ 1.35 │ 1.35 │ 1 │ 1.17 │ 1.17 │ 1 │ │ E5440 @ 2.83GHz │ 1.35 │ 1.33 │ 1.42 │ 1 │ 0.99 │ 1.05 │ 0.94 │ │ Cavium ThunderX2 │ 0.84 │ 0.87 │ 0.87 │ 0 │ 1.04 │ 1.04 │ 1 │ └───────────────────────┴──────┴───────┴──────┴──────┴─────────────┴───────────┴────────────────┘