Pull to refresh

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

Reading time 9 min
Views 7K

UPD 2018.03.15: Git давно использует свой вариант compact varint. Различия в послесловии.


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


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


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


Оригинальный varint просто делит число на кусочки по 7 бит. И записывает их в порядке от младшего к старшему добавляя к каждому кусочку старший 8ой бит (MSB — most significant bit). Значение этого бита зависит от того последний это кусочек (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 поможет сэкономить немного байт.


Послесловие


2018.03.15


Через несколько дней я наткнулся на статью в википедии Variable-length quantity. Там в разделе Removing Redundancy описывается представленная в моей статье идея.


Оказывается Git давно использует compact varint но записывает их от старшего к младшему. Это даёт несколько недостатков:


  1. При кодировании используется дополнительный буфер который в конце копируется в конечный:
    git/varint.c#L22 (encode_varint)


    unsigned char varint[16];

    git/varint.c#L28 (encode_varint)


    memcpy(buf, varint + pos, sizeof(varint) - pos);

    В представленном в моей статье варианте запись ведётся напрямую в конечный буфер:
    proto/encode.go#L99 (EncodeVarint)


    buf[n] = 0x80 | uint8(x&0x7F)

  2. При декодировании отдельно прибавляется единица и сбрасывается старший бит:
    git/varint.c#L10 (decode_varint)


    val += 1;

    git/varint.c#L14 (decode_varint)


    val = (val << 7) + (c & 127);

    В моём варианте старший бит прибавляется к числу заменяя эти две операции:
    proto/decode.go#L70 (DecodeVarint)


    x += (b & 0xFF) << shift

  3. git/varint.c не совместим с моим поскольку использует другой порядок байт.

Источники


  1. Encoding | Protocol Buffers | Google Developers / Base 128 Varints
  2. Multiformats/unsigned-varint
  3. New varint with unique values
  4. Compact varint
  5. Порядок байтов
  6. Variable-length quantity
Tags:
Hubs:
+11
Comments 18
Comments Comments 18

Articles