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

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

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

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

char *pos = class_name;
size_t len = class_name_len;
while ((pos = memchr(pos, '\\', len - (pos - class_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支持mmx, sse, sse2, ssse3, 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;
}

if (len) {
  //用传统方式处理后续不满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码’_’(95)和‘\\‘(92)之间差了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个字符，效率会大大提升。我们来做个简单的测试，测试脚本在这里：replace_chr.c,
下载下来以后，用-O2编译，在我的开发机上跑的结果是(结果会根据字符串中出现’\\’的位置和数量不同而有些许差异):

| Length |  Nomal |  SSE2  |  RAT |
-----------------------------------
|      4 |   5259 |   5397 |   3% |
|      8 |   2847 |   3045 |   7% |
|     16 |   1752 |    750 | -57% |
|     32 |   1557 |    843 | -46% |
|     64 |   1212 |    672 | -45% |
|    128 |   1149 |    594 | -48% |
|    256 |   1005 |    480 | -52% |
|    512 |    561 |    330 | -41% |

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

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

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