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

这个算是一个比较有用的提速的技巧吧，主要是刚刚在重构Yaf_Loader的时候又用到，想着这个操作比较常见，就专门拎出来做个小分享吧。

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

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

char *pos = class_name;
size_t len = class_name_len;
while ((pos = memchr(pos, '\\', len - (pos - name)))) {
    *pos++ = '_';
}

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

cat /proc/cpuinfo | grep flags
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm ida arat xsaveopt pln pts dts tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms

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

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

char *pos = class_name;
size_t len = class_name_len;

const __m128i slash = _mm_set1_epi8('\\');
const __m128i delta = _mm_set1_epi8('_' - '\\');

while (len >= 16) {
    __m128i op = _mm_loadu_si128((__m128i *)pos);
    __m128i eq = _mm_cmpeq_epi8(op, slash);
    if (_mm_movemask_epi8(eq)) {
        eq = _mm_and_si128(eq, delta);
        op = _mm_add_epi8(op, eq);
        _mm_storeu_si128((__m128i*)pos, op);
    }
    len -= 16;
    pos += 16;
}

//接下来用传统方式处理后续不满16个字符的部分

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

1. __m128i eq = _mm_cmpeq_epi8(op, slash);
2. eq = _mm_and_si128(eq, delta);
3. op = _mm_add_epi8(op, eq);
4. _mm_storeu_si128((__m128i*)pos, op);

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

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

  G\Namespace\pack

  来说，会得到结果:

  0 -1 000000000 -1 0000

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

  0 -1 000000000 -1 0000
  &  3  3 333333333  3 3333
  -------------------------
     0  3 000000000  3 0000

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

  G \ Namespace \ pack
  +  0 3 000000000 3 0000
  ----------------------
     G _ Namespace _ pack

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

这样以来，我就可以用一条指令同时检测16个字符，效率会大大提升。完整的实现可以参考： Yaf Commit log

之前在开发PHP7的时候，我也为PHP7引入过采用SIMD指令来实现快速的base64_encode/decode函数，有兴趣的可以参看 Base64 Encode with SSSE3 , 以后我有空了也可以分享下那个例子是怎么做的。

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