Optimizing String Replacement Using SSE2 SIMD Instructions

This article discusses optimizing string replacement operations using SSE2 SIMD instructions. The author begins by explaining a common string processing need: replacing all occurrences of one character with another in a target string, such as converting backslashes to underscores in namespace class names.

The traditional approach using standard string replacement functions is compared with an SSE2-optimized solution. The author explains that modern CPUs universally support SSE2, which can be verified by checking /proc/cpuinfo for supported SIMD instruction sets like mmx, sse, sse2, ssse3, sse4.1, sse4.2, and avx.

The core optimization leverages SIMD 128-bit instructions to process 16 characters simultaneously. The implementation uses three key steps: first, comparing 16 characters against the target character using _mm_cmpeq_epi8, which produces a mask where matching positions contain 0xff and non-matching positions contain 0; second, using bitwise AND with a precomputed delta (the ASCII difference between the target and replacement characters, which is 3 for backslash and underscore); and third, adding the delta back to the original string and writing the results to memory.

The article provides a detailed step-by-step explanation with visual examples showing how the algorithm works on a sample string "G\Namespace\package\classname". Performance testing demonstrates that while the SSE2 version is slightly slower for strings under 16 characters, it becomes significantly faster for longer strings, with the advantage becoming very clear once string length exceeds 16 characters.

The author emphasizes that the main goal is to share the problem-solving approach of using SIMD for batch operations rather than just solving this specific character replacement problem. They mention having previously implemented SIMD-based base64_encode/decode functions in PHP7 with similar performance benefits. The article concludes by providing a reference to Intel's Intrinsics Guide for further exploration of SIMD instructions.