从字符串中获取IPv4地址的最快方法

Question

我有以下代码,比inet_addr快约7倍.我想知道是否有办法改进这个以使其更快或者如果存在更快的替代方案.

这段代码要求提供一个有效的空终止IPv4地址,没有空格,在我的情况下总是如此,所以我针对这种情况进行了优化.通常你会有更多的错误检查,但如果有办法使更快或更快的替代存在,我会非常感激.

UINT32 GetIP(const char *p)
{
    UINT32 dwIP=0,dwIP_Part=0;
    while(true)
    {
        if(p[0] == 0)
        {
            dwIP = (dwIP << 8) | dwIP_Part;
            break;
        }
        if(p[0]=='.') 
        {       
            dwIP = (dwIP << 8) | dwIP_Part;                     
            dwIP_Part = 0;
           p++;
        }
        dwIP_Part = (dwIP_Part*10)+(p[0]-'0');
        p++;
    }
    return dwIP;
}

Answer 1

由于我们正在谈论最大化IP地址解析的吞吐量,我建议使用矢量化解决方案.

这是特定于x86的快速解决方案(需要SSE4.1,或者至少需要SSSE3):

__m128i shuffleTable[65536];    //can be reduced 256x times, see @IwillnotexistIdonotexist

UINT32 MyGetIP(const char *str) {
    __m128i input = _mm_lddqu_si128((const __m128i*)str);   //"192.167.1.3"
    input = _mm_sub_epi8(input, _mm_set1_epi8('0'));        //1 9 2 254 1 6 7 254 1 254 3 208 245 0 8 40 
    __m128i cmp = input;                                    //...X...X.X.XX...  (signs)
    UINT32 mask = _mm_movemask_epi8(cmp);                   //6792 - magic index
    __m128i shuf = shuffleTable[mask];                      //10 -1 -1 -1 8 -1 -1 -1 6 5 4 -1 2 1 0 -1 
    __m128i arr = _mm_shuffle_epi8(input, shuf);            //3 0 0 0 | 1 0 0 0 | 7 6 1 0 | 2 9 1 0 
    __m128i coeffs = _mm_set_epi8(0, 100, 10, 1, 0, 100, 10, 1, 0, 100, 10, 1, 0, 100, 10, 1);
    __m128i prod = _mm_maddubs_epi16(coeffs, arr);          //3 0 | 1 0 | 67 100 | 92 100 
    prod = _mm_hadd_epi16(prod, prod);                      //3 | 1 | 167 | 192 | ? | ? | ? | ?
    __m128i imm = _mm_set_epi8(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6, 4, 2, 0);
    prod = _mm_shuffle_epi8(prod, imm);                     //3 1 167 192 0 0 0 0 0 0 0 0 0 0 0 0
    return _mm_extract_epi32(prod, 0);
//  return (UINT32(_mm_extract_epi16(prod, 1)) << 16) + UINT32(_mm_extract_epi16(prod, 0)); //no SSE 4.1
}

以下是所需的预先计算shuffleTable:

void MyInit() {
    memset(shuffleTable, -1, sizeof(shuffleTable));
    int len[4];
    for (len[0] = 1; len[0] <= 3; len[0]++)
        for (len[1] = 1; len[1] <= 3; len[1]++)
            for (len[2] = 1; len[2] <= 3; len[2]++)
                for (len[3] = 1; len[3] <= 3; len[3]++) {
                    int slen = len[0] + len[1] + len[2] + len[3] + 4;
                    int rem = 16 - slen;
                    for (int rmask = 0; rmask < 1<<rem; rmask++) {
//                    { int rmask = (1<<rem)-1;    //note: only maximal rmask is possible if strings are zero-padded
                        int mask = 0;
                        char shuf[16] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
                        int pos = 0;
                        for (int i = 0; i < 4; i++) {
                            for (int j = 0; j < len[i]; j++) {
                                shuf[(3-i) * 4 + (len[i]-1-j)] = pos;
                                pos++;
                            }
                            mask ^= (1<<pos);
                            pos++;
                        }
                        mask ^= (rmask<<slen);
                        _mm_store_si128(&shuffleTable[mask], _mm_loadu_si128((__m128i*)shuf));
                    }
                }
}

这里提供完整的测试代码.在Ivy Bridge处理器上它打印:

C0A70103
Time = 0.406   (1556701184)
Time = 3.133   (1556701184)

这意味着建议的解决方案在吞吐量方面比OP的代码快7.8倍.它每秒处理336百万个地址(3.4 Ghz的单核).

现在我将尝试解释它是如何工作的.请注意,在列表的每一行上,您可以看到刚刚计算的值的内容.所有数组都以little-endian顺序打印(虽然set内在函数使用big-endian).

首先,我们通过lddqu指令从未对齐的地址加载16个字节.请注意,在64位模式下,内存由16字节块分配,因此这很有效.在32位上,它理论上可能导致超出范围访问的问题.虽然我不相信它真的可以.无论后端字节中的值如何,后续代码都能正常工作.无论如何,您最好确保每个IP地址至少占用16个字节的存储空间.

然后我们从所有字符中减去'0'.之后 '.' 变成-2,零变成-48,所有数字都保持非负数.现在我们采用所有字节符号的位掩码_mm_movemask_epi8.

根据此掩码的值,我们从查找表中获取一个非平凡的16字节混洗掩码shuffleTable.该表非常大:总计1Mb.预计算需要相当长的时间.但是,它不占用CPU缓存中的宝贵空间,因为实际上只使用了该表中的81个元素.这是因为IP地址的每个部分可以是一个,两个,三个数字长=>因此总共有81个变体.请注意,字符串结尾后的随机无用字节原则上可能会导致查找表中的内存占用增加.

编辑:您可以在评论中找到由@IwillnotexistIdonotexist修改的版本,该版本使用仅4Kb大小的查找表(虽然它有点慢).

巧妙的_mm_shuffle_epi8内在允许我们使用shuffle掩码重新排序字节.因此,XMM寄存器包含四个4字节块,每个块包含小端顺序的数字.我们将每个块转换为16位数_mm_maddubs_epi16后跟_mm_hadd_epi16.然后我们重新排序寄存器的字节,以便整个IP地址占用较低的4个字节.

最后,我们从XMM寄存器中提取低4字节到GP寄存器.它是用SSE4.1 intrinsic(_mm_extract_epi32)完成的.如果你没有它,用其他线替换它_mm_extract_epi16,但它会运行得慢一点.

最后,这是生成的程序集(MSVC2013),以便您可以检查您的编译器是否生成任何可疑内容:

lddqu   xmm1, XMMWORD PTR [rcx]
psubb   xmm1, xmm6
pmovmskb ecx, xmm1
mov ecx, ecx               //useless, see @PeterCordes and @IwillnotexistIdonotexist
add rcx, rcx               //can be removed, see @EvgenyKluev
pshufb  xmm1, XMMWORD PTR [r13+rcx*8]
movdqa  xmm0, xmm8
pmaddubsw xmm0, xmm1
phaddw  xmm0, xmm0
pshufb  xmm0, xmm7
pextrd  eax, xmm0, 0

PS如果您还在阅读,请务必查看评论=)