16

我目前正在研究协议缓冲区的文档。Varints 被描述为：

varint 中的每个字节，除了最后一个字节，都设置了最高有效位 (msb)——这表明还有更多字节要到来。每个字节的低 7 位用于存储以 7 位为一组的数字的二进制补码表示，最低有效组在前。

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

4

4 回答 4

26

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

唯一没有好处的整数类型是哈希或随机生成的 ID 号，它们实际上并不代表一个数量，而只是一个位字符串。对于这些，您应该使用 Protobufsfixed32或fixed64类型。

请注意，varint 编码节省了线路上的空间，但实际上相对较慢，因为它需要很多分支来编码/解码。当然，它不像文本编码那么慢，但随着二进制格式的发展，它并不是那么好。这就是Cap'n Proto决定推翻这一决定并在线路上放置固定宽度整数的原因之一。Cap'n Proto 还包括一个可选的“打包”算法，它压缩零值字节，产生与 Protobuf 相似的消息大小，但通常更快，因为该算法使用较少的分支。

（披露：我是 Cap'n Proto 的作者，也是 Google 发布的大部分 Protobuf 代码的作者。）

于 2014-07-08T21:55:50.310 回答
20

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

使用 protobuf 中使用的 varint 之类的编码，小的值可以占用更小的空间，并且该值2只需要 1 字节的空间就可以在线传输，同时仍然足够灵活，不会限制可以使用的值的范围使用。

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

于 2014-07-07T15:56:27.830 回答
5

这是一个权衡，取决于您要发送的典型数字。

  • 如果它们通常很小，请使用“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
于 2019-03-01T11:40:17.907 回答
3

如果您有很多小数字，使用这种方法可以节省相当多的内存空间和/或传输时间，同时仍然能够表示任意大的数字。例如，您不必为每个数字分配 8 个字节。如果您有很多小数字，那么这些字节中的大多数无论如何都会为零。对于 8 字节数字，您的值被限制为 (2^64 - 1)，如果您的值为 2^64 或更大，则需要做一些特殊的事情。

使用 varint 编码，您通常会节省大量内存并获得表示任何数量级数字的能力。

于 2014-07-07T15:57:37.497 回答