为什么simdjson这么快? 第1页

最近这个SimdJson 在社区里还挺火，看来大家忍这个问题很久了。也有微软的人把它移植到了C#（用的是我给.NET Core 3.0 做的SIMD intrinsic）EgorBo/SimdJsonSharp

为什么SimdJson这么快？或者说比其他用了SIMD向量化的parser还快？

最主要的是它的思路是（现阶段）正确的：以前大多数的JSON parser 在做向量化的时候其实用的还是标量（或者叫顺序式）编程的老思路，SIMD在他们手里只是用来加速一些基本操作。比如用向量化的String.IndexOf 来加速向前搜索某个特定字符，加速跳过空白符等等。本质上还是顺序式的思想，parsing算法并没有并行化。

然而JSON parser 这种本质上的递归下降程序是很难高度SIMD并行化的，这是由于SIMD并行化的特定和parser算法的特点共同导致的：

1. 高效的SIMD并行化和GPU并行化非常相似（其实GPU就是SIMD），它要求并行数据处理之间不能有交互，或者很少有交互，才能达到最好的性能。举个例子，ray tracing 很容易用SIMD或者GPGPU并行化处理是因为每条光线的碰撞/反射/颜色表现是和其他光线没有关系的，每一个SIMD lane或者CUDA thread 可以只负责一条光线的（部分）数据计算而无需去知道其他SIMD lane或者CUDA thread 的信息。

2. Parser 在并行化时的本质不同在于它不能“独立”处理每一个数据单元（比如字符），当我们独立地看到一个引号时我们不知道怎么处理它，因为它有可能是字符串的开头，也有可能是字符串的结尾，也有可能就是一个引号（前面有转义字符），这完全取决于它前后的数据。

SimdJson的思路正确之处在于它把并行parsing问题分层处理了，即把相对容易并行的问题并行化，把难并行的问题暂时放弃，而不是眉毛胡子一把抓。具体的做法是把JSON parsing 分为了两步：

Stage 1：这步类似于普通parser 的词法分析再加上utf-8 验证。向量化验证部分不是什么新技术，创新点主要在于“词法分析”。当然JSON parsing 的词法分析有所不同，它不是把所有输入的字符数据序列化成一个个token。而是只找出对于后续parsing 重要的token。以上文提到的“引号”为例，要判断一个引号是字符串开头还是结尾显然是一件比较难并行化的任务，而判断一个引号到底是不是JSON的引号（有没有被转义）显然更简单。所以SimdJson在这步用SIMD并行查找引号前后的转义字符，然后标出真正的“引号”位置来供下一步“语法分析”使用。

Stage 2：这步类似于普通parser 的语法分析，基本没有并行化，但由于前一步已经找出了所有关键token，所以简化了算法实现了加速。

从数据来看SimdJson的效果还是不错的，C# 的简单移植也轻松击败了 .NET Core 3.0 即将推出的基于Span的新parser。但这不代表SimdJson 就没问题了，我个人觉得后续应该还有两个方面需要改进：

1. 算法上如果想要再有大的改进，stage 2 的并行化必须要做（我记得MSR好像有一篇相关的论文用类似符号执行的思想在并行单元之间传播语法信息）。因为如果还是按照当前思路一直优化stage 1 的话（比如多线程化，GPGPU化），stage 2 迟早会成为瓶颈。

2. 工程实现上，SimdJson 用的是AVX2，但我觉得AVX-512 其实天然得更适合这个算法。AVX-512 的mask register机制可以显著简化stage 1 中的mask 生成/提取/计算。