Главная » Хабрахабр » Compact varint — уникальность и большие значения за ту же стоимость

Compact varint — уникальность и большие значения за ту же стоимость

Внимание: Код представленный в статье немного отличается от оригинальных EncodeVarint и DecodeVarint и даёт другие результаты. Будьте внимательны.

В multiformats/unsigned-varint обсуждении правильной записи числа в varint было замечено что многие числа в оригинальном varint могут быть записаны в последовательности разной длинны. Это даст разные блоки и их хеши при идентичных значениях кодированных в протобуфер.

Оригинальный varint

Оригинальный varint просто делит число на кусочки по 7 бит. И записывает их в порядке от младшего к старшему добавляя к каждому кусочку старший 8ой бит. Значение этого бита зависит от того последний это кусочек (0) или нет (1).

Таким образом например значение 0 мы можем записать во многих вариантах:

  1. 0000 0000 (0x00) varint = 0
  2. 1000 0000 0000 0000 (0x8000) varint = 0
  3. 1000 0000 1000 0000 0000 0000 (0x808000) varint = 0
    и так далее.

Compact varint

Я подумал что можно начинать значения контейнера большего размера от максимального значения предыдущего контейнера + 1. Ведь если мы используем контейнер такого размера то число должно быть больше максимума предыдущего контейнера.

Преимущества:

  1. Уникальное значение для каждого набора байт.
    1. 0000 0000 (0x00) varint = 0
    2. 1000 0000 0000 0000 (0x8000) varint = 128
    3. 1000 0000 1000 0000 0000 0000 (0x808000) varint = 16 512
  2. Б`ольшие значения для набора байт того же размера.
    1. Для 2х байт максимум 16 511 что на 128 больше чем 16 383 у оригинального varint
    2. Для 8ми байт максимум уже на 567 382 630 219 904 больше

Кодируем в compact varint

Как я уже говорил выше код мало отличается от оригинала. Тут я всего лишь добавил одну строчку:

x -= 1

И она дала уникальность и экономию.

https://github.com/ivan386/protobuf-1/blob/b76098a2adb7a080231cf14903ab7f3687667ce6/proto/encode.go#L95-L106

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

  1. отделяем первые 7 бит: " uint8(x&0x7F), x >>= 7 "
    010 1100

  2. добавляем к ним старший бит (1 поскольку есть ещё биты): " 0x80 | "
    1 010 1100

  3. вычитаем единицу из оставшегося: " x -= 1 "
    (000 0010) - 1 = 000 0001
    Это ключевое и единственное отличие от оригинального EncodeVarint. За счёт него мы можем записать большее значение в то же количество байт.

  4. добавляем к ним старший бит (0 поскольку это последняя часть)
    0 000 0001

  5. склеиваем
    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) << shift

https://github.com/ivan386/protobuf-1/blob/b76098a2adb7a080231cf14903ab7f3687667ce6/proto/decode.go#L63-L78

func 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. разделяем

    1 010 1100
    0000 000 1
    

  2. добавляем нули или сдвигаем " (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.

  3. теперь складываем " 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. разделяем
    1 111 1111
    0111 111 1
    
  2. добавляем нули или сдвигаем

    1 111 1111 = 0000 000 1 111 1111
    0111 111 1 = 0111 111 1 000 0000
    

  3. складываем
    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. разделяем

    1 111 1111
    0 111 1111
    

  2. отбрасываем старший бит

    111 1111
    111 1111
    

  3. склеиваем биты
    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й байт на гораздо более значительном отрезке значений

Код для вычисления разницы:

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
}

Тестим на The Go Playground: https://play.golang.org/p/uqtD6hjTgiU

Заключение

Мой pull request в golang/protobuf пролежал год прежде чем в него заглянули и направили в правильное место для моего предложения.

Multiformats/unsigned-varint всё также использует оригинальный varint. Теперь уже поздно это менять.

А я надеюсь что хоть кому то comact varint поможет сэкономить немного байт.

Источники

  1. Encoding | Protocol Buffers | Google Developers / Base 128 Varints
  2. Multiformats/unsigned-varint
  3. New varint with unique values
  4. Compact varint
  5. Порядок байтов

x

Ещё Hi-Tech Интересное!

[Из песочницы] Исследователи из Карнеги-Меллона создали пока самые правдоподобные «deepfakes»

Когда-либо слышали о «deepfakes»? ИИ, который накладывает лицо одного человека на тело другого, использовали для замены Харрисона Форда на Николаса Кейджа в бесчисленных видеоклипах, а также и для более гнусных целей: знаменитости без их ведома появились в порно и пропаганде. ...

Очередной сказ о том, как на Мегафоне воруют деньги

upd: уточняю: это не жалоба, а статья-предупреждение, проверьте свои детализации Сидел я значит на диване, никого не трогал, переписывался в контактике (каюсь три раза). Дело было вечером, делать было нечего. Поборов лень, я встал с дивана, подошел к телефону и ...