Комментарии 18
СтОит ли экономия менее чем одного процента некоторой потери прозрачности формата? Не уверен.
СтОит ли потери совместимости? Уверен, что нет.
Я и не думаю что надо менять оригинальный varint на compact varint по умолчанию. Если его таки захотят принять то отельными дополнительными функциями. Тогда для compact varint будут новые обозначения в протобуфере (например: uint64c, int64c). По сути запись такая же как и у varint только значение получаем чуть чуть по другому. Старшие биты теперь указывают не только размер контейнера но и его начальное значение.
И экономия в процентах маленькая а в числах огромная. 1 из 9 это больше 10 процентов.
Вы считаете криво. 1 из 9 на маленьком диапазоне — это в среднем меньше одного процента (байт кодирует 128 значений, а не 127 — причём это касается не всех 8 байт).
А вообще, что касается эффективности — попробуйте мыслить иначе. Представьте ваш вариант varint как арифметическое кодирование. Так вот, чтобы оно было оптимальным — надо угадать вероятности однобайтовых, двухбайтовых и т.д. чисел. Может статься, оптимальным будет резать на группы по два байта. Или, напротив, по 4 бита. Или использовать дифференциальное кодирование. Короче, если ещё немного усложнить — ваш энкодер тоже можно обойти. Так что есть резон оставить всё, как есть (предельно просто), а при необходимости жать данные — использовать алгоритм, который даст бОльший выигрыш.
Так я вроде не сильно усложнил исходя из изменений кода. Может просто коряво объяснил?
Покажите в каком месте я считаю криво а то я вас плохо понимаю.
В 8 байтах мы экономим 1 из 9 байт (11%) на диапазоне значений от 72057594037927936 до 72624976668147839 ( 0.7% но 567 382 630 219 904 зничений) по сравнению с оригинальным varint. И это без учета экономии на других диапазонах.
В первых 2х байтах мы экономим 1 байт из 3 (33%) на диапазоне значений от 16384 до 16511 (те же 0.7% но всего 128 значений) по сравнению с оригинальным varint.
В 8 байтах экономим 11% на очень узком диапазоне значений — менее 1% от всего диапазона. Итого в среднем — менее 0.1%, не из за чего суетиться. На 2 байтах экономия заметнее, но всё равно ни о чём...
Даже если взять ваш 0.1% и примерить к 100ГБ данных то получаем 100МБ экономии по простому. И это при условии что постояно используются огромные числа которые нельзя записать меньшим количеством байт.
Даже если взять ваш 0.1% и примерить к 100ГБ данных то получаем 100МБ экономии по простому.0.1% — это 0.1%. От чего его не бери. Да, от 100 рублей это будет 10 копеек, а от миллиарда — аж прямо миллион… но компания, платящая за что-то миллиард вряд ли откажется от сделки, если она будет на миллион дороже… или ухватится если она будет на миллион дешевле.
Идея не только в экономии байт но и большей жёсткости формата. 1 значение = определённый набору байт без вариантов.
Определённый хеш от числа.
В статье используется код из оригинального golang/protobuf с мелкими но важными изменениями. Оба варианта(мой и оригинальный) используют минимально возможное для алгоритма количество байт для записи числа.
В оригинальном varint проблема не только для нуля. Любое число можно записать используя большее количество байт чем для него необходимо.
Это можно сделать намерянно. Тогда при перегоне из протобуфера в протобуфер потеряется хвост и хеш данных изменится. Может вскроются другие уязвимости которые возникнут из за этой разницы.
Дополнил код для вычисления разницы. Результаты под спойлером ниже.
Вычисляется объем необходимый для записи всех значений до заданного и выводится статистика разницы между старым и новым вариантом.
Экономим от 0.38% (128 B) на маленьких числах до 0.09% (520 TB) на больших. На 9 байтах результат 0.7% но не уверен что это правильно.
Если где ошибся подскажите.
Оказывается Git давно использует свой вариант compact varint. Добавил к статье послесловие в котором разобрал различия алгоритмов.
Compact varint — уникальность и большие значения за ту же стоимость