🏅 🥐 ♌️ コンパクトバリント-同じ価格で独自性と大きな価値 📺 🚾 🐂

UPD 2018.03.15： Gitは以前からコンパクトなヴァリントバリアントを使用しています。あとがきの違い。

注：この記事に記載されているコードは、元のEncodeVarintおよびDecodeVarintとは若干異なり、他の結果を提供します。 注意してください。

varintでの数値の正確な記述に関する multiformats / unsigned-varintの議論では、元のvarintの多くの数値が異なる長さのシーケンスで記述できることに気付きました。これにより、 protobufferでエンコードされた同一の値を持つ異なるブロックとそれらのハッシュが得られます。

オリジナルヴァリント

元のvarintは、数値を7ビットの断片に分割します。そして、各ピースにシニア8ビット（MSB-最上位ビット）を追加して、小さいものから古いものへ順番に書き込みます。このビットの値は、最後のピースが（0）かそうでないか（1）によって異なります。

したがって、たとえば、さまざまな方法で値0を書き込むことができます。

0000 0000 (0x00)

varint = 0
1000 0000 0000 0000 (0x8000)

varint = 0
1000 0000 1000 0000 0000 0000 (0x808000)

varint = 0

などなど。

コンパクトヴァリント

前のコンテナの最大値+ 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
同じサイズの一連のバイトのより大きな値。
1. 2バイトの場合、最大値は16 511で、元のvarintの16 383よりも128大きい
2. 8バイトの場合、最大値はすでに567 382 630 219 904です

コンパクトバリントのコーディング

上で言ったように、コードはオリジナルとほとんど変わりません。次に、1行追加しました。

 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

最初の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

コンパクトバリントをデコードする

復号化も大きな変更を受けていません。次に、1行変更しました。

 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 }

例

コンパクトvarint形式の300 = 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個のゼロを追加し、2番目のバイトを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バイトの最大コンパクトバリント値： 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バイト： 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（コンパクトvarint）-16383（varint）= 128

2バイトの場合、サイズは大きくありませんが、元のvarintと比較して16384〜16511の値でバイトを節約します。

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 } }

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 -------------------------------------------------------

おわりに

golang / protobufでのプルリクエストは1年続き、調査の前に適切な場所に送信されました。

Multiformats / unsigned-varintは、元のvarintも使用します。今では変更するには遅すぎます。

そして、少なくとも誰かがコンパクトバリントを使用して数バイトを節約できることを願っています。

あとがき

2018.03.15

数日後、ウィキペディアの記事Variable-length quantityに出会いました。そこで、冗長性の削除セクションで、私の記事で提示されたアイデアを説明します。

Gitは長い間コンパクトvarintを使用してきましたが、最も古いものから最も若いものに書き込みます。これにはいくつかの欠点があります。

エンコード時には、追加のバッファーが使用され、最後に最後のバッファーにコピーされます。

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)

デコード時には、ユニットが個別に追加され、最上位ビットがリセットされます。

git / varint.c＃L10（decode_varint）

 val += 1;

git / varint.c＃L14（decode_varint）

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

私のバージョンでは、これらの2つの操作を置き換える番号に最上位ビットが追加されています。

proto / decode.go＃L70（DecodeVarint）

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

git / varint.cは、異なるバイト順を使用するため、私のものと互換性がありません。

コンパクトバリント-同じ価格で独自性と大きな価値