22.2 SIMD strlen() implementation

SIMD指令可能通过特殊的宏8插入到C/C++代码中。MSVC中他们被保存在intrin.h中。

Strlen()函数9的实现使用了SIMD指令，比常规的实现快了2-2.5倍。该函数将16个字符加载到一个XMM寄存器并检查是否为零

size_t strlen_sse2(const char *str)
{
        register size_t len = 0;
        const char *s=str;
        bool str_is_aligned=(((unsigned int)str)&0xFFFFFFF0) == (unsigned int)str;
        if (str_is_aligned==false)
                return strlen (str);
        __m128i xmm0 = _mm_setzero_si128();
        __m128i xmm1;
        int mask = 0;
        for (;;)
        {
                xmm1 = _mm_load_si128((__m128i *)s);
                xmm1 = _mm_cmpeq_epi8(xmm1, xmm0);
                if ((mask = _mm_movemask_epi8(xmm1)) != 0)
                {
                        unsigned long pos;
                        _BitScanForward(&pos, mask);
                        len += (size_t)pos;
                        break;
                }
                s += sizeof(__m128i);
                len += sizeof(__m128i);
        };
        return len;
}

(这里的例子基于源代码).

MSVC 2010 /Ox 编译选项:

_pos$75552 = -4                 ; size = 4
_str$ = 8                       ; size = 4
?strlen_sse2@@YAIPBD@Z PROC     ; strlen_sse2
    push    ebp
    mov     ebp, esp
    and     esp, -16 ; fffffff0H
    mov     eax, DWORD PTR _str$[ebp]
    sub     esp, 12 ; 0000000cH
    push    esi
    mov     esi, eax
    and     esi, -16 ; fffffff0H
    xor     edx, edx
    mov     ecx, eax
    cmp     esi, eax
    je      SHORT $LN4@strlen_sse
    lea     edx, DWORD PTR [eax+1]
    npad    3
$LL11@strlen_sse:
    mov     cl, BYTE PTR [eax]
    inc     eax
    test    cl, cl
    jne     SHORT $LL11@strlen_sse
    sub     eax, edx
    pop     esi
    mov     esp, ebp
    pop     ebp
    ret     0
$LN4@strlen_sse:
    movdqa  xmm1, XMMWORD PTR [eax]
    pxor    xmm0, xmm0
    pcmpeqb         xmm1, xmm0
    pmovmskb        eax, xmm1
    test    eax, eax
    jne     SHORT $LN9@strlen_sse
$LL3@strlen_sse:
    movdqa  xmm1, XMMWORD PTR [ecx+16]
    add     ecx, 16 ; 00000010H
    pcmpeqb         xmm1, xmm0
    add     edx, 16 ; 00000010H
    pmovmskb        eax, xmm1
    test    eax, eax
    je      SHORT $LL3@strlen_sse
$LN9@strlen_sse:
    bsf     eax, eax
    mov     ecx, eax
    mov     DWORD PTR _pos$75552[esp+16], eax
    lea     eax, DWORD PTR [ecx+edx]
    pop     esi
    mov     esp, ebp
    pop     ebp
    ret     0
?strlen_sse2@@YAIPBD@Z ENDP ; strlen_sse2

首先，检查str指针，如果不是按照16字节对齐则调用常规实现。

然后使用movdqa指令加载16个字节到xmm1.这里不使用movdqu的原因是如果指针不一致则从内存中加载的数据可能会不一致。

是的，它可能会以这种方式做，如果指针对齐，使用MOVDQA加载数据，否则使用比较慢的MOVDQU。

但是我们应该注意到这样的警告：

在windowsNT操作系统但不限于该操作系统，内存页按4kb对齐。每个win32进程独占4GB虚拟内存。事实上，只有部分地址空间与真实物理内存对应，如果进程访问的内存没有对应物理内存，将触发异常。这是虚拟内存的工作方式10.

一个函数一次加载16个字节，可能会跨内存分块访问。我们考虑这样一种情况，操作系统在x008c0000分配8192（0x2000）字节,因此块字节从地质0x008c0000到0x008c1fff。 内存块之后从0x008c2000什么都没有，操作系统没有分配任何内存。访问该地址将触发异常。

假如内存块包含的最后5个字符如下：

0x008c1ff8      ’h’
0x008c1ff9      ’e’
0x008c1ffa      ’l’
0x008c1ffb      ’l’
0x008c1ffc      ’o’
0x008c1ffd      ’x00’
0x008c1ffe      random noise
0x008c1fff      random noise

正常情况下，strlen()只会读取到”hello”。

如果我们使用MOVDQU读取16个字节，将会触发异常，应该避免这种情况。

因为我们要确保16字节对齐，保证我们不会读取未分配的内存。

让我们回到函数：

_mm_setzero_si128()—宏pxor xmm0, xmm0—清空XMM0寄存器。
_mm_load_si128()—宏 MOVDQA, 从内存加载16个字节到XMM寄存器。
_mm_cmpeq_epi8()—宏PCMPEQB,比较XMM寄存器的字节位，如果相等则为0xff否则为0。

比如：

XMM1: 11223344556677880000000000000000
XMM0: 11ab3444007877881111111111111111

执行pcmpeqb xmm1, xmm0之后，XMM1寄存器的值为：

XMM1: ff0000ff0000ffff0000000000000000

在本例中该指令比较每一个16字节块与16字节0字节块对比，XMM0通过pxor xmm0 xmm0置零。

接下来宏_mm_movemask_epi8() —这是PMOVMSKB指令。

pmovmskb eax, xmm1

pmovmskb创建源操作数每一个字节的自高位掩码，并保存结果到目的操作数的低byte。源操作数必须为MMX寄存器，目的操作数必须为32位通用寄存器。

比如：

XMM1: 0000ff00000000000000ff0000000000

对应的EAX：

EAX=0010000000100000b

之后bsf eax,eax被执行，eax值为5，意味着第一个是1的位置是5（从0开始）。

MSVC关于这个指令的宏是：_BitScanForward.

至此，找到结尾0的位置，然后程序返回长度计数。

整个过程大致就是这样。

顺便提一下，MSVC为了优化，使用了两个并排的循环。

SSE 4.2(英特尔core i7)提供了更多的指令,这些可能更容易字符串操作。

http://www.strchr.com/strcmp_and_strlen_using_sse_4.2 # 64位化