如何使用 SIMD 向量化和/或并行化让编译器为字符串搜索循环输出更快的代码？

Question

我有这个 C：

#include <stddef.h>
size_t findChar(unsigned int length, char*  __attribute__((aligned(16))) restrict string) {
    for (size_t i = 0; i < length; i += 2) {
        if (string[i] == '[' || string[i] == ' ') {
            return i;
        }
    }
    return -1;
}

它检查字符串的所有其他字符并返回字符串的第一个索引，即[or 。使用 x86-64 GCC 10.2 -O3 -march=skylake -mtune=skylake，这是汇编输出：

findChar:
        mov     edi, edi
        test    rdi, rdi
        je      .L4
        xor     eax, eax
.L3:
        movzx   edx, BYTE PTR [rsi+rax]
        cmp     dl, 91
        je      .L1
        cmp     dl, 32
        je      .L1
        add     rax, 2
        cmp     rax, rdi
        jb      .L3
.L4:
        mov     rax, -1
.L1:
        ret

看起来它可以被显着优化，因为我看到了多个分支。如何编写我的 C 以便编译器使用 SIMD、字符串指令和/或矢量化对其进行优化？

我如何编写我的代码以向编译器发出可以优化此代码的信号？

Godbolt 上的交互式装配输出：https ://godbolt.org/z/W19Gz8x73

将其更改为具有明确声明长度的 VLA 并没有多大帮助：https : //godbolt.org/z/bb5fzbdM1

这是修改后的代码版本，因此该函数将只返回每 100 个字符：https : //godbolt.org/z/h8MjbP1cf

Answer 1

我不知道如何说服编译器为此发出良好的自动向量化代码。但我知道如何手动矢量化。由于您\xe2\x80\x99正在针对Skylake进行编译，因此\xe2\x80\x99是您的函数的AVX2版本。未经测试。

\n

#include <stddef.h>\n#include <immintrin.h>\n\nptrdiff_t findCharAvx2( size_t length, const char* str )\n{\n    const __m256i andMask = _mm256_set1_epi16( 0xFF );\n    const __m256i search1 = _mm256_set1_epi16( '[' );\n    const __m256i search2 = _mm256_set1_epi16( ' ' );\n\n    const char* const ptrStart = str;\n    const char* const ptrEnd = str + length;\n    const char* const ptrEndAligned = str + ( length / 32 ) * 32;\n    for( ; str < ptrEndAligned; str += 32 )\n    {\n        // Load 32 bytes, zero out half of them\n        __m256i vec = _mm256_loadu_si256( ( const __m256i * )str );\n        vec = _mm256_and_si256( andMask, vec );\n\n        // Compare 16-bit lanes for equality, combine with OR\n        const __m256i cmp1 = _mm256_cmpeq_epi16( vec, search1 );\n        const __m256i cmp2 = _mm256_cmpeq_epi16( vec, search2 );\n        const __m256i any = _mm256_or_si256( cmp1, cmp2 );\n        const int mask = _mm256_movemask_epi8( any );\n\n        // If neither character is found, mask will be 0.\n        // Otherwise, the least significant set bit = index of the first matching byte in `any` vector\n#ifdef _MSC_VER\n        unsigned long bitIndex;\n        // That's how actual instruction works, it returns 2 things at once, flag and index\n        if( 0 == _BitScanForward( &bitIndex, (unsigned long)mask ) )\n            continue;\n#else\n        if( 0 == mask )\n            continue;\n        const int bitIndex = __builtin_ctz( mask );\n#endif\n        return ( str - ptrStart ) + bitIndex;\n    }\n\n    // Handle the remainder\n    for( ; str < ptrEnd; str += 2 )\n    {\n        const char c = *str;\n        if( c == '[' || c == ' ' )\n            return str - ptrStart;\n    }\n    return -1;\n}\n

\n