为什么varint是一种有效的数据表示？

Question

我目前正在研究协议缓冲区的文档.Varints描述为:

varint中的每个字节(最后一个字节除外)都设置了最高有效位(msb) - 这表示还有其他字节.每个字节的低7位用于存储7位组中的二进制补码表示,最低有效组优先.

我的问题是为什么人们会选择在每个字节上丢失一位的表示？这种方法有什么好处？

Answer 1

实际上,绝大多数整数值都很小.即使在您希望某个值有时非常大的情况下,因此您将其设置为32位甚至64位,通常也很小,因为从统计上讲,大多数物理量遵循幂律分布.因此,如果较小的值可以存储在较少的字节中,那么如果较大的值需要额外的字节就可以了.

关于唯一没有受益的整数是哈希或随机生成的ID号,它们实际上并不代表数量,而只是一个字符串.对于这些,您应该使用Protobufs' fixed32或fixed64类型.

请注意,varint编码节省了线路上的空间,但实际上相对较慢,因为它需要大量的分支来编码/解码.当然,它并不像文本编码那么慢,但作为二进制格式,它并不是那么好.这就是为什么Cap'n Proto决定改变这个决定并在线上放置固定宽度的一个原因的原因之一.Cap'n Proto还包括一个可选的"打包"算法,它压缩零值字节,产生与Protobuf类似的消息大小,但通常更快,因为算法使用较少的分支.

(披露:我是Cap'n Proto的作者,也是Google发布的大部分Protobuf代码.)

Answer 2

这是为了节省空间/带宽,例如,许多编程语言和协议具有固定大小的数据类型.例如,uint8_t,uint16_t,uint32_t等,无论值有多大,这些都会占用固定数量的字节.例如,如果将值存储2在uint32_t中,则占用4个字节.

使用protobuf中使用的varint等编码,较小的值可占用较小的空间,并且该值2仅需要在线上传输1个字节的空间,同时仍然足够灵活,不会限制可以使用的值的范围使用.

如果小值比大值更常见,这通常是一个净赢 - 通常就是这种情况.

Answer 3

这是一个权衡，取决于您想要发送的典型号码。

• 如果它们通常很小，请使用“varint”编码 ( int32, int64, uint32, uint64, sint32, sint64, bool, enum)
• 如果它们通常很大，请使用非“varint”编码 ( fixed32, sfixed32, float, fixed64, sfixed64, double)

sint64以下是、int64和fixed64对于不同数字所使用的字节的比较：

[ RUN      ] ProtobufOutputStream.printNumberOfBytesOnWireForInts
                        number  sint64   int64 fixed64
                             0       2       2       9
                             1       2       2       9
                            -1       2      11       9
                            63       2       2       9
                           -63       2      11       9
                            64       3       2       9
                           -64       2      11       9
                         10000       4       3       9
                        -10000       4      11       9
           9223372036854775807      11      10       9
          -9223372036854775808      11      11       9