如何使用SSE2指令集加速字符替换

导语

我们在写代码的时候，在字符串处理的时候，可能会遇到这样的需求，就是把一个目标字符串中所有出现的某个字符 a 替换为另外一个字 c.

比如对于Yaf_Loader中，在处理命名空间的类名的自动加载的时候，我需要把所有的 \ 替换为 _ ，一般通常的写法会是:

SSE2如何加速

而目前SIMD指令的支持已经非常普遍，尤其 SSE2，基本当代的CPU都支持, 可以通过 cat /proc/cpuinfo 来看cpu支持的SIMD指令集：

可见我的这个CPU支持 mmx，sse，sse2，ssse3，sse4.1，sse4.2，avx.

回到正题，我们知道 SIMD 128 指令集可以一次处理 16 个字符，上面的代码可以通过如下代码来等效实现：

这里面核心的代码部分是：

我来一行一行解释，假设我们现在要处理的字符串是"G\Namespace\package\classname：

• 第一行：拿 16 个字符和字符 ‘\’ 做比较，如果某位相等，则 16 位结果中对应的 byte 就为 0xff(-1)，否则就为 0，那么对于：

来说，会得到结果:

• 第二行：如果对比的结果不全为零的话，就进行到这行，这行的核心思想是因为ascii 码 ‘_’(95) 和 ‘\’(92) 之间差了 3，所以我们通过and指令得到如下结果：

• 第三行：我们把刚刚的 delta 结果加回到原始字符串中去，也就是：

• 第四行：把结果写回内存

总结

这样一来，我就可以用一条指令同时检测 16 个字符，效率会大大提升。我们来做个简单的测试，测试脚本在这里是：replace_chr.c（阅读原文可见）

下载下来以后，用 -O2 编译，在我的开发机上跑的结果是（结果会根据字符串中出现 ‘\’ 的位置和数量不同而有些许差异）：

从结果上可以看到，在字符串长度小于 16 的时候，SSE2 版本的速度略逊于普通版本，但是当字符串长度大于 16以后，SSE2 的版本的优势就非常明显了。

附言

与其说是针对这个特定的字符替换的问题，我其实更主要对是想分享这种使用 SIMD 解决问题的思路，如何把类似的问题抽象为这样的”批量操作”。比如在之前在开发 PHP7 的时候，我也为 PHP7 引入过采用 SIMD 指令来实现快速的base64_encode/decode函数，这个性能提升很明显，因为被操作的字符串一般都很长，有兴趣的伙伴可以参看Base64 Encode with SSSE3（阅读原文可见） , 以后有机会也可以分享下那个例子是怎么做的。

最后，关于 SIMD 指令集的速查，可以看这里：Intel Intrinsics Guide。