Protocol Buffers和Avro中ZigZag编码的原因是什么？

Question

ZigZag需要很多额外的操作来读/写数字。实际上，我惊讶地发现它并不仅仅将int/long值按原样写入，而是进行了大量的额外混淆。甚至涉及到一个循环： https://github.com/mardambey/mypipe/blob/master/avro/lang/java/avro/src/main/java/org/apache/avro/io/DirectBinaryEncoder.java#L90 我无法在Protocol Buffers文档或Avro文档中找到答案，也不能自行推理，为什么这种数字混淆有优势？为什么在编码后正负数会交替出现才更好？为什么不只是以小端、大端或网络顺序写入，这只需要将它们读入内存，并可能反转位的顺序？我们用性能换取了什么？

- Endrju

---

如果您对类似于protobuf但不执行昂贵的varint编码的东西感兴趣，请参见https://capnproto.org。它更快，但在传输时占用的空间更多。（声明：我是Cap'n Proto的作者，也是Google开源Protobuf代码的大部分作者。） - Kenton Varda

@KentonVarda 感谢提供的信息，我之前不知道 Cap'n'proto。现在已经加入到我的协议工具箱中了。 - Endrju

协议缓冲区，至少在版本2中，允许您使用固定大小编码的整数（例如-fixed32、sfixed64等），如果这对您的应用程序更有意义。例如，如果您的值将均匀分布在可能的值范围内，则要使用固定形式而不是可变形式。话虽如此，常用值很常见地聚集在靠近零的位置，这种简单的可变长度编码可以节省大量空间。 - jschultz410

Answer 1

这是一种可变长度的7位编码。编码值的第一个字节高位为0，后续字节高位为1。这样解码器就能知道使用了多少个字节来编码该值。无论机器架构如何，字节顺序始终为小端模式。

这是一种编码技巧，允许尽可能少地写入字节以编码该值。因此，如果一个8字节的long值在-64和63之间，则只需要一个字节。这很常见，实际上很少使用long提供的范围。

紧密打包数据，而无需像gzip压缩方法那样的开销，是设计目标。它也被用于.NET Framework中。需要的处理器开销微不足道。已经比压缩方案低得多，是I/O成本的非常小的一部分。

- Hans Passant

---

非常感谢。我非常感激你的帮助。现在它变得非常清晰了。我曾经迷失过，因为我开始查看了一些Java源代码，其中某些地方是不必要的混淆。天哪，Java真的需要手工展开循环代码才能快速运行吗？ - Endrju

@Endrju：低级库协议的性能要求非常高，因为这些库的用户变化如此之大。库代码有着非常多样化的客户端，其中一些具有严格的性能要求。此外，库代码往往会成为瓶颈，因此优化库通常是至关重要的。在选择库时，性能经常是主要考虑因素。 - Brian

@Brian 我知道我知道，但是……循环展开？Java JITter在这么多年和版本之后难道不能同样好甚至更好地做到吗？… - Endrju

可能吧，但针对嵌入式系统可能不是这样。乐观地说，我们希望有人已经测试了代码并验证了它的优点。现实情况是，它很可能被验证为正确且性能足够好，然后被忽略了。除非他们已经因其他原因而改变了它，否则熟练的专业人员通常会犹豫修改已满足性能和正确性目标的工作代码。您可以分析更改历史记录以找出为什么那个循环被展开；也许是为了响应基准测试而完成的？ - Brian

这个回答的第二句话是错误的。每个八位字节的最高有效位用来表示编码是否继续。唯一的例外是第九个字节，其中所有8个位都代表该值的一部分。 - jschultz410

一个常常被忽略的要点是：在传输/转移一个字节所需的时间往往远远超过了处理奇怪编码所需的时间。即使以1Gb/s的线速度，一个运行在2GHz以上的现代处理器也会通过花费周期来进行简单编码而“获胜”，而不是进行传输。在IoT和BLE等环境中，带宽非常受限，而处理器相对更加高效，因此奇怪的编码会大大提升性能。 - Julie in Austin