SIMD Parser 原理精读:把逐字节状态机编译成位运算数据流

上一篇《SIMD 深入解析:从硬件原理到加密货币 HFT 中的应用》(下称"硬件篇")讲了 SIMD 的硬件机理与加密 HFT 链路全景,其中 §10.3 说"simdjson 比逐字符解析快约 10 倍",但没有回答为什么能快——毕竟解析看起来是最"串行"的活:每个字节的含义取决于它前面的所有字节。这一篇专门拆这个问题:SIMD parser 如何把一个逐字节状态机改写成位运算数据流。其中最漂亮的一击,是用一条乘法指令跑完 64 步状态转移。

1. 先理解敌人:parser 是 CPU 最不擅长的负载 #

一个标量 JSON parser 的本质是逐字节状态机:

for (each byte c) {
    switch (state) {
        case IN_STRING: if (c == '"')  state = OUT;
                        else if (c == '\\') state = ESC;      break;
        case OUT:       if (c == '{') push(OBJ);
                        else if (c == '"') state = IN_STRING; break;
        ...
    }
}

这段代码同时踩中现代 CPU 的两个死穴:

① 串行数据依赖。第 i 个字节的状态取决于第 i-1 个字节的状态——这条依赖链把乱序执行废掉了。CPU 有 6~8 的发射宽度、几百条指令的乱序窗口,但状态机强迫它一步一步走,IPC 掉到 1 以下。

② 数据依赖分支。switch (state) 和 if (c == '"') 的跳转方向由报文内容决定,分支预测器学不到规律(行情数据本来就近似随机)。每次误预测清空流水线,罚 15~20 个周期。一条 200 字节的报文如果吃 30 次误预测,光罚款就是 ~500 周期。

所以标量 parser 的典型成本是 2~4 cycles/byte,RapidJSON 量级在几百 MB/s。注意瓶颈不是"计算量大",而是控制流的形状与硬件相性极差——这正好是硬件篇 §7.3"分支与提前退出是向量化天敌"的反面教材:parser 整个就是由这种代码构成的。

2. 范式转换:控制流问题变成数据流问题 #

SIMD parser(simdjson 是集大成者,Langdale & Lemire 2019 Parsing Gigabytes of JSON per Second)的核心思想只有一句话:

不再逐字节问"我现在处于什么状态",而是把 64 字节一次性变换成若干个 64-bit 位掩码,用位运算一次算出全部 64 个位置的状态。

字符流 → 位掩码流。三板斧:

批量分类:64 字节并行判定"每个字节是不是引号/反斜杠/结构字符/空白",得到 4~5 个 64-bit 掩码,全程无分支;
状态传播闭式化:状态机的逐步转移,找到等价的位运算闭式解(§4,精髓所在);
分支推迟:最后才回到标量世界,但此时处理的不是 200 个字节,而是 ~20 个结构位置。

下面按这个顺序拆。

3. 三板斧的机制 #

3.1 找字符:比较 + movemask,进入位世界 #

__m256i chunk = _mm256_loadu_si256((__m256i *)buf);   // 载入 32 字节
__m256i eq    = _mm256_cmpeq_epi8(chunk, _mm256_set1_epi8('"'));
uint32_t quote_bits = _mm256_movemask_epi8(eq);       // 32 个比较结果 → 32-bit 掩码

三条指令回答"这 32 字节里所有引号在哪"。cmpeq 每个 lane 独立比较(匹配的 lane 全 1),movemask 抽取每个 lane 的最高位压成一个标量整数。从这一刻起,问题就从字节世界进入了位世界——后续所有状态推理都在 64-bit 通用寄存器上做位运算,SIMD 单元反而退场了。这是 SIMD 与 SWAR(用普通寄存器玩位并行)的接力配合。

3.2 字符分类:pshufb 双查表 #

引号用一次 cmpeq 就能找,但结构字符有 6 种({}[]:,)、空白有 4 种,逐个比要 10 次。pshufb 一次解决。

pshufb 的语义是 16 项字节查找表:out[i] = table[in[i] & 0x0F],16/32/64 个 lane 并行查。表只有 16 项、字符有 256 个,怎么办?把 ASCII 表看成 16×16 网格,字符类别 = 行约束 ∩ 列约束:

cls = pshufb(lo_table, c & 0x0F)     // 低 nibble 查列:该列可能属于哪些类别(位集)
    & pshufb(hi_table, c >> 4);      // 高 nibble 查行:该行可能属于哪些类别(位集)

表项是类别位集(bit0=空白、bit1=逗号冒号、bit2=括号……),两次查表结果按位与:只有行、列约束同时满足的类别位存活。以 ,(0x2C)为例——lo_table[0xC] 含"逗号"位,hi_table[0x2] 也含"逗号"位,与完该 lane 的逗号位为 1;而 l(0x6C)低 nibble 相同,但 hi_table[0x6] 没有逗号位,与完归零。两条 pshufb 加一条 AND,64 字节 × 8 个类别同时分类完毕。

这也是 pshufb 被称为"SIMD 瑞士军刀"的原因:它是任意 4-bit→8-bit 函数的硬件求值器,absl::flat_hash_map 的分组探测之外,SIMD 世界里另一半技巧都建立在它上面。(SSE4.2 曾为此专门做过 pcmpistri 字符串指令,但延迟 10+ 周期、端口受限,现代 parser 一律回到 pshufb+movemask。)

3.3 消费掩码:tzcnt / blsr #

分类完得到"结构字符位置掩码"后,抽取成索引数组:

while (mask) {
    index[n++] = base + _tzcnt_u64(mask);   // 最低置位 = 下一个结构字符
    mask = _blsr_u64(mask);                  // 清掉最低置位
}

循环次数 = popcount(一个 64 字节块通常 5~15 个)。这是整个第一阶段唯一依赖数据的循环——每字节一次的分支,被压缩成每个结构字符一次。

4. 精髓:上下文相关性的闭式解 #

到这里有个致命问题:{"px":"64123.45"} 里,字符串内部的 { : 不是结构字符。“我在不在字符串里"恰恰是那个逐字节的串行状态——SIMD parser 真正的智力含量,在于给这个状态传播找到了位运算闭式解。

(以下示意图都按文本顺序画:第一个字节在最左,对应掩码的最低位;加法进位的传播方向即文本方向。)

4.1 转义:借加法进位链跑游程奇偶 #

引号前面有奇数个连续反斜杠才算被转义(\" 转义,\\" 不转义)。判定每段反斜杠游程的奇偶,看似必须逐字节数。但注意一个事实:

二进制加法的进位传播,天然就是"沿着连续 1 逐位推进状态"的硬件原语。

对反斜杠掩码 B,把游程起点(S = B & ~(B<<1))加回 B,进位会沿整段连续 1 涟漪传播,在游程结束后的第一个 0 位落下一个 1:

字符:        x  \  \  \  "  y
B:           0  1  1  1  0  0
S=B&~(B<<1): 0  1  0  0  0  0      ← 游程起点
B+S:         0  0  0  0  1  0      ← 进位穿过游程,落在 " 的位置

落点位置的奇偶、结合起点位置的奇偶,恰好编码了游程长度的奇偶。simdjson 把起点按奇偶地址分成两组(与 0x5555…/0xAAAA… 相与)分别做加法,总共几条 add/and/xor,64 字节内所有转义位置一次算清。一条 64-bit 加法 = 64 步逐字节推进——借用 ALU 里现成的进位链做并行状态传播,这是 SWAR 世界的经典手法。

4.2 字符串内外:前缀异或 = 无进位乘法 #

拿到"未转义引号掩码"Q 后,“位置 i 在不在字符串里” = i 之前出现过奇数个还是偶数个引号 = Q 的前缀异或(prefix XOR):

字符:  a  "  b  c  "  d  "  e
Q:     0  1  0  0  1  0  1  0
S:     0  1  1  1  0  0  1  1      ← 每遇引号翻转一次 = "在字符串内"掩码

(约定开引号本身算"内”、闭引号算"外",边界归属不影响原理。)

前缀异或看起来又是串行的(S_i = S_{i-1} ⊕ Q_i)。绝招来了:

S = _mm_clmulepi64_si128(Q, all_ones);   // PCLMULQDQ:无进位乘法

为什么乘以全 1 等于前缀异或:乘法 = 被乘数按乘数的每个置位左移后求和;“无进位"意味着求和用 XOR。乘全 1 就是

Q × 111…1 = Q ⊕ (Q<<1) ⊕ (Q<<2) ⊕ …

其第 i 位 = Q_i ⊕ Q_{i-1} ⊕ … ⊕ Q_0,正是前缀异或的定义。

PCLMULQDQ 本是给 CRC 和 AES-GCM 的 GHASH 设计的加密指令(硬件篇 §10.1、§10.4 里它已经出场过两次),被 parser 借来用约 5 个周期跑完 64 步状态机转移。整个 SIMD parsing 领域最漂亮的一击。

4.3 跨块状态:串行依赖被压缩 32 倍 #

64 字节块之间当然还有依赖:上一块结尾是否在字符串里、是否以奇数个反斜杠收尾。但携带进下一块的只有 2~3 个 bit。串行依赖没有被消灭,而是从每字节一次压缩到每 64 字节一次——乱序窗口足以在等这几个 bit 的同时,把下一块的载入、分类、掩码计算全部预做完。这是理解"为什么它能逼近内存带宽"的最后一块拼图。

5. 总装:simdjson 的两阶段架构 #

Stage 1(结构索引):对每个 64 字节块做 §3~§4 的全套位运算,得到 结构掩码 & ~字符串内 & ~空白,tzcnt 抽成结构索引数组。全程无数据依赖分支,~1 cycle/byte,顺路完成 UTF-8 合法性校验——同样是 pshufb 查表法(Keiser & Lemire, Validating UTF-8 In Less Than One Instruction Per Byte)。

Stage 2(按需取值):在索引数组上走语法。分支不可避免,但对象已从 200 个字节缩到 ~20 个位置。值解析同样并行化,以 8 位数字转整数为例:

// "64123450" 每字节减 '0' → [6,4,1,2,3,4,5,0]
t1 = pmaddubsw(digits, [10,1,10,1,...]);   // 相邻两位乘加: [64,12,34,50]
t2 = pmaddwd  (t1,     [100,1,100,1]);     // 相邻两对乘加: [6412,3450]
// 最后 6412×10000+3450 → 64123450:三条乘加指令,标量要 8 轮 mul+add

(simdjson 里另有等价的 SWAR 版本,两次 64-bit 乘法完成同样的合并。)行情报文里 "64123.45" 这类价格串的解析,大头就在这。

6. 快多少,以及为什么 p99 也受益 #

	成本	吞吐	200B 报文
标量状态机(RapidJSON 量级)	2~4 cycles/byte	几百 MB/s	~400ns+
simdjson(DOM)	<1 cycle/byte	~2.5 GB/s	~80ns
simdjson(On-Demand)	—	6~7 GB/s	更低

比平均值更重要的是分布形状:branch-free 代码的周期数几乎不随内容抖动。标量 parser 的误预测风暴是尾延迟的重要来源(报文内容一换,分支模式全变);SIMD parser 的 p99 和 p50 几乎贴着走。结合硬件篇 §11 的结论——解析吞吐余量决定行情风暴时的尾延迟——这两个性质在加密 HFT 里是同一枚硬币的两面:吞吐余量扛住突发,确定性压平抖动。

7. 加密 HFT 的解析层级:从"解析得快"到"不解析” #

把视野从单个库拉高到选型,解析优化其实是一个四层的阶梯:

层级	技术	适用
0. 不解析	SBE 等二进制协议,字段定长定偏移直读	交易所支持时的最优解(Binance/OKX 等已提供)
1. 全 SIMD parser	simdjson 两阶段	延迟敏感的 JSON 路径(行情、订单回报)
2. SWAR parser	yyjson 这类用 64-bit 通用寄存器玩同样位技巧的实现,宽度窄但无对齐/padding 负担	次热路径,或不想引 C++ 重依赖时
3. 标量 DOM parser	RapidJSON 等	冷路径:配置、REST 低频接口

三条工程提醒:

小报文会打折扣。simdjson 的 GB/s 数字来自大文档基准;150~250B 的行情报文上,padding 要求(SIMDJSON_PADDING,输入尾部要有 64 字节余量)和固定启动开销会把 10 倍优势压到 3~5 倍——依然值得,但 document/parser 对象必须复用,避免每条报文一次分配。
比 simdjson 更快的不是更好的 parser。交易所报文是固定 schema,下一步优化是特化提取:不建语法树,直接定位 "p":" 抽字段。再往上,就是推动接入二进制协议——解析的终极优化是消灭解析。
按延迟敏感度分层部署,而不是全链路一把梭:热路径层级 0/1,冷路径层级 3 完全没问题,别为配置解析引战。

8. 这套方法论不是 JSON 专属 #

“分类成掩码 → 状态传播闭式化(进位链/CLMUL)→ 分支推迟到压缩后的索引流”,同样的三段式出现在:

base64 编解码(Muła & Lemire 的 SIMD base64,浏览器和 CDN 在用);
UTF-8 校验/转码(simdutf,WebSocket 收包路径的合规成本,见硬件篇 §10.2);
CSV 解析(simdcsv:引号语义和 JSON 字符串同构,CLMUL 原样复用);
HTTP 头解析(picohttpparser 用 SSE4.2 扫描 token 边界);
WS 帧 unmask(纯纵向 XOR,平凡但同源)。

判据只有一条:只要逐字节状态机的状态转移能改写成结合律友好的位运算,它就能被 SIMD/SWAR 摊平。反例也清晰——需要真正任意跳转的状态机(比如正则的回溯)就没有这样的闭式解,这是这套技术的边界。

9. 延伸阅读 #

Langdale & Lemire, Parsing Gigabytes of JSON per Second(2019)——本文 §3~§5 的完整版,附各步位运算的精确定义。
Keiser & Lemire, Validating UTF-8 In Less Than One Instruction Per Byte(2021)。
Wojciech Muła 的网站——pshufb 技巧、SIMD base64/CSV 的原始出处,SIMD 位技巧的百科全书。
simdjson / simdutf / yyjson 源码——三种档位(全 SIMD / 全 SIMD / SWAR)的实现对照。
Daniel Lemire 的博客——上述所有工作的连载现场。

本站相关

《SIMD 深入解析:从硬件原理到加密货币 HFT 中的应用》 — 硬件机理与 HFT 链路全景,本文是其 §10.3 的完整展开
《高频交易中的 WebSocket 架构设计》 — WebSocket 协议细节,§8 中 unmask 与 UTF-8 校验的业务背景
《C++ Map 容器性能差异的底层实现分析》 — flat_hash_map 的 SIMD 分组探测,cmp+movemask+ctz 三件套的另一实例
《行情数据解析优化最佳实践》 — simdjson 的早期实战与 profile 方法
《高频交易系统中的背压机制设计讨论》 — 背压与突发,§6"吞吐余量即尾延迟"的系统视角

结语 #

压缩成四条:

parser 慢不是因为计算多,而是控制流形状差:逐字节串行依赖废掉乱序,数据依赖分支喂不饱预测器,2~4 cycles/byte 全是结构性浪费。
SIMD parser 的本质是把控制流编译成数据流:字符流变位掩码流,分类无分支(cmpeq/pshufb),消费有节制(tzcnt/blsr)。
串行状态的解法是位运算闭式解:转义用加法进位链跑游程奇偶,字符串内外用 CLMUL 乘全 1 算前缀异或——一条指令跑完 64 步状态转移;跨块只传 2~3 个 bit。
解析优化的终点是不解析:simdjson 之上还有 schema 特化提取和二进制协议;按延迟敏感度分层,热路径向层级 0 迁移,冷路径不折腾。

发布时间:2026-08-24;CC BY 4.0,转载请署名并保留链接。欢迎讨论和指正。