Хабрахабр

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

При выполнении запросов в ClickHouse можно обратить внимание, что в профайлере на одном из первых мест часто видна функция LZ_decompress_fast. Почему так происходит? Этот вопрос стал поводом для целого исследования по выбору лучшего алгоритма разжатия. Здесь я публикую исследование целиком, а короткую версию можно узнать из моего доклада на HighLoad++ Siberia.

А во время выполнения запросов ClickHouse старается почти ничего не делать — использовать минимум ресурсов CPU. Данные в ClickHouse хранятся в сжатом виде. Тогда остаётся выполнить разжатие. Бывает, что все вычисления, на которые могло тратиться время, уже хорошо оптимизированы, да и запрос хорошо написан пользователем.

Казалось бы, LZ4 — очень лёгкий алгоритм: скорость разжатия, в зависимости от данных, обычно составляет от 1 до 3 ГБ/с на одно процессорное ядро. Вопрос — почему разжатие LZ4 может быть узким местом? Более того, мы используем все доступные ядра, а разжатие линейно масштабируется по всем физическим ядрам.
Но следует иметь в виду два момента. Это уже существенно больше скорости работы дисковой подсистемы. Если коэффициент сжатия достаточно большой, то с дисков почти ничего не надо считывать. Во-первых, с диска читаются сжатые данные, а скорость разжатия приведена в количестве несжатых данных. Но при этом разжатых данных образуется много, и разумеется, это влияет на расход CPU: объём работы по разжатию данных в случае LZ4 почти пропорционален объёму самих разжатых данных.

Для этого можно полагаться на page cache или использовать свой собственный кэш. Во-вторых, чтение данных с дисков может не требоваться вообще, если данные находятся в кэше. Вот почему LZ4 в смысле нагрузки на CPU часто является узким местом. В столбцовых БД использование кэша более эффективно за счёт того, что в него попадают не все столбцы, а только часто используемые.

Если разжатие данных «тормозит», то может, их вообще не стоит сжимать? Отсюда ещё два вопроса. Недавно в ClickHouse можно было настроить всего два варианта сжатия данных — LZ4 и Zstandard. Но на практике это предположение бессмысленно. Переключившись на Zstandard, можно сделать сжатие сильнее и медленнее. По умолчанию используется LZ4. Именно поэтому я очень люблю LZ4. А вот полностью отключить сжатие ещё совсем недавно было нельзя — LZ4 рассматривается как разумный минимум, который можно использовать всегда. 🙂

Я ответил, что такой возможности нет, но её легко добавить. Но недавно в англоязычном чате поддержки ClickHouse появился таинственный незнакомец, который рассказал, что у него очень быстрая дисковая подсистема (NVMe SSD) и всё упирается в сжатие — неплохо было бы иметь возможность его выключить. Я попросил привести результаты — насколько это помогло, насколько ускорились запросы. Через несколько дней нам пришёл пул-реквест, в котором реализуется метод сжатия none. Человек сказал, что эта новая фича оказалась бесполезной на практике, поскольку данные без сжатия стали занимать слишком много места.

Это допускается — во многих случаях так удастся избавиться от необходимости разжатия. Второй возникающий вопрос: если есть кэш, почему бы не хранить в нём уже разжатые данные? Но на него жалко тратить много оперативки из-за его низкой эффективности. И в ClickHouse есть такой кэш — кэш разжатых блоков. Он оправдывает себя только на мелких, идущих подряд запросах, которые используют почти одни и те же данные.

Всегда записывайте их на диск со сжатием. Общее соображение: данные надо сжимать, желательно всегда. На мой взгляд, сжатие по умолчанию следует считать оправданным даже при передаче в 10-гигабитной сети без переподписки в пределах дата-центра, а передавать данные без сжатия между дата-центрами вообще недопустимо. Передавайте по сети тоже со сжатием.

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

Почему же используется именно LZ4? Можно ли подобрать нечто ещё более лёгкое? В принципе, можно, и это правильно и полезно. Но давайте сначала рассмотрим, к какому классу алгоритмов относится LZ4.

К примеру, если вы заранее знаете, что у вас будет массив целых чисел, то можете использовать один из многочисленных вариантов алгоритма VarInt — так будет эффективнее по CPU. Во-первых, он не зависит от типа данных. Предположим, у вас есть упорядоченный временной ряд показаний датчика — массив с числами типа float. Во-вторых, LZ4 не слишком сильно зависит от требуемых допущений на модель данных. Тогда вы можете посчитать дельты, а затем сжимать дальше, и это будет эффективнее по коэффициенту сжатия.

Конечно, у него есть своя специализация (об этом ниже), и в некоторых случаях его использование бессмысленно. То есть LZ4 можно без проблем использовать для любых массивов байтов — для любых файлов. И заметим, что, благодаря внутреннему устройству, LZ4 в качестве частного случая автоматом реализует алгоритм RLE. Но если его назвать алгоритмом общего назначения, это будет небольшой ошибкой.

Такие алгоритмы называются pareto frontier — это значит, что не существует другого алгоритма, который строго лучше по одному показателю и не хуже по другим (да ещё и на широком множестве датасетов). Другой вопрос: неужели LZ4 — наиболее оптимальный алгоритм данного класса по совокупности скорости и силы сжатия? Есть алгоритмы, которые быстрее, но дают меньший коэффициент сжатия, а есть те, которые сжимают сильнее, но при этом медленнее сжимают или разжимают.

Есть варианты, которые чуть-чуть лучше. На самом деле LZ4 — не pareto frontier. В достоверности результатов можно не сомневаться благодаря сообществу на encode.ru (крупнейшем и примерно единственном форуме по сжатию данных). Например, это LZTURBO от некоего powturbo. Также стоит обратить внимание на Lizard (бывший LZ5) и Density. Но разработчик не распространяет ни исходники, ни бинарники, а только даёт их ограниченному кругу лиц для тестирования или за кучу денег (вроде никто до сих пор не заплатил). Также обратите внимание на LZSSE — крайне интересная вещь. Они могут работать чуть лучше LZ4 при выборе некоторого уровня сжатия. Впрочем, посмотреть на неё лучше после прочтения этой статьи.

Как работает LZ4

Давайте рассмотрим, как вообще работает LZ4. Это одна из реализаций алгоритма LZ77: L и Z указывают на фамилии авторов (Лемпель и Зив), а 77 — на 1977 год, когда алгоритм был опубликован. У него множество других реализаций: QuickLZ, FastLZ, BriefLZ, LZF, LZO, а также gzip и zip в случае использования низких уровней сжатия.

Сжатый с помощью LZ4 блок данных содержит последовательность записей (команд, инструкций) двух видов:

  1. Литерал (literals): «возьми следующие N байт как есть и скопируй их в результат».
  2. Матч (match, совпадение): «возьми N байт, которые уже были в разжатом результате по смещению offset от текущей позиции».

Пример. До сжатия:
Hello world Hello

После сжатия:
literals 12 "Hello world " match 5 12

Если взять сжатый блок и пройтись по нему курсором, выполняя эти команды, то мы получим в качестве результата исходные, разжатые данные.

Также ясна суть: для выполнения сжатия алгоритм кодирует повторяющиеся последовательности байт с помощью матчей. Мы примерно рассмотрели, как данные разжимаются.

Этот алгоритм byte-oriented — он не препарирует отдельные байты, а лишь копирует их целиком. Ясны и некоторые свойства. Для примера, zstd является композицией LZ77 и энтропийного кодирования. Здесь кроется отличие, например, от энтропийного кодирования.

Например, можно выбрать 64 КБ — так буферы для сжатых и несжатых данных поместятся в L2-кэш и половина ещё останется. Заметим, что размер сжатого блока выбирается не слишком большим, чтобы не тратить много оперативки во время разжатия; чтобы не сильно замедлить random access в сжатом файле (который состоит из множества сжатых блоков); и иногда — чтобы блок помещался в какой-нибудь кэш CPU.

Заодно рядом с каждым сжатым блоком удобно расположить дополнительные данные — размеры, чек-сумму. Если нам потребуется сжать файл большего размера, мы просто будем конкатенировать сжатые блоки.

Эта величина называется sliding window. Максимальное смещение для матча ограничено, в LZ4 — 64 килобайтами. Действительно, это значит, что по мере продвижения курсора вперёд совпадения могут находиться в окне размером 64 килобайта до курсора, которое движется вместе с курсором.

Конечно, вы можете использовать suffix trie (классно, если вы о нём слышали). Теперь рассмотрим, как сжать данные — другими словами, как найти в файле совпадающие последовательности. Это называется optimal parsing и даёт почти лучший коэффициент сжатия для фиксированного формата сжатого блока. Есть варианты, при которых в процессе сжатия среди предыдущих байт гарантированно находится самая длинная совпадающая последовательность. Самый эффективный способ его найти — использовать хэш-таблицу. Но есть и более эффективные варианты — когда мы находим какое-нибудь достаточно хорошее совпадение в данных, но не обязательно самое длинное.

Например, 4 байта. Для этого проходимся по исходному блоку данных курсором и берём несколько байт после курсора. Величина 4 называется min-match — с помощью такой хэш-таблицы мы можем отыскать совпадения минимум в 4 байта. Хэшируем их и кладём в хэш-таблицу смещение от начала блока — где эти 4 байта встретились.

Может быть, там ещё много чего совпадает. Если мы посмотрели в хэш-таблицу, а там уже есть запись, и если смещение не превышает sliding window, то мы проверяем, сколько ещё байт совпадает после этих четырёх байт. Это нормально — можно просто заменить значение в хэш-таблице на новое. Возможно и такое, что в хэш-таблице возникла коллизия и не совпадает ничего. Кстати, такой вид хэш-таблиц (фиксированного размера и без разрешения коллизий) называется cache table, кэш-таблица. Коллизии в хэш-таблице будут просто приводить к меньшему коэффициенту сжатия, поскольку найдётся меньше совпадений. Это тоже логично — в случае коллизии кэш-таблица просто забывает про старую запись.

Пусть данные — это массив чисел типа UInt32 в формате little endian, представляющий собой часть последовательности натуральных чисел: 0, 1, 2… Объясните, почему при использовании LZ4 эти данные не сжимаются (объём сжатых данных оказывается не меньше, чем объём несжатых данных). Задача для внимательного читателя.

Как всё ускорить

Итак, я хочу ускорить разжатие LZ4. Давайте посмотрим, что из себя представляет цикл разжатия. Вот этот цикл в псевдокоде:

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;
}

Формат LZ4 устроен так, что в сжатом файле литералы и матчи чередуются. И очевидно, первым всегда идёт literal (потому что с самого начала матч ещё неоткуда взять). Поэтому их длины кодируются вместе.

Из файла читается один байт, и из него берутся две половинки (nibble), в которых закодированы числа от 0 до 15. На самом деле всё чуть-чуть сложнее. А если оно равно 15, то длина больше и она закодирована в следующих байтах. Если соответствующее число не равно 15, то оно считается длиной литерала и матча соответственно. Далее, если оно равно 255, то мы продолжаем — считываем следующий байт так же. Тогда считывается следующий байт, и его значение прибавляется к длине.

И второе (бесполезное) наблюдение: если ваши данные очень избыточны, то применение LZ4 дважды позволит увеличить коэффициент сжатия. Отметим, что максимальный коэффициент сжатия для формата LZ4 не достигает 255.

Когда мы прочитали длину литерала (а затем так же — длину матча и смещение матча), для разжатия достаточно просто скопировать два фрагмента памяти.

Как копировать фрагмент памяти

Казалось бы, можно использовать функцию memcpy, которая как раз предназначена для копирования фрагментов памяти. Но это неоптимально и всё-таки некорректно.

Потому что она: Почему использовать функцию memcpy неоптимально?

  1. обычно находится в библиотеке libc (а библиотека libc обычно линкуется динамически, и вызов memcpy будет идти косвенно, через PLT),
  2. не инлайнится с неизвестным в compile time аргументом size,
  3. делает много усилий для корректной обработки «хвостов» фрагмента памяти, не кратных размеру машинного слова или регистра.

Последний пункт самый важный. Допустим, мы попросили функцию memcpy скопировать ровно 5 байт. Было бы очень хорошо скопировать сразу 8 байт, использовав для этого две инструкции movq.

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

Функция memcpy не имеет права это делать — действительно, ведь так мы перезапишем какие-то данные в нашей программе, будет «проезд» по памяти. Но тогда мы скопируем три лишних байта — то есть будем писать за границу переданного буфера. Тогда мы получим segfault (это хорошо). А если мы писали по невыровненному адресу, то эти лишние байты могут быть расположены на невыделенной странице виртуальной памяти или на странице без доступа на запись.

Можем считывать лишние байты в input-буфере до тех пор, пока лишние байты расположены в нём целиком. Но в нашем случае мы почти всегда можем писать лишние байты. При тех же условиях мы можем записать лишние байты в output-буфер — потому что на следующей итерации мы их всё равно перезапишем.

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

inline void copy8(UInt8 * dst, const UInt8 * src)
{ memcpy(dst, src, 8); /// На самом деле здесь memcpy не вызывается.
} inline void wildCopy8(UInt8 * dst, const UInt8 * src, UInt8 * dst_end)
while (dst < dst_end);
}

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

В цикле два копирования — литерала и матча. Впрочем, всё равно есть некоторые тонкости. При копировании матча проверка не выполняется, но в самой спецификации формата LZ4 есть условия, которые позволяют её избежать: Но при использовании функции LZ4_decompress_fast (вместо LZ4_decompress_safe) проверка выполняется один раз — когда нам нужно скопировать литерал.

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.

Специально подобранные входные данные могут вызвать «проезд» по памяти. Если вы используете функцию LZ4_decompress_fast, вам нужна защита от плохих данных. Сжатые данные надо по крайней мере чек-суммировать. А если вам нужна защита от злоумышленника, то используйте функцию LZ4_decompress_safe. Другие варианты: берите криптографическую хэш-функцию в качестве чек-суммы, но это почти наверное убьёт всю производительность; либо выделяйте больше памяти для буферов; либо выделяйте память для буферов отдельным вызовом mmap и создайте guard page.

Можно копировать по 16 байт, используя SSE-регистры: Когда я вижу код, который копирует данные по 8 байт, сразу спрашиваю — а почему именно по 8 байт?

inline void copy16(UInt8 * dst, const UInt8 * src)
{
#if __SSE2__ _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), _mm_loadu_si128(reinterpret_cast<const __m128i *>(src)));
#else memcpy(dst, src, 16);
#endif
} inline void wildCopy16(UInt8 * dst, const UInt8 * src, UInt8 * dst_end)
{ do { copy16(dst, src); dst += 16; src += 16; } while (dst < dst_end);
}

Аналогично работает копирование 32 байт для AVX и 64 байт для AVX-512. Кроме того, можно развернуть цикл в несколько раз. Если вы когда-нибудь смотрели, как реализована memcpy, то в ней именно такой подход. (Кстати, компилятор в данном случае не будет ни разворачивать, ни векторизовывать цикл: это потребует вставки громоздких проверок.)

Во-первых, неочевидно, лучше это или хуже. Почему в оригинальной реализации LZ4 так не сделано? Вдруг они все короткие и лишняя работа будет ни к чему? Результат зависит от размеров фрагментов, которые нужно копировать. А во-вторых, это рушит те условия в формате LZ4, которые позволяют избежать лишнего бранча во внутреннем цикле.

Тем не менее, будем пока держать этот вариант в уме.

Хитрые копирования

Вернёмся к вопросу — всегда ли можно таким образом копировать данные? Предположим, нам нужно скопировать матч — то есть скопировать фрагмент памяти из output-буфера, находящийся на некотором смещении позади от курсора, в позицию этого курсора.

Представим простой случай — нужно скопировать 5 байт по смещению 12:

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

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

То есть он частично указывает на данные, которые ещё не были записаны в output-буфер. Но есть более сложный случай — когда нам нужно скопировать фрагмент памяти, длина которого больше смещения.

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

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

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

Функция memcpy не подходит для того, чтобы его скопировать: она не поддерживает случай, когда диапазоны фрагментов памяти пересекаются. В процессе сжатия у нас есть все данные, и такой матч вполне может найтись. Копировать нужно так же, как если бы мы копировали побайтово. Кстати, функция memmove тоже не подходит, потому что фрагмент памяти, откуда нужно брать данные, ещё не полностью инициализирован.

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

В оригинальной реализации LZ4 для этого написан удивительно непонятный код: То есть мы должны создать повторяющуюся последовательность.

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;

Мы копируем первые 4 байта побайтово, смещаемся на какое-то магическое число, копируем следующие 4 байта целиком, смещаем указатель на match на другое магическое число. Автор кода (Ян Коллет) по какой-то нелепой причине забыл оставить комментарий, что это значит. К тому же имена переменных запутывают. Обе называются dec...table, но одну из них мы прибавляем, а другую — вычитаем. Кроме того, ещё одна из них имеет тип unsigned, а другая — int. Впрочем, стоит отдать должное: как раз недавно автор улучшил это место в коде.

Копируем первые 4 байта побайтово: Вот как на самом деле это работает.

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

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

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

Можно продолжить как обычно, копируя 8 байт сразу:

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

Вот что получилось: Как вы знаете из опыта, иногда лучший способ понять код — это переписать его.

inline 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 for unknown reason. 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];
}

Производительность, конечно же, не изменилась никак. Впрочем, я очень хотел попробовать оптимизацию, в которой обычное копирование — сразу по 16 байт.

Копирование (начала) пересекающихся диапазонов для случая 16-байтных копирований выглядит так: Но это усложняет «особый случай» и приводит к тому, что он вызывается чаще (условие offset < 16 выполнено не реже, чем offset < 8).

inline 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-инструкция, ведь мы всего лишь хотим записать 16 байт, которые целиком состоят из нескольких байт входных данных (от 1 до 15). Их, в свою очередь, нужно просто повторить в правильном порядке.

Она принимает два 16-байтных регистра. Такая инструкция есть — она называется pshufb (от слов packed shuffle bytes) и входит в SSSE3 (три буквы S). В другом — «селектор»: в каждом байте записано число от 0 до 15 — в зависимости от того, из какого байта исходного регистра взять результат. В одном регистре содержатся исходные данные. Или, если значение байта селектора больше 127 — заполнить соответствующий байт результата нулём.

Вот пример:

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

Каждый байт результата мы заполнили выбранным нами байтом исходных данных — это как раз то что надо! Вот как выглядит код в результате:

inline void copyOverlap16Shuffle(UInt8 * op, const UInt8 *& match, const size_t offset)
{
#ifdef __SSSE3__ static constexpr UInt8 __attribute__((__aligned__(16))) masks[] = { 0, 1, 2, 1, 4, 1, 4, 2, 8, 7, 6, 5, 4, 3, 2, 1, /* offset = 0, not used as mask, but for shift amount instead */ 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<const __m128i *>(match)), _mm_load_si128(reinterpret_cast<const __m128i *>(masks) + offset))); match += masks[offset]; #else copyOverlap16(op, match, offset);
#endif
}

Здесь _mm_shuffle_epi8 — это intrinsic, разворачивающийся в инструкцию pshufb.

Ведь SSSE3 — очень старый набор инструкций, существующий с 2006 года. Можно ли сделать такую операцию для большего числа байт сразу, используя более новые инструкции? Она называется уже не packed shuffle bytes, а vector permute bytes — слова другие, а смысл такой же. В AVX2 есть инструкция, которая делает это сразу для 32 байт, но только независимо для отдельных 16-байтных фрагментов. Похожие инструкции также есть в ARM NEON — они называются vtbl (vector table lookup), но позволяют записывать только 8 байт. В AVX-512 VBMI есть ещё одна инструкция, работающая сразу для 64 байт, но процессоры с её поддержкой появились совсем недавно.

Он как раз подходит для замены исходного варианта кода. Кроме того, существует вариант инструкции pshufb с 64-битными MMX-регистрами, чтобы сформировать 8 байт. Правда, вместо неё я решил всё равно использовать вариант, работающий с 16 байтами (по серьёзным причинам).

На конференции Highload++ Siberia после моего доклада ко мне подошёл слушатель и сказал, что для случая 8 байт можно просто использовать умножение на специально подобранную константу (также потребуется сдвиг) — я об этом раньше даже не думал!

Как убрать лишний if

Допустим, я хочу использовать вариант, копирующий по 16 байт. Как избежать необходимости дополнительной проверки выхода за границы буфера?

В комментарии к функции будет написано, что разработчику следует выделить кусок памяти на указанное количество байт больше, чем требуется, чтобы позволить нам читать и писать туда ненужный мусор. Я решил, что вообще не буду делать эту проверку. Интерфейс функции станет неудобным, но это уже другие проблемы.

Допустим, данные, которые нам надо разжимать, были сформированы из блоков по 65 536 байт. Впрочем, могут возникнуть негативные последствия. Но с новым интерфейсом функции пользователь будет обязан выделить фрагмент памяти, например, из 65 551 байта. Тогда пользователь даёт нам фрагмент памяти размером 65 536 байт для разжатых данных. Если же аллокатор очень плохой, он может внезапно перестать кэшировать фрагмент памяти у себя в «куче» и начать каждый раз использовать mmap для выделения памяти (либо освобождать память с помощью madvice). Тогда аллокатор, вполне возможно, будет вынужден на самом деле выделить 96 или даже 128 килобайт — в зависимости от его реализации. В итоге маленькая попытка оптимизации может привести к тому, что всё начнёт тормозить. Такой процесс будет ужасно медленным из-за page faults.

Есть ли ускорение?

Итак, я сделал вариант кода, в котором применены три оптимизации:

  1. Копируем по 16 байт вместо 8.
  2. Используются shuffle-инструкции для случая offset < 16.
  3. Убран один лишний if.

Я стал тестировать этот код на самых разных наборах данных и получил неожиданные результаты.

67 GB/sec.
16 bytes, shuffle: 2. Пример 1:
Xeon E2650v2, данные Яндекс.Браузера, столбец AppVersion.
reference: 1. 94 GB/sec (на 76% быстрее).

30 GB/sec.
16 bytes, shuffle: 1. Пример 2:
Xeon E2650v2, данные Яндекс.Директа, столбец ShowsSumPosition.
reference: 2. 91 GB/sec (на 20% медленнее).

Потом на других файлах увидел, что ничего не ускорилось. Сначала я увидел, что всё ускорилось на десятки процентов и успел обрадоваться. Я сделал вывод, что результаты зависят от коэффициента сжатия. Ещё на каких-то замедлилось, хоть и ненамного. Это естественно: чем больше коэффициент сжатия, тем больше средняя длина фрагментов, которые нужно копировать. Чем больше сжат файл — тем больше преимущество от перехода на 16 байт.

Чтобы лучше разобраться, я с помощью шаблонов C++ сделал варианты кода для четырёх случаев: оперируем 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)

На разных файлах выигрывали совершенно разные варианты кода, но при тестировании на рабочем компьютере вариант с shuffle всегда выигрывал. На рабочем компьютере тестировать неудобно, приходится делать так:

sudo echo 'performance' | tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
kill -STOP $(pidof firefox) $(pidof chromium)

Потом я пошёл на один из старых «разработческих» серверов (c процессором Xeon E5645), достал ещё больше наборов данных и получил почти диаметрально противоположные результаты, которые меня окончательно запутали. Выяснилось, что выбор оптимального алгоритма определяется не только коэффициентом сжатия, но и моделью процессора. От неё зависит то, когда лучше использовать shuffle-инструкцию, а также порог, начиная с которого лучше использовать 16-байтные копирования.

Кстати при тестировании на серверах имеет смысл делать так:

sudo kill -STOP $(pidof python) $(pidof perl) $(pgrep -u skynet) $(pidof cqudp-client)

Иначе результаты будут нестабильными. Также следите за thermal throttling и power capping.

Как выбрать лучший алгоритм

Итак, у нас есть четыре варианта алгоритма, и нужно в зависимости от условий выбирать лучший. Можно было бы создать репрезентативный набор данных и железа, затем провести хорошее нагрузочное тестирование и выбрать тот метод, который лучше в среднем. Но у нас нет репрезентативного набора данных. Для тестирования я взял выборку данных Метрики, Директа, Браузера и авиаперелётов в США. Но этого недостаточно: ClickHouse используется сотнями компаний по всему миру, и переоптимизировав его на одном наборе данных, мы можем не заметить падения производительности с другими данными. А если результаты зависят от модели процессора, придётся явно вписывать условия в код и тестировать его на каждой модели (либо смотреть справочные данные по таймингам инструкций — как считаете?). В любом случае это слишком трудоёмко.

Это «многорукие бандиты». Тогда я решил использовать другой метод, который очевиден для коллег, которые не зря учились в ШАДе. Суть в том, что вариант алгоритма выбирается случайным образом, а затем мы на основе статистики начинаем чаще выбирать те варианты, которые хорошо себя показали.

То есть нужны независимые вызовы функции разжатия данных. У нас есть много блоков данных, которые нужно разжать. Такая операция обычно ничего не стоит по сравнению с обработкой блока данных — а в ClickHouse блок несжатых данных составляет минимум 64 КБ. Мы можем для каждого блока выбирать какой-нибудь из четырёх алгоритмов и измерять время его работы. (Прочтите статью про измерение времени.)

Это аналогия с автоматами в казино, у которых есть несколько ручек, которые можно дёрнуть, чтобы получить какое-то случайное количество денег. Чтобы понять, как конкретно работает алгоритм «многорукие бандиты», узнаем, почему он так называется. У каждой ручки есть фиксированное соответствующее ей вероятностное распределение количества выдаваемых денег, но игрок его не знает и может лишь оценить его, исходя из опыта игры. Игрок может много раз дёргать ручки в любой выбираемой им последовательности. Тогда он сумеет максимизировать свою выгоду.

Затем в уме «разыгрываем» случайный выигрыш для каждой ручки, основываясь на полученных распределениях. Один из подходов к максимизации выигрыша состоит в том, чтобы на каждом шаге оценивать вероятностное распределение для каждой ручки, исходя из статистики игры на предыдущих шагах. Этот подход называется Thompson Sampling. И затем дёргаем ту ручку, для которой разыгранный в уме исход оказался лучше.

Результат — время работы в пикосекундах на байт: чем меньше, тем лучше. Мы, в свою очередь, должны выбрать алгоритм разжатия. Чтобы оценивать распределение случайной величины, надо использовать методы математической статистики. Будем считать время работы случайной величиной и оценивать её распределение. Можно использовать параметрический подход — сказать, что случайная величина принадлежит какому-то семейству случайных величин, зависящих от параметров; и затем оценивать эти параметры. Для таких задач часто используют байесовский подход, но было бы неэффективно вписывать сложные формулы в код на C++.

Для примера мы могли бы считать, что время выполнения кода имеет нормальное распределение. Как выбрать семейство случайных величин? Во-первых, время выполнения не может быть отрицательным, а нормальное распределение принимает значения на всей числовой прямой. Но это абсолютно неверно. Во-вторых, время выполнения, как я предполагаю, имеет большой «хвост» справа.

Причина в том, что необходимая оценка матожидания и дисперсии выполняется очень просто, а после достаточного количества итераций нормальное распределение станет более-менее узким, не сильно отличающимся от распределений, которые мы бы получили другими методами. Впрочем, есть факторы, исходя из которых использовать оценку нормального распределения лишь для целей Thompson Sampling — неплохая идея (даже несмотря на то, что распределение искомой величины заведомо не является нормальным). Если нас не очень сильно интересует скорость сходимости на первых шагах, то такими деталями можно пренебречь.

Из опыта известно, что среднее время выполнения запроса, загрузки сайта и так далее представляет собой «мусор», который не имеет смысла вычислять. С одной стороны, это несколько «невежественный» подход. Но это несколько сложнее, и как я покажу дальше, для практических целей описанный метод себя оправдывает. Лучше было бы вычислять медиану — робастную статистику.

Сначала я реализовал расчёт матожидания и дисперсии, а потом решил, что это слишком хорошо, и нужно упростить код, чтобы получилось «хуже»:

/// For better convergence, we don't use proper estimate of stddev.
/// We want to eventually separate between two algorithms even in case
/// when there is no statistical significant difference between them.
double sigma() const
{ return mean() / sqrt(adjustedCount());
} double sample(pcg64 & rng) const
{ ... return std::normal_distribution<>(mean(), sigma())(rng);
}

Я написал всё так, чтобы первые несколько итераций не учитывались — чтобы исключить эффект memory latencies.

Получилась тестовая программа, которая умеет сама подбирать лучший алгоритм на входных данных, а в качестве дополнительных режимов работы — использовать референсную реализацию LZ4 либо фиксированный вариант алгоритма.

Таким образом, есть шесть вариантов работы:
— reference (baseline): оригинальный LZ4 без наших модификаций;
— variant 0: копировать по 8 байт, не использовать shuffle;
— variant 1: копировать по 8 байт, использовать shuffle;
— variant 2: копировать по 16 байт, не использовать shuffle;
— variant 3: копировать по 16 байт, использовать shuffle;
— «бандитский» вариант, который сам во время работы выбирает лучший из четырёх перечисленных оптимизированных вариантов.

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

Если результат сильно зависит от модели CPU, было бы любопытно изучить, как именно. Может быть, на некоторых CPU разница особенно большая?

И посмотрел, какие CPU у серверов, на которых я могу запустить бенчмарки. Я подготовил набор датасетов из разных таблиц в ClickHouse с реальными данными, всего 256 разных файлов по 100 МБ несжатых данных (число 256 просто совпало). 60GHz
— Intel® Xeon® CPU E5-2660 v4 @ 2. Я нашёл серверы с такими CPU:
— Intel® Xeon® CPU E5-2650 v2 @ 2. 20GHz
— Intel® Xeon® CPU E5645 @ 2. 00GHz
— Intel® Xeon® CPU E5-2660 0 @ 2. 10GHz
— Intel® Xeon® CPU E5530 @ 2. 40GHz
— Intel Xeon E312xx (Sandy Bridge)
— AMD Opteron(TM) Processor 6274
— AMD Opteron(tm) Processor 6380
— Intel® Xeon® CPU E5-2683 v4 @ 2. 83GHz
— Intel® Xeon® CPU E5-2667 v2 @ 3. 40GHz
— Intel® Xeon® CPU E5440 @ 2. 30GHz

Для них мои SIMD-оптимизации надо потребовалось немного переделывать. Дальше самое интересное — процессоры, предоставленные отделом R&D:
— AMD EPYC 7351 16-Core Processor — новый серверный процессор AMD.
— Cavium ThunderX2 — а это вообще не x86, а AArch64. На сервере определяется 224 логических и 56 физических ядер.

Получается 199 680 результатов, и их можно сравнивать. Всего 13 серверов, на каждом из которых запускается тест на 256 файлах в 6 вариантах (reference, 0, 1, 2, 3, adaptive), причём тест запускаем 10 раз, чередуя варианты вперемешку.

Но не стоит делать поспешные выводы из этих результатов: мы тестируем только алгоритм разжатия LZ4 на одном ядре (очень узкий кейс — получается микробенчмарк). Например, можно сравнить разные CPU между собой. Но я тестировал на нём сам ClickHouse, и он «рвёт» Xeon E5-2650 v2 на тяжёлых запросах за счёт превосходства по количеству ядер, даже несмотря на отсутствие многих оптимизаций, которые в ClickHouse делаются только для x86. К примеру, у Cavium самое слабое ядро.

┌─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.20 │ 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 │
└───────────────────────┴──────┴───────┴──────┴──────┴─────────────┴───────────┴────────────────┘

ref, adapt, max — это скорость в гигабайтах в секунду (величина, обратная к среднему арифметическому времени по всем запускам на всех наборах данных). best — номер лучшего алгоритма среди оптимизированных вариантов, от 0 до 3. adapt_boost — относительное преимущество адаптивного алгоритма по сравнению с baseline. max_boost — относительное преимущество лучшего из неадаптивных вариантов по сравнению с baseline. adapt_over_max — относительное преимущество адаптивного алгоритма по сравнению с лучшим неадаптивным.

Даже на ARM мы получили плюс 4%, несмотря на то, что мы уделили меньше внимания оптимизации под эту архитектуру. Как видно, на современных процессорах x86 мы смогли ускорить разжатие на 12–20%. Также заметно, что в среднем по разным наборам данных «бандитский» алгоритм выигрывает у выбранного наперёд лучшего варианта на всех процессорах кроме очень старых Intel.

Выводы

На практике проделанная работа имеет сомнительную полезность. Да, само разжатие LZ4 ускорилось в среднем на 12–20%, а на отдельных наборах данных есть даже более чем двухкратный прирост производительности. Но в целом на время выполнения запроса это влияет существенно меньше. Не так легко найти настоящие запросы, на которых преимущество в скорости будет более пары процентов.

Стоит иметь в виду, что на нескольких кластерах Метрики, предназначенных для выполнения «длинных» запросов, мы решили использовать ZStandard level 1 вместо LZ4: на холодных данных важнее экономить IO и место на дисках.

Но специально для этого сценария у нас разработано отдельное решение, которое позволяет ускорить такие запросы на порядки. Наибольшие преимущества от оптимизации разжатия наблюдаются на сильно сжимающихся данных — например, на столбцах с повторяющимися строковыми значениями.

LZ4 использует очень хороший формат, но у Lizard, Density и LZSSE другие форматы, которые могут работать быстрее. Ещё одно полезное соображение: оптимизация скорости алгоритма сжатия часто ограничена форматом сжатых данных. Возможно, вместо попыток ускорить LZ4 было бы лучше просто подключить LZSSE к ClickHouse.

На самом деле это очень частый случай при улучшении алгоритмов: оптимизации не укладываются в старые абстракции, требуют их пересмотра. Внедрение этих оптимизаций в саму библиотеку LZ4 маловероятно: для их использования нужно изменить или дополнить интерфейс библиотеки. Например, в части inc- и dec-таблиц теперь всё правильно. В то же время в оригинальной имплементации уже сейчас исправлено довольно много названий. Мы и сами пробовали вариант с 32 байтами — результаты получились не такими классными, но в целом ускорение тоже есть. Кроме того, несколько недель назад оригинальная имплементация ускорила разжатие на те же 12–15% с помощью копирования по 32 байта, а не по 16, как указано выше.

Ускорение этих двух операций полезно для слабо сжимающихся данных, так как они производятся над сжатыми данными. Если посмотреть на профиль в начале статьи, можно заметить, что мы могли бы убрать одно лишнее копирование из page cache в userspace (либо с помощью mmap, либо с помощью O_DIRECT и userspace page cache — оба варианта сопряжены с проблемами), а также немного улучшить вычисление чек-сумм (сейчас используется CityHash128 без CRC32-C, а можно взять HighwayHash, FARSH или XXH3).

Вот видео с HighLoad++ Siberia, а вот презентация. В любом случае, изменения уже добавлены в master, а полученные в результате этого исследования идеи нашли применение в других задачах.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть