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

导语

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

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

SSE2如何加速

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

可见我的这个CPU支持 mmxssesse2ssse3sse4.1sse4.2avx.

回到正题,我们知道 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

  • 发表于:
  • 本文为 InfoQ 中文站特供稿件
  • 首发地址https://www.infoq.cn/article/GuesrrywdwQhIL93EaTg
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券