如何利用x86 SIMD优化批量变长整数编解码（附可运行基准）

现有编码规则 #

将16个int64_t组成的小块编码为以下结构的块：

• 8字节标志位段：打包16个半字节（4位）的flag，每字节存储2个flag
• 可变长度payload段：每个输入int64_t对应1个或多个字节，具体规则：
  1. 单个flag占4位（半字节）
  2. flag高位1位存储sign(value)（符号标识）
  3. flag低3位存储abs(value)所需的字节数
  4. payload中存储abs(value)的二进制数据，字节数由flag低3位指定

经实际数据测试，该方案的压缩率与编解码速度均优于LEB128（varint）和LZ4。

特殊数据特征 #

• 绝大多数abs(value)的存储长度≤2字节
• 99%的场景下：
  • 连续4个abs(value)的总存储字节数≤7
  • 连续16个abs(value)的总存储字节数≤31

优化需求 #

核心聚焦解码速度优化，允许调整编解码格式，希望了解是否可通过SIMD指令集实现加速。核心优化目标函数为encode和decode_original。

附：现有实现及测试信息 #

原始实现代码 #

// 此处填入decode_original及encode的原始实现代码

优化版本实现（aqrit、Soonts版本） #

// 此处填入aqrit、Soonts的优化实现代码

编译命令 #

# 示例编译命令，可根据实际环境调整
gcc -O3 -march=native -o codec_test codec.c

多CPU基准测试结果 #

内容的提问来源于stack exchange，提问作者Huy Le