Yappy!

Компания google выложила библиотечку компрессии snappy http://code.google.com/p/snappy/. Библиотечка сжимает и разжимает со скоростью работы  SSD дисков, правда коэффициент компрессии не фонтан, хуже gzip. Но с дурацкими lzo, quicklz и прочей шушерой вполне сравнима.

Сразу захотелось поглядеть внутрь, что там. Внутри вариации на тему lz, 70 годы прошлого века.  Отсюда  поинт – вечное не тухнет. Что такое lz? Это две команды. Первая команда “прочитай N байт из потока и положи в буфер распаковки”, вторая команда “прочитай из буфера распаковки по смещению OFFSET от текущей позиции MATCH байт и опять положи в буфер распаковки”.

Компрессор snappy так и жмет примерно.  Он умеет кодировать OFFSET с помощью 1, 2 или 4 байт.

Сразу захотелось написать свое. Выходные, все такое. Решил, что мой код будет еще проще. Буду кодировать OFFSET с помощью 1 байта, всегда. А методу распаковки выдам лимит в 32 строчки С++ кода.

Родилось вот такое: http://www.everfall.com/paste/id.php?o3ug124i2l7p . Назовем его yappy.

Код распаковки там со строчки 14 по 45. Кроме распаковки там нет ничего интересного. Разве что эвристика, как выбираются 224 разных значения пар [OFFSET / 256: MATCH].

Сразу захотелось измерить пипиську творению.

Возьмем тестовые данные от snappy,  положим их без компрессии в tar архив, сожмем.

SNAPPY: [b 4096K] bytes 4638720 -> 2165687 46.7%  comp 214.9 MB/s  uncomp 683.6 MB/s

SNAPPY: [b 4K] bytes 4638720 -> 2445428 52.7%  comp 226.9 MB/s  uncomp 681.2 MB/s

За буковкой b идет размер блока в килобайтах. А теперь сожмем yappy:

YAPPY: [b 4096K] bytes 4638720 -> 2021663  43.6%  comp  49.2 MB/s  uncomp 1432.3 MB/s

YAPPY: [b 4K] bytes 4638720 -> 2268955  48.9%  comp  49.2 MB/s  uncomp 1476.1 MB/s

Видно две вещи. Вещь первая – что google выложил неудачные тестовые данные. Они слишком короткие, чтобы snappy со своими смещениями в 2 и 4 байта мог развернуться. Очевидно, что на больших продакшн данных все должно сжиматься лучше. Вещь вторая, что программисты google кабаны, они сделали чертовски быструю компрессию.  Собственно, ради чего все и затевалось – чтобы быть всюду быстрее сети и диска.

А теперь… Возьмем одну из компонент продакшн индекса в Яндексе. Она блочная, блоки по 4k. Готовится оффлайн, время компрессии нас не очень волнует.

Сожмем snappy и yappy.

SNAPPY: [b 4K] bytes 1328385387 -> 750585721 56.5%  comp 182.2 MB/s  uncomp 623.4 MB/s

YAPPY: [b 4K] bytes 1328385387 -> 686910077  51.7%  comp  48.5 MB/s  uncomp 1399.8 MB/s

Отсюда  мораль. Тырьте хорошие идеи, тырьте у грандов. И, вдруг, получите немножко технического экселенса, который приятен.