在 C/C++ 中高效编码变长整数

在许多情况下使用固定宽度整数是空间低效的，特别是如果大多数值较低且只使用较低有效字节。

本指南描述 varint（变长整数）编码的基础知识，以 C++ 为编程语言重点，但基本概念适用于任何语言。

Varint 编码只使用适当表示整数值所需的字节。varint 算法可以仅用一个字节表示数字 10，而用 4 字节编码 800000000（8 亿）。在许多应用中，这产生了显著的开销减少，因为如果你的值有可能超出适用于大多数值的整数类型的边界，你需要使用更大的整数。此外，你通常只能使用 8、16、32 或 64 位整数，而 48 位整数在大多数语言中需要手动编码。例如，如果你的大多数值在 0 到 100 之间，但少数可能大于 16384（对于无符号整数），你通常会使用完整的 32 位整数，即使大多数值可以用单个字节表示。

何时（以及何时不）使用 varint 编码？

并非所有应用都能从 varint 编码中受益，有些可能需要在 varint 编码器之上使用特殊算法（参见 Delta 编码）。

如果性能和/或空间在你的应用中真的关键，问自己这些问题：

你选择的特定 varint 算法是否真的减少了表示数据所需的空间？

本文描述的 MSB 算法对大数表现不佳，经常使用比固定宽度整数更多的空间。
如果你的数据集中有大量非常小的数字但少数数字比其他大得多，则节省最多空间。

整数长度是否有绝对限制？

理论上不存在限制
特定 varint 实现可能因计数器溢出而出现未定义行为
通常，可用内存量限制输出大小。

减少 IO 字节获得的性能是否超过 varint 编码/解码开销？

如果空间严重受限，你无法为任务使用固定宽度整数，且无法处理性能开销，你的系统设计可能有缺陷

你写入的大容量存储介质是什么？

HDD 随机访问速度低，顺序读取速度中等，所以碎片化很重要。如果你能通过使用 varint 提高任何读取被缓存或顺序的概率，你可能会从中受益
USB 闪存驱动器读取速度低到中等，随机访问速度通常略低。碎片化不太重要，但对于大型数据集，总体读取时间可能产生明显差异
SSD 读取速度高，随机访问速度几乎一样高。碎片化完全不重要（除非常特殊的情况外）。因为总体速度如此高，varint 需要引起内存使用的显著减少才能抵消开销
RAM 是特殊情况，因为你几乎总是在写入其他大容量存储介质之前写入 RAM。RAM 在顺序和随机访问模式下都极快，但其大小严重受限。如果在你的应用中，由于使用 varint 减小了大小，数据集可以存储在 RAM 中而不是磁盘上，你的性能通常会提高几个数量级。如果你的数据集很小，轻松放入 RAM，IO 性能提升（主要通过减少页面错误）很少能抵消开销，除了一些非常特殊的情况如 RAM 碎片化 - 但这些相当罕见且难以分析。

重新计算数据是否比从大容量存储介质读取 varint 编码数据更快？

它真的有区别吗，还是你在不真正需要的地方浪费时间为 0.1% 的效率？（参见Wikipedia 机会成本）
它是否使你的代码不可读或以任何其他方式降低代码质量？

MSB varint 编码

MSB 表示最高有效位（在其他一些情况下，它可能表示最高有效字节，所以要注意！）。该算法基于最高有效字节比最低有效字节使用频率更低的假设（因此它对小数字效果最好）

对于 MSB 生成的字节流中的任何字节，只有当流中有下一个字节时才设置最高有效位。因此任何字节只能表示值的七位，但不需要外部保存大小字节。对于小于或等于 2^64 的整数，MSB 编码与外部保存大小字节并简单剥离未使用的最高有效字节一样空间高效（对于 64 位整数）或更空间高效（对于 48 位或更少整数）。

例如，如果我们编码整数 1（00000001），它将简单地编码为 1（00000001），因为 1 < 127（2^7-1），算法因此只需要使用一位（因此最高有效位未设置）。

然而如果我们编码 255（11111111），第一个字节将设置下一字节标志（即最高有效位）。第一个 varint 字节因此将是 11111111，因为 255 中所有 7 个数据位都设置了，而第二个字节不会设置它，只显示剩余的一个数据位（第二个 varint 字节：00000001）

更复杂的示例是编码 814 - 第一位将设置下一字节标志，但并非所有数据位都设置（第一个 varint 字节将是 10101110），第二位不会设置下一字节标志，并保存剩余数据位（第二个 varint 字节将是 10000010）。

编写编码器/解码器

如果你理解了原理，编写编码器和解码器相当简单。

在编码器中，如果值 > 127，你知道需要附加字节。因此你知道是否设置下一字节标志。然后，你取数据的最低有效 7 位，递增你写入的数组索引（或你使用的任何东西），将数据右移你刚使用的 7 位并重新开始循环。

解码器同样简单，你可以取当前 varint 输入字节的 7 个最低有效位，乘以 2^7 乘以输入字节的当前（0 基）索引，当遇到没有设置下一字节标志的位时停止循环。

无符号 vs 有符号整数

通常我们只需要处理无符号整数情况，因为任何有符号整数可以隐式或显式转换为无符号整数，然而这可能导致极其低效的 varint 编码，因为输入的最高有效位通常用于表示符号（参见Wikipedia 二补数）。因此算法尽可能低效地工作，32 位整数使用 5 字节，64 位整数使用 10 字节（比适当固定宽度整数大小多 25%）。

字节顺序

注意存储 varint 结果有两种不同的可能顺序排列：上面描述的算法是小端序（参见 Wikipedia 字节序）。你可以通过反转输出字节在字节顺序之间转换 - 在设计异构系统时记住这一点（网络字节序标准化为大端序）

C++ 中无符号整数的 MSB 编码

在 C++ 中，你可以使用此基于模板的头文件，使用上面描述的算法轻松编码和解码变长整数。

varint.hpp

/**
 * 变长整数编码的 C++ 实用工具
 * 使用 -std=c++11 或更高版本编译
 *
 * 版本 1.1：使用 size_t 作为大小参数，改进函数签名
 *
 * 许可证：CC0 1.0 Universal
 * 最初发布在 https://techoverflow.net
 * 版权所有 (c) 2015 Uli Koehler
 */
#ifndef __VARIABLE_LENGTH_INTEGER_H
#define __VARIABLE_LENGTH_INTEGER_H

#include <cstdint>

/**
 * 使用 MSB 算法编码无符号变长整数。
 * 此函数假设值以小端序存储。
 * @param value 输入值。允许任何标准整数类型。
 * @param output 指向预留内存的指针。必须具有取决于输入大小的最小大小（32 位 = 5 字节，64 位 = 10 字节）。
 * @return 输出内存中使用的字节数。
 */
template<typename int_t = uint64_t>
size_t encodeVarint(int_t value, uint8_t* output) {
    size_t outputSize = 0;
    //当剩余超过 7 位数据时，占用最后一个输出字节
    // 并设置下一字节标志
    while (value > 127) {
        //|128：设置下一字节标志
        output[outputSize] = ((uint8_t)(value & 127)) | 128;
        //移除我们刚写入的七位
        value >>= 7;
        outputSize++;
    }
    output[outputSize++] = ((uint8_t)value) & 127;
    return outputSize;
}

/**
 * 使用 MSB 算法解码无符号变长整数。
 * @param value 任意大小的变长编码整数。
 * @param inputSize 有多少字节
 */
template<typename int_t = uint64_t>
int_t decodeVarint(uint8_t* input, size_t inputSize) {
    int_t ret = 0;
    for (size_t i = 0; i < inputSize; i++) {
        ret |= (input[i] & 127) << (7 * i);
        //如果设置了下一字节标志
        if(!(input[i] & 128)) {
            break;
        }
    }
    return ret;
}

#endif //__VARIABLE_LENGTH_INTEGER_H

/**
 * 变长整数编码的 C++ 实用工具
 * 使用 -std=c++11 或更高版本编译
 *
 * 版本 1.1：使用 size_t 作为大小参数，改进函数签名
 *
 * 许可证：CC0 1.0 Universal
 * 最初发布在 https://techoverflow.net
 * 版权所有 (c) 2015 Uli Koehler
 */
#ifndef __VARIABLE_LENGTH_INTEGER_H
#define __VARIABLE_LENGTH_INTEGER_H

#include <cstdint>

/**
 * 使用 MSB 算法编码无符号变长整数。
 * 此函数假设值以小端序存储。
 * @param value 输入值。允许任何标准整数类型。
 * @param output 指向预留内存的指针。必须具有取决于输入大小的最小大小（32 位 = 5 字节，64 位 = 10 字节）。
 * @return 输出内存中使用的字节数。
 */
template<typename int_t = uint64_t>
size_t encodeVarint(int_t value, uint8_t* output) {
    size_t outputSize = 0;
    //当剩余超过 7 位数据时，占用最后一个输出字节
    // 并设置下一字节标志
    while (value > 127) {
        //|128：设置下一字节标志
        output[outputSize] = ((uint8_t)(value & 127)) | 128;
        //移除我们刚写入的七位
        value >>= 7;
        outputSize++;
    }
    output[outputSize++] = ((uint8_t)value) & 127;
    return outputSize;
}

/**
 * 使用 MSB 算法解码无符号变长整数。
 * @param value 任意大小的变长编码整数。
 * @param inputSize 有多少字节
 */
template<typename int_t = uint64_t>
int_t decodeVarint(uint8_t* input, size_t inputSize) {
    int_t ret = 0;
    for (size_t i = 0; i < inputSize; i++) {
        ret |= (input[i] & 127) << (7 * i);
        //如果设置了下一字节标志
        if(!(input[i] & 128)) {
            break;
        }
    }
    return ret;
}

#endif //__VARIABLE_LENGTH_INTEGER_H

这是一个简单的测试和演示程序：

varint_test.c

/**
 * varint.hpp 的测试程序
 *
 * 编译方式：g++ -std=c++11 -o varint-test varint-test.cpp
 *
 * 许可证：CC0 1.0 Universal
 * 最初发布在 https://techoverflow.net
 * 版权所有 (c) 2015 Uli Koehler
 */
#include <iostream>
#include <string>

#include "varint.hpp"

using namespace std;

int main(int argc, char** argv) {
    uint8_t* buf;
    size_t outsize = encodeVarint<uint64_t>(0xCAFE, buf);
    //应该打印 51966
    std::cout << decodeVarint(buf, outsize) << endl;
}

/**
 * varint.hpp 的测试程序
 *
 * 编译方式：g++ -std=c++11 -o varint-test varint-test.cpp
 *
 * 许可证：CC0 1.0 Universal
 * 最初发布在 https://techoverflow.net
 * 版权所有 (c) 2015 Uli Koehler
 */
#include <iostream>
#include <string>

#include "varint.hpp"

using namespace std;

int main(int argc, char** argv) {
    uint8_t* buf;
    size_t outsize = encodeVarint<uint64_t>(0xCAFE, buf);
    //应该打印 51966
    std::cout << decodeVarint(buf, outsize) << endl;
}

Check out similar posts by category: Allgemein

If this post helped you, please consider buying me a coffee or donating via PayPal to support research & publishing of new posts on TechOverflow

Buy me a coffee