Publish: @IronPeter про вариант varint с Хаффманом

Тем временем, у нас на Кружочках происходит много разного – сделали поиск, появились возможности знакомиться с людьми вне своего списка итд итп, но самое главное – случаются интересные дискуссии. Некоторые из них, по понятным причинам, публиковать нельзя, а некоторыми народ соглашается поделиться (спасибо, Петя!).

В сегодняшей серии @IronPeter рассказывает про интересный вариант varint.

Simon Kozlov: @All
Выясняю последствия наличия сотен тысяч кубиков
Файл на 200K кубиков занимает пол-гигабайта
Открывается две минуты
При запуске локального клиента и сервера клиент валится с таймаутом, потому что все это не успевает загрузиться за две минуты
А так-то можно 700K

AND: reply @Simon Kozlov
это как?

Simon Kozlov: reply @AND
А вот!
XML!
Со всеми пропертями кубика!

IronPeter: reply @Simon Kozlov
потому что правильный формат – это протобуф!

Crio: reply @IronPeter
чем он лучше своего велосипеда в его случае? кроме автоматической генерации сереализаторов и встроенного контроля версий.

IronPeter: reply @Crio
зависит от своего велосипеда, может и не быть лучше.
Я вот недавно сделал забавный proto-buf like велосипед, битовый, он хранит для каждого поля табличку Хаффмана, которой сжимается.
охуенно жмет, но описание схемы включает в себя таблички Хаффмана. И чуть тормозной.

Crio: reply @IronPeter
дак заебись же, оверхеда на хранение табличек нету ведь. А чего тормозит?

IronPeter: reply @Crio
много действий надо. В самом Хаффмане условных переходов нет, но зато много всяких чтений и сдвигов. Зато есть высокоуровневая логика, с ифами.
хотя как поглядеть, оно распаковывает где-то наверное полгига в секунду на одном ядре в стандартных условиях (половина полей нули и распаковывать не надо).
Я кстати понял, как правильно Хаффмана надо готовить.

aruslan: reply @IronPeter
расскажи!

IronPeter: reply @aruslan
Все очень просто. Одно значение в дереве Хаффмана – одно кодируемое значение. Это неудобно, когда кодируемых значений много. Большая табличка (иногда на ui32), неудобно тем, что длина префикса большая.
Хочется, чтобы длина префикса была фиксирована.
скажем, меньше 8 бит.
или 6.
чтобы лукапом взять и узнать собственно huffman entry.
Окей. Но тогда huffman entry пусть кодирует не одно число, а range. Т.е. после префикса p лежат еще N бит.
и такая entry кодирует интервал [huffmanValue, huffmanValue + 2 ** N)

aruslan: reply @IronPeter
huffmanValue – это в смысле код, не значение?

IronPeter: reply @aruslan
значение.
ну вот представь, что у тебя есть поток данных со статистикой 1000500 + RAND(1024)

aruslan: reply @IronPeter
ммм, т.е. ты квантизируешь входные значения в ranges, ranges упаковываешь, получаешь Хаффмана плюс дельты, так?

IronPeter: reply @aruslan
такой поток данных кодируется 10 битами.
я представляю поток данных в виде объединения (не обязательно непересекающегося) десятка-другого таких потоков.

aruslan: reply @IronPeter
да, понял.

IronPeter: reply @aruslan
вот оказывается, что реальные статистики очень хорошо приближаются таким образом.

aruslan: reply @IronPeter
а для тупых — комбо предиктор или моделирование какое-нибудь + хаффман => де-хаффман + депредиктор/демоделлер — оно не такое же получится?

IronPeter: reply @aruslan
это исключительно для того, чтобы снизить длину префикса в Хаффмане и упростить распаковку. Больше не за чем.
вдруг оказывается, что 6 бит заглаза хватает.

aruslan: reply @IronPeter
а что конкретно у тебя в сжатом потоке идёт в случае 1000500+RAND(1024)?

IronPeter: reply @aruslan
префикс хаффмана для этого случая и 10 бит

aruslan: reply @IronPeter
а, правильно, 10 бит ты все равно сжать не сможешь ибо RAND, угу, тупил
прикольно
как ты выбираешь ширину range?
оно потоковое, правильно? т.е. ты адаптируешься пока строишь и пока декомпрессируешь? или оно статическое?

IronPeter: reply @aruslan
статическое

http://www.everfall.com/paste/id.php?2xkmk0vfmwwi

распаковка примерно такая

aruslan: reply @IronPeter
а, вижу. 6 бит и пизда.
и 6 бит – это из предварительного человеческого анализа потока? :)

IronPeter: reply @aruslan
ну вот достаточно. А анализ машинный, то есть по потоку строится не более 64 разных val + ranges.

aruslan: reply @IronPeter
угу. круто!

IronPeter: reply @aruslan
оно плюс-минус хорошее, потому что например покрывает varint.

aruslan: reply @IronPeter
да-да.

Simon Kozlov: reply @IronPeter
Можно вот про varint подробнее?
Что значит покрывает? Что такое varint?

IronPeter: reply @Simon Kozlov
покрывает – включает в себя. Это кодировка, когда мы берем первый байтик и считаем единичные биты, пока не наткнемся на нулевой.
насчитали n бит, код содержит n + 1 байт.
из этих n + 1 байт n + 1 бит занят префиксом Хаффмана ( n единиц и 1 нуль), остальное – значащие биты.

Simon Kozlov: reply @IronPeter
А, то есть range для varint автоматически используется для битности префикса Хаффмана?

IronPeter: reply @Simon Kozlov
Нееееее. Это тупая схема, когда числа меньше 1 << 7 укладывают в байт
меньше 1 << 14 в 2 байта
меньше 1 << 21 в 3
и так далее
первый вариант кодируется битами 0 XXXXXXX, второй 1 0 XXXXXXXXXXXXXX, третий 1 1 0 XXXXXXXXXXXXXXXXXXXXX

Simon Kozlov: reply @IronPeter
> из этих n + 1 байт n + 1 бит занят префиксом Хаффмана ( n единиц и 1 нуль), остальное – значащие биты.
Я вот про эту фразу
В вот этих XXXXX же лежит хаффман + оффсет, да?

IronPeter: reply @Simon Kozlov
нет. Там живые биты лежат.
хаффман это 0, 1 0, 1 1 0, 1 1 1 0, etc

Simon Kozlov: reply @IronPeter
Ах
То есть вместо varint prefix у тебя хаффман-префикс
Догнал

IronPeter: reply @aruslan
ну и там одно из значений может быть 0 + rand(ui32_max), так что обучение может быть достаточно грубое.
т.е. мы не свалимся, если в табличке есть редкий но гарантированно мажорирующий все значения интервал.

Это произошло на #gamedeff