变长整数编码（Variable-Length Integer Encoding）是数据序列化系统的核心组件，广泛应用于 Protocol Buffers、TLV 格式、区块链协议等场景。其设计目标是在 64 位空间内高效编码小整数与大整数，兼顾紧凑性与解码速度。本文基于 VarU64 和 vu128 等成熟方案，分析位布局设计的关键决策点。
三种主流位布局模式
变长整数编码的核心差异体现在首字节语义的设计上，这直接决定了编码长度、解码分支数量与实现复杂度。
模式一：直接值阈值（VarU64 方案）
VarU64 采用最简单的设计：首字节值小于 248 时直接表示该数值，248-255 则指示后续 1-8 字节的负载长度。这种设计的优势在于单字节快速路径覆盖 97.7% 的小整数场景（0-247），且解码逻辑仅需一次比较操作。
首字节 < 248: 直接值（单字节）
首字节 = 248: 1 字节负载（大端序）
首字节 = 249: 2 字节负载
...
首字节 = 255: 8 字节负载
该方案采用大端序存储负载字节，符合网络协议的传统习惯，但在小端 CPU 上需要额外的字节交换操作。
模式二：前缀变长（vu128 方案）
vu128 采用更精细的三级分区策略，通过首字节的高位模式区分编码布局：
- 单字节区（0-127）：MSB 为 0，直接存储值
- 前缀变长区（128-2^28）：使用 10/110/1110/11110 前缀指示 1-4 字节负载，每字节承载 7 位数据
- 二进制长度前缀区（2^28-2^128）：首字节高 4 位为 1111，低 4 位编码负载长度减一
这种设计的精妙之处在于位掩码比条件分支更廉价—— 现代 CPU 的流水线架构下，通过位运算提取长度信息比逐字节判断 MSB 的延续标志更高效。
模式三：逐字节延续标志（LEB128/Protobuf）
LEB128 每个字节使用低 7 位存储数据，高 1 位作为延续标志。这种设计的缺点是每个字节都需分支判断，导致解码路径上的分支预测失败成本累积。实测表明，即使经过精心优化的 LEB128 实现，性能也仅为前缀变长方案的 20%。
边界值优化策略
变长整数编码的性能关键取决于小整数的处理效率，因为在大多数应用场景中，小整数（如数组索引、枚举值、长度字段）占绝对多数。
快速路径设计原则
- 零值与极小值优先：确保 0-127 范围内的整数单字节编码，覆盖最常见的计数场景
- 分支最小化：解码逻辑应尽量减少条件分支，优先使用位掩码和查表法
- 对齐友好：编码长度应避免产生非对齐内存访问，尤其在 32/64 位边界处
vu128 的修订历史展示了边界值优化的典型迭代：早期版本将 0xF0-0x3FFF 编码为 3 字节，虽减少了分支但牺牲了空间效率；最终版本调整为 2 字节编码，与 LEB128 持平但保持性能优势。
字节序与跨平台考量
字节序选择直接影响解码实现的复杂度：
- 大端序（VarU64）：网络协议传统，人工可读性较好，但小端 CPU 需字节交换
- 小端序（vu128）：与主流 CPU（x86-64、ARM）原生字节序一致，可直接使用未对齐内存读取优化
对于跨平台兼容性，建议遵循以下准则：
- 规范明确定义字节序，不依赖平台默认行为
- 提供规范的编解码实现，避免用户自行处理字节交换
- 考虑使用
memcpy或std::ptr::read_unaligned等安全方式处理未对齐访问
工程实现要点
基于上述分析，实现高性能变长整数编码的关键参数如下：
编码决策表
| 值范围 | 编码长度 | 首字节模式 | 负载字节序 |
|---|---|---|---|
| 0-127 | 1 | 0xxxxxxx | - |
| 128-2^14-1 | 2 | 10xxxxxx | 小端 |
| 2^14-2^21-1 | 3 | 110xxxxx | 小端 |
| 2^21-2^28-1 | 4 | 1110xxxx | 小端 |
| 2^28-2^128-1 | 2-17 | 1111xxxx | 小端（长度前缀） |
解码优化技巧
- 查表法：使用 256 字节的查找表将首字节映射到解码函数指针或长度信息
- SIMD 友好：批量解码时，可先提取所有首字节进行向量化前缀分析
- 边界检查：规范应明确定义最大编码长度（如 9 字节对应 u64），解码器需验证输入边界
规范化要求
为避免同一数值存在多种合法编码（如 VarU64 中 0 可编码为 0x00 或 0xf800），规范应强制要求最短编码原则。解码器发现非最短编码时应视为错误，这有助于防止编码膨胀并简化相等性比较。
性能对比参考
在 AMD Ryzen 7 3700X 上的基准测试显示，前缀变长方案相比 LEB128 有 2-5 倍性能提升。核心差异在于：
- LEB128：每个字节需判断 MSB，平均 3-4 次分支 / 数值
- 前缀变长：首字节即确定总长度，后续纯位运算，平均 1-2 次分支 / 数值
对于高频场景（如解析百万级整数的消息队列），这一差距会转化为显著的吞吐提升。
结论
Bijou64 类型的变长整数编码设计需要在紧凑性与解码速度之间权衡。VarU64 的阈值方案实现简单、覆盖广泛；vu128 的分层前缀方案在复杂场景下性能更优。工程实践中，建议优先保证 0-127 单字节快速路径，采用小端序以适配主流硬件，并强制最短编码规范以确保互操作性。
参考来源
- VarU64 Specification - GitHub (AljoschaMeyer/varu64)
- vu128: Efficient variable-length integers - John Millikin
内容声明：本文无广告投放、无付费植入。
如有事实性问题，欢迎发送勘误至 i@hotdrydog.com。