Внимание: Код представленный в статье немного отличается от оригинальных EncodeVarint и DecodeVarint и даёт другие результаты. Будьте внимательны.
В multiformats/unsigned-varint обсуждении правильной записи числа в varint было замечено что многие числа в оригинальном varint могут быть записаны в последовательности разной длинны. Это даст разные блоки и их хеши при идентичных значениях кодированных в протобуфер.
Оригинальный varint
Оригинальный varint просто делит число на кусочки по 7 бит. И записывает их в порядке от младшего к старшему добавляя к каждому кусочку старший 8ой бит. Значение этого бита зависит от того последний это кусочек (0) или нет (1).
Таким образом например значение 0 мы можем записать во многих вариантах:
0000 0000 (0x00)varint = 01000 0000 0000 0000 (0x8000)varint = 01000 0000 1000 0000 0000 0000 (0x808000)varint = 0
и так далее.
Compact varint
Я подумал что можно начинать значения контейнера большего размера от максимального значения предыдущего контейнера + 1. Ведь если мы используем контейнер такого размера то число должно быть больше максимума предыдущего контейнера.
Преимущества:
- Уникальное значение для каждого набора байт.
0000 0000 (0x00)varint = 01000 0000 0000 0000 (0x8000)varint = 1281000 0000 1000 0000 0000 0000 (0x808000)varint = 16 512
- Б`ольшие значения для набора байт того же размера.
- Для 2х байт максимум 16 511 что на 128 больше чем 16 383 у оригинального varint
- Для 8ми байт максимум уже на 567 382 630 219 904 больше
Кодируем в compact varint
Как я уже говорил выше код мало отличается от оригинала. Тут я всего лишь добавил одну строчку:
x -= 1И она дала уникальность и экономию.
func EncodeVarint(x uint64) []byte {
var buf [maxVarintBytes]byte
var n int
for n = 0; x > 127; n++ {
buf[n] = 0x80 | uint8(x&0x7F)
x >>= 7
x -= 1
}
buf[n] = uint8(x)
n++
return buf[0:n]
}Пример
300 = 000 0010 010 1100
отделяем первые 7 бит: "
uint8(x&0x7F),x >>= 7"
010 1100
добавляем к ним старший бит (1 поскольку есть ещё биты): "
0x80 |"
1 010 1100
вычитаем единицу из оставшегося: "
x -= 1"
(000 0010) - 1 = 000 0001
Это ключевое и единственное отличие от оригинального EncodeVarint. За счёт него мы можем записать большее значение в то же количество байт.
добавляем к ним старший бит (0 поскольку это последняя часть)
0 000 0001
- склеиваем
1 010 1100 ++ 0 000 0001 = 1 010 1100 0 000 0001
300 = 1010 1100 0000 0001 (0xAC01) compact varint
Декодируем compact varint
Расшифровка также не подверглась большим изменениям. Тут я изменил одну строку:
x |= (b & 0x7F) << shiftна
x += (b & 0xFF) << shiftfunc DecodeVarint(buf []byte) (x uint64, n int) {
for shift := uint(0); shift < 64; shift += 7 {
if n >= len(buf) {
return 0, 0
}
b := uint64(buf[n])
n++
x += (b & 0xFF) << shift
if (b & 0x80) == 0 {
return x, n
}
}
// The number is too large to represent in a 64-bit value.
return 0, 0
}Пример
число 300 в формате compact varint = 1 010 1100 0000 000 1 (0xAC01)
разделяем
1 010 1100 0000 000 1
добавляем нули или сдвигаем "
(b & 0xFF) << shift"
1 010 1100 = 0000 000 1 010 1100 0000 000 1 = 0000 000 1 000 0000
К первому байту мы просто добавили старших 7 нулей для выравнивания а второй байт сдвинули на 7 бит вперёд
(b & 0xFF) << shift. При этом старший бит сохраняется в отличие от оригинального varint.
теперь складываем "
x +="
0000 000 1 010 1100 + 0000 000 1 000 0000 = 0000 001 0 010 1100 > 256 + 32 + 8 + 4 = 300
Это ключевой момент отличия от оригинального DecodeVarint. Вместо операции "или" мы делаем сложение. За счёт сохранённого на предыдущем этапе старшего бита мы получаем больший результат.
Почему он более компактный:
Вычислим 2х байтовое максимальное значение
a := []byte{255,127} // 1111 1111 0111 1111 2х байтовое максимальное значение compact varint: 16511
закодировано: 1 111 1111 0111 111 1 (0xFF7F)
- разделяем
1 111 1111 0111 111 1 добавляем нули или сдвигаем
1 111 1111 = 0000 000 1 111 1111 0111 111 1 = 0111 111 1 000 0000
- складываем
0000 000 1 111 1111 + 0111 111 1 000 0000 = 1000 000 0 111 1111 = 16511
результат: 16511
2х байтовое максимальное значение оригинального varint: 16383
закодировано: 1 111 1111 0 111 1111 (0xFF7F)
разделяем
1 111 1111 0 111 1111
отбрасываем старший бит
111 1111 111 1111
- склеиваем биты
111 1111 ++ 111 1111 > 111 1111 111 1111 = 16383
Результат: 16383
разница между максимальными значениями: 16511 (compact varint) — 16383 (varint) = 128
Для 2х байт она не большая но экономит байт при значениях от 16384 до 16511 в сравнении с оригинальным varint.
Рассчитаем экономию для 8ми байтовой записи
// 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 0111 1111
a := []byte{255,255,255,255,255,255,255,127} 72624976668147839 ( максимальное значение для 8 байтового compact varint)
-
72057594037927935 ( максимальное значение для 8 байтового оригинального varint )
=
567382630219904 ( разница ) Тут мы экономим 9й байт на гораздо более значительном отрезке значений
Код для вычисления разницы:
Здесь вычисляется объем необходимый для записи всех значений до заданного и выводится статистика разницы между старым и новым вариантом.
package main
import (
"fmt"
)
func DecodeVarintDifference(buf []byte) (difference uint64, newVarint uint64, oldVarint uint64, n int) {
for shift := uint(0); shift < 64; shift += 7 {
if n >= len(buf) {
return 0, 0, 0, 0
}
b := uint64(buf[n])
n++
newVarint += (b & 0xFF) << shift
oldVarint |= (b & 0x7F) << shift
if (b & 0x80) == 0 {
return newVarint - oldVarint, newVarint, oldVarint, n
}
}
// The number is too large to represent in a 64-bit value.
return 0, 0, 0, 0
}
func convert(i uint64)(string){
v := []string{"B","KB","MB", "GB", "TB", "PB", "EB"}
l := 0
for ; i > 1024; i = i / 1024 {l++}
return fmt.Sprintf("(%d %s)",i, v[l])
}
func main() {
a := []byte{255,255,255,255,255,255,255,255,127}
var newByteCount, newStart, oldByteCount, oldStart uint64
for i := len(a) - 1; i >= 0; i-- {
difference, nVarint, oVarint, n := DecodeVarintDifference(a[i:])
newByteCount += (nVarint - newStart + 1) * uint64(n)
oldByteCount += (oVarint - oldStart + 1) * uint64(n)
fmt.Println("size:", n, "B")
fmt.Println()
fmt.Println(
"new start value:", newStart,
"\nnew max value:",nVarint)
fmt.Println()
fmt.Println(
"old start value:", oldStart,
"\nold max value:",oVarint)
fmt.Println()
fmt.Println("max value diff:", difference)
oldByteCountForSameRange := oldByteCount + ( difference * uint64(n + 1) )
sizeDifference := oldByteCountForSameRange - newByteCount
fmt.Println()
fmt.Println("for range from 0 to", nVarint)
fmt.Println("new varint data size:", newByteCount, "B", convert(newByteCount))
fmt.Println("old varint data size:", oldByteCountForSameRange, "B", convert(oldByteCountForSameRange))
fmt.Println("size differece:", sizeDifference, "B", convert(sizeDifference))
fmt.Println("percent from data size new:", float64(sizeDifference) / float64(newByteCount) * 100, "%")
fmt.Println("percent from data size old:", float64(sizeDifference) / float64(oldByteCountForSameRange) * 100, "%")
fmt.Println("average byte per value new:", float64(newByteCount) / float64( nVarint + 1 ) )
fmt.Println("average byte per value old:", float64(oldByteCountForSameRange) / float64( nVarint + 1 ) )
fmt.Println("-------------------------------------------------------")
fmt.Println()
newStart = nVarint
oldStart = oVarint
}
}Тестим на The Go Playground: https://play.golang.org/p/HPyb-sXMSjJ
size: 1 B
new start value: 0
new max value: 127
old start value: 0
old max value: 127
max value diff: 0
for range from 0 to 127
new varint data size: 128 B (128 B)
old varint data size: 128 B (128 B)
size differece: 0 B (0 B)
percent from data size new: 0 %
percent from data size old: 0 %
average byte per value new: 1
average byte per value old: 1
-------------------------------------------------------
size: 2 B
new start value: 127
new max value: 16511
old start value: 127
old max value: 16383
max value diff: 128
for range from 0 to 16511
new varint data size: 32898 B (32 KB)
old varint data size: 33026 B (32 KB)
size differece: 128 B (128 B)
percent from data size new: 0.38908140312481004 %
percent from data size old: 0.38757342699691155 %
average byte per value new: 1.9923691860465116
average byte per value old: 2.0001211240310077
-------------------------------------------------------
size: 3 B
new start value: 16511
new max value: 2113663
old start value: 16383
old max value: 2097151
max value diff: 16512
for range from 0 to 2113663
new varint data size: 6324357 B (6 MB)
old varint data size: 6340997 B (6 MB)
size differece: 16640 B (16 KB)
percent from data size new: 0.26310975171072726 %
percent from data size old: 0.2624193009395841 %
average byte per value new: 2.9921297803245928
average byte per value old: 3.0000023655604675
-------------------------------------------------------
size: 4 B
new start value: 2113663
new max value: 270549119
old start value: 2097151
old max value: 268435455
max value diff: 2113664
for range from 0 to 270549119
new varint data size: 1080066185 B (1 GB)
old varint data size: 1082196489 B (1 GB)
size differece: 2130304 B (2 MB)
percent from data size new: 0.19723828313354705 %
percent from data size old: 0.19685001953466882 %
average byte per value new: 3.992126032418808
average byte per value old: 4.000000033265678
-------------------------------------------------------
size: 5 B
new start value: 270549119
new max value: 34630287487
old start value: 268435455
old max value: 34359738367
max value diff: 270549120
for range from 0 to 34630287487
new varint data size: 172878758030 B (161 GB)
old varint data size: 173151437454 B (161 GB)
size differece: 272679424 B (260 MB)
percent from data size new: 0.15772870369226125 %
percent from data size old: 0.15748031203751395 %
average byte per value new: 4.992125984801758
average byte per value old: 5.00000000040427
-------------------------------------------------------
size: 6 B
new start value: 34630287487
new max value: 4432676798591
old start value: 34359738367
old max value: 4398046511103
max value diff: 34630287488
for range from 0 to 4432676798591
new varint data size: 26561157824660 B (24 TB)
old varint data size: 26596060791572 B (24 TB)
size differece: 34902966912 B (32 GB)
percent from data size new: 0.13140604465515907 %
percent from data size old: 0.1312335957776889 %
average byte per value new: 5.992125984257845
average byte per value old: 6.000000000004512
-------------------------------------------------------
size: 7 B
new start value: 4432676798591
new max value: 567382630219903
old start value: 4398046511103
old max value: 562949953421311
max value diff: 4432676798592
for range from 0 to 567382630219903
new varint data size: 3967210831773851 B (3 PB)
old varint data size: 3971678411539355 B (3 PB)
size differece: 4467579765504 B (4 TB)
percent from data size new: 0.1126126126124338 %
percent from data size old: 0.1124859392574144 %
average byte per value new: 6.992125984252029
average byte per value old: 7.000000000000048
-------------------------------------------------------
size: 8 B
new start value: 567382630219903
new max value: 72624976668147839
old start value: 562949953421311
old max value: 72057594037927935
max value diff: 567382630219904
for range from 0 to 72624976668147839
new varint data size: 580427963135197347 B (515 PB)
old varint data size: 580999813345182755 B (516 PB)
size differece: 571850209985408 B (520 TB)
percent from data size new: 0.09852216748768333 %
percent from data size old: 0.0984251968503923 %
average byte per value new: 7.9921259842519685
average byte per value old: 8
-------------------------------------------------------
size: 9 B
new start value: 72624976668147839
new max value: 9295997013522923647
old start value: 72057594037927935
old max value: 9223372036854775807
max value diff: 72624976668147840
for range from 0 to 9295997013522923647
new varint data size: 9803799999989973164 B (8 EB)
old varint data size: 9876996826868106412 B (8 EB)
size differece: 73196826878133248 B (65 PB)
percent from data size new: 0.7466168922071861 %
percent from data size old: 0.7410838351088465 %
average byte per value new: 1.0546259842519685
average byte per value old: 1.0625
-------------------------------------------------------Заключение
Мой pull request в golang/protobuf пролежал год прежде чем в него заглянули и направили в правильное место для моего предложения.
Multiformats/unsigned-varint всё также использует оригинальный varint. Теперь уже поздно это менять.
А я надеюсь что хоть кому то comact varint поможет сэкономить немного байт.
Источники
Комментарии (17)
ivan386 Автор
10.03.2018 15:48Дополнил код для вычисления разницы. Результаты под спойлером ниже.
Вычисляется объем необходимый для записи всех значений до заданного и выводится статистика разницы между старым и новым вариантом.
Экономим от 0.38% (128 B) на маленьких числах до 0.09% (520 TB) на больших. На 9 байтах результат 0.7% но не уверен что это правильно.
Если где ошибся подскажите.
aamonster
СтОит ли экономия менее чем одного процента некоторой потери прозрачности формата? Не уверен.
СтОит ли потери совместимости? Уверен, что нет.
ivan386 Автор
Я и не думаю что надо менять оригинальный varint на compact varint по умолчанию. Если его таки захотят принять то отельными дополнительными функциями. Тогда для compact varint будут новые обозначения в протобуфере (например: uint64c, int64c). По сути запись такая же как и у varint только значение получаем чуть чуть по другому. Старшие биты теперь указывают не только размер контейнера но и его начальное значение.
И экономия в процентах маленькая а в числах огромная. 1 из 9 это больше 10 процентов.
aamonster
Вы считаете криво. 1 из 9 на маленьком диапазоне — это в среднем меньше одного процента (байт кодирует 128 значений, а не 127 — причём это касается не всех 8 байт).
А вообще, что касается эффективности — попробуйте мыслить иначе. Представьте ваш вариант varint как арифметическое кодирование. Так вот, чтобы оно было оптимальным — надо угадать вероятности однобайтовых, двухбайтовых и т.д. чисел. Может статься, оптимальным будет резать на группы по два байта. Или, напротив, по 4 бита. Или использовать дифференциальное кодирование. Короче, если ещё немного усложнить — ваш энкодер тоже можно обойти. Так что есть резон оставить всё, как есть (предельно просто), а при необходимости жать данные — использовать алгоритм, который даст бОльший выигрыш.
ivan386 Автор
Так я вроде не сильно усложнил исходя из изменений кода. Может просто коряво объяснил?
Покажите в каком месте я считаю криво а то я вас плохо понимаю.
В 8 байтах мы экономим 1 из 9 байт (11%) на диапазоне значений от 72057594037927936 до 72624976668147839 ( 0.7% но 567 382 630 219 904 зничений) по сравнению с оригинальным varint. И это без учета экономии на других диапазонах.
В первых 2х байтах мы экономим 1 байт из 3 (33%) на диапазоне значений от 16384 до 16511 (те же 0.7% но всего 128 значений) по сравнению с оригинальным varint.
aamonster
В 8 байтах экономим 11% на очень узком диапазоне значений — менее 1% от всего диапазона. Итого в среднем — менее 0.1%, не из за чего суетиться. На 2 байтах экономия заметнее, но всё равно ни о чём...
ivan386 Автор
Даже если взять ваш 0.1% и примерить к 100ГБ данных то получаем 100МБ экономии по простому. И это при условии что постояно используются огромные числа которые нельзя записать меньшим количеством байт.
khim
ivan386 Автор
Идея не только в экономии байт но и большей жёсткости формата. 1 значение = определённый набору байт без вариантов.
khim
А какая практическая польза от этой жёсткости?
ivan386 Автор
Определённый хеш от числа.
khim
Ну дык «запретите законодательно» использовать «пустнышки — и будет вам „определённых хеш“.
ivan386 Автор
Я алгоритмом это сделал.
supcry
А разве тот же protobuf не кодирует однозначно? Зачем использовать много байт при кодировании нуля, когда можно задействовать один. Имхо, проблема несколько натянута. Но за статью спасибо.
ivan386 Автор
В статье используется код из оригинального golang/protobuf с мелкими но важными изменениями. Оба варианта(мой и оригинальный) используют минимально возможное для алгоритма количество байт для записи числа.
В оригинальном varint проблема не только для нуля. Любое число можно записать используя большее количество байт чем для него необходимо.
Это можно сделать намерянно. Тогда при перегоне из протобуфера в протобуфер потеряется хвост и хеш данных изменится. Может вскроются другие уязвимости которые возникнут из за этой разницы.