Accelerating character replacement with the SSE2 instruction set中文EN

This is a fairly useful performance optimization trick. I happened to use it again just now while refactoring Yaf_Loader, and since this operation is quite common, I thought I'd pull it out for a little writeup.

When we write code, while doing string processing, we may run into a requirement like this: replace every occurrence of a character a in a target string with another character c.

For example, in Yaf_Loader, when auto-loading a class name in a namespace, I need to replace all \ with _. The usual way to write it would be:

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

Meanwhile, SIMD instruction support is already very widespread, especially SSE2 — basically every modern CPU supports it. You can see the SIMD instruction sets your CPU supports via cat /proc/cpuinfo:

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

As you can see, my CPU supports mmx, sse, sse2, ssse3, sse4.1, sse4.2, and avx.

Zooming out: we know the SIMD 128-bit instruction set can process 16 characters at once. The code above can be equivalently implemented as follows:

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) {
  //handle the remaining part (less than 16 chars) the traditional way
}

The core part of the code here is:

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);

Let me walk through it line by line. Suppose the string we want to process right now is "G\Namespace\package\classname:

• Line one: compare 16 characters against the character '\'. If a given position matches, the corresponding byte in the 16-bit result is 0xff (-1); otherwise it's 0. So for:

  G\Namespace\pack
  

  we get the result:

  0 -1 000000000 -1 0000
  

• Line two: if the comparison result isn't all zeros, we proceed to this line. The core idea here is that the ASCII code of '_' (95) and '\' (92) differ by 3, so we use the and instruction to get the following result:

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

• Line three: we add the delta result back into the original string, that is:

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

• Line four: write the result back to memory.

This way, I can use a single instruction to inspect 16 characters at a time, which greatly improves efficiency. Let's do a simple test; the test script is here: replace_chr.c.
After downloading it, compile with -O2. The result on my dev machine is (results vary slightly depending on where and how many '\' appear in the string):

| 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% |

From the results, you can see that when the string length is less than 16, the SSE2 version is slightly slower than the normal version; but once the string length exceeds 16, the SSE2 version's advantage becomes very clear.

OK, to wrap up: rather than about this specific character-replacement problem, what I really mainly want to share is the approach of using SIMD to solve problems like this — how to abstract a similar problem into such a "batch operation." For instance, earlier, while developing PHP7, I also introduced a SIMD-instruction-based implementation of fast base64_encode/decode functions for PHP7; this performance improvement is very noticeable, because the strings being operated on are generally long. Those interested can take a look at Base64 Encode with SSSE3; when I have time later I can also share how that example was done.

Finally, for a quick reference on the SIMD instruction sets, see here: Intel Intrinsics Guide.