Внимание: Код представленный в статье немного отличается от оригинальных 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й байт на гораздо более значительном отрезке значений


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


Здесь вычисляется объем необходимый для записи всех значений до заданного и выводится статистика разницы между старым и новым вариантом.


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 поможет сэкономить немного байт.


Источники


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

Комментарии (17)


  1. aamonster
    09.03.2018 20:38

    СтОит ли экономия менее чем одного процента некоторой потери прозрачности формата? Не уверен.
    СтОит ли потери совместимости? Уверен, что нет.


    1. ivan386 Автор
      09.03.2018 20:51

      Я и не думаю что надо менять оригинальный varint на compact varint по умолчанию. Если его таки захотят принять то отельными дополнительными функциями. Тогда для compact varint будут новые обозначения в протобуфере (например: uint64c, int64c). По сути запись такая же как и у varint только значение получаем чуть чуть по другому. Старшие биты теперь указывают не только размер контейнера но и его начальное значение.


      И экономия в процентах маленькая а в числах огромная. 1 из 9 это больше 10 процентов.


      1. aamonster
        09.03.2018 21:12

        Вы считаете криво. 1 из 9 на маленьком диапазоне — это в среднем меньше одного процента (байт кодирует 128 значений, а не 127 — причём это касается не всех 8 байт).


        А вообще, что касается эффективности — попробуйте мыслить иначе. Представьте ваш вариант varint как арифметическое кодирование. Так вот, чтобы оно было оптимальным — надо угадать вероятности однобайтовых, двухбайтовых и т.д. чисел. Может статься, оптимальным будет резать на группы по два байта. Или, напротив, по 4 бита. Или использовать дифференциальное кодирование. Короче, если ещё немного усложнить — ваш энкодер тоже можно обойти. Так что есть резон оставить всё, как есть (предельно просто), а при необходимости жать данные — использовать алгоритм, который даст бОльший выигрыш.


        1. ivan386 Автор
          09.03.2018 21:48

          Так я вроде не сильно усложнил исходя из изменений кода. Может просто коряво объяснил?
          Покажите в каком месте я считаю криво а то я вас плохо понимаю.


          В 8 байтах мы экономим 1 из 9 байт (11%) на диапазоне значений от 72057594037927936 до 72624976668147839 ( 0.7% но 567 382 630 219 904 зничений) по сравнению с оригинальным varint. И это без учета экономии на других диапазонах.
          В первых 2х байтах мы экономим 1 байт из 3 (33%) на диапазоне значений от 16384 до 16511 (те же 0.7% но всего 128 значений) по сравнению с оригинальным varint.


          1. aamonster
            09.03.2018 22:25

            В 8 байтах экономим 11% на очень узком диапазоне значений — менее 1% от всего диапазона. Итого в среднем — менее 0.1%, не из за чего суетиться. На 2 байтах экономия заметнее, но всё равно ни о чём...


            1. ivan386 Автор
              09.03.2018 22:40

              Даже если взять ваш 0.1% и примерить к 100ГБ данных то получаем 100МБ экономии по простому. И это при условии что постояно используются огромные числа которые нельзя записать меньшим количеством байт.


              1. khim
                10.03.2018 00:54

                Даже если взять ваш 0.1% и примерить к 100ГБ данных то получаем 100МБ экономии по простому.
                0.1% — это 0.1%. От чего его не бери. Да, от 100 рублей это будет 10 копеек, а от миллиарда — аж прямо миллион… но компания, платящая за что-то миллиард вряд ли откажется от сделки, если она будет на миллион дороже… или ухватится если она будет на миллион дешевле.


            1. ivan386 Автор
              09.03.2018 22:52

              Идея не только в экономии байт но и большей жёсткости формата. 1 значение = определённый набору байт без вариантов.


              1. khim
                10.03.2018 01:15

                А какая практическая польза от этой жёсткости?


                1. ivan386 Автор
                  10.03.2018 09:25

                  Определённый хеш от числа.


                  1. khim
                    10.03.2018 19:01

                    Ну дык «запретите законодательно» использовать «пустнышки — и будет вам „определённых хеш“.


                    1. ivan386 Автор
                      10.03.2018 19:03

                      Я алгоритмом это сделал.


                  1. supcry
                    10.03.2018 21:04

                    А разве тот же protobuf не кодирует однозначно? Зачем использовать много байт при кодировании нуля, когда можно задействовать один. Имхо, проблема несколько натянута. Но за статью спасибо.


                    1. ivan386 Автор
                      10.03.2018 21:39

                      В статье используется код из оригинального golang/protobuf с мелкими но важными изменениями. Оба варианта(мой и оригинальный) используют минимально возможное для алгоритма количество байт для записи числа.


                      В оригинальном varint проблема не только для нуля. Любое число можно записать используя большее количество байт чем для него необходимо.


                      Это можно сделать намерянно. Тогда при перегоне из протобуфера в протобуфер потеряется хвост и хеш данных изменится. Может вскроются другие уязвимости которые возникнут из за этой разницы.


  1. ivan386 Автор
    10.03.2018 15:48

    Дополнил код для вычисления разницы. Результаты под спойлером ниже.


    Вычисляется объем необходимый для записи всех значений до заданного и выводится статистика разницы между старым и новым вариантом.


    Экономим от 0.38% (128 B) на маленьких числах до 0.09% (520 TB) на больших. На 9 байтах результат 0.7% но не уверен что это правильно.


    Если где ошибся подскажите.


  1. smile616
    11.03.2018 13:53

    Правильно ли я понимаю что для декодирования Compact varint необходимо знать длину закодированной последовательности?


    1. ivan386 Автор
      11.03.2018 13:55

      Да. Она определяет начальное значение контейнера.