Сегодня начинается двухнедельный марафон постов. Я каждый день постараюсь писать

Question

Сегодня начинается двухнедельный марафон постов. Я каждый день постараюсь писать

что-то содержательное. Ибо накопилось, а мотивации сдампить нет. Плана тоже нет. Как будет ехать, так и поедет.

1.

Я в апреле прошлого года писал про то, что мы собираемся менять стандартную сортировку в LLVM.

Как обычно, после 8 месяцев ревью, мы всё таки закоммитили это после консультации с Android+Chrome командой и с Meta. Ура, в LLVM 16 будет новая сортировка. Примерно по скорости как pdqsort, быстрее для больших типов из-за меньшего кол-ва сравнений на рандомных данных.

2.

Я в последнее время занимался очень много компрессией данных. Хочется рассказать историю. В Google работает человек, который придумал brotli -- такой алгоритм сжатия (https://github.com/google/brotli), который использовался в Google, чтобы переехать с zlib в году так 2013. Как примерно и все разработчики алгоритмов сжатия, выглядит это всё в ретроспективе странно, идеи были взяты из теории, обсуждения на https://encode.su/ и так далее. Алгоритм сам по себе неплохой, только вот автор (jyrki@) кажется сильно огорчился, когда вышла zstd. zstd хоть и сама вышла после обсуждения на encode.su.

Спустя несколько лет, мы в Google переехали на zstd, потому что он

* Намного быстрее разжимает
* Лучше поддерживается
* Намного приятнее общаться с автором хоть автор zstd работает в Meta
* Начинает выигрывать у brotli

Почему начинает? Мы хоть и знаем всякое энтропийное кодирование, но у brotli есть ещё контекстное моделирование -- храним больше информации о том какие зависимости между символами. Zstd обходится намного более простыми техниками как алгоритм Хаффмана и ANS системы. Тем самым у brotli больше информации для сжатия и сжимать он должен лучше.

Только это вот не правда для lvl1-4, которые самые распространнённые в мире из-за того, что они сжимают хотя бы 75MB/s. Даже какой-то бенчмарк это показывает (раз, два, три). Я смог выбить лучше rate у brotli при достаточно высоких левелах, но скорость разжатия оставляет желать лучшего (3x от zstd). Фактически brotli лучше для round-trip на высоких левелах и если данные вообще не трогать. Но высокие левела это уже сжатие в 10MB/s, что просто не очень :)

Jyrki любит ходить в комментарии на HN, очень расстраивается, когда его поделие основанное на brotli JPEG XL убирают из Chrome.

Правда в том, что в Facebook всё на zstd, Amazon S3 на zstd, в Google (мне разрешили признаться) мы используем zstd в 15 раз больше, чем brotli. Brotli остался хоть и хорошим решением, которое появилось до zstd, сейчас оно проигрывает почти по всем фронтам. Brotli почти никак не развивается и просто уходит немного в серую даль.

Плохо только то, что мне сейчас приходится работать с Jyrki для переезда последнего крупного клиента brotli на zstd. И это просто ад, чтобы доказать, что brotli надо закопать. Коммуникация и эскалация помогают. С цифрами спорить сложно, но когда есть зацепиться хоть к одной цифре, человек за неё цепляется. Кажется людям сложно отпустить своё поделие. Понимаю, наверное, мне тоже было бы сложно.

Используйте zstd, библиотека получше поддерживается, чем наш старый brotli. Никаких чувств, что наша компания сделала что-то хуже, чем соперник, в итоге всё равно в open source же :)